Fişierul intrare/ieşire:2sah.in, 2sah.outSursăOJI 2015
AutorAdrian PanaeteAdăugată deheracleRadu Muntean heracle
Timp execuţie pe test0.3 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

2sah (clasele 11-12)

Se dă o tablă de şah cu n+1 linii (numerotate de sus în jos începând cu 1) şi 2n+1 coloane (numerotate de la stânga la dreapta începând cu 1). Pe prima linie pătratul din mijloc conţine 1 gram de fân, iar celelalte pătrate de pe prima linie nu conţin nimic. Începând cu linia a doua fiecare pătrat conţine o cantitate de fân obţinută prin adunarea cantităţilor de fân din cele 3 pătrate ale liniei anterioare cu care se învecinează (pe verticală şi diagonală). De exemplu dacă n=3 tabla are 4 linii, 7 coloane şi următoarea configuraţie.

Un cal pleacă de pe prima linie, de pe o coloană k ≤ n, sare din orice poziţie (i,j) în poziţia (i+1,j+2) atât timp cât este posibil şi mănâncă tot fânul din pătratele prin care trece. De exemplu, pentru n=3 şi k=2, pătratele prin care trece calul sunt marcate cu asterisc (*).

Cerinţe

  1. Cunoscând n şi k, să se calculeze cantitatea de fân de pe linia k a tablei.
  2. Cunoscând n şi k, să se calculeze câte grame de fân mănâncă un cal care pleacă de pe prima linie, de pe coloana k.

Întrucât aceste numere pot fi mari, se cere doar restul modulo 100.003 ale acestor numere.

Date de intrare

Fişierul de intrare 2sah.in va conţine pe prima linie un număr t cu valoarea 1 sau 2. Pe a doua linie a fişierului de intrare se găsesc două numere naturale n şi k separate printr-un spaţiu.

Dacă t=1 se va rezolva prima cerinţă, deci pentru valoarea n citită tabla are n+1 linii şi 2n+1 coloane, iar k reprezintă numărul liniei de pe care trebuie calculată cantitatea de fân.

Dacă t=2 se va rezolva a doua cerinţă, deci pentru valoarea n citită tabla are n+1 linii şi 2n+1 coloane, iar k reprezintă numărul coloanei din prima linie de unde pleacă calul.

Date de ieşire

Dacă t din fişierul de intrare este 1 se va rezolva doar prima cerinţă.

În acest caz fişierul de ieşire 2sah.out va conţine un singur număr reprezentând cantitatea totală de fân din toate pătratele situate pe tabla pe linia k (trebuie afişat restul modulo 100.003).

Dacă t din fişierul de intrare este 2 se va rezolva doar a doua cerinţă.

În acest caz fişierul de ieşire 2sah.out va conţine un singur număr reprezentând cantitatea totală de fân mâncată de un cal care pleacă de pe linia 1 şi coloana k (trebuie afişat restul modulo 100.003).

Restricţii

  • 1 ≤ k ≤ n ≤ 1.000.000.000 (un miliard)
  • La cerinţa 1 pentru 80% dintre teste k ≤ n ≤ 1.000.000, iar pentru alte 20% din teste k ≤ n ≤ 1.000.000.000
  • La cerinţa 2 pentru 30% dintre teste k ≤ n ≤ 1.000, pentru alte 30% dintre teste k ≤ n ≤ 1.000.000, iar pentru restul de 40% dintre teste k ≤ n ≤ 1.000.000.000.
  • Rezolvarea corectă a primei cerinţe asigură 30% din punctajul testului respectiv.
  • Rezolvarea corectă a celei de a doua cerinţe asigură 70% din punctajul testului respectiv.

Exemplu

2sah.in2sah.outExplicaţie
1
3 2
3
t=1, deci se rezolvă prima cerinţă.
Pe linia a doua există 3 pătrate care conţin fiecare câte un gram de fân (vezi desenul din enunţ).
2
3 2
2
t=2, deci se rezolvă doar a doua cerinţă.
Traseul calului este: (1,2) -> (2,4) -> (3,6) adică exact pătrăţelele marcate cu asterisc în desenul din enunţ.
Prima poziţie nu conţine fân, iar celelalte două conţin câte un gram de fân. Deci calul mănâncă 2 grame de fân.
Trebuie sa te autentifici pentru a trimite solutii. Click aici