結果

問題 No.4 おもりと天秤
コンテスト
ユーザー ramia777
提出日時 2022-05-20 22:01:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 2,934 bytes
コンパイル時間 1,082 ms
コンパイル使用メモリ 91,184 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-09-20 08:09:12
合計ジャッジ時間 1,999 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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>
#include <cstring>

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


int memo[20000][200];
int N;
int W[100];

int _debug_flag = 0;

int possible = 0;
int _target_weight = 0;

//
// 半分の重さになるおもりの組み合わせがあるかを調べる
// target_weight : おもり
// n：おもりのインデックス


int  func(int n,  int target_weight)
{
	//cout << "n=" << n << ",target_weight=" << target_weight << endl;

	if (possible)
		return 1;

	if (n >= N)
		return 0;

	if (target_weight > _target_weight)
		return 0;

	if (target_weight == _target_weight)
	{
		possible = 1;
		//cout << "possible:n=" << n << ",target_weight=" << _target_weight << endl;
		return 1;
	}

	//同じ引数で関数を通るときは答えは同じなので前回の答えを返す
	if (-1 != memo[target_weight][n])
	{
		//cout << "memo:n=" << n << ",target_weight=" << target_weight << endl;
		//cout << "memo ret=" << memo[target_weight][n]<< endl;
		return memo[target_weight][n];
	}

	_debug_flag |= (1 << n);

	//最初は n番目のおもりを置いてみる
	if (func(n + 1, target_weight + W[n]))
	{
		//cout << "possible:n=" << n << ",target_weight=" << _target_weight << endl;

		memo[target_weight][n] = 1;
		return 1;
	}
	
	_debug_flag &= ~(1 << n);

	// 上手くいかなかったら n番目のおもりを置かない場合を試してみる
	if (func(n + 1, target_weight))
	{
		//cout << "possible:n=" << n << ",target_weight=" << _target_weight << endl;

		memo[target_weight][n] = 1;
		return 1 ;
	}

	

	//n番目の重りを置いてもおかなくてもだめだった
	memo[target_weight][n] = 0;

	return 0;
}

//降順
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;

	//cout << _target_weight << endl;

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

	memset(memo,-1, 20000*200);

	//半分の重さになるかを深さ（再帰）探索
	if(func(0, 0))
	{

		/*
		for (int i=0;i<N;i++)
		{
			if (_debug_flag & (1 << i))
				cout << W[i] << ",";
		}
		cout << endl;
		*/

		cout << "possible" << endl;
	}
	else
	{
		cout << "impossible" << endl;
	}

	//getchar();


	return 0;
}
0