DEADLINE: Marti, 19 ianuarie
TIMP DE IMPLEMENTARE: 90 minute
"In vreme de razboi..."
-----------------------
In timpul razboiului, impartirea hranei poate crea numeroase probleme.
Numai cu un calculator performant se poate rezolva aceasta spinoasa
problema :).
Dandu-se N soldati, acestia trebuie impartiti in b bastioane, bastioane ce
vor fi plasate de-a lungul frontului de lupta.
Se stie ca fiecare soldat poate cara un anumit nr. de pachete de hrana.
Pentru a nu se crea conflicte, soldatii trebuie impartiti in b bastioane,
astfel incat, in cazul distrugerii primelor d bastioane (pentru orice d
de la 0 la b-1) proviziile de hrana din bastionul d+1 sa poata fi impartite
in mod exact la numarul de soldati ramasi.
Datele de intrare se citesc din fisierul "razboi.in", care are urmatoarea
configuratie:
N -> numarul de soldati, 1<=N<=1000
x1 x2 .... xN -> xI reprezinta numarul de pachete de hrana carate
de soldatul I. 1<=xI<=1000, I=1,n.
Datele de iesire se scriu in fisierul "razboi.out", fisier care va
contine b linii (b numarul de bastioane). Atentie ! Numarul de bastioane
nu se da, ci va trebui sa il decideti voi !
Pe linia I se vor scrie datele despre bastionul I. Datele despre un bastion
vor fi de forma xI1, xI2,... xIr, unde I1, I2, .... , Ir sunt soldatii
grupati in respectivul bastion.
Exemplu: Explicatia exemplului:
|
Pentru fisierul "razboi.in", | Avem 6 soldati care cara cantitatile
6 |4,7,3,9,10 si respectiv 3 pachete de
4 2 3 9 10 3 |hrana.
| Acestia au fost impartiti in 4
un fisier corect de iesire este: |bastioane, astfel:
razboi.out | In primul bastion se afla 2 soldati,
---------- |unul carand 9 pachete de hrana, si
9 3 |celalalt 3 pachete.
4 | Analog in bastionul 2 se afla un
10 2 |singur soldat care cara 4 pachete,
3 |in bastionul 3 se afla 2 soldati ce
|cara 10 respectiv 2 pachete, iar in
------------------------------------+
bastionul 4 se afla un singur soldat ce cara 3 pachete.
Iesirea este corecta pentru ca:
1) Daca nu este distrus nici un bastion, cantitatea de hrana din primul
bastion (9+3=12 pachete) poate fi impartita exact la cei 6 soldati in
viata.
2) Daca este distrus primul bastion, cantitatea de hrana din al 2-lea
bastion (4 pachete) poate fi impartita exact la cei 4 soldati ramasi
in viata.
3) Daca sunt distruse primele 2 bastioane, cantitatea de hrana din
al 3-lea bastion (10+2=12 pachete) poate fi impartita exact la cei 3
soldati ramasi in viata.
3) Daca sunt distruse primele 3 bastioane, cantitatea de hrana din
al 4-lea bastion (3 pachete) poate fi impartita exact la singurul
soldat ramas in viata.
Timp de executie: 1 sec./test pe Pentium 166 Mhz.
|
|
