Question

Salutare va rog sa ma ajutati la aceasta problema http://olimpiada.info/oji2005/index.php?cid=arhiva oji 2004 clasa 6 prima problema...


 

Gigel a
primit spre păstrare un set de n cutii de
greutăţi nu neapărat distincte. El a cântărit cutiile şi pentru fiecare
greutate distinctă a notat pe o foaie, în ordine crescătoare a greutăţilor,
numărul de cutii cu greutatea respectivă.

Deoarece fratele său mai mic
avea prostul obicei să se joace cu numerele scrise de el pe foaie, Gigel s-a
gândit să calculeze un „număr de control” după următorul algoritm: începând de
la primul număr a grupat numerele de apariţii ale greutăţilor câte trei (dacă
îi rămân numere negrupate la sfârşit, le ignoră). Dacă într-un grup sunt numai
numere pare sau numai impare notează grupul cu cifra 1, altfel îl notează cu
cifra 0. Din şirul astfel obţinut, se 
formează un număr care are ca valoare cifra zecilor egală cu numărul de
valori 1 şi cifra unităţilor egală cu numărul de valori 0, obţinându-se astfel
„numărul de control”.

 

Cerinţă

Citind greutăţile cutiilor,
să se determine „numărul de control” şi să se verifice dacă este număr prim.

 

Date de intrare

Se citeşte de la tastatură
numărul n urmat de greutăţile
cutiilor.

 

Date de ieşire

Se va scrie pe ecran
„numărul de control”, urmat de valoarea 0 sau 1 pe linia următoare. Pe
următoarea linie se va afişa 1 dacă numărul este prim, respectiv 0 în caz
contrar.

Atenţie:
Se vor afişa doar două valori, fără mesaje, pe două linii diferite!!!

 

Restricţii

1 £ n £ 100

Fiecare greutate este un
număr natural, mai mic sau egal cu 200

 

Observaţie

Datele de intrare sunt
corecte (nu necesită validare).

 

Exemplu

Date de intrare

n=21

1 3 2 6 2 6 2 8 9 8 8 9 10 8
11 18 11 12  14 15 17

 

Date de ieşire

31

1

Explicaţie

După
ordonare se obţine şirul:
1 2 2 2 3 6 6 8 8 8 8 9 9 10 11 11 12
14 15 17 18










 




 



Se obţine apoi: 1 3 1 2
4 2 1 2 1 1 1 1 1

                      

                            1       1      
0       1

 

Din valorile 1 1 0 1  se obţine numărul de control 31, care este
număr prim.

Timp
maxim de executare: 1 secundă/test

Answer 1

Cum fiecare greutate este sub 200, vei crea un vector v[200]. Știi că nu există greutatea 0, deci greutățile 1-200 se potrivesc la v[0] până la v[199], adică g-1, unde g este greutatea.
Vectorul trebuie inițializat cu 0. Vei pune declarația vectorului înafara funcției main().
În main(), vei citi n. Apoi, la fiecare greutate citită, vei crește valoarea lui v[g-1], dacă ai citit în g.
Apoi vei trece prin vector și la fiecare 3 numere nenule calculezi dacă este un 1 sau un 0 (și îl numeri). Dacă o grupare nu se completează, nu mai adaugi nimic.
Să facem efectiv:
#include <fstream>
using namespace std;
short v[200];
int main()
{
int n,a=0,b=0,c=0,d=0,g,i;
cin>>n;
for(i=0;i<n;i++)
{cin>>g;
v[g-1]++;}
for(i=0;i<200;i++)
{if(v[i]==0) continue; //sare direct la următorul i în for dacă am dat de un 0; ne interesează doar nenulele
c++;
d=d+v[i]; //adunăm numerele pozitive
if(c==3)
{c=0;
if(d%2==1)a=a+1;else b=b+1; //numărăm direct
d=0;}
}
a=a%10;b=b%10; //a sau b ar putea să fi depășit 9
cout<<10*a+b;
return 0;
}