結果

問題 No.4 おもりと天秤
コンテスト
ユーザー shiratama
提出日時 2017-05-07 12:26:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 1,554 bytes
コンパイル時間 501 ms
コンパイル使用メモリ 59,508 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-14 14:40:10
合計ジャッジ時間 3,449 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 RE * 16
権限があれば一括ダウンロードができます

ソースコード

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