Editing 1135 - p2sah


Se dă o tablă de șah cu <code>n+1</code> linii (numerotate de sus în jos începând cu <code>1</code>) și <code>2n+1</code> coloane (numerotate de la stânga la dreapta începând cu <code>1</code>). Pe prima linie pătratul din mijloc conține <code>1</code> 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 <code>3</code> pătrate ale liniei anterioare cu care se învecinează (pe verticală și diagonală). De exemplu dacă <code>n=3</code> tabla are <code>4</code> linii, <code>7</code> coloane și următoarea configurație.

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

= Cerinţe =
1. Cunoscând <code>n</code> și <code>k</code>, să se calculeze cantitatea de fân de pe linia <code>k</code> a tablei.

2. Cunoscând <code>n</code> și <code>k</code>, să se calculeze câte grame de fân mănâncă un cal care pleacă de pe prima linie, de pe coloana <code>k</code>.

Întrucât aceste numere pot fi mari, se cere doar restul modulo <code>100003</code> ale acestor numere.

= Date de intrare =
Fișierul de intrare <code>p2sah.in</code> conține pe prima linie un număr <code>t</code> cu valoarea <code>1</code> sau <code>2</code>. Pe a doua linie a fișierului de intrare se găsesc două numere naturale <code>n</code> și <code>k</code> separate printr-un spațiu.

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. 

= Date de ieșire =
Dacă <code>t</code> din fișierul de intrare este <code>1</code> se va rezolva doar prima cerință.

În acest caz fișierul de ieșire <code>p2sahIN.txt.txt</code> va conține un singur număr reprezentând cantitatea totală de fân din toate pătratele situate pe tabla pe linia <code>k</code> (trebuie afișat restul modulo <code>100003</code>).

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 cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ k ≤ n ≤ 1.000.000.000</code>
* La cerința 1 pentru 80% dintre teste <code>k ≤ n ≤ 1.000.000</code>, iar pentru alte 20% din teste <code>k ≤ n ≤ 1.000.000.000</code>
* La cerința 2 pentru 30% dintre teste <code>k ≤ n ≤ 1000</code>, pentru alte 30% dintre teste <code>k ≤ n ≤ 1.000.000</code>, iar pentru restul de 40% dintre teste <code>k ≤ n ≤ 1.000.000.000</code>.
* 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 =
<code>p2sahIN.txt</code>
 1
 3 2
<code>p2sahOUT.txt</code>
 3

= Exemplul 2 =
<code>p2sahIN.txt</code>
 1
 3 4
<code>p2sahOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare == 
<syntaxhighlight lang="python" line="1">
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()

</syntaxhighlight>