結果

問題 No.4 おもりと天秤
ユーザー ramia777
提出日時 2022-05-19 09:33:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,917 bytes
コンパイル時間 622 ms
コンパイル使用メモリ 92,268 KB
実行使用メモリ 10,144 KB
最終ジャッジ日時 2024-09-17 15:02:29
合計ジャッジ時間 7,465 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

//Yukicoder No.4
//重りと天秤


//#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <vector>
#include <list>//list
#include <set> //tree
#include <map> //連想配列
#include <unordered_set> //hash
#include <unordered_map> //hash
#include <algorithm>
#include <iomanip>
#include <string>
#include <stdlib.h>


using namespace std;
typedef unsigned long long ULL;
typedef signed long long SLL;
typedef unsigned int UINT;



int N;
int W[100];


int possible = 0;
int _target_weight = 0;

//
// 半分の重さになるおもりの組み合わせがあるかを調べる
//
// n：おもりのインデックス
// total_weight:載せた合計の重さ　	　
void func(int n, int total_weight)
{

	if (possible)
		return;

	if (n >= N)
		return;

	if (_target_weight < total_weight)
		return;

	if (_target_weight == total_weight)
	{
		possible = 1;
		return;
	}


	func(n + 1, total_weight + W[n]); //先に  n番目を載せた場合を調べる(探索枝を短くするため）
	func(n + 1, total_weight);        //後から n番目を載せなかった場合を調べる

	return;
}

//降順
int compare(const int * a, const int *b)
{
	if (*a < *b)
		return (1);
	else if (*a > *b)
		return (-1);
	return (0);
}

int main()
{
	int total = 0;

	cin >> N;

	for (int i=0;i<N;i++)
	{
		cin >> W[i];
		total += W[i];
	}


	if (total % 2)
	{
		//そもそも２分割できない合計だったらすぐさまimpossibleを返す
		cout << "impossible" << endl;
		return 0;
	}


	// 半分に割る
	_target_weight = total >> 1;

	//降順のソート
	qsort(W, N, sizeof(int), (int(*)(const void*, const void*))compare);

	//半分の重さになるかを深さ（再帰）探索。重たいものから載せる(探索枝を短くするため）
	func(0,0);

	
	if (possible == 1)
	{
		cout << "possible" << endl;
	}
	else
	{
		cout << "impossible" << endl;
	}

	//getchar();


	return 0;
}
0