| Fişierul intrare/ieşire: | dinti.in, dinti.out | Sursă | Algoritmiada 2010, Runda 2 |
| Autor | Cosmin Gheorghe | Adăugată de |  Gheorghe Cosmin •gcosmin |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 36096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dinti
Speranta trebuie sa rezolve o problema de potrivire de siruri mai neobisnuita. Ea are astfel un sir A de lungime N de 1 si 0. Primind mai multe siruri B de lungime L tot de 1 si 0, Speranta vrea sa stie daca poate suprapune sirul B undeva peste sirul A astfel incat doua 1-uri sa nu se suprapuna. Mai exact pentru sirul B, Speranta trebuie sa stie daca exista o pozitie k in sirul A astfel incat MAX ( A[ k ] + B[ 1 ], A[ k + 1 ] + B[ 2 ], ..., A[ k + L - 1 ] + B[ L ] ) <= 1, unde k + L - 1 ≤ N.
Date de intrare
Fisierul de intrare dinti.in va contine pe prima linie numerele N, M si L reprezentand lungimea sirului A si respectiv numarul si lungimea sirurilor B. A doua linie va contine sirul A. Urmatoarele M linii vor contine fiecare cate un sir B.
Date de ieşire
In fişierul de iesire dinti.out veti afisa M linii reprezentand raspunsul pentru fiecare intrebare: 1 daca sirul B se poate suprapune peste sirul A astfel incat sa respecte conditia din enunt sau 0 daca nu.
Restricţii
- 1 ≤ L ≤ 20
- L ≤ N ≤ 106
- 1 ≤ M ≤ 105
Exemplu
| dinti.in | dinti.out |
|---|---|
| 15 10 5 110110100101000 10101 11100 11010 01110 01101 11011 00111 10110 11011 11000 | 1 0 1 0 1 0 1 1 0 1 |
