Untitled
unknown
plain_text
2 years ago
2.4 kB
7
Indexable
#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; }
Editor is loading...