Nu aveti permisiuni pentru a descarca fisierul grader_test10.in
Inverseaza reviziile

Diferente pentru problema/dinti intre reviziile #1 si #12

Diferente intre titluri:

dinti

Dinti

Diferente intre continut:

== include(page="template/taskheader" task_id="dinti") ==

Poveste şi cerinţă...

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 &le; N$.

h2. Date de intrare

Fişierul de intrare $dinti.in$ ...

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$.

h2. Date de ieşire

În fişierul de ieşire $dinti.out$ ...

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.

h2. Restricţii

* $... &le; ... &le; ...$

* $1 &le; L &le; 20$
* $L &le; N &le; 10^6^$
* $1 &le; M &le; 10^5^$

h2. Exemplu
table(example). |_. dinti.in |_. dinti.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 15 10 5
110110100101000
10101
11100
11010
01110
01101
11011
00111
10110
11011
11000
| 1
0
1
0
1
0
1
1
0
1

|

h3. Explicaţie
...
 
== include(page="template/taskfooter" task_id="dinti") ==

==Include(page="template/taskfooter" task_id="dinti")==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 

4376