Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
0
Indexable
Never
//////////////hugo ve nha
#include<iostream>
using namespace std;
int N;
int M[25][2];
int min_sum =1000000;
void BT(int k,int b1,int b2,int b3,int summ)
{
	if(summ > min_sum) { return; }
	if(k == N+1) {
		if(summ < min_sum) { min_sum = summ; }
		return;
	}
	//th1 :pass
	BT(k+1,b1,b2,b3,summ + M[k][1]);
	// th2 : hire
	BT(k+1,b1 + M[k][0],b2,b3,summ + 2*M[k][1]);
	/// th3 : battle
	if(b1 +b2 +b3 >= M[k][0]){
		if(b3 >= M[k][0]){
			BT(k+1, 0,b1,b2,summ);
		}
		else if(b2 +b3 >= M[k][0]){
			BT(k+1,0,b1,b2+b3 - M[k][0],summ);
		}
		else if(b1+b2+b3 >= M[k][0]){
			BT(k+1,0, b1+b2 +b3 -M[k][0],0, summ);
		}
	}
}

int main()
{
	int t;
	cin >> t;
	for(int stt=1; stt <=t; stt++)
	{
		cin >> N;
		for(int i=1; i<=N; i++)
		{
			cin >> M[i][0] >> M[i][1];
		}
		///////////////////////
		BT(1,0,0,0,0);
		cout << "#" << stt << " " << min_sum << endl;
		min_sum =1000000;
	}
}
////////////////////////////////hu go thi chay
#include<iostream>
using namespace std;
int M, D;
int phut , giay , nl;
int A[10][2];
int minn;
bool kt;
void BT(int k,int time, int sum_nl,int sum_kc)
{
	if(time > minn ) {return ;}
	if(sum_nl > M) { return;}
	if(k == 5)
	{
		//cout << k << " " << A[k][0] << endl;
		if(time + (D- sum_kc) * A[k][0]  < minn && sum_nl + (D- sum_kc) * A[k][1] <= M) {
			minn = time + (D- sum_kc) * A[k][0] ;
			kt =false;
		}
		return;
	}
	for(int i=0 ; i<= D - sum_kc; i++)
	{
		BT(k+1, time + i* A[k][0] , sum_nl + i* A[k][1],sum_kc +i );
	}
}
int main()
{
	//freopen("Text.txt","r",stdin);
	int t;
	cin >> t;
	for(int stt =1; stt <= t; stt ++)
	{
		cin >> M >> D;
		for(int i=1; i<=5; i++)
		{
			cin >> phut >> giay >> nl;
			A[i][0] = phut *60 + giay;
			A[i][1] = nl;
		}
		///////////////////
	minn =100000000;
	kt = true;
	BT(1,0,0,0);
	if( !kt){
	cout <<"Case #" << stt << endl <<  minn / 60 << " " << minn % 60 << endl;
	}
	else cout << "Case #" << stt << endl << "-1" << endl;

	}

}
///////////////////////