結果

問題 No.10 ＋か×か
コンテスト
ユーザー Onju
提出日時 2015-02-12 02:58:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,522 bytes
コンパイル時間 497 ms
コンパイル使用メモリ 59,912 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-14 15:26:56
合計ジャッジ時間 1,076 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <bitset>
#include <algorithm>
#include <climits>
#define N_MAX 50
#define T_MAX 100000
#define setBit(x,b) ((x)|((ULL)1<<(b)))
typedef unsigned long long ULL;
using namespace std;

int N, T, A[N_MAX];
int Amin[N_MAX], Amax[N_MAX];

ULL calc(int t, int n, ULL op)
{
	static ULL ans = ULLONG_MAX;

	if (n < 0 && t == 0)
	{
		if (op < ans)
			ans = op;
		return 0;
	}
	if (n < 0 || t <= 0)
		return 0;

	if (t < Amin[n] || t > Amax[n])
		return 0;

	for (; n > 0 && (t%A[n]); --n)
		t -= A[n];

	//1の連続だけは単独で計算しないと全通り探索される
	if (A[n] == 1 )
	{
		int count = 1;
		for (int i = n - 1; i > 0 && A[i] == 1; --i)
			++count;

		for (int i = count; i >= 0; --i)
		{
			calc(t - i, n - count, op);
			op = setBit(op, N - n + (count - i));
		}

		return ans;
	}

	calc(t - A[n], n - 1, op);
	if (n > 0)
		calc(t / A[n], n - 1, setBit(op, N - n));

	return ans;
}

ULL calc()
{
	Amin[0] = A[0];
	Amax[0] = A[0];
	for (int i = 1; i < N; ++i)
	{
		if (A[i] == 1 || Amin[i - 1] == 1)
			Amin[i] = Amin[i - 1] * A[i];
		else
			Amin[i] = Amin[i - 1] + A[i];

		if (A[i] == 1 || Amax[i - 1] == 1)
			Amax[i] = Amax[i - 1] + A[i];
		else
			Amax[i] = Amax[i - 1] * A[i];
		if (Amax[i] > T_MAX)
			Amax[i] = T_MAX;
	}

	return calc(T, N - 1, 0);
}

int main()
{
	const char* op = "+*";

	cin >> N >> T;
	for (int i = 0; i < N; ++i)
		cin >> A[i];

	//計算
	bitset<64> ans(calc());
	for (int i = N - 1; i >= 1; --i)
		cout << op[ans[i]];
	cout << endl;

	return 0;
}
0