Untitled

#include<iostream>

using namespace std;

struct typeRun{
	int phut,giay,nangLuongTieuHao;
};

typeRun kieuChay[10];
int M,phut,giay,D,timeMinMinutes,timeMinSeconds;
int mmin;

void init(){
	cin>>M>>D;
	mmin=999999;
	for (int i = 1; i <= 5; i++)
	{
		cin>>kieuChay[i].phut>>kieuChay[i].giay>>kieuChay[i].nangLuongTieuHao;
	}
}

void timeSetUp(int phut,int giay){
	int temp = giay/60;
	phut=phut+temp;
	giay=giay%60;
}

int min(int a,int b){
	if(a<b) return a;
	return b;
}

void backTracking(int d,int index, int time,int energy){
	if(time >= mmin || energy > M) return;
	if(index == 5){
		energy += d*(kieuChay[index].nangLuongTieuHao);
		time += d*(kieuChay[index].phut*60 + kieuChay[index].giay);
		if(energy <= M) mmin = min(mmin,time);
		return;
	}
	for (int i = 0; i <= D; i++)
	{
		int tg = i*(kieuChay[index].giay + kieuChay[index].phut*60);
		backTracking( d-i , index+1 , time+tg , energy + i*kieuChay[index].nangLuongTieuHao);
	}

}

void solve(){
	int nangLuongTb = M/D;
	bool ok = true;
	for (int i = 1; i <= 5; i++)
	{
		if(nangLuongTb < kieuChay[i].nangLuongTieuHao){
			ok=false;
		}
		else{
			ok=true;
			break;
		}
	}
	if(ok==true){
		backTracking(D,1,0,0);
		cout<<mmin/60<<" "<<mmin%60<<endl;
	}
	else{
		cout<<-1<<endl;
	}

}

int main(){
	freopen("input.txt","r",stdin);
	int t;cin>>t;
	for (int i = 1; i <= t; i++)
	{
		init();
		cout<<"Case #"<<i<<endl;
		solve();
	}

	return 0;
}
code 2
#include<iostream>
using namespace std;
int M,D,k[5][3],b[5][2];
int tong;
//kq- tgian, step da chay, k kieu chay
void backtrack(int k,int kq,int nangluong, int step){
	if(k==4){
		if(tong>kq+(D-step)*b[4][0]&&nangluong+(D-step)*b[4][1]<=M){
			tong=kq+(D-step)*b[4][0];
		}
		return;
	}
	if(kq>=tong||nangluong>M) return; //kq : tgian 
	for(int i=0;i<=D-step;i++){ //0-qd chua chay
		backtrack(k+1,kq+i*b[k][0],nangluong+i*b[k][1],step+i);
	}
}
int main(){
	//freopen("Text.txt","r",stdin);
	int T;
	cin>>T;
	for (int tc = 1; tc <= T; tc++)
	{
		tong=999999999;
		cin>>M>>D;
		for (int i = 0; i < 5; i++)
		{
			cin>>k[i][0]>>k[i][1]>>k[i][2];
			b[i][0]=k[i][0]*60+k[i][1];// so giay
			b[i][1]=k[i][2];// nang luong
		}
		backtrack(0,0,0,0);
		int h=tong/60;
		int g=tong%60;
		cout<<"Case #"<<tc<<endl;
		if(tong==999999999){
			cout<<"-1"<<endl;
		}
		else{
			cout<<h<<" "<<g<<endl;
		}
	}
	return 0;
}