Fişierul intrare/ieşire:dinti.in, dinti.outSursăAlgoritmiada 2010, Runda 2
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.1 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/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.indinti.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content