Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | prajituri.in, prajituri.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | din folclor | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.3 sec | Limită de memorie | 524288 KB |
| Scorul tău | N/A | Dificultate |
   2.25
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Prăjituri (clasele 9-12)
Moș Crăciun a găsit sub brad n borcane cu prăjituri, numerotate de la 1 la n. Borcanul i conține ai prăjituri.
Moș Crăciun vrea să mănînce prăjituri, dar are două reguli ciudate:
- Din fiecare borcan, Moșul mănîncă fie toate prăjiturile, fie niciuna.
- Moșul dorește să mănînce un număr maxim de prăjituri modulo m.
Aflați numărul maxim de prăjituri pe care Moșul le poate mînca modulo m și ce borcane trebuie să mănînce.
Date de intrare
Fișierul de intrare prajituri.in conține pe prima linie numerele n și m. Pe următoarea linie apar valorile a1, a2, ..., an.
Date de ieșire
În fișierul de ieșire prajituri.out afișați pe prima linie numărul maxim de prăjituri modulo m pe care le poate mînca Moșul. Pe a doua linie afișați un șir de 0 și 1, fără spații, în care al i$-lea caracter este $1 dacă Moșul mănîncă prăjiturile din borcanul i sau 0 în caz contrar.
Dacă există mai multe soluții, afișați-o pe oricare.
Restricții
• 2 ≤ n ≤ 40
• 1 ≤ m ≤ 10.000.000
• 1 ≤ ai < m pentru 1 ≤ i ≤ n
• Testele nu sînt grupate.
| subtask | puncte | restricții |
|---|---|---|
| 1 | 52 | n ≤ 24 |
| 2 | 36 | n ≤ 37 |
| 3 | 12 | Fără restricții suplimentare. |
Exemplu
| prajituri.in | prajituri.out |
|---|---|
| 5 50 38 37 44 6 22 |
47 11001 |
Explicație
Moș Crăciun mănîncă borcanele 1, 2 și 5, care au 97 de prăjituri în total (adică 47 modulo 50).
