Fişierul intrare/ieşire: | routere.in, routere.out | Sursă | Algoritmiada 2018 Runda Finala |
Autor | Mihai Calancea | Adăugată de | |
Timp execuţie pe test | 0.15 sec | Limită de memorie | 256000 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Routere
Mihai, ajuns la sediul Aneraofni pentru o noua zi de munca, a fost convins de catre marele boss al organizatiei sa renoveze sediul. Sediul Aneraofni are forma unui inel cu N camere -- camera 1 se leaga de camerele N si 2, camera 2 se leaga de camerele 1 si 3, si asa mai departe.
Partea esentiala a renovarii o constituie amplasarea routerelor prin camerele sediului. Routerele pot avea diverse raze de acoperire. Mai exact, toate routerele vor avea o calitate naturala nenula R, aleasa de Mihai, si vor putea acoperi un interval de R camere consecutive. Din cauza fragilitatii sistemului electric din sediul Aneraofni, nu pot fi amplasate doua routere care acopera acelasi interval.
Planul de renovare care vine de la marele boss al organizatiei specifica ca fiecare camera in parte are nevoie de semnal de la un anume numar de routere.
Mihai se intreaba: "in cate moduri pot alege calitatea routerelor, respectiv in cate moduri pot alege in care camere sa le amplasez, astfel incat planul marelui boss sa fie satisfacut?"
Date de intrare
Fişierul de intrare routere.in va contine, pe primul rand, numarul N.
Pe al doilea rand, vom gasi numarul de routere de la care are nevoie semnal fiecare camera in parte, in ordine.
Date de ieşire
În fişierul de ieşire routere.out vom gasi numarul cerut, afisat modulo 666013.
Restricţii
- 1 ≤ N ≤ 1 000
- R < N
- 0 ≤ numarul de routere de care are nevoie semnal oricare camera ≤ N
- Pentru teste in valoare de 21 de puncte, N ≤ 20.
- Pentru teste in valoare de 39 de puncte, N ≤ 100.
- Aveti grija ! Precum in viata reala, marele boss poate cere si ceva imposibil.
Exemplu
routere.in | routere.out |
---|---|
3 1 1 1 | 1 |
5 0 1 2 1 0 | 1 |
6 1 2 2 1 1 1 | 2 |
3 0 0 0 | 2 |
20 5 5 5 5 5 6 6 6 6 7 7 7 7 7 7 6 6 6 6 5 | 59 |
Explicatie
In primul exemplu, alegem R = 1 si punem un router in fiecare camera.
In al doilea exemplu, alegem R = 2 si punem un routere pe intervalele [2, 3] si [3, 4].
In al treilea exemplu, alegem R = 2 si punem un router pe intervalele [1, 2], [2, 3], [3, 4], [5, 6], sau alegem R = 4 si punem router pe intervalele [2, 5], [6, 3] (intervalul [6, 3] este cel ce incepe in camera 6, si continua in camerele 1, 2 si 3).
In penultimul exemplu, alegem R = 1 sau R = 2, si nu amplasam niciun router.