Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
1.3 kB
4
Indexable
Never
#include <iostream>
#include <stdio.h>
using namespace std;
int T, n;
int a[200][2], dam[200][2];
int kq = 0;

void dequy(int gg, int count = 0) {
	if(gg == n) {
		if(kq > count) kq = count;
		return;
	}
	if(count > kq) return;

	//pass
	dequy(gg+1, count + a[gg][1]);

	//buy
	dam[gg][0] = a[gg][0];
	dequy(gg+1, count + 2*a[gg][1]);
	dam[gg][0] = 0;

	//attack
	int linh = 0;
	int thua = a[gg][0];
	for(int i = 0; i < n; i++) {
		if(dam[i][1] < 3) linh += dam[i][0];
	}
	if(linh >= thua) {
		int sav[200][2];
		for(int i = 0; i < n; i++) {
			sav[i][0] = dam[i][0];
			sav[i][1] = dam[i][1];
		}
		for(int i = 0; i < n; i++) {
			if(dam[i][1] < 3 && dam[i][0] > 0) {
				if(dam[i][0] - thua <= 0) {
					thua -= dam[i][0];
					dam[i][0] = 0;
					dam[i][1] ++;
				}
				else {
					dam[i][0] = dam[i][0] - thua;
					thua = 0;
					dam[i][1] ++;
				}
			}
		}
		dequy(gg+1, count);
		for(int i = 0; i < n; i++) {
			dam[i][0] = sav[i][0];
			dam[i][1] = sav[i][1];
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	cin >> T;
	for (int stt = 1; stt <= T; stt++) {  
		cin >> n;
		for(int i = 0; i < n; i ++) {
			cin >> a[i][0] >> a[i][1];
			dam[i][0] = 0; dam[i][1] = 0;
		}
		kq = 100000;
		dequy(0);
		cout << "#" << stt << " " << kq << endl;
	}
	return 0;
}