Untitled
unknown
plain_text
2 years ago
10 kB
11
Indexable
#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;
}
}
////////////////////////////////hugo
//#include<iostream>
//using namespace std;
//int M,N,sr,sc;
//int C,H,T;
//int Chay[200][2];
//int Ho[200][2];
//int Thoat[200][2];
//int Arr[20][20];
//int Arr_thoat[20][20];
//int diamond[20][20];
//int time_chay[20][20];
//bool visit[20][20];
//int f=-1,r=-1;
//int Qx[100000];
//int Qy[100000];
//int max_kt=0;
//int dx[4] ={0,0,1,-1};
//int dy[4]={-1,1,0,0};
//bool dich = false;
//void push(int x,int y)
// {
// f++;
// Qx[f] =x;
// Qy[f]=y;
// }
//void pop(int &x,int &y)
// {
// r++;
// x= Qx[r];
// y= Qy[r];
// }
//void bfs(int x,int y)
// {
// f=r=-1;
// for(int i=1; i<=C; i++)
// {
// push(Chay[i][0], Chay[i][1]);
// time_chay[Chay[i][0]][Chay[i][1]] =0;
// }
// while(f != r)
// {
// pop(x,y);
// for(int i=0; i<4; i++)
// {
// int xx= x+dx[i];
// int yy =y+dy[i];
// if(xx>=1 && xx <=M && yy >=1 && yy <=N)
// {
// if(time_chay[xx][yy] >time_chay[x][y] +1 && Arr[xx][yy] !=2){
// push(xx,yy);
// time_chay[xx][yy] = time_chay[x][y] +1;
// }
// }
// }
// }
// }
//void BT(int sr,int sc,int time ,int summ)
// {
// //cout << summ << endl;
// if(Arr_thoat[sr][sc] == 3){
// if(summ > max_kt) { max_kt = summ; }
// dich= true;
// //Arr_thoat[sr][sc] =0;
// //return ;
// }
// for(int i=0; i<4; i++)
// {
// int xx= sr+dx[i];
// int yy =sc+dy[i];
// if((xx<1 && xx >M && yy <1 && yy >N) || visit[xx][yy]){
// continue;
// }
// else {
// int next_time;
// if(Arr[xx][yy] == 2) { next_time =time +2;}
// else { next_time = time +1;}
// if(next_time < time_chay[xx][yy] ){
// visit[xx][yy] =true;
// BT(xx,yy,next_time,summ + diamond[xx][yy]);
// visit[xx][yy] =false;
// }
// }
// }
// }
//int main()
// {
// int t;
// cin >> t;
// for(int stt=1; stt <=t; stt++)
// {
// cin >> M >> N >> sr >> sc;
// for(int i=1; i<=M; i++)
// {
// for(int j=1; j<=N; j++)
// {
// visit[i][j] = Arr_thoat[i][j] = Arr[i][j]=0;
// }
// }
// visit[sr][sc] = true;
// cin >> C;
// for(int i=1; i<=C; i++)
// {
// cin >> Chay[i][0] >> Chay[i][1];
// }
// cin >> H;
// for(int i=1; i<=H; i++)
// {
// cin >> Ho[i][0] >> Ho[i][1];
// Arr[Ho[i][0]][Ho[i][1]] =2;
// }
// cin >> T;
// for(int i=1; i<=T; i++)
// {
// cin >> Thoat[i][0] >> Thoat[i][1];
// Arr_thoat[Thoat[i][0]][Thoat[i][1]] =3;
// }
// for(int i=1; i<=M; i++)
// {
// for(int j=1; j<=N; j++)
// {
// cin >> diamond[i][j];
// time_chay[i][j] = 1000;
// }
// }
// ////////////////////////////////////////////////
// bfs(0,0);
// BT(sr,sc,0,diamond[sr][sc]);
// if(dich == false){
// cout << "Case #" << stt << endl << "-1" << endl;
// }
// else { cout << "Case #" << stt << endl << max_kt << endl;}
// max_kt =0;
// dich = false;
// ///////
// }
// }
///////////////////////////lk
#include<iostream>
using namespace std;
int N,M;
int market[30];
int Mang[35][1000];
int price_combo[35];
int tb_combo[35];
int tbmt[20];
int sotb_canmua;
int combo_canmua[20];
int price=0;
int minn= 10000000;
void buy(int k)
{
price += price_combo[k];
for(int i=1; i<= tb_combo[k]; i++){
tbmt[Mang[k][i]] ++;
}
}
void unbuy(int k)
{
price -= price_combo[k];
for(int i=1; i<= tb_combo[k]; i++){
tbmt[Mang[k][i]] --;
}
}
void BT(int k)
{
if(price >= minn) { return; }
if(k==M+1 ) {
int price_market=0;
for(int i=1; i<=sotb_canmua; i++)
{
if(tbmt[combo_canmua[i]] ==0){
price_market += market[combo_canmua[i]];
cout << price << " " << price_market << " " <<minn << endl;
if(price_market + price >= minn) { break;}
}
}
if(price_market +price < minn) { minn = price_market +price ;}
return;
}
for(int i=0; i<2; i++)
{
if(i==0) { BT(k+1); }
if(i==1){
buy(k);
BT(k+1);
unbuy(k);
}
}
}
int main()
{
int t;
cin >> t;
for(int stt=1; stt <=t; stt++)
{
cin >> N;
for(int i=1; i<=N; i++)
{
cin >> market[i];
tbmt[i] =0;
}
cin >> M;
for(int i=1; i<=M; i++)
{
cin >> price_combo[i] >> tb_combo[i];
for(int j=1; j<= tb_combo[i]; j++)
{
cin >> Mang[i][j];
}
}
cin >> sotb_canmua;
for(int i=1; i<= sotb_canmua; i++)
{
cin >> combo_canmua[i];
}
//////////////////////////////////////////
BT(1);
//cout << price << endl;//
cout << "#" << stt << " " << minn << endl;
price =0;
minn =10000000;
}
}
////////////////sum
#include<iostream>
using namespace std;
int S,N;
int M[100];
int save[100][100];
int lengt[100];
int summ=0;
int count_ =0;
int index_y=0;
int index_x=1;
void BT(int k)
{
if(summ == S)
{
lengt[index_x] = index_y;
count_ ++;
cout << k << endl;
for(int i=1; i<=index_y; i++)
{
cout << save[index_x][i] << " ";
}
cout << endl;
index_x ++;
return;
}
if(summ > S || k>N) { return; }
for(int i=0; i<2; i++)
{
if(i ==0){
BT(k+1);
}
if(i ==1){
summ += M[k];
index_y ++;
save[index_x][index_y] = M[k];
BT(k+1);
index_y --;
summ -= M[k];
}
}
}
bool kt_diffient(int x1, int x2)
{
if(lengt[x1] != lengt[x2]) { return true;}
else{
for(int i=1; i<=lengt[x1]; i++)
{
if(save[x1][i] != save[x2][i]) return true;
}
}
return false;
}
int main()
{
int t;
cin >> t;
for(int stt=1; stt <=t; stt++)
{
cin >> S >> N;
for(int i=1; i<=N ; i++)
{
cin >> M[i];
}
/*for(int i=1; i<=N; i++)
{
for(int j=i+1; j<=N; j++)
{
if(M[j] > M[i])
swap(M[i], M[j]);
}
}*/
/////////////////////////////
BT(1);
/*for(int i=1; i< index_x; i++)
{
if(!kt_diffient(i,i+1)){
count_ --;
}
}*/
/*for(int i=1; i<= index_x; i++)
{
cout << lengt[i] << endl;
for(int j=1; j<= lengt[i]; j ++)
{
cout << save[i][j] << " ";
}
cout << endl;
}*/
cout << "#" << stt << " " << count_ << endl;
summ =count_ = index_x =index_y =0;
}
}
//////////////////////////////////////////////////////
#include <iostream>
#define MAXN 16
#define MAX_QUEUE 10000
using namespace std;
int hugo[MAXN][MAXN];
int diamond[MAXN][MAXN];
int fireCnt, diamondCnt, exitCnt, lakeCnt;
int fire[MAXN][MAXN], lake[MAXN][MAXN], exitM[MAXN][MAXN];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int N, M, xStart, yStart;
int ans;
int front, rear;
int Q[MAX_QUEUE];
bool check;
clock_t endT, startT;
void push(int x, int y)
{
rear++;
Q[rear] = x;
rear++;
Q[rear] = y;
}
int pop()
{
front++;
return Q[front];
}
void resetQ()
{
front = -1;
rear = -1;
}
void input()
{
cin >> N >> M >> xStart >> yStart;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
hugo[i][j] = 0;
diamond[i][j] = 0;
fire[i][j] = 0;
exitM[i][j] = 0;
lake[i][j] = 0;
}
}
int a, b;
cin >> fireCnt;
for(int i = 0; i < fireCnt; i++){
cin >> a >> b;
fire[a][b] = 1; // Lua
}
cin >> lakeCnt;
for(int i= 0; i < lakeCnt; i++){
cin >> a >> b;
lake[a][b] = 1; // Ho
}
cin >> exitCnt;
for(int i = 0; i < exitCnt; i++){
cin >> a >> b;
exitM[a][b] = 1; // Loi ra
}
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
cin >> diamond[i][j];
}
}
}
void BFS_fire()
{
resetQ();
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
if(fire[i][j] == 1){
push(i,j);
}
}
}
while(front != rear){
int x = pop();
int y = pop();
for(int i = 0; i < 4; i++){
int xx = x + dx[i];
int yy = y + dy[i];
if(xx < 1 || yy < 1 || xx > N || yy > M)
continue;
if((fire[xx][yy] == 0 || fire[xx][yy] > fire[x][y] + 1) && lake[xx][yy] != 1){ // cap nhat lai lua
fire[xx][yy] = fire[x][y] + 1;
push(xx, yy);
}
}
}
}
void hugo_backTrack(int xCurrent, int yCurrent, int curDiamond)
{
if(exitM[xCurrent][yCurrent] == 1){
if(ans < curDiamond){
ans = curDiamond;
check = true;
}
//return; // tim den loi thoai van thu di tiep
}
for(int i = 0; i < 4; i++){
int xx = xCurrent + dx[i];
int yy = yCurrent + dy[i];
if(xx < 1 || yy < 1 || xx > N || yy > M)
continue;
if(hugo[xx][yy] == 0){
if(lake[xx][yy] == 1){
hugo[xx][yy] = hugo[xCurrent][yCurrent] + 2;
hugo_backTrack(xx, yy, curDiamond + diamond[xx][yy]);
hugo[xx][yy] = 0;
}
else{
if( hugo[xCurrent][yCurrent] + 1 < fire[xx][yy] || fire[xx][yy] == 0){
hugo[xx][yy] = hugo[xCurrent][yCurrent] + 1;
hugo_backTrack(xx, yy, curDiamond + diamond[xx][yy]);
hugo[xx][yy] = 0;
}
else
continue;
}
}
}
}
int main()
{
// freopen("input1.txt", "r", stdin);
startT = clock();
int T;
cin >> T;
for(int tc = 1; tc <= T; tc++){
input();
ans = 0;
check = false;
BFS_fire();
if(lake[xStart][yStart] == 1)
hugo[xStart][yStart] = 2;
else
hugo[xStart][yStart] = 1;
hugo_backTrack(xStart, yStart, diamond[xStart][yStart]);
if(check)
cout <<"Case #" << tc << " " << endl << ans << endl;
else
cout <<" Case #" << tc << " " << endl << "-1" << endl;
}
endT = clock();
double dur = (double)(endT - startT);
cout << dur;
return 0;
}Editor is loading...