C++の学習をするためにAtCoderに登録し、Beginners Selectionの問題に取り組んでイたのですが9個目のOtoshidama(ABC085C)という問題がどうしてもクリアできません。
不正解と表示されるのはテストされる全24ケースのうち一つだけなのでアルゴリズムに間違いがあるのだと思います。
問題文は以下の通りです。
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計
で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。
(制約)
・1≤N≤2000
・1000≤Y≤2×10^7
・N は整数である。
・Y は 1000 の倍数である。
(入力)
N Y
自分の提出コードは以下の通りです。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, y;
cin >> n >> y;
int yukichi, higuchi, noguchi;
int temp_yu, temp_hi, count_yu = 0, count_hi = 0, count_no = 0;
int x, z, flag = 0;
temp_yu = y / 10000;
for(int i = 0; i <= temp_yu; i++){
x = y - 10000*i;
yukichi = i;
count_yu += i;
temp_hi = x / 5000;
for(int j = 0;j <= temp_hi; j++){
z = x - 5000*j;
higuchi = j;
count_hi += j;
noguchi = z / 1000;
count_no += noguchi;
if(count_yu + count_hi + count_no == n){
break;
}
count_hi = 0;
count_no = 0;
}
if(count_yu + count_hi + count_no == n){
flag = 1;
break;
}
count_yu = 0;
}
if(flag == 1){
cout << yukichi << " " << higuchi << " " << noguchi << endl;
}
else{
cout << "-1 -1 -1" << endl;
}
return 0;
}