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ța

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 și precizări

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.

Exemplu

cercetasi.in

8 
2 3 4 1 5 8 6 7

cercetasi.out

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Cercetasi:

#include <fstream>
using namespace std;
#define Nmax 10002
ifstream fin ("cercetasi.in");
ofstream fout ("cercetasi.out");

int n,ok[Nmax][3];
int mutare(int poz){

    int k=0,aux;
    do
    {
        k++;
        aux=ok[poz][2];
        ok[poz][2]=poz;
        ok[poz][1]=1;
        poz=aux;
    }while (ok[poz][2]!=poz);
    return k;

}
void calcul(int n, int &k, int &x)
{
   k=1;x=n;
     if(n%4==0)
        {while(n%(k*2)==0&&n/(k*2)%2==0&&n/(k*2)-(k*2-1)>0)
            k=k*2;
         x=n/k-(k-1);
        }
}

int main(){
    int m,i,nr=0,x,cx;
    fin>>n;
    calcul(n,m,cx);
   x=cx;
   fout<<m<<"
";
   for(i=1;i<=m;i++){
        fout<<x<<" ";
        ok[x][0]=1;
        x=x+2;
    }
    fout<<"
";
    for(i=1;i<=n;i++)
        {fin>>x;
        if(x==i) ok[x][1]=1;
        if(ok[x][0]==1&&x==i)nr++;
        ok[x][2]=i;
        }

    if(nr==m) fout<<"0
";
    else
    {   nr=0;
        for(i=1;i<=m;i++)
            {if(ok[cx][0]==1&&ok[cx][1]==0)
                nr=nr+mutare(cx);
             cx=cx+2;
            }
        fout<<nr<<"
";
    }
  return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1704 Cercetasi

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1704 Cercetasi de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1704 Cercetasi