Fişierul intrare/ieşire:cerc5.in, cerc5.outSursăConcursul National de Soft "Grigore Moisil" Lugoj, Clasele 9-10
AutorAdriana SimulescuAdăugată deSRaduRadu Szasz SRadu
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cerc5

Ionel este la ora de sport. Copiii sunt aşezaţi pe un rând şi au inscripţionate pe tricouri numere distincte din intervalul [1,N]. Ionel le propune să participe la două jocuri.

  • La primul joc, pentru că lui Ionel ii place ordinea, se gândeşte să determine care este numărul minim de colegi pe care ar trebui să îi scoată din rând astfel încât cei rămaşi să aibă numerele de pe tricouri în ordine crescătoare. După eliminare, în rând rămân M copii.
  • La al doilea joc, cei N copii se rearanjează astfel încât numerele de pe tricourile lor să fie în ordine şi se aşează într-un cerc, cu faţa spre interiorul cercului. Copilul cu numărul 1 este aşezat pe un loc marcat cu roşu, copilul cu numărul 2 se afla în dreapta sa, şi aşa mai departe, fiecare copil numerotat cu i are în dreapta sa copilul cu numărul i+1, cu excepţia copilului cu numărul N care are în dreapta sa copilul cu numărul 1. Jocul se desfăşoară astfel: La etapa i copilul aflat pe locul marcat cu roşu îşi va schimba locul de pi ori cu copilul aflat în dreapta sa, pi fiind al i-lea element din şirul numerelor prime.

Cerinta

Fiind dat numărul N de copii şi numerele de pe tricourile lor în rândul în care erau aşezaţi la început, să se determine:

  1. Pentru primul joc numărul M de copii care rămân astfel încât numerele de pe tricouri să fie în ordine strict crescătoare
  1. Pentru al doilea joc, care vor fi vecinii din dreapta şi din stânga copilului cu numărul 1 dupa k etape ale jocului.

Date de intrare

În fişierul cerc5.in, pe prima linie se află separate prin spaţii trei numere naturale:

  • p – numărul jocului (1 sau 2),
  • N – numărul de copii
  • K numărul de etape ale celui de al doilea joc.

Pe linia următoare se află N numere naturale nenule, distincte două câte două, separate prin câte un spaţiu, reprezentând numerele de pe tricourile copiilor, în ordinea în care sunt aşezaţi pe rândul iniţial.

Date de ieşire

  • Dacă valoarea lui p este 1, se va rezolva numai cerinţa 1. În acest caz, fişierul de ieşire cerc5.out va conţine un număr natural M reprezentând numărul de copii rămaşi.
  • Dacă valoarea lui p este 2, se va rezolva numai cerinţa 2. În acest caz, fişierul de ieşire cerc5.out va conţine două numere naturale, reprezentând, în această ordine, vecinul din dreapta şi vecinul din stânga al copilului cu numărul 1 după cele K etape.

Restricţii

  • 3 ≤ N ≤ 100.000
  • 1 ≤ K ≤ 50.000

Exemplu

cerc5.incerc5.out
1 5 3
1 3 2 4 5
4
2 5 3
1 2 3 4 5
3 5

Explicaţie

  • Exemplul 1 După jucarea primului joc, ramân 4 copii în rând.
  • Exemplul 2 La început, copiii sunt aşezaţi în ordinea 1,2,3,4,5. Jucătorul 1 este pe spaţiul roşu. La etapa 1 jucătorul 1 îşi schimbă de două ori locul cu cel din dreapta sa şi astfel copiii vor ajunge în ordinea 2,3,1,4,5. Dupa prima etapă jucătorul 2 ajunge pe spaţiul roşu. La etapa 2, jucătorul cu numărul 2 îşi schimbă locul de 3 ori cu jucătorul din dreapta sa şi ordinea devine: 3,1,4,2,5. La etapa 3, jucătorul cu numărul 3 îşi schimbă locul de 5 ori cu jucătorul din dreapta sa şi ordinea devine: 3 4 2 5 1. În final jucătorul cu numărul 1 are în dreapta sa jucătorul cu numărul 3 şi în stânga sa jucătorul cu numărul 5.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content