全探索 atcoder

ABC085 C - お年玉

ABC085 C - お年玉
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://atcoder.jp/contests/abc085/tasks/abc085_c

2つの整数$N$と$Y$が与えられて、10000円、5000円、1000円のお札を合計$N$枚使って$Y$が作れるか.
また作れるならその組み合わせの1例をあげる問題.

解説

10000円札、5000円札、1000円札の枚数をそれぞれ$a$、$b$、$c$とおく.
2つの方程式が得られる.
また、お札の枚数なので(3)が得られる.

$$
\begin{cases}
a + b + c = N (1) \
10000a + 5000b + 1000c = Y (2) \
0 \leq a, b, c \leq N (3)
\end{cases}
$$

(1)より、$a$と$b$が決まれば$c$は一意に定まる.

$$
c = N - a - b
$$

このときこの$a$、$b$、$c$について(2) (3)を満たす組み合わせを初めて見つけた時、出力して終了.

計算量

$O(N^2)$

$a$と$b$の組み合わせの全列挙に2重ループ.

解答

 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
#define MAX_N 2001
#define MAX_Y 20000001

Int N, Y;

void input() {
  cin >> N >> Y;
}

void solve() {
  loop(a,0,N+1) {
    loop(b,0,N+1) {
      Int c = N - a - b;
      if (a + b > N || c < 0) continue;
      if (a * 10000 + b * 5000 + c * 1000 == Y) {
        cout << a << ' ' << b << ' ' << c << endl;
        return;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}