.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » sir9

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
sir9


Timp maxim de execuţie / test:
0.8s
Memorie totala disponibilă / stivă:
2MB / 1MB

Definim recursiv următorul șir:
x[0]=x0,
x[1]=x1,
x[i]=ax[i-1]+bx[i-2]+c, pentru orice i2.

Cerinţă

Realizați un program care calculează suma x[s]+x[s+1]+...+x[f]. Deoarece această sumă poate fi foarte mare se cere afișarea acesteia modulo 101587009.

Date de intrare

Pe prima linie a fișierului de intrare sir9.in se găseşte numărul natural T, reprezentând numărul de instanţe ale problemei ce trebuiesc rezolvate. Următoarele T linii conţin descrierea celor T instanţe. Mai exact, pe linia i+1 se găsesc numerele naturale x0, x1, a, b, c, s şi f reprezentând datele pentru instanţa i.

Date de ieşire

Fișierul de ieșire sir9.out va conține T linii. Pe linia i se va afla răspunsul pentru instanţa i.

Restricţii

1T1000
0x0, x1, a, b, c108
0sf1018
Pentru teste în valoare de 20 puncte, suma valorilor lui f pentru cele T instanţe nu va depăşi 107.

Exemple

sir9.insir9.outExplicaţii
2 0 1 1 1 0 3 5 2 1 2 1 3 0 4 10 74 Sunt două instanțe. Pentru prima instanţă, şirul x este 0, 1, 1, 2, 3, 5, ..., deci suma cerută este 2+3+5=10. Pentru a doua instanţă, şirul x este 2, 1, 7, 18, 46, ..., deci suma cerută este 2+1+7+18+46=74.

autor: Stud. Vlad Tudose
propunător: Stud. Vlad Manea
FII
vlad.c.manea@gmail.com
Probleme recomandate
De la FII Competition 2011: lipsa, reducere, viena, sablon2, fibgcd, acoperire, razboi, safeu, centrala, benzina2, bradut2, capra, agendatelefonica, cds, micro, wg
De acelaşi autor: circuit, graphgame, dag
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, 2ndesc, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor