În clasa lui Andrei sunt n elevi, codificaţi cu numerele 1, 2, …, n. Ei au fost rugaţi de către diriginta lor să propună un coleg de clasă care să devină liderul lor. Fiecare elev şi-a exprimat opţiunea scriind pe un bileţel codul său şi codul elevului ales de el pentru funcţia de şef de clasă. În acest fel diriginta a putut afla pe cine a votat fiecare elev. După studierea propunerilor venite din partea elevilor săi, diriginta lui Andrei a dorit să determine un grup cât mai numeros de elevi care s-au votat unii pe alţii. Cu alte cuvinte, pentru fiecare elev din grup să existe un membru al grupului care să-l fi votat. Dacă de exemplu, sunt 5 elevi şi elevul 1 îl votează pe 3, 2 îl votează pe 4, votul lui 3 merge spre 2, al lui 4, spre 2 iar 5 se votează pe sine, grupul determinat va fi format din elevii 2, 4 şi 5. Să observăm că şi elevii din grupurile {2, 4} şi {5} îşi exercită votul în cadrul grupului dar aceste grupuri nu sunt maximale.
Cerința
Scrieţi un program care, pe baza voturilor elevilor clasei, să determine un grup cu un număr maxim de elevi pentru care voturile primite de ei provin de la elevi aparţinând aceluiaşi grup.
Date de intrare
Pe prima linie a fişierului vot.in se găseşte un număr natural n, reprezentând numărul de elevi din clasa lui Andrei. Pe linia a doua se dau n numere naturale din mulţimea {1, 2, …, n}, separate prin câte un spaţiu, reprezentând voturile elevilor, astfel: numărul \(f_i\) de pe pozitia i indică pe cine a votat elevul i.
Date de ieșire
Pe prima linie din fişierul vot.out se găseşte un număr natural m reprezentând numărul de elevi din grupul determinat. Pe linia a doua se găsesc, în ordine crescătoare, cele m coduri ale elevilor din grup.
Restricții și precizări
• 1< n ≤ 1000
• Este posibil ca un elev să se voteze pe sine.
Exemplu
vot.in
10 10 3 3 1 1 5 1 1 7 9
vot.out
5 1 3 7 9 10
Explicație
Se observă că 1 îl votează pe 10, 3 se votează pe el însuşi, votul lui 7 merge spre 1, al lui 9 – spre 7 iar 10 îl votează pe 9, deci toti elevii din acest grup primesc voturi din partea unor elevi ai grupului şi acesta este maximal cu proprietatea cerută.
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 Vot:
#include<fstream>
using namespace std;
ifstream fin("vot.in");
ofstream fout("vot.out");
int n, x[1001],b[1001],i,j,ex,k,c[1001],p,u;
int main()
{
fin>>n;
for(i=1;i<=n;i++)
{
fin>>x[i];
b[x[i]]++;
}
p=1;u=0;
for(i=1;i<=n;i++)
if(b[i]==0){u++;c[u]=i;}
while(p<=u)
{
j=c[p];
if(x[j]>0 && b[j]==0)
{
b[x[j]]--;
if(b[x[j]]==0){u++;c[u]=x[j];}
x[j]=-1;
}
p++;
}
fout<<n-u<<'\n';
for(i=1;i<=n;i++)
if(x[i]>0)fout<<i<<' ';
fout.close();
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 
.
Rezolvarea problemei #2110 Vot
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2110 Vot 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!