1135 - p2sah: Diferență între versiuni
Fără descriere a modificării |
Fără descriere a modificării |
||
Linia 16: | Linia 16: | ||
Dacă <code>t=1</code> se va rezolva prima cerință, deci pentru valoarea <code>n</code> citită tabla are <code>n+1</code> linii și <code>2n+1</code> coloane, iar <code>k</code> reprezintă numărul liniei de pe care trebuie calculată cantitatea de fân. | Dacă <code>t=1</code> se va rezolva prima cerință, deci pentru valoarea <code>n</code> citită tabla are <code>n+1</code> linii și <code>2n+1</code> coloane, iar <code>k</code> reprezintă numărul liniei de pe care trebuie calculată cantitatea de fân. | ||
Dacă <code>t=2</code> se va rezolva a doua cerință, deci pentru valoarea <code>n</code> citită tabla are <code>n+1</code> linii și <code>2n+1</code> coloane, iar <code>k</code> reprezintă numărul coloanei din prima linie de unde pleacă calul. | Dacă <code>t=2</code> se va rezolva a doua cerință, deci pentru valoarea <code>n</code> citită tabla are <code>n+1</code> linii și <code>2n+1</code> coloane, iar <code>k</code> reprezintă numărul coloanei din prima linie de unde pleacă calul. | ||
= Date de ieșire = | = Date de ieșire = | ||
Linia 25: | Linia 25: | ||
Dacă <code>t</code> din fișierul de intrare este <code>2</code> se va rezolva doar a doua cerință. | Dacă <code>t</code> din fișierul de intrare este <code>2</code> se va rezolva doar a doua cerință. | ||
În acest caz fișierul de ieșire <code>p2sahOUT.txt</code> va conține un singur număr reprezentând cantitatea totală de fân mâncată de un cal care pleacă de pe linia <code>1</code> și coloana <code>k</code> (trebuie afișat restul modulo <code>100003</code>). | În acest caz fișierul de ieșire <code>p2sahOUT.txt</code> va conține un singur număr reprezentând cantitatea totală de fân mâncată de un cal care pleacă de pe linia <code>1</code> și coloana <code>k</code> (trebuie afișat restul modulo <code>100003</code>). În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse". | ||
= Restricții și precizări = | = Restricții și precizări = |
Versiunea curentă din 18 mai 2024 16:37
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 coloana 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 100003
ale acestor numere.
Date de intrare
Fișierul de intrare p2sah.in
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 p2sahIN.txt.txt
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 100003
).
Dacă t
din fișierul de intrare este 2
se va rezolva doar a doua cerință.
În acest caz fișierul de ieșire p2sahOUT.txt
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 100003
). În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".
Restricții și precizări
1 ≤ k ≤ n ≤ 1.000.000.000
- La cerința 1 pentru 80% dintre teste
k ≤ n ≤ 1.000.000
, iar pentru alte 20% din testek ≤ n ≤ 1.000.000.000
- La cerința 2 pentru 30% dintre teste
k ≤ n ≤ 1000
, pentru alte 30% dintre testek ≤ n ≤ 1.000.000
, iar pentru restul de 40% dintre testek ≤ n ≤ 1.000.000.000
. - Rezolvarea corectă a primei cerințe asigură 20% din punctajul testului respectiv.
- Rezolvarea corectă a celei de a doua cerințe asigura 70% din punctajul testului respectiv.
Exemplul 1
p2sahIN.txt
1 3 2
p2sahOUT.txt
3
Exemplul 2
p2sahIN.txt
1 3 4
p2sahOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
MOD = 100003
def solve(M, T, S):
if M in S:
return
m = M // 2
solve(m + 1, T, S)
solve(m, T, S)
solve(m - 1, T, S)
solve(m - 2, T, S)
S.add(M)
if M % 2:
T[M] = (1 * T[m] * T[m - 1] + 1 * T[m] * T[m - 1] + 1 * T[m] * T[m] + 1 * T[m + 1] * T[m + 1]) % MOD
else:
T[M] = (1 * T[m] * T[m + 1] + 1 * T[m - 1] * T[m] + 1 * T[m - 2] * T[m] + 1 * T[m - 1] * T[m - 1]) % MOD
def check_restrictions(k, n):
return 1 <= k <= n <= 1_000_000_000
def main():
with open("p2sahIN.txt", "r") as f:
lines = f.readlines()
if len(lines) < 2:
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return
t = int(lines[0].strip())
if t not in (1, 2):
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return
try:
n, k = map(int, lines[1].strip().split())
except ValueError:
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return
if not check_restrictions(k, n):
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return
if t == 1:
k -= 1
sol = 1
p = 3
while k:
if k & 1:
sol = (sol * p) % MOD
p = (p * p) % MOD
k //= 2
else:
T = {0: 0, 1: 1, 2: 1, 3: 2}
S = {0, 1, 2, 3}
n = n + 2 - k
solve(n, T, S)
sol = T[n]
with open("p2sahOUT.txt", "w") as g:
g.write(f"{sol}\n")
if __name__ == "__main__":
main()