1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# 1. Wczytaj dane
h, w = map(int, input().split())
n = int(input())
d = list(map(int, input().split()))
d = sorted(d, reverse=True)

# 2. Zdefiniuj funkcję wytnij(h, w, d), która zwróci minimalną liczbę obrazów potrzebnych do pokrycia ściany
cache = {}
def wytnij(h, w):
    #print(h, w)
    if h < w:
        h, w = w, h
    if (h, w) in cache:
        return cache[(h, w)]
    
    if w == 0 or h == 0:
        return 0
    if len(d) == 0:
        return -1
    for x in d:
        if x <= h and x <= w:
            l = h // x
            k = w // x
            res = l * k
            r1_2 = wytnij(h, w % x)
            #print(r1_2)
            r1_1 = wytnij(h % x, k * x)
            #print(r1_1)

            r2_1 = wytnij(l * x, w % x)
            #print(r2_1)
            r2_2 = wytnij(h % x, w)
            #print(r2_2)

            if r1_1 == -1 or r1_2 == -1:
                r1 = -1
            else: r1 = r1_1 + r1_2

            if r2_1 == -1 or r2_2 == -1:
                r2 = -1
            else: r2 = r2_1 + r2_2

            if r1 >= 0 and r2 >= 0:
                res += min(r1, r2)
            elif r1 >= 0:
                res += r1
            elif r2 >= 0:
                res += r2
            else:
                res = -1
            cache[(h, w)] = res
            return res
    
    return -1 

# 3. Wypisz wynik
print(wytnij(h, w))