結果

問題 No.4 おもりと天秤
ユーザー shiratamashiratama
提出日時 2017-05-07 12:26:43
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 1,554 bytes
コンパイル時間 2,764 ms
コンパイル使用メモリ 60,252 KB
実行使用メモリ 4,504 KB
最終ジャッジ日時 2023-10-12 16:00:16
合計ジャッジ時間 3,598 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1 ms
4,368 KB
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 AC 1 ms
4,368 KB
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 AC 1 ms
4,372 KB
testcase_13 AC 1 ms
4,372 KB
testcase_14 AC 2 ms
4,368 KB
testcase_15 AC 1 ms
4,368 KB
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

auto has_next_combination(std::vector<int>& v) -> bool {
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == 0) {
			return true;
		}
	}
	return false;
}

auto next_combination(std::vector<int>& v) -> void {
	int first_one_i = -1;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == 1) {
			first_one_i = i;
			break;
		}
	}

	if (first_one_i == -1) {
		v[v.size() - 1] = 1;
	} else {
		int last_zero_i = -1;
		for (int i = first_one_i+1; i < v.size(); i++) {
			if (v[i] == 0) {
				last_zero_i = i;
			}
		}

		if (last_zero_i == -1 && first_one_i != 0) { 
			v[first_one_i - 1] = 1;
			for (int i = first_one_i; i < v.size(); i++) {
				v[i] = 0;
			}
	       	} else {
			v[last_zero_i] = 1;
			for (int i = last_zero_i+1; i < v.size(); i++) {
				v[i] = 0;
			}
		}
	}
}

auto main() -> int {
	int n_weights;
	std::cin >> n_weights;

	std::vector<int> weights(4);
	for (int i = 0; i < n_weights; i++) {
		std::cin >> weights[i];
	}

	bool found_combinations = false;
	std::vector<int> combinations(n_weights);

	next_combination(combinations);
	while (has_next_combination(combinations)) {
		int total_a = 0;
		int total_b = 0;
		for (int i = 0; i < n_weights; i++) {
			if (combinations[i] == 1) {
				total_a += weights[i];
			} else {
				total_b += weights[i];
			}
		}

		if (total_a == total_b) {
			found_combinations = true;
			break;
		}

		next_combination(combinations);
	}

	if (found_combinations) {
		std::cout << "possible" << std::endl;
	} else {
		std::cout << "impossible" << std::endl;
	}
}
0