| Fişierul intrare/ieşire: | bordura.in, bordura.out | Sursă | ad-hoc |
| Autor | Adrian Budau | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bordura
Primarul Bucurestiului s-a hotarat dintro-data sa construiasca foarte multe sensuri giratorii. Si pentru fiecare trebuie sa construiasca borduri (nu poti sa ai sensuri giratorii fara borduri). Spatiul din jurul sensului giratoriu e impartit in N sectoare numerotate de la 1 la N, oricare 2 sectoare consecutive fiind vecine. Pe deasupra sectorul 1 si sectorul N sunt si ele vecine. El are doua tipuri blocuri cu care poate sa bordeze sensurile giratorii, cele albastre (care ocupa 2 sectoare vecine pe un singur bloc) si cele rosii (care ocupa un singur sector).
Primarul Bucurestiului fiind un om artistic vrea ca toate sensurile giratorii sa fie bordate diferite, asa ca va roaga pe voi sa-i calculati cate bordari diferite exista pentru un sens giratoriu cu bordura impartita in N sectoare exista. Deoarece acest numar poate fi foarte mare el va roaga sa il afisati modulo 666013.
Date de intrare
Fişierul de intrare bordura.in va contine pe primul si singurul rand un numar natural N.
Date de ieşire
În fişierul de ieşire bordura.out trebuie sa se afle un singur numar reprezentand raspunsul la intrebarea primarului.
Restricţii
- 3 ≤ N ≤ 100.000
- Pentru teste valorand 20% din punctajul maxim N ≤ 15
Exemplu
| bordura.in | bordura.out |
|---|---|
| 3 | 4 |
Explicaţie
Cele 4 bordari diferite sunt:
RRR
AAR
ARA
RAA
unde cu A am notat un sector peste care s-a pus un bloc albastru, iar cu R un sector peste care s-a pus un bloc rosu.
De observat ca RRA nu e solutie pentru ca blocurile albatre acopera 2 sectoare vecine, nu pot ocupa un singur sector.
