Fişierul intrare/ieşire:auto.in, auto.outSursăONI 2008, clasa a 9-a
AutorAdrian Airinei, Adrian PinteaAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Auto

Se considera o autostrada dispusa in linie dreapta avand N puncte de acces (intrare si iesire). In fiecare punct de acces exista containere pentru colectarea deseurilor, toate containerele au aceeasi capacitate si in fiecare punct de acces pot fi mai multe astfel de containere. Firma care asigura curatenia dispune de un singur mijloc de transport al containerelor. Acest mijloc de transport poate incarca exact un numar K de containere. Accesul mijlocului de transport pe autostrada se face cu restrictii pentru a nu perturba traficul si din acest motiv trebuie ca la fiecare acces pe autostrada sa fie colectate exact atatea containere cat este capacitatea masinii, dar dintr-un punct de colectare trebuie sa ia exact un container, deci daca se intra pe autostrada la punctul de acces P, unde P ≤ N-K+1, atunci trebuie sa ia containere de la punctele de acces numerotate cu P, P+1, P+2, ..., P+K-1, in aceste puncte de acces scade cu 1 numarul containerelor ramase. Firma trebuie sa gaseasca toate valorile posibile pentru K astfel incat sa poata colecta toate containerele.

Cerinta

Se cere sa se gaseasca toate valorile posibile pentru K astfel incat sa fie adunate toate containerele.

Date de intrare

Fisierul de intrare auto.in va contine pe prima linie numarul natural T, reprezentand numarul de seturi de date de intrare. In continuare urmeaza seturile de date de intrare, fiecare pe cate doua linii. Pe prima linie a unui set se afla numarul N, avand semnificatia din enunt. Pe urmatoarea linie se afla N numere naturale separate printr-un spatiu, reprezentand numarul de containere din fiecare punct de acces.

Date de iesire

Fisierul de iesire auto.out va contine T linii, pe linia i aflandu-se raspunsul pentru al i-lea set de date de intrare. Valorile posibile pentru K se vor afisa in ordine crescatoare, separate printr-un spatiu.

Restrictii

  • 2 ≤ T ≤ 30
  • 2 ≤ N ≤ 9.000
  • 1 ≤ K ≤ N
  • 0 ≤ numarul de containere din fiecare punct de acces ≤ 10.000

Exemplu

auto.inauto.out
2
8
1 2 3 4 2 0 0 0
3
1 1 1
1 2
1 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content