Javaを用いてのAtCoder Beginners Selection 9問目:Otoshidama

Question

前提

現在、Javaを用いてAtCoderのAtCoder Beginners Selectionを進めております。
その9問目、Otoshidamaでテストケースa03, b10, b13, b14, b21, b22で
WAとなり不合格になってしまいます。
サンプルでも一つエラーが出ておりますが、ローカルで実行した場合問題なく出力されているように見えます。

該当のソースコード

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		//お札の枚数N、合計金額Yを入力
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Y = sc.nextInt();

		boolean check = false;

		//ラベル付きbreakで一つでも組み合わせが見つかったら全てのforを抜ける
		outerLabel: for (int x = 0; x <= N; x++) {                  //xは10000円札の枚数
			for (int y = 0; x + y <= N; y++) { 　　　　　　　　       //yは5000円札の枚数
				for (int z = 0; x + y + z <= N; z++) {              //zは1000円札の枚数
					if (z * 1000 + y * 5000 + x * 10000 == Y) {
						System.out.print(x + " " + y + " " + z);
						check = true;
						break outerLabel;
					}
				}
			}
		}

		if (check == false) {
			System.out.print("-1 -1 -1");
		}
	}

}

試したこと

例外時の"-1 -1 -1"の出力方法に問題があるのではと思い、

for (int i = 0; i < 3; i++) {
 System.out.print(-1);
}

などに変えてみたりしましたが結果は変わりませんでした。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

1<N<2000なので三重ループさせると最大80億周近くなので死にますね。

そもそもZはループさせる必要がないと思います。札の合計がN枚なのが確定なので、

z=N-(x+y)

で必然的にZが求まります。この時の合計金額がY円かどうかを判定すればいいだけなので、模範解答としては2重ループになるのではないでしょうか。

また、コードを見たところ、金額しか判定していないので仮にN=5,Y=16000と入力した場合1 1 1と返ってきてしまい、正しい答えと言えません。ここが不正解とされた原因だと思います。（って追記してたらZuishinさんが解説してくれてたわ）

Answer 2

解決後ソースコード

効率的なロジックではないかもしれませんが、一応
無事通過したソースコードを載せておきます。

ご回答いただいた皆さん、ありがとうございました。

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		//お札の枚数N、合計金額Yを入力
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Y = sc.nextInt();

		boolean check = false;

		//ラベル付きbreakで一つでも組み合わせが見つかったら全てのforを抜ける
		outerLabel: for (int x = 0; x <= N; x++) { //xは10000円札の枚数
			for (int y = 0; x + y <= N; y++) { //yは5000円札の枚数
				int z = N - (x + y); //zは1000円札の枚数

				if (z * 1000 + y * 5000 + x * 10000 == Y) {
					System.out.print(x + " " + y + " " + z);
					check = true;
					break outerLabel;

				}
			}
		}

		if (check == false) {
			System.out.print("-1 -1 -1");
		}
	}

}

Comments

[YT0014]

Zは、N - (x + y)で算出しているので、x + y + z == Nは、常にtrueになるので、三重ループでないのなら、不要かと。

[pig_vba]

不要ですね。まぁあっても誤作動が起こるようなものではないですが

[chotto]

本当ですね。修正しました。
このようなことにぱっと気付けるようになりたいです。

[jimbe]

見つかったらループを抜ける必要も無く表示して exit してしまえば、 check 変数も outerLabel も最後の if 文も無くなり、もちょっと簡単(短く)なりますねぇ。

Answer 3

三重ループでは LTE になるというのは pig_vba さんのおっしゃる通りです。

しかし、なぜ LTE ではなく WA なのかというところに回答すると、お札の枚数が N 枚という制約を満たしていないからです。

N 枚より少なくてもループを終了してしまうためにそのような結果になります。

Comments

[chotto]

条件にx, y, zの合計がNであるという条件を&&で追加し、
無事通過することができました。
ご回答いただきありがとうございました！