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
58
59
60
61
62
63
64
65
66
67
68
69
70
// Autor: Nicolas Wochnik
#include <iostream>
#include <vector>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  long long height, width;
  std::cin >> height >> width;

  size_t blocks_size;
  std::cin >> blocks_size;

  // if (blocks_size > 30) {
  //   return 1;
  // }

  std::vector<long long> blocks(blocks_size);

  for (auto &block : blocks) {
    std::cin >> block;
  }

  std::vector<long long> needed_blocks(blocks.size());

  for (size_t i = 0; i < blocks.size(); ++i) {
    long long remaining = height;
    long long ptr = i;
    long long needed = 0;

    while (ptr >= 0) {
      long long amount = remaining / blocks[ptr];
      remaining -= blocks[ptr] * amount;
      needed += (blocks[i] / blocks[ptr]) * amount;
      ptr--;
    }

    if (remaining != 0) {
      std::cout << "-1\n";
      return 0;
    }

    needed_blocks[i] = needed;
  }

  // for (auto var : needed_blocks) {
  //   std::cout << var << " ";
  // }
  // std::cout << "\n";

  long long remaining = width;
  long long ptr = blocks.size() - 1;
  long long needed = 0;

  while (ptr >= 0) {
    long long amount = remaining / blocks[ptr];
    remaining -= blocks[ptr] * amount;
    needed += needed_blocks[ptr] * amount;
    ptr--;
  }

  if (remaining != 0) {
    std::cout << "-1\n";
    return 0;
  }

  std::cout << needed << "\n";
  return 0;
}