Clasele 2-3
Problema 1 -
Povestea unui numar 100
puncte
Câte picioruse au impreună a ciuperci, b papagali, c catei, 3
copii si o mămică? Dacă ați aflat, adunați-l cu cel mai mare număr care are
atâtea cifre câte am eu, cu cifra zecilor 2.
Restrictie: numerele a, b și c au cel mult o cifră.
Date
de intrare:
Se
citesc de la tastatură numerele: a, b și c.
Date
de iesire:
Se va afișa pe primul rând un număr care va reprezenta câte
piciorușe au împreună cipercile, papagalii, căteii, copii și mămica.
Pe al doilea rând, se va afișa numărul cerut.
Exemplu:
Date de intrare:
a=9 b=1
c=1
|
Date de ieșire:
23 piciorușe
52
|
Problema 2 – Flori 100
puncte
Enunț:
Bunicuța Rahiluța are in grădina
ei un strat cu 3 flori. Una din ele este o orhidee, alta este o panseluță și
alta o crizantemă.
Cum aceasta nu vede prea bine,
ea va roagă să îi aflați cele mai frumoase 2 flori de pe strat.
Cerință:
Frumusețea unei flori se
determină în funcție de numărul de petale pe aceasta îl are. Cu cât floarea are
mai multe petale, cu atât este mai frumoasă.
Date
de intrare:
Se citesc de la tastatură 3
numere naturale reprezentând numărul de petale al fiecărei flori, o-orhideea, p-panseluța și c-crizantema.
Date
de ieșire:
Pe prima linie se va afișa
numele celei mai frumoase flori, iar pe a doua linie numele celei de-a doua cea
mai frumoasă floare.
Exemplu:
Date de intrare:
8 100
23113
↑ ↑ ↑
o p c
|
Date de ieșire:
Crizantema
Panseluta
|
239 123
0
↑
↑ ↑
o
p c
|
Orhidee
Panseluta
|
Restricții
și precizări:
Nu
vor exista numere identice. Prima literă din numele fiecărei flori se va scrie
cu literă mare.
o,p,c<100000
Clasa a IV-a
Problema 1 - Problema potiuni 100
puncte
Enunț
Am aflat ca eroina mea preferata,
Leblanc, prefera potiunile care ii dau multa putere. Aceasta a aflat la randul
ei, de la prietena ei, Elise, ca potiunile care ii dau cea mai multa putere o
vor face sa-si iasa din minti si Leblanc nu doreste asta. De aceea ea prefera
potiunile cu putere maxima. Leblanc a gasit pe un raft N potiuni, iar Elise i-a spus ce putere are fiecare potiune.
Leblanc se intreaba cate potiuni care ofera puterea dorita de ea exista?
Cerința
Ajutați-o
pe Leblanc să aleagă poțiunile spunându-i câte poțiuni au puterea potrivită.
Date de intrare
Pe prima
linie a fisierului „potiuni.in” se
afla numarul N. Pe cea de-a doua
linie se afla puterile oferite de potiuni.
Date de iesire
Pe prima
linie a fisierului „potiuni.out” se
afla numarul de potiuni care ofera putere egala cu maximul sirului.
1<=N<=100;
1<=puterile
potiunilor<=100000;
Exemple
potiuni.in
|
potiuni.out
|
Explicatii
|
5
1 9 1 9 9
|
3
|
Maximul este 9.
Sunt 3 potiuni de putere 9.
|
5
11 11 12 12 100
|
1
|
Maximul este 100.
Este 1 potiune de putere 100.
|
10
9 2 9 2 9 9 2 4 2
4
|
4
|
Maximul este
reprezentat de 9. Sunt 4 potiuni de putere 4.
|
Timp de
executie/test 0.1 sec
Problema 2 -
Cod de bare 100
puncte
La fabrica de ciocolată din Suceava s-a adus un nou
calculator care să supravegheze tipărirea codurilor de bare de pe etichetele
care se vor lipi pe fiecare etichetă. Un cod de bare reprezintă un număr de cel
mult nouă cifre. Din cauza unor erori de programare câteodată programul
tipărește greșit codul de pe etichetă și anume scrie încă odată prima cifră a
numărului. De asemenea nu pot fi folosite codurile de bare care au două cifre
prime alăturate.
Gigel este șef de secție la departamentul etichete și
trebuie să elimine codurile de bare care nu sunt corecte. Știind numerele celor
n etichete și că acestea vin în
pachete de câte cinci să se afișeze câte etichete greșite au fost tipărite și câte
pachete au rămas incomplete?
Date de intrare:
Se citeste n,
numărul de etichete și n numere
reprezentând numerele codurilor de bare
de pe etichete
Date de iesire:
Se va afișa pe primul rând un numar care va reprezenta
câte etichete au fost greșite iar pe al
doilea rând numărul de pachete incomplete.
Restricții
și precizări:
5 <= n <= 15
numerele codurilor de bare au cel puțin doua cifre
se consideră cifre prime cifrele 2, 3, 5, 7
Exemplu:
Date de intrare
10
24 567 89 789 19 3345 234 568 73 3456
Date de iesire
3
1
Clasa a V-a
Problema 1
– pagini 100
puncte
Biblioteca şcolii are un
număr foarte mare de cărţi. Paginile cărţilor sunt numerotate cu numerele
naturale consecutive începând de la pagina 1.
Fiecare carte are şi o etichetă pe care este scris un număr natural care reprezintă
numărul total de cifre pe care editorii le-au folosit pentru numerotarea corectă a tuturor paginilor cărţii.
Din păcate, cărţile fiind vechi, pe unele etichete nu se mai poate citi
numărul, iar din unele cărţi lipsesc pagini sau nu se mai poate citi numărul de
pagină.
Cerinţe
Programul va rezolva une dintre următoarele două cerinţe:
- Cunoscând numărul de pagini ale
cărţii, să se determine numărul de cifre necesare pentru a numerota
paginile acesteia, număr care trebuie scris pe eticheta cărţii.
- Cunoscând numărul de pe eticheta
cărţii, să se determine câte pagini trebuie să conţină cartea.
Date de intrare
Fişierul de intrare pagini.in conţine pe prima linie numărul natural c,
reprezentând cerinţa (1 sau 2). Pe linia a doua a fişierului de intrare
se găseşte un număr natural n. Dacă c=1,
numărul n reprezintă
numărul de pagini ale cărţii. Dacă c=2, numărul n
reprezintă numărul de cifre de pe eticheta cărţii.
Date de ieşire
Fişierul de ieşire pagini.out va conţine o singură linie pe care va fi scris răspunsul corespunzător
cerinţei c din fişierul de intrare. Dacă c=1,
răspunsul va fi numărul de cifre necesar pentru numerotarea celor n pagini ale cărţii. Dacă c=2 răspunsul va fi numărul de pagini ce pot
fi corect numerotate cu cele n
cifre.
Restricţii şi precizări
·
1 ≤ c ≤ 2
·
1 ≤ numărul
de pagini ≤ 100000
·
1 ≤ numărul
de cifre ≤ 488895
·
Pentru
datele de test există întotdeauna soluţie
Exemple
pagini.in
|
pagini.out
|
Explicaţii
|
1
22
|
35
|
Cerinţa 1: se cunoaşte numărul de pagini, se
cere numărul de cifre necesare
Pentru a numerota 22 de pagini sunt
necesare 35 de cifre (9+13*2)
|
2
59
|
34
|
Cerinţa 2: se cunoaşte numărul de cifre, se cere
numărul de pagini
Dacă există 59 de cifre (corecte) cu
ele se pot numerota 34 de pagini (9+50/2)
|
1
100
|
192
|
Pentru a numerota 100 de pagini sunt
necesare 192 cifre
|
2
38899
|
10001
|
Dacă există 38899 cifre (corecte) cu ele
se pot numerota 10001 pagini
|
Timp maxim de execuţie/test: 0.1
secunde
Problema 2 – Tema 100
puncte
La Palatul Copiilor
s-au înscris la cursul de informatică n elevi, pe care i-am numerotat, pentru a mă referi mai
uşor la ei, cu numere de la 1 la n.
În fiecare
săptămână ei au de făcut o temă. Când primesc tema, îmi notez numărul copilului
care a trimis tema.
Din păcate de
fiecare dată există cel puţin un copil care nu trimite tema.
Cerinţă
Scrieţi un program
care să afişeze, în ordine strict crescătoare, numerele copiilor care nu au
trimis tema săptămâna aceasta.
Date de intrare
Fişierul de intrare
tema.in conţine pe prima linie un număr natural n, reprezentând numărul de elevi
înscrişi la cursul de informatică. Pe a doua linie se află un număr natural m, reprezentând numărul elevilor
care au trimis tema. Pe a treia linie se află m numere naturale distincte,
cuprinse între 1 şi n, separate prin câte un spaţiu, reprezentând numerele copiilor care au
trimis tema.
Date de ieşire
Fişierul de ieşire tema.out va conţine pe
prima linie numerele de ordine ale copiilor care nu au trimis tema, în ordine
crescătoare, separate prin câte un spaţiu.
Restricţii
· 2 ≤ n ≤ 100
· 0≤m<n
·
Pentru 40% dintre
teste m=n-1
·
Pentru 60% dintre
teste numerele copiilor care au trimis tema din fişierul de intrare sunt în
ordine strict crescătoare.
Exemplu
tema.in
|
tema.out
|
Explicaţie
|
7
5
4 1 7 2 6
|
3 5
|
2 copii nu au trimis tema (copilul cu numărul 3 şi copilul cu
numărul 5).
|
Timp maxim de execuţie pe test: 0.1 secunde
Clasa a VI-a
Problema 1 – Grupe 100
puncte
Se consideră un şir format din n cifre. Numărul este divizat în m grupe de cifre alăturate cu
proprietatea că produsul obţinut din numărul de cifre al fiecărei grupe este
maxim.
Dacă notăm cu nr1,nr2,...,nrm numărul de
cifre al fiecărei grupe , avem relaţiile :
nr1+nr2+...+nrm=n
,
nr1≥nr2≥...≥nrm şi
nr1*r2*...*nrm
este maxim.
Cerinţă
Pentru fiecare grupă afişaţi
baza de numeraţie minimă b în care
poate fi scris numărul format din toate cifrele grupei.
Date de intrare
Din fişierul
grupe.in se citeşte de pe prima linie
numărul natural n, iar de pe a doua linie cele n cifre.
Date de ieşire
În fişierul grupe.out se vor afişa, fără spaţii, m
cifre ce reprezintă cifrele maxime din fiecare grupă.
Restricţii şi precizări
·
1 ≤ n ≤ 10000 ; 1≤ m ≤ 100 ; m≤ n.
·
2
≤ b ≤ 10
;
·
Dacă
există mai multe posibilităţi de grupare a cifrelor astfel încât să fie
respectate condiţiile din enunţ, se va alege cea în care grupele au numărul de
cifre în ordine descrescătoare.
Exemplu
Date de intrare
|
Date de ieşire
|
Explicaţie
|
9 3
1 2 3 4 5 6 7 8 9
|
369
|
Cele 9 cifre determină 3
grupe de câte 3 cifre alăturate fiecare. Prima grupă este 1,2,3, a doua grupă
este 4,5,6 iar a treia grupă este formată din 7,8,9. Este îndeplinită condiţia
din enunţ. 3+3+3=9 cifre şi 3*3*3 este
maxim faţă de orice altă grupare a celor 9 cifre.
Cifra maximă din prima
grupă(primele 3 cifre) este 3, din a doua grupă(următoarele 3 cifre) este 6
iar din ultima grupă(ultimile 3 cifre) este 9.
|
15 6
2 5 4 8 7 9 6 5 7 1 0 0 1 4 5
|
597115
|
Cele 15 cifre determină 3
grupe cu 3 cifre (primele grupe) şi 3 grupe de câte 2 cifre.
3+3+3+2+2+2=15 şi
3*3*3*2*2*2 este maxim faţă de orice altă grupare a celor 15 cifre. Prima
grupă este formată din cifrele 2,5,4, a doua grupă este 8,7,9, a treia grupă
este formată din 6,5,7, a patra grupă este 1,0, a cincea grupă este 0,1 iar
ultima este 4,5. Se determină cifra maximă din fiecare grupă, adică 5,9,7,1,1
respectiv 5.
|
Timp maxim de execuţie/test: 0.1
secunde/test.
Problema 2 - Joc 100
Puncte
Dorel doreşte să-şi uimească colegii cu inteligenţa sa, propunându-le
acestora următorul joc. După ce a ales un grup de elevi, a început prezentarea
regulilor jocului. Colegii vor trebuie să-şi aleagă fiecare câte un număr
natural, să facă câteva operaţii şi apoi să-i comunice lui Dorel rezultatul
obţinut, iar acesta va ghici numerele alese de colegii săi.
O primă condiţie este următoarea: doar primul coleg poate alege orice număr
natural dintr-un interval precizat, ceilalţi (de la al doilea încolo) fiind
obligaţi să aleagă câte un număr de o singură cifră.
Cu numerele astfel alese vor fi efectuate următoarele operaţii:
-
primul dintre
colegii lui Dorel va înmulţi numărul ales de el cu 2, va aduna 1 şi va înmulţi
totul cu 5, apoi va comunica rezultatul obţinut, pe ascuns, următorului coleg;
-
al doilea coleg va
aduna numărul ales de el la numărul primit, va înmulţi numărul obţinut
cu 2, va aduna 1 şi va înmulţi totul cu 5 apoi va comunica rezultatul obţinut, pe ascuns, următorului coleg;
......
-
ultimul coleg doar
va aduna numărul ales de el la numărul primit.
Numărul astfel obţinut îi va fi comunicat lui Dorel.
Cerinţă
Pentru un număr construit după regulile de mai sus, ajutaţi-l pe Dorel să
răspundă la următoarele cerinţe:
a)
Câte cifre are
numărul ales de primul dintre colegii săi;
b)
Care sunt numerele
alese de colegii săi.
Întrucât Dorel s-a dovedit foarte priceput, aceştia au decis să joace mai
multe jocuri.
Date de intrare
Fişierul de intrare joc.in conţine pe prima linie numărul
natural n ce reprezintă numărul de
jocuri.
Pe următoarele n linii se află
câte două numere k şi x cu următoarele semnificaţii: k reprezintă numărul de colegi ai lui
Dorel care joacă jocul curent, i, iar
x este numărul ce-i va fi comunicat
lui Dorel.
Date de ieşire
Fişierul de ieşire joc.out va conţine n linii. Pe fiecare din cele n linii se vor scrie, în ordine,
numărul de cifre ale primului număr ales apoi, sepatate prin exact un spaţiu,
cele k numere alese fiecare dintre colegii
lui Dorel.
Restricţii şi precizări
·
1 ≤ x ≤ 1015 ; 1 ≤k ≤10
·
Datele de intrare
sunt totdeauna corecte.
·
n nu poate depăşi 1000.
·
Pentru prima
cerinţă determinată şi afişată corect pentru toate testele din fişier se va
acorda 30% din punctajul total.
Exemplu
joc.in
|
joc.out
|
Explicaţii
|
3
4 17286
5 2156468
4 56789
|
2 16 7 3 1
3 215 0 9 1 3
2 56 2 3 4
|
Există 3 jocuri în fişierul de intrare. La
primul joc participă 4 copii, iar numărul final comunicat lui Dorel este
17286.
Numerele alese de cei 4 copii sunt 16, 7, 3 şi
1. Din acestea, primul are 2 cifre.
|
Timp maxim de execuţie: 1 secundă/test
Clasa a VII-a
Problema 1 – Coduri 100
puncte
Enunț
Doi prieteni buni au inventat un mod de comunicare astfel
încât, oricine ar avea acces la mesajele schimbate între ei, să nu le înțeleagă.
Inițial au convenit să înlocuiască fiecare literă din alfabet cu un număr
astfel: A cu 1, B cu 2, etc. Însă, un coleg de clasă, foarte bun la matematică,
a înțeles imediat codificarea, de aceea au hotărât să schimbe zilnic regulile.
Astfel, la începutul unei zile, stabileau împreună numărul corespunzător
fiecărei litere mari pe care o vor utiliza. De asemenea, la final, în ordinea:
spațiu, virgulă, punct, semnul întrebării, semnul exclamării, atribuie acestor
caractere speciale câte un număr. După fiecare dintre următoarele semne de
punctuație se trece la un rând nou: punct, semnul întrebării și semnul
exclamării.
Cerință
Scrieți un program care să decodifice
mesajul schimbat de cei doi preiteni.
Date de intrare
Din fișierul text coduri.in se citesc:
-
de pe prima linie, separate prin câte un spațiu, numerele
asociate literelor din alfabet;
-
de pe a doua linie, separate prin câte un spațiu, numerele
asociate caracterelor speciale;
-
de pe liniile următoare, numărul de caractere al mesajului șirul de numere
ce trebuie decodificat.
Date de ieșire
În fișierul text coduri.out se va afișa
textul decodificat.
Restricții și precizări
-
Numerele utilizate pentru codificare au întotdeauna exact
două cifre;
-
Mesajele sunt scrise întotdeauna cu litere mari ale alfabetului
englez;
-
Un mesaj poate avea maxim 5000 de caractere;
-
Sfârșitul de rând din fișierul de intrare nu coincide
neapărat cu sfârșitul de rând din textul decodificat.
-
Alfabetul este alcătuit din literele (în această ordine!): A,
B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z.
-
Fiecare caracter al codificării are asociat un număr unic și
distinct de celelalte asociate altor caractere.
-
Toate mesajele se termină cu unul dintre caracterele: ’.’, ’?’, ’!’
Exemplu:
coduri.in
|
coduri.out
|
22 10 24 13 11 14 16 81 18 21 20 23 26 29 41 47 80 28 19
17 15 27 25 30 45 12
79 65 84 36 91
29
26 11 28 16 11 26 79 24
15 79 10 18 24 18 24 23 11 17 11 23 11 36 17 11 79 28 41
16 91
|
MERGEM CU BICICLETELE?
TE ROG!
|
Timp de execuție: 0. 1 secunde/test
Problema 2 – Tablou 100
puncte
Enunț
Gigel
joacă un joc pe calculator. El se află pe un câmp de luptă și trebuie să
salveze prizonierii și civilii aflați în perimetrul respectiv. Dar știe de
asemenea că, pe teren, pot exista mine. La întâlnirea unei mine, pentru a se
salva, trebuie să fugă, în linie dreaptă până la ieșirea din perimetru, astfel
încât să nu mai dea peste alte mine. Perimetrul este dat printr-o dimensiune lat reprezentând lățimea și o
dimensiune lung reprezentând
lungimea acestuia. Acesta poate fi împărțit în culoare orizontale și verticale
de lățime 1 (unu). Poziția
prizonierilor, civililor și minelor este cunoscută prin intermediul a două
valori (i și j) reprezentând numărul orizontalei și a verticalei din perimetru. Prizonierii
și civilii sunt marcați prin valoarea lor care este un număr natural nenul și
printr-un caracter p sau c a
căror semnificație poate fi ușor intuită. Gigel primește în joc o poziție
inițială dată printr-un set de coordonate (i,
j). El are voie să se deplaseze doar pe liniile orizontale sau verticale
până la părăsirea perimetrului prin punctul din colțul dreapta – jos.
Atunci
când întâlnește o mină, marcată prin m,
Gigel trebuie să alerge către marginea tabloului, pe orizontală sau verticală, dar fără să mai schimbe culoarul ales,
astfel încât să nu mai întâlnească altă mină.
El pierde toți prizonierii și civilii salvați până atunci, dar are șansa
să nu-și piardă viața dacă nu mai întâlnește altă mină.
Cerințe
a)
Ajutați-l
pe Gigel să salveze cât mai mulți oameni și să acumuleze cât mai multe puncte
în joc știind că el este obligat să se deplaseze pe cel mai scurt traseu
posibil. Dacă există mai multe astfel de trasee cu lungime egală, are voie să
meargă pe cel mai profitabil. Totalul punctelor este dat de suma valorilor
prizonierilor. La aceasta se adaugă câte un 1 pentru fiecare civil salvat.
b) Aflați numărul maxim de posibilități de scăpare la
întâlnirea unei mine cu coordonatele i și
j precizate.
Date de intrare
Din
fișierul text tablou.in se citesc:
- de pe prima linie, numerele lat, lung, nrp, nrc și nrm, i și j reprezentând: lățimea și
lungimea perimetrului, numărul prizonierilor, civililor și minelor aflați în
acest perimetru și coordonatele poziției inițiale ocupată de Gigel în joc.
- de pe următoarele nrp
+ nrc + nrm linii se citesc câte 4 valori de valori i, j, eticheta (p, c sau
m) și valoarea (toate minele au
valoarea 0)
- de pe linia nrp+nrc+nrm+2
se află o pereche i, j de valori ce
reprezintă poziția minei de la punctul b) al cerinței.
Date de ieșire:
În
fișierul text tablou.out se vor afișa, pe câte un rând rezultatele obținute în
urma rezolvării cerințelor a), respectiv b).
Restricții și precizări:
-
lat
și lung sunt numere naturale nenule
mai mici decât 100;
-
1≤ i ≤ lat
și 1≤ j≤ lung;
-
toți
prizonierii, civilii și minele au poziții în interiorul perimetrului precizat;
-
valorile
prizonierilor și civililor sunt numere naturale nenule mai mici decât 100;
-
la
întânirea unei mine, ieșirea din perimetru este permisă prin orice punct;
-
Gigel
nu are voie să treacă de mai multe ori prin același punct de coordonate (i, j);
-
lungimea
unui traseu se calculează ca numărul de celule 1x1 din perimetru pe care are
loc deplasarea
-
Cerința
a) valorează 70% din punctajul total. Cerința b) valorează 30% din punctajul
total.
Exemplu
tablou.in
|
tablou.out
|
Explicații
|
4 6 6 4 4 3 1
1 2 p 20
1 4 c 5
2 1 p 30
2 2 m 0
2 3 m 0
2 4 p 8
2 6 m 0
3 2 c 10
3 3 m 0
3 5 p 37
4 1 p 14
4 3 c 11
4 4 p 12
4 6 p 1
2 3
|
28
1
|
Perimetrul arată astfel:
|
p
|
|
c
|
|
|
p
|
m
|
m
|
p
|
|
m
|
|
c
|
m
|
|
p
|
|
p
|
|
c
|
p
|
|
p
|
Valoarea 28 este obținută prin parcurgerea pozițiilor: (3,1) – (4,1) – (4,2)
– (4,3) – (4,4) – (4,5) – (4,6).
Parcurgerea următoare nu este posibilă: (3,1) – (3,2) – (4,3) – (4,4) –
(4,5) – (4,6)
Parcurgerea (3,1) – (3,2) – (3,3) conduce la întâlnirea unei mine
|
Timp de execuție: 0.5 secunde / test
Clasa a VIII-a
Problema 1 – Clase 100
puncte
Lui Gigel îi place
să se joace nu numai cu numerele, ci şi cu cuvintele.
Astfel, el a citit că anagrama unui cuvânt dat se obţine prin schimbarea
ordinii literelor sale. De exemplu având dat cuvântul 'tari', cuvintele 'trai' şi 'itar'
reprezintă anagrame ale cuvântului dat. Evident, în cazul în care o literă se
repetă într-un cuvânt, prin interschimbarea a două litere egale nu se obţine o
anagramă (de exemplu interschimbând cele două litere 'g' din cuvântul 'gigel' se va
obţine tot 'gigel').
Prin cuvânt
vom înţelege o succesiune de maxim 200 caractere litere mici ale alfabetului
englez (de la 'a' la 'z').
Să considerăm o
listă nevidă de cuvinte. În listă pot să apară cuvinte care sunt anagrame ale
altor cuvinte din listă. Prin urmare, se pune problema partiţionării listei în clase
de anagrame.
O clasă de anagrame
conţine toate anagramele distincte
ale unui cuvânt aflate în lista dată, scrise în ordine lexicografică (ordinea
cuvintelor din dicţionar). Primul cuvânt dintr-o clasă de anagrame este prin
urmare cel mai mic din punct de vedere lexicografic (primul în ordinea
cuvintelor din dicţionar) şi va fi numit reprezentantul clasei.
Cerinţă
Dată fiind o listă
de cuvinte, determinaţi partiţionarea acesteia în clase de anagrame.
Date
de intrare
Fişierul de intrare
clase.in conţine cuvintele din listă, câte un cuvânt pe o linie.
Date
de ieşire
Fişierul de ieşire clase.out
conţine clasele de anagrame, câte o clasă pe o linie. O clasă de anagrame este
specificată scriind cuvintele din clasa de anagrame respectivă, în ordine
lexicografică, separate prin câte un spaţiu. Clasele sunt specificate în fişier
în ordinea lexicografică a reprezentanţilor acestora.
Restricţii
- 0 < lungimea
unui cuvânt ≤ 200
- 0 < numărul
de cuvinte distincte din listă ≤ 600
- Cuvintele conţin numai litere mici ale alfabetului englez (de la 'a' la 'z').
- Cuvintele din listă se pot repeta.
Exemple
clase.in
|
clase.out
|
Explicaţii
|
tari
trai
mare
rame
itar
berber
atri
mare
eram
rame
|
atri itar tari trai
berber
eram mare rame
|
Au fost detectate trei clase de anagrame.
Fiecare clasă conţine anagrame în ordine lexicografică. De exemplu
pentru prima clasă de anagrame atri<itar<tari<trai, iar atri
este reprezentantul clasei.
Clasele sunt specificate în ordinea lexicografică a reprezentanţilor
(atri<berber<eram)
Se observă faptul că o clasă poate fi formată dintr-un singur cuvânt.
Cuvintele mare şi rame se repetă în lista de cuvinte.
|
armata
tamara
atamar
marata
|
armata atamar marata tamara
|
Toate cele patru cuvinte formează o singură clasă de anagrame.
|
Timp maxim de execuţie/test: 0.1
secunde
Problema 2 – Vot 100
puncte
În Utopia
sunt alegeri parlamentare. Pe buletinul de vot apar N partide, numerotate de la 1 la N. După vot,
fiecare buletin de vot este scanat. Scannerul produce un şir de N caractere din mulţimea {'+', '-'}. Dacă al i-lea caracter din şir este '+' deducem că există o ştampilă în zona corespunzătoare partidului i (1≤i≤N). Caracterul
'-' semnifică faptul că nu a fost pusă ştampila în dreptului
partidului respectiv.
Un buletin de
vot este considerat valid dacă pe buletin apare exact o singură ştampilă în
zona unui singur partid.
Un partid
ajunge în Parlament dacă obţine cel puţin 5% din numărul voturilor valide.
Cerinţă
Scrieţi un program care să determine partidele care ajung în Parlament,
în ordinea crescătoare a numerelor lor.
Date de intrare
Fişierul de intrare vot.in conţine pe prima linie două numere naturale separate
prin spaţiu N şi M, reprezentând numărul de partide şi respectiv numărul de
buletine de vot. Pe următoarele M linii sunt
descrise buletinele de vot, câte un buletin pe o linie, în formatul descris în
enunţ.
Date de ieşire
Fişierul de
ieşire vot.out va conţine o
singură linie pe care vor fi scrise partidele care intră în Parlament, în
ordinea crescătoare a numerelor lor. Numerele partidelor sunt separate prin
spaţii.
Restricţii
· 1 ≤ N ≤ 200
· 1 ≤ M ≤ 50000
·
Există cel
puţin un buletin de vot valid.
·
Pentru datele
de teste există cel puţin un partid care intră în Parlament.
Exemplu
vot.in
|
vot.out
|
Explicaţie
|
3 4
+--
+--
-+-
+-+
|
1 2
|
Sunt 3 partide şi 4 buletine de vot.
Partidul 1 are două voturi (cele de pe buletinele de
vot 1 şi 2).
Partidul 2 are un vot (cel de pe buletinul de vot 3).
Partidul 3 are 0 voturi.
Buletinul de vot 4 este invalid.
Există 3 voturi valide.
5% din numărul de voturi valide înseamnă 0.15 voturi.
Ca urmare, partidele 1 şi 2 intră în Parlament.
|
Timp maxim de execuţie pe test: 0.4 secunde
Memorie totală disponibilă: 2MB, din care 1 MB pentru stivă.