Fișierul intrare/ieșire auto.in, auto.out Sursă ONI 2008, clasa a 9-a
Autor Adrian Airinei | Adrian Pintea Adăugată de avatar Tiberiu02 Tiberiu Musat Tiberiu02
Timp de execuție pe test 0.15 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate N/A

Auto ( clasa a 9-a )

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 ieșire

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.

Restricții

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

Exemplu

auto.in auto.out
2
8
1 2 3 4 2 0 0 0
3
1 1 1
1 2
1 3

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii