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

Perry a ajuns la "Doofenshmirtz":https://www.youtube.com/watch?v=zHNy4ztdn7w pentru a-l împiedica din a distruge întreaga lume cu noul său inator.

Perry a ajuns la Doofenshmirtz pentru a-l împiedica din a distruge întreaga lume cu noul său inator.

Totuşi, odata ce intră pe uşă are o surpriză: în loc de sala mare, obişnuită, se află într-un hol cu podeaua acoperită cu $N$ plăcuţe aşezate în linie, numerotate de la $1$ la $N$, el aflându-se la intrare, fix *în spatele* plăcuţei $1$.

Robotul Norm, asistentul lui Doofenshmirtz îi zice apoi agentului P: "_Te afli în cea mai noua capcană anti-ornitorinci. Tot ce trebuie să faci ca să scapi este să ajungi la finalul holului, să treci de plăcuţa $N$. Totuşi, sub $K$ dintre plăcuţe se află bombe. Am fi pus sub toate, dar nu ne-a permis bugetul, deci dacă vei călca pe o plăcuţă care are sub ea o bombă, vei muri pe loc. Baftă să evadezi şi de data asta!_"

Robotul Norm, asistentul lui Doofenshmirtz îi zice apoi agentului P: "_Te afli în cea mai noua "capcană":https://www.youtube.com/watch?v=zHNy4ztdn7w anti-ornitorinci. Tot ce trebuie să faci ca să scapi este să ajungi la finalul holului, să treci de plăcuţa $N$. Totuşi, sub $K$ dintre plăcuţe se află bombe. Am fi pus sub toate, dar nu ne-a permis bugetul, deci dacă vei călca pe o plăcuţă care are sub ea o bombă, vei muri pe loc. Baftă să evadezi şi de data asta!_"

Ca întotdeauna, Perry este pregătit. Are un dispozitiv în care poate scrie, de mai multe ori, câte un triplet $(c, a, b)$, iar dispozitivul îi va returna $1$ dacă in secvenţele de plăcuţe de lungime c care încep pe a, respectiv b sunt un număr egal de plăcuţe periculoase (cu bombe sub), sau $0$ altfel.

* $K * 2 + 1 ≤ N$
* Pentru $20%$ din teste, $1 ≤ N ≤ 2000$
* Pentru încă $20%$ din teste, $K = 1$

* Placuţele capcană sunt fixate de dinainte. (Graderul nu este adaptiv)

h2. Punctare

* $50%$ din punctajul pe test pentru $Q ≤ 2 * (K + 1) * ( log ~2~ N + 4 )$
* $100%$ din punctajul pe test pentru $Q ≤ (K + 1) * ( log ~2~ N + 4 )$

* *In plus* pentru $1 ≤ N ≤ 2000$, punctajul pe test va fi acordat în totalitate dacă răspunsul este cel corect, indiferent de $Q$

* *In plus* pentru $1 ≤ N ≤ 2000$, punctajul pe test va fi acordat în totalitate dacă răspunsul este cel corect, atata timp cat $Q ≤ 10^4$

h2. Exemplu

Din cele 3 plăcuţe, doar una este periculoasă. Când aflăm ca plăcuţa 1 si plăcuţa 3 sunt identice, devine clar faptul că niciuna dintre cele două nu pot avea o bombă sub, deoarece $K = 1$. Astfel putem trage concluzia că plăcuţa 2 este cea periculoasă.

== include(page="template/taskfooter" task_id="capcana") ==