Fişierul intrare/ieşire:routere.in, routere.outSursăAlgoritmiada 2018 Runda Finala
AutorMihai CalanceaAdăugată de
Timp execuţie pe test0.3 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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.inroutere.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?