Fișierul intrare/ieșire sport.in, sport.out Sursă ONI 2011 clasa a 8-a
Autor Emanuela Cerchez Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Sport (clasa a 8-a)

Profesorul nostru de sport este bun prieten cu profesorul de matematică. Din acest motiv la ora de sport inventează tot felul de probleme și apoi îi cere profesorului de matematică să le rezolve. Azi la ora de sport participă N elevi, care poartă tricouri cu numerele 1, 2, ..., N. La începutul orei, cei N elevi se așează în rând în ordinea p[1] p[2] ... p[N] (adică elevul cu tricoul p[1] se așează pe poziția 1 în rând, elevul cu tricoul p[2] stă pe poziția 2, etc., pozițiile în rând fiind numerotate de la 1 la N de la stânga la dreapta). Profesorul de sport spune așa: ″La comanda mea schimbați locurile astfel: pe poziția i să se așeze elevul care acum stă pe poziția p[p[i]] (pentru fiecare 1≤i≤N)″.

De exemplu, dacă N=6 și inițial elevii s-au așezat astfel: 3 1 4 2 6 5

După prima comandă: 4 3 2 1 5 6

Observați că pe poziția 1 se află elevul 3 iar pe poziția 3 se află elevul 4. După prima comandă pe poziția 1 va ajunge elevul p[p[1]]=p[3]=4. Pe poziția 2 se află elevul 1, iar pe poziția 1 se află elevul 3. După prima comandă pe poziția 2 va ajunge elevul p[p[2]]=p[1]=3...

După a doua comandă: 2 4 1 3 6 5

Observați că în configurația obținută după prima comandă pe poziția 1 stătea elevul 4 deci după încă o comandă va ajunge pe poziția 1 elevul p[4], adică elevul 2. Pe poziția 2 stătea elevul 3, deci după încă o comandă va ajunge pe poziția 2 elevul p[3], adică elevul 4 etc.

După a treia comandă se obține configurația 1 2 3 4 5 6

Iar după a patra comandă se revine la configurația inițială.

Profesorul de sport îl întreabă pe profesorul de matematică: care este numărul minim de comenzi pe care trebuie să le dau astfel încât elevii să revină în configurația inițială? Și care ar fi cea mai mică configurație inițială (considerând ordinea lexicografică) pentru care este necesar același număr minim de comenzi pentru a reveni la configurația inițială.

Cerință

Scrieți un program care să îl ajute pe profesorul de matematică să răspundă la cele două întrebări ale profesorului de sport.

Date de intrare

Fișierul de intrare sport.in conține pe prima linie un număr natural N reprezentând numărul de elevi. Pe cea de a doua linie se află N valori distincte cuprinse între 1 și N reprezentând configurația inițială a elevilor.

Date de ieșire

Fișierul de ieșire sport.out va conține două linii. Pe prima linie va fi scris un număr natural reprezentând numărul minim de comenzi ce trebuie date astfel încât elevii să revină la configurația inițială. Pe cea de a doua linie vor fi scrise N valori distincte cuprinse între 1 și N reprezentând cea mai mică configurație inițială (considerând ordinea lexicografică) pentru care este necesar același număr minim de comenzi pentru a reveni la configurația inițială.

Restricții

  • 1 ≤ N ≤ 500
  • Valorile scrise pe aceeași linie în fișierul de intrare, respectiv în fișierul de ieșire sunt separate prin spații.
  • Spunem că o configuratie p=(p 1, p 2, ..., p N) este mai mică din punct de vedere lexicografic decât o altă configurație q=(q1, q2, ..., qN) dacă există un indice k, 1≤k≤N astfel încât pi=qi, pentru orice 1≤ikk.
  • Numărul minim de comenzi ce trebuie să fie efectuate este ≤2000000000 (două miliarde).
  • Punctaj. Se acordă 50% din punctajul pe teste pentru prima cerință. Punctajul integral se acordă pentru rezolvarea ambelor cerințe.

Exemplu

sport.in sport.out
6
3 1 4 2 6 5
4
1 2 4 5 6 3

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii