0

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;
}

1 件の回答 1

1

こちらの条件判定ですが、お札の組み合わせが問題文の条件を満たさない場合にもTRUEになってしまう可能性があります。

  if(count_yu + count_hi + count_no == n){
    flag = 1;
    break;
    }

以下の入力例での処理を追えばわかると思います。

1 11000
1
  • ありがとうございます!いわれた通りに試してみたら、問題点が見つかりました。
    – Yuto Ota
    Commented 2023年11月2日 2:07

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。