| Fişierul intrare/ieşire: | kpart.in, kpart.out | Sursă | EJOI 2021, ziua 1 |
| Autor | Ionel Vasile Pit Rada | Adăugată de |  Voicu Mihai Valeriu •cadmium_ |
| Timp execuţie pe test | 1.575 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Kpart
Virgil tocmai şi-a propus să studieze proprietăţi ale şirurilor. Astfel, el defineşte un K-şir ca fiind orice şir de numere naturale nenule care are proprietatea că orice subsecvenţă a sa de lungime K se poate partiţiona în două subşiruri disjuncte, nu neapărat subsecvenţe, având suma egală. De exemplu 1, 2, 1, 3 este un 3-şir, căci 1, 2, 1 poate fi partiţionat în 1, 1 şi 2, şi 2, 1, 3 poate fi partiţionat în 2, 1 şi 3. Nu este 2-şir căci 1, 2 nu poate fi partiţionat în două subşiruri cu sumă egală. Totodată nu este 4-şir
Pentru T şiruri de numere naturale nenule A, Virgil doreşte să afle toate valorile K, pentru care şirul A poate fi numit K-şir.
Date de intrare
Pe prima linie a fişierul de intrare kpart.in se află numărul T. Urmează apoi T şiruri. Fiecare şir este dat prin două linii. Prima linie conţine valoarea lui N. A doua linie conţine elementele şirului separate prin câte un spaţiu.
Date de ieşire
În fişierul de ieşire kpart.out afişaţi răspunsurile pentru fiecare şir în ordine. Pentru fiecare şir afişaţi câte o linie care conţine mai întâi numărul de valori K pentru care şirul este K-şir şi apoi, în ordine crescătoare, acele valori K pentru care şirul este K-şir.
Restricţii
- 1 ≤ T ≤ 20
- Fie S suma valorilor dintr-un şir (nu suma valorilor tuturor şirurilor). Atunci 1 ≤ S ≤ 100 000
- În plus:
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 10 | 1 ≤ N ≤ 30 |
| 2 | 20 | 31 ≤ N ≤ 120 |
| 3 | 70 | 121 ≤ N ≤ 1 000 |
Exemplu
| kpart.in | kpart.out |
|---|---|
| 2 7 7 3 5 1 3 3 5 6 1 2 3 5 8 3 | 2 4 6 2 3 6 |
Explicaţie
Primul şir, cel de lungime 7 este 4-şir şi 6-şir, deoarece fiecare secvenţă de lungime 4, respectiv 6, conţin câte două subşiruri disjuncte cu suma egală care partiţionează secvenţa. Al doilea şir, cel de lungime 6 este 3-şir şi 6-şir, deoarece fiecare secvenţă de lungime 3 şi fiecare secvenţa de lungime 6, conţin câte două subşiruri disjuncte cu suma egală care partiţionează secvenţa.
