Zenit CK 2024/2025, 1a¶

https://zenit.ksp.sk/task/zenit24ck1a/

In [1]:
n = 3
mriezka = [[0 for _ in range(n)] for _ in range(n)]
In [32]:
def zobraz_mriezku(mriezka):
    print('---', sum(sum(riadok) for riadok in mriezka))
    for riadok in mriezka:
        print(*riadok)
        
zobraz_mriezku(mriezka)

--- 20
5 5
5 5
In [33]:
def hodnota(x, y):
    if 0 <= x < n and 0 <= y < n:
        return mriezka[x][y]
    return None

def cisla(indexy):
    return [ hodnota(x, y) for x, y in indexy]

def over(r, s):
    #overi ci hodnota [r][s] ma za susedov kazde mensie cislo
    if r < 0:
        return True
    susedia = cisla([[r-1, s], [r+1, s], [r, s-1], [r, s+1]])
    for cislo in range(1, mriezka[r][s]):
        if not cislo in susedia:
            return False
    return True

def gen(riadok, stlpec):
    if riadok == n:
        for s in range(n):
            if not over(riadok-1, s):
                return
        zobraz_mriezku(mriezka)
        return
    #overime ci policko riadok nad je ok            
    for hodnota in range(1, 6):            
        mriezka[riadok][stlpec] = hodnota
        if over(riadok-1, stlpec):
            if stlpec < n-1:
                gen(riadok, stlpec+1)
            else:
                gen(riadok+1, 0)
    
n = 2    
mriezka = [[0 for _ in range(n)] for _ in range(n)]
gen(0, 0)

--- 4
1 1
1 1
--- 5
1 1
1 2
--- 5
1 1
2 1
--- 6
1 1
2 2
--- 7
1 1
2 3
--- 7
1 1
3 2
--- 5
1 2
1 1
--- 6
1 2
1 2
--- 7
1 2
1 3
--- 6
1 2
2 1
--- 7
1 3
1 2
--- 5
2 1
1 1
--- 6
2 1
1 2
--- 6
2 1
2 1
--- 7
2 1
3 1
--- 6
2 2
1 1
--- 7
2 3
1 1
--- 7
3 1
2 1
--- 7
3 2
1 1
In [23]:
mriezka
Out[23]:
[[1, 1, 1], [1, 4, 3], [3, 1, 1]]
In [24]:
r, s = 0, 0
set(cisla([[r-1, s], [r+1, s], [r, s-1], [r, s+1]]))
Out[24]:
{1, None}
In [25]:
over(1,1)
Out[25]:
False
In [26]:
mriezka[0][1] = 2
In [28]:
zobraz_mriezku(mriezka)

---
1 2 1
1 4 3
3 1 1
In [29]:
over(1,1)
Out[29]:
True
In [50]:
%%time
def hodnota(x, y):
    if 0 <= x < n and 0 <= y < n:
        return mriezka[x][y]
    return None

def cisla(indexy):
    return [ hodnota(x, y) for x, y in indexy]

def over(r, s):
    #overi ci hodnota [r][s] ma za susedov kazde mensie cislo
    susedia = cisla([[r-1, s], [r+1, s], [r, s-1], [r, s+1]])
    for cislo in range(1, mriezka[r][s]):
        if not cislo in susedia:
            return False
    return True

def zobraz_mriezku(mriezka):
    global najviac
    suma = sum(sum(riadok) for riadok in mriezka)
    if suma > najviac:
        print('---', suma)
        for riadok in mriezka:
            print(*riadok)
        najviac = suma    
        
def gen(riadok, stlpec):
    if riadok == n:
        for s in range(n):
            if not over(riadok-1, s):
                return
        zobraz_mriezku(mriezka)
        return
    #overime ci policko riadok nad je ok            
    for hodnota in range(5, 0, -1):            
        mriezka[riadok][stlpec] = hodnota
        if over(riadok-1, stlpec):
            if stlpec < n-1:
                gen(riadok, stlpec+1)
            else:
                gen(riadok+1, 0)
    
n = 3
najviac = 0
mriezka = [[0 for _ in range(n)] for _ in range(n)]
gen(0, 0)

--- 19
3 2 3
1 1 1
3 2 3
--- 20
2 4 1
1 3 2
2 4 1
CPU times: total: 188 ms
Wall time: 177 ms
In [42]:
5**(25) //10**10/3600
Out[42]:
8278.422777777778
In [46]:
5**(2*8) //10**10 [15s pre n = 8, ak kombinacie dvoch riadkov]
Out[46]:
15
In [49]:
5**8
Out[49]:
390625

Nájdené súčty:

3

--- 20
2 4 1
1 3 2
2 4 1

5

--- 60
3 2 4 3 2
1 1 1 1 1
3 5 2 5 3
2 4 1 4 2
1 3 2 3 1

8

--- 151
3 2 4 3 2 4 3 2
1 1 1 1 1 1 1 1
4 3 5 4 3 5 4 3
2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1
4 3 5 2 5 3 5 2
2 2 4 1 4 2 4 1
1 1 3 2 3 1 3 2
In [ ]: