== include(page="template/taskheader" task_id="calc") ==
Poveste şi cerinţă...
!>problema/calc?example.jpeg!
La un concurs de informatică participă $2∙N$ elevi împărţiţi în $N$ echipe de câte $2$ . Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în reţea. Laboratorul de informatică e mai special: are $2∙N$ calculatoare, distribuite pe două rânduri la distanţă de un metru între ele (vertical şi orizontal) şi $N$ cabluri de reţea de lungime un metru. Concursul se desfăşoară pe mai multe zile şi nu există două zile de concurs cu aceeaşi configuraţie a reţelei.
$Exemplu:$ pentru $N=3$ , cei $6$ elevi au fost împărţiţi în $3$ echipe, iar aranjarea reţelei în cele $3$ zile de concurs este cea din figura alăturată.
Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configuraţiile folosite în zilele de concurs. Cablul orizontal se notează prin $0$ , iar cel vertical prin $1$ . Lucrând ordonat şi eficient, pentru cele trei zile el îşi va nota valorile: $001$ , $100$ , respectiv $111$ . Se observă că o reprezentare de genul $000 , 010 , 011 , 101$ nu poate fi realizată.
h2. Cerinţă
Cunoscând $N$, să se determine:
1. Numărul de zile modulo $1 000 000 007$ în care se desfăşoară concursul.
2. Configuraţiile laboratorului în ziua $X-1$ şi ziua $X+1$ , cunoscând configuraţia zilei $X$ .
h2. Date de intrare
Fişierul de intrare $calc.in$ ...
Fişierul de intrare $calc.in$ conţine pe prima linie un număr natural $p$ . Pentru toate testele de intrare, numărul $p$ poate avea doar valoarea $1$ sau valoarea $2$ .
Pe linia a doua vom avea numărul natural $N$ .
Pe linia a treia se va găsi un şir de $N$ cifre binare, fără spaţii între ele, reprezentând configuraţia corectă realizată de administrator în ziua $X$ .
h2. Date de ieşire
În fişierul de ieşire $calc.out$ ...
Dacă valoarea lui $p$ este $1$, se va rezolva numai punctul $1)$ din cerinţă. În acest caz, în fişierul de ieşire $calc.out$ se va scrie un singur număr natural $Z$ reprezentând numărul de zile în care se desfăşoară concursul pentru cele $N$ echipe.
Dacă valoarea lui $p$ este $2$, se va rezolva numai punctul $2)$ din cerinţă. În acest caz, fişierul de ieşire $calc.out$ va conţine două linii. Pe prima linie se vor scrie $N$ cifre binare, fără spaţii între ele, reprezentând configuraţia reţelei din ziua precedentă, iar pe a doua linie $N$ cifre binare, fără spaţii între ele, reprezentând configuraţia din ziua următoare. Dacă în ziua precedentă nu există o configuraţie conform cerinţelor problemei, se va scrie pe prima linie valoarea $-1$ . Dacă în ziua următoare nu există o configuraţie conform cerinţelor problemei, se va scrie pe a doua linie valoarea $-1$ .
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100000$
* Pentru rezolvarea corectă a primei cerinţe se acordă $20$ de puncte, iar pentru cerinţa a doua se acordă $80$ de puncte.
h2. Exemplu
table(example). |_. calc.in |_. calc.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
3
001
| 3
|
| 2
3
001
| -1
100
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="calc") ==
