Basics 0/97

Complete search: enumerating candidate solutions · 2 of 3

Brute force

Shrink a search written as nested loops by computing one choice from the others, or by looping over the possible answers instead of the input.

1,382 words · 7 min read

Part 1 of 4 One loop per choice

One loop for each choice

When a candidate is made of a few separate choices, a complete search has one loop for each choice. Two loops list every pair, and three loops list every triple. Each added loop multiplies the number of candidates, so the first thing to settle about a brute-force program is which choices need a loop. Here is a problem with three choices.

Difficulty tier:Easy

An envelope holds NN bills. Each bill is worth 10000, 5000 or 1000 yen, and together they are worth YY yen. Find how many bills of each kind the envelope could hold.

The input is one line with NN and YY. Print three counts, of 10000-yen, 5000-yen and 1000-yen bills, that make exactly NN bills worth YY yen; any valid answer is accepted. If no counts work, print -1 -1 -1.

Constraints

  • 1≤N≤20001 \le N \le 2000
  • 1000≤Y≤2×1071000 \le Y \le 2 \times 10^7
  • YY is a multiple of 1000

Sample 1 · Input

9 45000

Output

4 0 5

Sample 2 · Input

20 196000

Output

-1 -1 -1

Sample 3 · Input

1000 1234000

Output

14 27 959

Sample 4 · Input

2000 20000000

Output

2000 0 0

In the first sample, 9 bills are worth 45000 yen. Four 10000-yen bills and five 1000-yen bills are one answer, since 40000+5000=4500040000 + 5000 = 45000. Nine 5000-yen bills are another, and the judge accepts either.

A candidate is a triple of counts (a,b,c)(a, b, c): aa bills of 10000 yen, bb of 5000 and cc of 1000. The direct search runs three nested loops, each from 0 to NN, and checks two conditions for every triple: the counts add up to NN, and the values add up to YY. For the largest input, N=2000N = 2000, the loops visit

2,0013=8,012,006,001≈8×109 triples2{,}001^3 = 8{,}012{,}006{,}001 \approx 8 \times 10^9 \text{ triples}

Even at 10810^8 simple operations a second that is about 80 seconds, and AtCoder gives this problem 2 seconds.