Fişierul intrare/ieşire:cercetasi.in, cercetasi.outSursăONI 2016 clasa a 8-a
AutorProf. Rodica BalasaAdăugată deisa_vlad.ulmeanuVlad Ulmeanu isa_vlad.ulmeanu
Timp execuţie pe test0.1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Cercetași (clasa a 8-a)

Un grup de N cercetaşi, numerotaţi de la 1 la N, se află în tabără la munte. Pentru ei, organizatorii au pregătit N scaune, de asemenea numerotate de la 1 la N, aşezate în cerc, astfel încât fiecare cercetaş să aibă locul său (locul cercetaşului i este pe scaunul i, 1≤i≤N).
Pentru desfăşurarea următoarei activităţi, organizatorii au decis ca M dintre cercetaşi să prezinte diferite exerciţii. Numărul M este egal cu cea mai mare putere a lui 2 cu proprietatea că numărul N de cercetaşi aflaţi în tabără se poate scrie ca sumă de M numere consecutive în mulţimea numerelor impare. Cei M cercetaşi care vor prezenta sunt cei numerotaţi cu numerele impare consecutive a căror sumă este N. De exemplu, dacă N=8, atunci M este 2, iar exerciţiile vor fi prezentate de cercetaşii numerotaţi cu 3, respectiv cu 5.
Din joacă, micii cercetaşi s-au aşezat pe scaune la întâmplare. Organizatorii au nevoie pentru a desfăşura activitatea ca cel puţin cei M cercetaşi care vor prezenta exerciţiile să se afle pe locurile lor. Pentru aceasta, o parte dintre cercetaşi trebuie să-şi schimbe locul şi organizatorii invită micii cercetaşi să participe la jocul numit ”Mutare”. Acest joc se desfăşoară astfel: unul dintre cercetaşii care nu se află pe locul lor se ridică şi merge în interiorul cercului. Cercetaşul numerotat cu numărul scaunului rămas liber îşi va ocupa locul, iar locul ocupat de el anterior rămâne astfel liber. Jocul continuă până când scaunul cercetaşului aflat în interiorul cercului se eliberează şi el se aşază pe locul său.

Cerinţă

Fiind dat numărul N, precum şi ordinea în care s-au aşezat cercetaşii pe scaunele numerotate de la 1 la N, scrieţi un program care să determine:
• numărul M de cercetaşi care vor prezenta exerciţii în cadrul activităţii;
• numerele de identificare ale celor M cercetaşi care vor prezenta exerciţiile, în ordine strict crescătoare;
• numărul minim de cercetaşi care îşi vor schimba locul, astfel încât toţi cei M cercetaşi care vor prezenta exerciţiile să se afle pe locurile lor.

Date de intrare

Fişierul de intrare cercetasi.in conţine pe prima linie numărul natural N cu semnificaţia din enunţ. Pe a doua linie, se află N numere naturale distincte din mulţimea {1, 2, ..., N}, separate prin spaţii, reprezentând ordinea în care s-au aşezat cei N cercetaşi pe scaunele numerotate de la 1 la N.

Date de ieşire

Fişierul de ieşire cercetasi.out va conţine 3 linii. Pe prima linie se va scrie un singur număr natural reprezentând numărul M de cercetaşi care vor prezenta exerciţiile. Pe a doua linie se vor scrie M numere naturale, în ordine strict crescătoare, separate prin câte un spaţiu, reprezentând cercetaşii care vor prezenta exerciţiile. Pe a treia linie se va scrie un număr natural, reprezentând numărul minim de cercetaşi care îşi vor schimba locul.

Restricţii

• 0 < N ≤ 10000 şi N∉ {x ∈ ℕ | x=4*k+2, k∈ ℕ}
• Un joc ”Mutare” odată început, se va încheia doar atunci când cercetaşul din interiorul cercului se aşază pe locul său.
• Din punctajul acordat pe un test, 40% se acordă dacă numărul M afişat pe prima linie este corect, 40% dacă valorile scrise pe a doua linie sunt corecte, respectiv 20% dacă numărul scris pe a treia linie este corect.

Exemplu

cercetasi.incercetasi.out
8
2 3 4 1 5 8 6 7
2
3 5
4

Explicaţie

Dacă N=8, atunci M este 2, iar exerciţiile vor fi prezentate de cercetaşii numerotaţi cu 3, respectiv cu 5.
Cercetaşul cu numărul 3 nu se află pe locul său şi va trece în interiorul cercului, astfel scaunul cu numărul 2 rămâne liber. Cercetaşul cu numărul 2 îşi ocupă locul şi rămâne liber scaunul cu numărul 1. Cercetaşul cu numărul 1 îşi ocupă locul şi rămâne liber scaunul cu numărul 4. Cercetaşul cu numărul 4 îşi ocupă locul şi rămâne liber scaunul cu numărul 3 şi astfel cercetaşul aflat în interiorul cercului se poate aşeza pe locul său. In cadrul acestui joc ”Mutare” şi-au schimbat locul 4 cercetaşi. Cum cercetaşul cu numărul 5 se află deja pe locul său, numărul de cercetaşi care îşi schimbă locul rămâne 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici