A: Sudoku

Tehtävä

Yksi tapa ratkaista tehtävä on koodata yleinen sudokun ratkaisija ja soveltaa sitä tehtävään. Tämä on kuitenkin tarpeettoman monimutkainen ratkaisu.

Keskeinen havainto on, että mikä tahansa täytetty sudokuruudukko kelpaa ratkaisun pohjaksi. Annettu ensimmäinen rivi antaa vain numeroille uuden järjestyksen.

Seuraavassa koodissa ratkaisun pohjana on tehtävänannossa annettu sudokuruudukko. Koodi korvaa ensin numerot 1 \ldots 9 merkeillä A \ldots I ja sitten merkit annetun ensimmäisen rivin mukaisesti.

s = """137692548
648513729
952478613
871349256
295867134
364251897
589136472
423785961
716924385"""
t = raw_input()
for i in range(9):
    s = s.replace(s[i],chr(65+i))
for i in range(9):
    s = s.replace(chr(65+i),t[i])
print s

B: Kertotaulu

Tehtävä

Osoittautuu, että lukujen summa alueella on s(y_1,y_2) \cdot s(x_1,x_2), missä s(a,b)=a+(a+1)+\cdots+b. Niinpä riittää laskea nopeasti funktion s arvo, mikä onnistuu summan laskukaavalla.

Seuraava koodi ratkaisee tehtävän:

def s(a,b):
    return b*(b+1)/2-a*(a-1)/2

y1, x1, y2, x2 = [int(x) for x in raw_input().split(" ")]
print (s(y1,y2)*s(x1,x2))%1000000007

C: Pussit

Tehtävä

Kun Uolevi jakaa pallot mahdollisimman tasaisesti pusseihin, suurin määrä palloja, joka hänen täytyy nostaa jostakin pussista, on z=\lfloor \frac{k-1}{n} \rfloor + 1.

Uolevi osoittaa aina pussia k kertaa niin, että hän saa pallon. Lisäksi Uolevi saattaa osoittaa pussia niin, että hän ei saa palloa.

Huonoin tapaus on, että Uolevi osoittaa ensin kaikkia pusseja, joissa on alle z palloa. Tällöin hän osoittaa n-\lfloor m/z \rfloor kertaa pussia niin, että hän ei saa palloa.

Jos \lfloor m/z \rfloor \ge n, jokaisessa pussissa on ainakin z palloa, eikä Uolevi koskaan osoita pussia saamatta palloa.

Seuraava koodi toteuttaa yllä olevan idean:

def f(n,m,k):
    z = (k-1)/n+1
    return k+max(n-m/z,0)

t = int(input())
for i in range(t):
        n, m, k = [int(x) for x in raw_input().split(" ")]
        print f(n,m,k)