Untitled
unknown
plain_text
a year ago
56 kB
29
Indexable
1.domino 1X2, tinh so canh dat
5
6 1 6 5 3 2 5 0
6 6 0 1 6 0 4 4
2 2 3 6 5 5 1 5
1 2 0 4 4 3 4 2
5 2 1 1 4 1 3 0
3 3 0 2 3 5 2 6
1 3 4 6 4 5 0 0
6 6 6 0 1 4 6 3
2 5 3 3 3 5 5 4
0 0 4 3 3 1 2 4
4 4 2 0 5 5 3 0
0 1 2 2 6 1 2 1
4 6 2 6 5 6 0 4
5 0 5 1 1 1 2 3
2 4 0 2 6 6 4 1
4 5 6 0 3 5 5 6
0 1 6 3 4 3 3 2
0 3 1 1 5 1 3 1
2 5 0 0 6 2 3 3
4 0 6 4 5 0 5 5
2 1 4 4 2 2 6 1
0 5 4 4 2 5 6 2
3 5 1 1 1 0 4 1
3 1 5 1 4 3 1 6
2 0 6 4 5 5 5 6
3 3 3 0 2 3 2 1
0 0 6 0 6 3 4 5
4 2 6 6 0 4 2 2
3 0 6 5 6 4 1 0
3 5 1 3 1 1 0 2
4 4 5 4 3 3 3 2
5 5 1 4 5 1 6 0
5 0 2 2 2 1 6 3
3 4 0 0 6 6 2 5
1 6 4 2 0 4 6 2
Output
#1 32
#2 24
#3 40
#4 16
#5 20
Code:
#include<iostream>
using namespace std;
int A[7][8];
int visited[7][8];
int used[7][7];
int dem;
void back(int num)
{
if(num==28) dem++;
bool flag=false;
for(int i=0;i<7;i++)
{
for(int j=0;j<8;j++)
{
if(visited[i][j]==0)
{
//dat theo hang ngang
if(j<7 && visited[i][j+1]==0)
{
if(used[A[i][j]][A[i][j+1]]==0 && used[A[i][j+1]][A[i][j]]==0)
{
used[A[i][j]][A[i][j+1]]=1;
used[A[i][j+1]][A[i][j]]=1;
visited[i][j]=1;
visited[i][j+1]=1;
back(num+1);
used[A[i][j]][A[i][j+1]]=0;
used[A[i][j+1]][A[i][j]]=0;
visited[i][j]=0;
visited[i][j+1]=0;
}
}
//dat theo hang doc
if(i<6 && visited[i+1][j] ==0)
{
if(used[A[i][j]][A[i+1][j]] ==0 && used[A[i+1][j]][A[i][j]]==0)
{
used[A[i][j]][A[i+1][j]]=1;
used[A[i+1][j]][A[i][j]]=1;
visited[i+1][j]=1;
visited[i][j]=1;
back(num+1);
used[A[i][j]][A[i+1][j]]=0;
used[A[i+1][j]][A[i][j]]=0;
visited[i+1][j]=0;
visited[i][j]=0;
}
}
flag=true;
break;
}
}
if(flag) break;
}
}
int main()
{
//freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
//
for(int i=0;i<7;i++)
{
for(int j=0;j<8;j++)
{
cin>>A[i][j];
visited[i][j]=0;
}
}
//
dem=0;
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++) used[i][j]=0;
}
//
back(0);
//
cout<<"#"<<tc<<" "<<dem<<endl;
}
return 0;
}
====================
2.We have to plan a path for a cleaning robot to clean a rectangular room floor of size NxM. The room floor paved with square tiles whose size fits the cleaning robot (1 × 1). There are clean tiles and dirty tiles, and the robot can change a dirty tile to a clean tile by visiting the tile. Also there may be some obstacles (furniture) whose size fits a tile in the room. If there is an obstacle on a tile, the robot cannot visit it. The robot moves to an adjacent tile with one move. The tile onto which the robot moves must be one of four tiles (i.e., east, west, north or south) adjacent to the tile where the robot is present. The robot may visit a tile twice or more.
Your task is to write a program which computes the minimum number of moves for the robot to change all dirty tiles to clean tiles, if ever possible.
Input
The input consists of multiple maps, the first line is the number of test case T (T < = 50).
Each test case begins with N and M representing the size of the room. ( 5 =< N, M <= 100)
The next N line representing the arrangement of the room with following describe:
0 : a clean tile
1 : a dirty tile
2 : a piece of furniture (obstacle)
3 : the robot (initial position)
In the map the number of dirty tiles does not exceed 10 and there is only one robot.
Output
Print each test case on two lines, the first line of each test case is "Case #x", where x is the test case number. The next line is the minimum number of moves for the robot to change all dirty tiles to clean tiles. If the map includes dirty tiles which the robot cannot reach, your program should output -1.
5
5 7
0 0 0 0 0 0 0
0 3 0 0 0 1 0
0 0 0 0 0 0 0
0 1 0 0 0 1 0
0 0 0 0 0 0 0
5 15
0 0 0 0 2 0 2 0 0 0 0 1 2 0 1
0 0 0 1 0 2 0 2 2 0 1 2 0 0 0
2 1 0 2 0 1 0 2 0 0 0 0 0 0 0
0 0 0 1 0 2 0 0 1 2 0 0 2 0 0
0 2 1 0 2 0 0 0 0 0 3 0 0 0 0
out:
Case #1
8
Case #2
38
Code:
#include<iostream>
using namespace std;
int M[101][101];
int visited[101][101];
int A[2][100];
int idx;
int ke[101][101];
int S[2][1000000];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n,m;
int top;
int bot;
int luu[11];
int used[11];
int minn,kq;
bool checkused()
{
for(int i=0;i<idx;i++)
{
if(used[i]==0) return true;
}
return false;
}
void tinhtoan(int x)
{
if(kq>minn) return;
if(!checkused())
{
if(kq<minn) minn=kq;
return;
}
for(int i=0;i<idx;i++)
{
if(used[i]==0)
{
kq+=ke[x][i];
used[i]=1;
tinhtoan(i);
used[i]=0;
kq-=ke[x][i];
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
idx=1;
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>M[i][j];
if(M[i][j]==3)
{
A[0][0]=i;
A[1][0]=j;
}
else if(M[i][j]==1)
{
A[0][idx]=i;
A[1][idx]=j;
idx++;
}
}
}
// xu ly
for(int i=0;i<101;i++)
for(int j=0;j<101;j++) ke[i][j]=0;
//
int dem=0;
bool firstcheck=true;
for(int i=0;i<idx;i++)
{
for(int a=0;a<101;a++)
for(int b=0;b<101;b++) visited[a][b]=0;
//khai bao queue
top=-1,bot=-1;
//
top++;
S[0][top]=A[0][i];
S[1][top]=A[1][i];
visited[A[0][i]][A[1][i]]=1;
//
while(top!=bot)
{
bot++;
int x=S[0][bot];
int y=S[1][bot];
//
for(int k=0;k<4;k++)
{
int xnew=x+dx[k];
int ynew=y+dy[k];
if(xnew >=0 && xnew <n && ynew >= 0 && ynew<m)
{
if(visited[xnew][ynew]==0 && M[xnew][ynew]!=2)
{
top++;
S[0][top]=xnew;
S[1][top]=ynew;
visited[xnew][ynew]=visited[x][y]+1;
}
}
}
}
//dua vao ma tran ke
for(int a=0;a<idx;a++)
{
ke[i][a]=visited[A[0][a]][A[1][a]]-1;
if(ke[i][a]==-1) firstcheck=false;
}
if(firstcheck) dem++;
}
if(dem<idx)
{
cout<<"Case #"<<tc<<endl<<-1<<endl;
continue;
}
minn=9999;kq=0;
for(int k=0;k<11;k++) used[k]=0;
//
tinhtoan(0);
//
cout<<"Case #"<<tc<<endl;
cout<<minn<<endl;
}
return 0;
}
===================================
3.Hugo
Có thử thách dành cho Hugo như sau: Hugo được thả vào 1 khu rừng có rất nhiều kim cương, tuy nhiên đồng thời lúc đó có các đám cháy xuất hiện. Các đám cháy này sẽ lây lan ra các khu vực lân cận theo bốn hướng sau 1 giờ. Tuy nhiên trong khu rừng có một số hồ nhỏ, và lửa không thể cháy lan trên hồ.
Thời gian để Hugo di chuyển giữa các khu đất là 1 giờ, qua khu hồ là 2 giờ. Hãy giúp Hugo thoát khỏi khu rừng cùng với số lượng kim cương lớn nhất có thể và đảm bảo Hugo không bị lửa thiêu.
Lưu ý khu rừng chỉ tồn tại một số lượng nhất định lối thoát, tại danh giới của khu rừng, và Hugo không bao giờ quay lại khu vực mình đã đi qua.
Input
Dòng đầu là số lượng test case T (T <= 50).
Dòng đầu của mỗi test case là 4 số N, M, SR, SC tương ứng là số hàng, số cột của khu rừng và tọa độ hàng, cột mà Hugo đang đứng. ( 4 <= N, M <= 15).
3 dòng tiếp theo, bắt đầu của mỗi dòng tương ứng là số lượng K các đám cháy hiện có, các hồ và các lối thoát, 2K số tiếp theo trên dòng là tọa độ tương ứng. N dòng tiếp theo sẽ là bản đồ mô tả số lượng kim cương D tại mỗi khu vực trong khu rừng. (0 <= D <= 1000)
Output
In mỗi test case trên 2 dòng, dòng đầu tiên là "Case #x", với x là số thứ tự của test case.
Dòng tiếp theo là số lượng kim cương lớn nhất mà Hugo có thể thu được, nếu Hugo không thể thoát ra khỏi khu rừng, in ra -1.
Sample
Input
5 <- Số lượng test case
4 4 1 2 <- Test case 1, khu rừng có kích thước 4x4, Hugo đang ở ô (1, 2)
2 1 1 4 1 <- 2 Khu vực bắt đầu cháy ở (1, 1) và (4, 1)
4 1 3 2 1 3 3 3 4 <- 4 Khu vực là hồ ở (1, 3), (2, 1), (3, 3) và (3, 4)
2 2 4 3 4 <- 2 lối thoát ở ô (2, 4) và (3, 4)
0 0 10 20 <- Số lượng kim cương hàng 1
9 3 2 5 <- Số lượng kim cương hàng 2
0 0 0 0 <- Số lượng kim cương hàng 3
0 10 0 100 <- Số lượng kim cương hàng 4
out:
Case #1
10 <- Số lượng kim cương lớn nhất mà Hugo có thể thu được
code:
#include<iostream>
using namespace std;
int n, m, sr, sc;
int fire, lake, exi;
int F[600], L[600], E[600];
int M[20][20], A[20][20];
int S[2][100000];
int top, bot;
int visited[20][20];
int FL[20][20];
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
int kq, maxx;
bool checkexit;
void back2(int tgian, int x, int y, int kq)
{
if (A[x][y] == 2)
{
if (kq > maxx) maxx = kq;
checkexit = true;
}
for (int i = 0; i < 4; i++)
{
int xnew = x + dx[i], ynew = y + dy[i];
if (xnew >= 1 && xnew <= n && ynew >= 1 && ynew <= m && visited[xnew][ynew] == 0)
{
if (tgian + 1 < FL[xnew][ynew] || FL[xnew][ynew]<0 )
{
visited[xnew][ynew] = 1;
if (FL[xnew][ynew] == 9998)
{
back2(tgian + 2, xnew, ynew, kq + M[xnew][ynew]);
visited[xnew][ynew] = 0;
}
else
{
back2(tgian + 1, xnew, ynew, kq + M[xnew][ynew]);
visited[xnew][ynew] = 0;
}
}
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
int t; cin >> t;
for (int tc = 1; tc <=t; tc++)
{
cin >> n >> m >> sr >> sc;
cin >> fire;
for (int i = 0; i < 2 * fire; i++) cin >> F[i];
cin >> lake;
for (int i = 0; i < 2 * lake; i++) cin >> L[i];
cin >> exi;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) A[i][j]=0;
for (int i = 0; i < 2 * exi; i += 2)
{
cin >> E[i] >> E[i + 1];
A[E[i]][E[i + 1]] = 2;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> M[i][j];
visited[i][j] = 0;
FL[i][j] = 0;
}
}
for (int i = 0; i < 2 * lake; i += 2)
{
FL[L[i]][L[i + 1]] = 9999;
}
//
top = bot = -1;
//
for (int i = 0; i < 2 * fire; i += 2)
{
//push vao queue
top++;
S[0][top] = F[i];
S[1][top] = F[i + 1];
FL[F[i]][F[i + 1]] = 1;
}
while (top != bot)
{
bot++;
int x = S[0][bot];
int y = S[1][bot];
for (int k = 0; k < 4; k++)
{
int xnew = x + dx[k];
int ynew = y + dy[k];
if (FL[xnew][ynew] == 0 && xnew <= n && xnew >= 1 && ynew <= m && ynew >= 1)
{
top++;
S[0][top] = xnew;
S[1][top] = ynew;
FL[xnew][ynew] = FL[x][y] + 1;
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) FL[i][j] = FL[i][j] - 1;
}
visited[sr][sc] = 1;
kq = M[sr][sc];
maxx = 0;
checkexit = false;
back2(0, sr, sc, kq);
cout << "Case #" << tc << endl;
if (checkexit) cout << maxx << endl;
else cout << -1 << endl;
}
return 0;
}
======================================
pizza location
#include<iostream>
using namespace std;
int k,r;
int m,M[21][2];
int n,N[101][3];
int A[21][101]; // mxn
int maxx;
int X[11];
int pow2(int a)
{
return a*a;
}
void tohop(int i)
{
for(int j=X[i-1] +1 ;j<=m-k+i;j++)
{
X[i]=j;
if(i==k)
{
//tinh toan
int dd[21]={0};
int tmp=0;
for(int a=1;a<=k;a++)
{
//dat nha hang tai vi tri X[a];
int vt=X[a]-1;
for(int b=0;b<n;b++)
{
if(A[vt][b]!=0) dd[b]=A[vt][b];
}
}
//
for(int a=0;a<21;a++) tmp+=dd[a];
if(tmp>maxx) maxx=tmp;
}
else
{
tohop(i+1);
}
}
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
cin>>k>>r;// so luong nha hang va ban kinh giao hang
cin>>m;//so luong dia diem de dat nha hang
for(int i=0;i<m;i++)
{
cin>>M[i][0]>>M[i][1];// toa do cac dia diem dat nha hang
}
cin>>n;//so bua tiec
for(int i=0;i<n;i++)
{
cin>>N[i][0]>>N[i][1]>>N[i][2];//toa do va sl nguoi cua moi bua tiec
}
//xu ly
for(int i=0;i<21;i++)
{
for(int j=0;j<101;j++) A[i][j]=0;
}
//1.tao 1 matran khoang cach
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
//diem I(hang i trong ma tran M) toi bua tiec thu J(hang j trong ma tran N)
if(pow2(r)>=(pow2(M[i][0]-N[j][0])+pow2(M[i][1]-N[i][1])))
{
A[i][j]=N[j][2];
}
}
}
//
maxx=0;
//
for(int i=0;i<11;i++) X[i]=0;
tohop(1);
cout<<"#"<<tc<<" "<<maxx<<endl;
}
return 0;
}
//
Input
3
2 2
3
1 0
4 0
7 0
4
0 0 1
3 0 7
5 0 9
8 0 1
2 2
3
-2 0
0 1
3 0
8
-3 1 1
-3 0 1
-3 -1 1
-2 -1 1
0 0 3
0 2 1
2 1 3
4 0 2
3 3
5
0 0
1 6
2 3
6 6
7 2
8
0 1 2
0 5 3
0 6 1
1 0 1
3 2 3
3 6 2
6 2 4
8 6 3
Output
#1 18
#2 12
#3 17
==========================
bai ???
#include<iostream>
using namespace std;
int M[101][101];
int visited[101][101];
int A[2][100];
int idx;
int ke[101][101];
int S[2][1000000];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n,m;
int top;
int bot;
int luu[11];
int used[11];
int minn,kq;
bool checkused()
{
for(int i=0;i<idx;i++)
{
if(used[i]==0) return true;
}
return false;
}
void tinhtoan(int x)
{
if(kq>minn) return;
if(!checkused())
{
if(kq<minn) minn=kq;
return;
}
for(int i=0;i<idx;i++)
{
if(used[i]==0)
{
kq+=ke[x][i];
used[i]=1;
tinhtoan(i);
used[i]=0;
kq-=ke[x][i];
}
}
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
idx=1;
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>M[i][j];
if(M[i][j]==3)
{
A[0][0]=i;
A[1][0]=j;
}
else if(M[i][j]==1)
{
A[0][idx]=i;
A[1][idx]=j;
idx++;
}
}
}
// xu ly
for(int i=0;i<101;i++)
for(int j=0;j<101;j++) ke[i][j]=0;
//
int dem=0;
bool firstcheck=true;
for(int i=0;i<idx;i++)
{
for(int a=0;a<101;a++)
for(int b=0;b<101;b++) visited[a][b]=0;
//khai bao queue
top=-1,bot=-1;
//
top++;
S[0][top]=A[0][i];
S[1][top]=A[1][i];
visited[A[0][i]][A[1][i]]=1;
//
while(top!=bot)
{
bot++;
int x=S[0][bot];
int y=S[1][bot];
//
for(int k=0;k<4;k++)
{
int xnew=x+dx[k];
int ynew=y+dy[k];
if(xnew >=0 && xnew <n && ynew >= 0 && ynew<m)
{
if(visited[xnew][ynew]==0 && M[xnew][ynew]!=2)
{
top++;
S[0][top]=xnew;
S[1][top]=ynew;
visited[xnew][ynew]=visited[x][y]+1;
}
}
}
}
//dua vao ma tran ke
for(int a=0;a<idx;a++)
{
ke[i][a]=visited[A[0][a]][A[1][a]]-1;
if(ke[i][a]==-1) firstcheck=false;
}
if(firstcheck) dem++;
}
if(dem<idx)
{
cout<<"Case #"<<tc<<endl<<-1<<endl;
continue;
}
minn=9999;kq=0;
for(int k=0;k<11;k++) used[k]=0;
//
tinhtoan(0);
//
cout<<"Case #"<<tc<<endl;
cout<<minn<<endl;
}
return 0;
}
=======================================
linh kien may tinh
++ code lai ++
====================================================
hugo quan ly tau
#include<iostream>
using namespace std;
int n;
int A[3][2];
int visit[65];
int minn;
int hoanvi[6][3]={{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
int sum=0;
void tinhtoan(int TH[3],int idx,int khoangcach[65])
{
if(idx==3)
{
int tmp=0;
for(int i=0;i<n;i++) tmp+=khoangcach[i];
cout<<tmp;
}
int vt=A[TH[idx]][0];
int sl=A[TH[idx]][1];
//
if(khoangcach[vt]==0)
{
khoangcach[vt]=1;
sl--;
}
int l=vt-1,r=vt+1;
int dem=2;
bool flag=false;
while(sl!=0)
{
if(l>=1 && khoangcach[l]==0 && r<=n && khoangcach[r]==0 && sl==1)
{
flag=true;
break;
}
if(l>=1 && khoangcach[l]==0)
{
khoangcach[l]=dem;
sl--;
}
if(r<=n && khoangcach[r]==0)
{
khoangcach[r]=dem;
sl--;
}
l--;
r++;
dem++;
}
//neu chi co the dat trai hoac phai
if(flag)
{
//dat ben trai
int khoangcach1[65];
for(int i=0;i<65;i++) khoangcach1[i]=khoangcach[i];
khoangcach1[l]=dem;
tinhtoan(TH,idx+1,khoangcach1);
//dat ben phai
int khoangcach2[65];
for(int i=0;i<65;i++) khoangcach2[i]=khoangcach[i];
khoangcach1[r]=dem;
tinhtoan(TH,idx+1,khoangcach2);
}
else tinhtoan(TH,idx+1,khoangcach);
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
cin>>n;
for(int i=0;i<3;i++)
for(int j=0;j<2;j++) cin>>A[i][j];
//
int khoangcach[65]={0};
}
return 0;
}
//
50
10
4 5
6 2
10 2
10
8 5
9 1
10 2
24
15 3
20 4
23 7
39
17 8
30 5
31 9
60
57 12
31 19
38 16
10
2 2
8 3
5 2
10
9 3
3 3
5 2
10
8 8
2 1
6 1
10
2 2
5 2
3 2
10
2 2
5 2
4 2
20
12 5
19 6
10 2
20
16 4
15 3
4 4
20
14 2
5 6
2 5
20
8 4
5 4
3 2
20
4 5
2 5
10 6
20
11 5
3 5
9 3
20
5 4
9 3
7 4
20
11 4
7 3
2 4
20
4 1
5 3
15 5
20
17 1
12 4
9 3
30
14 9
18 3
29 10
30
12 10
4 9
6 5
30
1 4
28 7
27 2
30
6 1
15 10
23 8
30
4 7
28 1
13 2
30
7 6
6 5
18 2
30
23 2
21 5
11 7
30
11 8
28 8
12 8
30
18 10
4 10
6 9
30
12 7
19 7
3 1
40
14 1
9 4
21 5
40
11 11
40 8
25 10
40
36 11
2 12
3 17
40
15 2
21 9
37 20
40
29 3
5 2
2 11
40
19 6
21 13
29 11
40
14 11
9 4
4 11
40
18 10
14 12
35 8
40
12 10
1 6
10 10
40
24 8
25 6
9 1
50
3 6
46 8
36 12
50
38 9
15 1
4 3
50
19 15
31 2
47 6
50
49 9
10 7
8 11
50
43 15
39 10
30 7
60
12 17
16 12
29 3
60
55 20
33 20
16 20
60
27 10
36 3
54 5
60
37 20
42 20
19 20
60
60 13
18 10
37 16
Case #1
18
Case #2
25
Case #3
57
Case #4
86
Case #5
339
====================
chi ong nau
5
5 3
300 410 150 55 370
120 185 440 190 450
165 70 95 420 50
5 5
356 55 41 453 12
401 506 274 506 379
360 281 421 311 489
425 74 276 371 164
138 528 461 477 470
Case #1
2250000
Case #2
3748096
code:
#include<iostream>
using namespace std;
int T, M, N;
int arr[20][20], visited[20][20];
int Answer;
// -1 0, 0 1, 1 1, 1 0, 1 -1, 0 -1
// -1 0, -1 1, 0 1, 1 0, 0 -1, -1 -1;
int dxc[6] = {-1, 0, 1, 1, 1, 0};
int dyc[6] = {0, 1, 1, 0, -1, -1};
int dxl[6] = {-1, -1, 0, 1, 0, -1};
int dyl[6] = {0, 1, 1, 0, -1, -1};
bool isValid(int x, int y){
return x >= 1 && x <= N && y > 0 && y <= M;
}
void bt(int x, int y, int sum, int count){
if(count == 4){
if(Answer < sum){
Answer = sum;
}
return;
}
for(int i = 0; i < 6; i++){
if(y % 2 == 0){
int nx = x + dxc[i];
int ny = y + dyc[i];
if(isValid(nx, ny) && visited[nx][ny] == 0 ){
visited[nx][ny] = 1;
bt(nx, ny, sum+ arr[nx][ny], count+1);
bt(x,y,sum+arr[nx][ny],count+1);
visited[nx][ny] = 0;
}
}
else{
int nx = x + dxl[i];
int ny = y + dyl[i];
if(isValid(nx, ny) && visited[nx][ny] == 0){
visited[nx][ny] = 1;
bt(nx, ny, sum+ arr[nx][ny], count+1);
bt(x,y,sum+arr[nx][ny],count+1);
visited[nx][ny] = 0;
}
}
}
}
void reset(){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
visited[i][j] = 0;
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++){
Answer = 0;
cin >> M >> N;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
cin >> arr[i][j];
}
}
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
visited[i][j] = 1;
int sum = arr[i][j];
bt(i, j, sum, 1);
reset();
}
}
cout << "Case #" <<tc << endl;
cout << long( Answer * Answer) << endl;
}
return 0;
}
===================================================================
hugo giao hang
code:
#include<iostream>
using namespace std;
int sx,sy,hx,hy;
int n;
int X[15],Y[15];
int matranke[15][15];
int dd[20];
long long kq;
long long minn;
int abyss(int a,int b)
{
if(a>b) return a-b;
return b-a;
}
void tinh(int x,int idx)
{
if(kq>minn) return;
if(idx>=n)
{
if(kq+matranke[n+1][x]<minn) minn=kq+matranke[n+1][x];
return;
}
for(int i=0;i<=n;i++)
{
if(dd[i]==0 && matranke[x][i]!=0)
{
kq+=matranke[x][i];
dd[i]=1;
tinh(i,idx+1);
dd[i]=0;
kq-=matranke[x][i];
}
}
}
void matrankhoangcach(int a,int x,int y)
{
for(int i=0;i<=n+1;i++)
{
matranke[a][i]=abyss(x,X[i])+abyss(y,Y[i]);
}
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
cin>>sx>>sy>>hx>>hy;
cin>>n;
X[0]=sx;Y[0]=sy;
for(int i=1;i<=n;i++)
{
cin>>X[i]>>Y[i];
}
X[n+1]=hx;Y[n+1]=hy;
//tao ma tran ke cua n diem va cong ty
for(int i=0;i<=n+1;i++)
{
dd[i]=0;
matrankhoangcach(i,X[i],Y[i]);
}
//
dd[0]=1;
kq=0;minn=9999999;
//
tinh(0,0);
cout<<"Case #"<<tc<<" ";
cout<<minn<<endl;
}
return 0;
}
===================================================
minimal big sum
#include<iostream>
using namespace std;
int A[100001];
int n,k;
int sum()
{
int res=0;
for(int i=0;i<n;i++) res+=A[i];
return res;
}
int max()
{
int res=A[0];
for(int i=1;i<n;i++)
{
if(A[i]>res) res=A[i];
}
return res;
}
int count(int a)
{
int cnt=1;
int cur=A[0];
for(int i=1;i<n;i++)
{
cur+=A[i];
if(cur>a)
{
cnt++;
cur=A[i];
}
}
return cnt;
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
cin>>k>>n;
for(int i=0;i<n;i++) cin>>A[i];
//xu ly
int high=sum();
int low=max();
int kq=0;
//
while(high>=low)
{
int mid=(high+low)/2;
int cnt=count(mid);
if(cnt>k) low=mid+1;
else if(cnt<=k)
{
kq=mid;
high=mid-1;
}
}
//
cout<<"#"<<tc<<" "<<kq<<endl;
}
return 0;
}
//
10
3
7
2 1 5 1 2 2 2
4
10
10 2 1 5 1 2 2 2 9 11
=========================================================
caculato 3
#include<iostream>
using namespace std;
struct Stack
{
char S[10000];
int top;
Stack()
{
top=-1;
}
void add(int n)
{
top++;
S[top]=n;
}
int pop()
{
return S[top--];//tra ve top sau do top giam di 1
}
bool empty()
{
return top<0;
}
int peek()
{
return S[top];
}
void reset()
{
top=-1;
}
};
int ut(char a)
{
if(a=='+' || a=='-') return 1;
else if(a=='*'||a=='/') return 2;
else if(a=='(') return 0;
}
int stoi(char S[])
{
int i=0;int res=0;
while(S[i]!=0)
{
res=res*10+S[i]-'0';
i++;
}
return res;
}
int main()
{
freopen("Text.txt","r",stdin);
for(int tc=1;tc<=10;tc++)
{
Stack stack = Stack();
int n;
cin>>n;
char A[1000];
cin>>A;
char out[1000];
int idx=0;
//chuyen trung to sang hau to
for(int i=0;i<n;i++)
{
if(A[i]<='9' && A[i]>='0')
{
out[idx]=A[i];
idx++;
}
else if(A[i]=='(')
{
stack.add(A[i]);
}
else if( A[i]== '+' || A[i]=='-'||A[i]=='*'||A[i]=='/')
{
if(ut(A[i])>=ut(stack.peek())) stack.add(A[i]);
else
{
out[idx]=stack.pop();
idx++;
stack.add(A[i]);
}
}
else if(A[i]==')')
{
while(stack.peek()!='(')
{
out[idx]=stack.pop();
idx++;
}
int rac=stack.pop();
}
}
while(!stack.empty())
{
out[idx]=stack.pop();
idx++;
}
// tinh toan
//tao stack 2
int S2[10000];
int top=-1;
int res=0;
for(int i=0;i<idx;i++)
{
if(out[i]<='9' && out[i]>='0')
{
// add vao s2
top++;
S2[top]=out[i]-'0';
}
else if(out[i]=='+'||out[i]=='-'||out[i]=='*'||out[i]=='/')
{
// pop ra 2 cai dau va tinh toan
int a=S2[top];top--;
int b=S2[top];top--;
int c;
if(out[i]=='+') c=a+b;
else if(out[i]=='*') c=a*b;
//add ket qua vao
top++;S2[top]=c;
}
}
int kq=S2[top];
cout<<"#"<<tc<<" "<<kq<<endl;
}
return 0;
}
//
113
(9+(5*2+1)+(3*3*7*6*9*1*7+1+8*6+6*1*1*5*2)*4*7+4*3*8*2*6+(7*8*4*5)+3+7+(2+6+5+1+7+6+7*3*(6+2)+6+6)*2+4+2*2+4*9*3)
85
(4+8+4*(8*5*(7*(6*8)+3+(6+(3+7+1*7*5*4)*3)*2*3+5)+6+7*7)*4+2+9*4+7+2*3*(7*6*1*8)+9+9)
97
(9*5+7+8+6+3+9*2+1+7+4+3+9*3*1+4*(4+4*3*1+9*3+(9*5)*1*7*8+2+8+8*7+9*4*9)+(1+1*8+8*9*7+1*4*5*2*5))
89
((3*1*4+6*3+8+4+5+4+2*1+5+3*4)*1+1+(3*2*2+9+5*4*6*9+9+4+1*8+9)*4*8+9+3*7+9*6*9*5+8+3*8+1)
125
(2+(6*5+6+5+3*9+6+2+8*2+2)+6+2*2+2*5*1*2+1*8+1*(4+7*5+8+9+7+3*8*5)+(2+9+5*4*4+1+3*9*6*4*5+(5*(3+4)*9+8+7+9*2)+7+7+2)+8+2+7+5)
113
(8+8*6+3*9*8*7*6*3+5*(7*6*6+3*5+2*4*9*3+5+2+1*4)*1*7+6*8+9+3+2+8*3+8*(2+6*9+2*2*7+8*1*2+9*3+1+5)*(5*8+4*1*2*4*2))
115
(7+9*2+6+5*7+1*7*(9+8+6)*1*2+7+5*9*6*3+4*8*9*6*1*3+7*1+2+5+1*4*9+6*4+7*1*2*4*2+3+((3*4+9+7*1+7+5+3*7*1*7+8*3*8)+7))
99
(9*4+(1+5*7*8+9+1+2)+5+(6*(7+4*5*2+4+8*4+7)+9)*1*3*1+1*2*8+3+(2+9*(1*5*9+7*1+1+7+3*2))+1+3*7*8+9*6)
75
(2*2+((7+8*8*6+(6*6)*7+7*1)*5)*7+3+1*5+1*8*4+(9+6+(7*5+3+1*8*8*9+4+7+9)*3))
117
(8+6*9+2*3+4+2+(6+9+3+7*5*1+2+2+2)*9+4+6*1+6*4+7+7*2+5+2*6*(8*9*8*6+4*2)*5+5*8*3+(6+1+3+3*8*1*2*1+5+6)+1+5+4*7*1*3+1)
===========================================================
turn over game
#include<iostream>
using namespace std;
char A[4][4];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int den,trang;
int minn;
int tmp;
int hangidx[16]={0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3},cotidx[16]={0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3};
int chuoi[16];
void lat(int x,int y)
{
if(A[x][y]=='b')
{
A[x][y]='w';
den--;
trang++;
}
else
{
A[x][y]='b';
trang--;
den++;
}
for(int i=0;i<4;i++)
{
int xnew=x+dx[i];
int ynew=y+dy[i];
if(xnew>=0 && xnew<4 && ynew>=0 && ynew <4)
{
if(A[xnew][ynew]=='b')
{
A[xnew][ynew]='w';
den--;
trang++;
}
else
{
A[xnew][ynew]='b';
trang--;
den++;
}
}
}
}
void back(int idx)
{
if(den==16 || trang ==16)
{
if(tmp<minn) minn=tmp;
}
if(idx==16) return;
chuoi[idx]=1;
int hang=hangidx[idx],cot=cotidx[idx];
lat(hang,cot);
tmp++;
back(idx+1);
chuoi[idx]=0;
lat(hang,cot);
tmp--;
back(idx+1);
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
//
den=0;trang=0;
minn=100000;
tmp=0;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
cin>>A[i][j];
if(A[i][j]=='b') den++;
else trang++;
}
}
// xu ly tren ma tran
for(int i=0;i<16;i++) chuoi[i]=0;
//
back(0);
cout<<"Case #"<<tc<<endl;
if(minn==100000) cout<<"impossible"<<endl;
else
{
cout<<minn<<endl;
}
}
return 0;
}
//
2
bwwb
bbwb
bwwb
bwww
bwbw
wwww
bbwb
bwwb
==============================================
chest rook
#include<iostream>
using namespace std;
int n;
char A[4][4];
int kq;
int tmp;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void saochep(int A[4][4],int B[4][4])
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) A[i][j]=B[i][j];
}
bool kiemtra(int dd[4][4])
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(dd[i][j]==0) return true;
}
}
return false;
}
void backtrack(int dd[4][4])
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(dd[i][j]==0)
{
tmp++;
int dd1[4][4];
saochep(dd1,dd);
for(int k=0;k<4;k++)
{
int r=0;
while(1)
{
int x=i+r*dx[k],y=j+r*dy[k];
if(x>=n || x<0 || y>=n || y<0 || dd1[x][y]==2) break;
dd1[x][y]=1;
r++;
}
}
//
if(!kiemtra(dd1))
{
if(tmp>kq) kq=tmp;
tmp--;
saochep(dd1,dd);
}
else
{
backtrack(dd1);
tmp--;
saochep(dd1,dd);
}
}
}
}
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
cin>>n;
for(int i=0;i<n;i++) cin>>A[i];
//reset
int dd[4][4],dd1[4][4];
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
if(A[i][j]=='.') dd[i][j]=0;
else dd[i][j]=2;
}
}
kq=0;
tmp=0;
backtrack(dd);
//
cout<<"Case #"<<tc<<endl;
cout<<kq<<endl;
}
return 0;
}
//
5
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
======================================================
8 queen
#include<iostream>
using namespace std;
int A[200][9],V[200][9],kq=0,dem=0;
bool kiemtra(int x,int y)
{
for(int i=0;i<8;i++)
if(V[i][y]==1) return false;
for(int i=0;i<8;i++)
if(V[x][i]==1) return false;
for(int i=x,j=y;i>=0 && j>=0 ;i--,j--)
{
if(V[i][j]==1) return false;
}
for(int i=x,j=y;i>=0 && j <8 ; i-- ,j++)
{
if(V[i][j]==1) return false;
}
for(int i=x,j=y;i<8 && j>=0; ++i,--j)
{
if(V[i][j]==1) return false;
}
for(int i=x,j=y;i<8 && j<8;++i,++j)
{
if(V[i][j]==1) return false;
}
return true;
}
void backtrack(int x)
{
if(x>=8)
{
dem=0;
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
if(V[i][j]==1) dem+=A[i][j];
}
}
if(dem>kq) kq=dem;
}
for(int i=0;i<8;i++)
{
if(V[x][i]==0)
{
if(kiemtra(x,i))
{
V[x][i]=1;
backtrack(x+1);
V[x][i]=0;
}
}
}
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
int n;cin>>n;
cout<<"Case #"<<tc<<endl;
for(int so=1;so<=n;so++)
{
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
cin>>A[i][j];
V[i][j]=0;
}
}
kq=0;
dem=0;
backtrack(0);
cout<<kq<<endl;
}
}
return 0;
}
//
2
1
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
2
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
===========================================================================
array game(chia mang ra 2 phan bang nhau)
#include<iostream>
using namespace std;
int A[20001];
int n;
int dem,maxx;
void back(long long tong,int bd,int kt)//xu ly tren mang B
{
//tim diem can bang
long long tmp=0;
int vt=-1;
for(int i=bd;i<=kt;i++)
{
tmp+=A[i];
if(tmp==tong-tmp)
{
vt=i;
break;
}
}
//tim duoc 1 diem chia
if(vt>=0)
{
dem++;
//
back(tmp,bd,vt);
back(tmp,vt+1,kt);
//
dem--;
if(dem>maxx) maxx=dem;
}
if(dem>maxx) maxx=dem;
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
cin>>n;
bool flag=false;
for(int i=0;i<n;i++)
{
cin>>A[i];
if(A[i]!=0) flag=true;
}
if(!flag)
{
cout<<n-1<<endl;
continue;
}
long long tong=0;
for(int i=0;i<n;i++)
{
if(A[i]!=0)
{
tong+=A[i];
}
}
if(tong%2!=0)
{
cout<<0<<endl;
continue;
}
//
dem=0;
maxx=0;
back(tong,0,n-1);
//
//if(maxx!=0) maxx=maxx+1;
cout<<maxx<<endl;
}
return 0;
}
//
20
42
0 2 0 2 0 0 0 0 2 0 0 2 2 0 2 2 2 2 0 0 0 2 0 0 2 2 2 2 2 2 0 0 0 0 2 0 2 0 2 0 2 2
24
2 0 0 2 2 0 0 0 0 2 0 2 0 2 0 2 0 0 0 2 0 0 2 0
64
999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994 999999994
====================================================
hugo di rung
#include<iostream>
using namespace std;
int n, m, sr, sc;
int fire, lake, exi;
int F[600], L[600], E[600];
int M[20][20], A[20][20];
int S[2][100000];
int top, bot;
int visited[20][20];
int FL[20][20];
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
int kq, maxx;
bool checkexit;
void back2(int tgian, int x, int y, int kq)
{
if (A[x][y] == 2)
{
if (kq > maxx) maxx = kq;
checkexit = true;
}
for (int i = 0; i < 4; i++)
{
int xnew = x + dx[i], ynew = y + dy[i];
if (xnew >= 1 && xnew <= n && ynew >= 1 && ynew <= m && visited[xnew][ynew] == 0)
{
if (tgian + 1 < FL[xnew][ynew] || FL[xnew][ynew]<0 )
{
visited[xnew][ynew] = 1;
if (FL[xnew][ynew] == 9998)
{
back2(tgian + 2, xnew, ynew, kq + M[xnew][ynew]);
visited[xnew][ynew] = 0;
}
else
{
back2(tgian + 1, xnew, ynew, kq + M[xnew][ynew]);
visited[xnew][ynew] = 0;
}
}
}
}
}
int main()
{
freopen("input.txt","r",stdin);
int t; cin >> t;
for (int tc = 1; tc <=t; tc++)
{
cin >> n >> m >> sr >> sc;
cin >> fire;
for (int i = 0; i < 2 * fire; i++) cin >> F[i];
cin >> lake;
for (int i = 0; i < 2 * lake; i++) cin >> L[i];
cin >> exi;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) A[i][j]=0;
for (int i = 0; i < 2 * exi; i += 2)
{
cin >> E[i] >> E[i + 1];
A[E[i]][E[i + 1]] = 2;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> M[i][j];
visited[i][j] = 0;
FL[i][j] = 0;
}
}
for (int i = 0; i < 2 * lake; i += 2)
{
FL[L[i]][L[i + 1]] = 9999;
}
//
top = bot = -1;
//
for (int i = 0; i < 2 * fire; i += 2)
{
//push vao queue
top++;
S[0][top] = F[i];
S[1][top] = F[i + 1];
FL[F[i]][F[i + 1]] = 1;
}
while (top != bot)
{
bot++;
int x = S[0][bot];
int y = S[1][bot];
for (int k = 0; k < 4; k++)
{
int xnew = x + dx[k];
int ynew = y + dy[k];
if (FL[xnew][ynew] == 0 && xnew <= n && xnew >= 1 && ynew <= m && ynew >= 1)
{
top++;
S[0][top] = xnew;
S[1][top] = ynew;
FL[xnew][ynew] = FL[x][y] + 1;
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) FL[i][j] = FL[i][j] - 1;
}
visited[sr][sc] = 1;
kq = M[sr][sc];
maxx = 0;
checkexit = false;
back2(0, sr, sc, kq);
cout << "Case #" << tc << endl;
if (checkexit) cout << maxx << endl;
else cout << -1 << endl;
}
return 0;
}
//
51
15 15 3 3
3 1 15 14 1 15 2
10 10 1 9 11 11 1 6 6 11 5 12 2 12 7 6 3 11 2 1 3
20 1 1 1 11 1 12 13 15 1 13 6 15 1 7 15 11 8 15 6 1 3 15 10 15 1 4 1 10 15 3 1 5 1 6 1 8 1 2 15 6
728 49 973 46 278 445 644 0 690 908 0 217 682 930 0
372 72 845 0 435 664 0 484 739 449 18 535 0 38 0
473 589 191 148 226 572 0 787 211 0 0 758 335 669 320
0 152 522 125 502 209 0 115 877 0 460 759 372 425 0
0 75 0 653 0 591 0 100 0 607 777 597 169 174 300
852 0 322 896 398 287 411 0 218 287 0 391 558 0 717
902 168 795 539 439 633 517 589 0 0 816 624 0 172 752
813 315 0 114 0 138 240 0 517 550 464 612 546 898 937
0 0 232 0 391 0 420 251 862 352 399 708 413 269 527
94 433 374 898 730 452 684 0 752 169 0 917 108 579 559
52 421 0 141 725 911 561 255 127 334 619 0 352 146 250
778 756 323 0 0 660 222 801 0 363 69 380 509 0 366
158 878 859 961 43 60 0 106 829 683 899 0 992 927 458
0 17 609 701 345 621 0 939 0 399 519 524 29 554 687
395 0 982 28 0 0 234 829 475 577 377 35 938 700 0
4 4 4 4
1 2 3
6 4 1 3 1 1 2 1 4 1 1 2 4
2 1 1 2 4
27 13 3 21
0 13 0 29
15 0 39 38
24 4 29 35
============================================================
pepe frog
#include<iostream>
using namespace std;
int A[200][200],X[200],Y[200],R[200],V[200],U[200];
int binh(int a)
{
return a*a;
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
int n;cin>>n;
for(int i=0;i<n;i++) cin>>X[i]>>Y[i]>>R[i];
//
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int kc=binh(X[i]-X[j])+binh(Y[i]-Y[j]);
if(kc<=0)
{
A[i][j]=0;
}
else
{
if(kc<=binh(40+R[i]+R[j])) A[i][j]=1;
else if(kc>binh(40+R[i]+R[j]) && kc<=binh(90+R[i]+R[j])) A[i][j]=1000;
else A[i][j]=0;
}
}
}
for(int i=0;i<n;i++) U[i]=0;
U[0]=1;
int a=0;
int duong=0;
for(int i=0;i<n;i++) V[i]=A[0][i];
for(int i=0;i<n;i++)
{
int minA=99999;
for(int j=0;j<n;j++)
{
if(V[j]<minA && U[j]==0 && V[j]!=0)
{
minA=V[j];
a=j;
}
}
U[a]=1;
for(int j=0;j<n;j++)
{
if(A[a][j]!=0 && A[a][j]+V[a]<V[j])
{
V[j]=A[a][j]+V[a];
}
if(V[j]==0 && A[a][j]!=0)
{
V[j]=A[a][j]+V[a];
}
}
}
duong=V[n-1];
if(duong==0) cout<<"-1"<<endl;
else
{
cout<<duong/1000<<" "<<duong%1000<<endl;
}
}
return 0;
}
//
1
10
41 7 5
110 59 5
38 108 5
65 11 4
81 101 2
112 17 1
21 44 3
126 88 6
49 22 6
14 103 4
========================================================
earning bigest prize 2
#include<iostream>
using namespace std;
char A[7];
bool best=false;
int result;
int l;
int stoi(char S[7])
{
int res=0;
int i=0;
while(S[i]!=0)
{
res=res*10+S[i]-'0';
i++;
}
return res;
}
int len(char S[7])
{
int l=0;
while(S[l]!=0) l++;
return l;
}
void try1(int n)
{
if(best) return;
if(n==0)
{
int t=stoi(A);
if(t>result) {result=t;return;}
return;
}
//
bool isDre=true;
for(int i=1;i<l && isDre;i++)
{
if(A[i]>A[i-1]) isDre=false;
}
if(isDre)
{
bool same=false;
for(int j=0;j<l && !same;j++)
{
for(int k=j+1;k<l && !same;k++)
{
if(A[j]==A[k]) same=true;
}
}
if(!same && n%2!=0)
{
char t=A[l-2];
A[l-2]=A[l-1];
A[l-1]=t;
//
}
result=stoi(A);
best=true;
return;
}
//
else
{
for(int i=0;i<l;i++)
{
for(int j=i+1;j<l;j++)
{
char t=A[i];A[i]=A[j];A[j]=t;
try1(n-1);
t=A[j];A[j]=A[i];A[i]=t;
}
}
}
}
int main()
{
freopen("input.txt", "r", stdin);
int t;cin>>t;
for (int tc = 1; tc <= t; tc++)
{
best=false;
A[0]='\0';
cin>>A;
int n;cin>>n;
result=stoi(A);
l=len(A);
try1(n);
cout<<"Case #"<<tc<<endl;
cout<<result<<endl;
}
return 0;
}
//
50
772 8
441296 9
5525 2
114 2
6575 3
0473 7
7321 10
1138 4
53179 9
975054 4
0128 9
50665 7
937 2
55960 5
564 9
50308 8
57308 6
215 4
377088 3
340 1
1136 6
37 2
58 8
1375 8
655673 10
29 4
153 3
583185 8
812 7
361 9
394 5
60153 1
65433 4
267825 10
969 9
027147 10
08343 8
57568 1
805683 8
83 8
97 9
7734 5
5005 7
216926 7
3560 7
50 1
679 9
16813 3
1415 8
751 10
===========================================================
Adv sche
#include<iostream>
using namespace std;
int n;
int L[3],P[3];
int bd[51],kt[51];
int maxx;
int kq[51];
int visit[51];
int tgbd,tgkt;
void reset()
{
for (int i = 0; i < 51; i++) visit[i] = 0;
}
bool kiemtravitri(int vt, int dodai)
{
int x = 0;
int a = visit[vt], b = visit[vt + dodai];
if(vt+dodai>50)
{
for(int i=vt;i<51;i++) x+=visit[i];
}
else
{
for (int i = vt; i <= vt + dodai; i++) x+=visit[i];
}
if (a + b == 0 && x == 0) return true;
else if (a + b == 1 && x <= 1) return true;
else if (a + b == 2 && x <= 2 && dodai>1) return true;
return false;
}
void saochep(int A[],int B[],int bot,int top) // sao chep A sang B
{
for (int i = bot; i <= top; i++) B[i] = A[i];
}
void abcd(int idx)
{
for(int i=tgbd;i<=tgkt;i++)
{
if(visit[i]==1 && visit[i+1]==1) continue;
if(visit[i]==0 && visit[i+1]==1 && L[idx]>1) continue;
if(kiemtravitri(i,L[idx]))
{
if(idx==2)
{
int tmp1[51];
saochep(kq,tmp1,0,n-1);
for (int a = 0; a < n; a++)// xet tung khach hang
{
//bd[a],kt[a]
if (bd[a] <= i && bd[a]+kt[a] >= i + L[idx] && kq[a] < P[idx]) kq[a] = P[idx];
}
int temp = 0;
for (int i = 0; i < n; i++) temp += kq[i];
if (temp > maxx) maxx = temp;
saochep(tmp1,kq,0,n-1);
}
else
{
int tmp1[51],tmp2[51];
saochep(visit,tmp1,1,50);
saochep(kq,tmp2,0,n-1);
//
for (int k = i; k <= i + L[idx]; k++)
{
visit[k] = 1;
if(k>50) break;
}
for (int a = 0; a < n; a++)// xet tung khach hang
{
//bd[a],kt[a]
if (bd[a] <= i && bd[a]+kt[a] >= i + L[idx] && kq[a] < P[idx]) kq[a] = P[idx];
}
//
abcd(idx+1);
//
saochep(tmp1, visit,1,50);
saochep(tmp2, kq, 0, n - 1);
}
}
}
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for (int tc = 1; tc <= t; tc++)
{
cin >> n;
for (int i = 0; i < 3; i++) cin >> L[i];
for (int i = 0; i < 3; i++) cin >> P[i];
for (int i = 0; i < n; i++)
{
cin >> bd[i] >> kt[i];
}
//tim khoang thoi gian [min ,max]
tgbd = bd[0];
tgkt = bd[0] + kt[0];
for (int i = 0; i < n; i++)
{
if (bd[i] < tgbd) tgbd = bd[i];
if (bd[i] + kt[i] > tgkt) tgkt = bd[i] + kt[i];
}
//
maxx = 0;
for (int i = 0; i < n; i++) kq[i] = 0;
reset();
//
abcd(0);
//
cout << "Case #" << tc << endl << maxx << endl;
}
return 0;
}
////
[Ràng buộc]
- Số lượng khách truy cập N (1 ≤ N ≤ 50)
- Thời gian đến Ai, khoảng thời gian Di của mỗi khách truy cập và độ dài của mỗi Quảng cáo L1, L2, L3 được cho là số nguyên (1 ≤ Ai, Di, L1, L2, L3 ≤ 50)
- Ai + Di ≤ 50
- L1 + L2 + L3 ≤ 50
- Thời gian bắt đầu của Quảng cáo: 1 ≤ thời gian bắt đầu ≤ 50
- P1, P2, P4 là các số nguyên (1 ≤ P1, P2, P3 ≤ 1000)
[Nhập]
Dòng thứ 1 cho T - tổng số TC (T ≤ 50)
Trong mỗi TC :
- Dòng thứ 1 chứa N, L1, L2, L3, P1, P2, P3 theo thứ tự này
- Các dòng N tiếp theo: mỗi dòng cho biết thời gian đến và khoảng thời gian Di của mỗi khách truy cập
5 // Số trường hợp kiểm thử T = 5
7 1 2 3 1 2 3 // Trường hợp thử nghiệm 1 N = 7, L1 = 1, L2 = 2, L3 = 3, P1 = 1, P2 = 2, P3 = 3
2 2 // A1 = 2, D1 = 2
6 4 // ...
3 3
7 2
1 1
2 1
1 10
4 3 2 1 6 4 3
1 5
1 3
2 4
2 2
...
[Ra]
Ra đặt tổng số điểm tối đa mà khách truy cập có thể nhận được từ việc xem quảng cáo.
Trường hợp #1
12
Trường hợp #2
18
Trường hợp #3
17
Trường hợp #4
16
Trường hợp #5
17998
======================================================================================
tat den
#include <iostream>;
using namespace std;
int N,K,A[200],dem,MAX;
void BackTrack(int index)
{
if(index==4)
{
dem = 0;
for(int i=1;i<=N;i++)
{
if(A[i]==0)
{
dem++;
}
}
if(dem>MAX)
{
MAX = dem;
}
return;
}
for(int i=1;i<=K;i++)
{
for(int j=0;i+j*(i+1)<=100;j++)
{
int a = i+j*(i+1);
if(A[a]==0)
{
A[a] =1;
}else
{
A[a] =0;
}
}
dem = 0;
for(int i=1;i<=N;i++)
{
if(A[i]==0)
{
dem++;
}
}
if(dem>MAX)
{
MAX = dem;
}
BackTrack(index+1);
for(int j=0;i+j*(i+1)<=100;j++)
{
int a = i+j*(i+1);
if(A[a]==0)
{
A[a] =1;
}else
{
A[a] =0;
}
}
}
}
int main()
{
// freopen("Text.txt","r",stdin);
int T;
cin>>T;
for(int tc=1;tc<=T;tc++)
{
cin>>N>>K;
for(int i=1;i<=N;i++)
{
cin>>A[i];
}
MAX = 0;
BackTrack(1);
cout<<"#"<<tc<<" "<<MAX<<endl;
}
return 0;
}
/////
Tắt Đèn
Nhà Ngô Tất Tố hiện tại đang có N bóng đèn và có K khóa. Các khóa được nối vào các bóng đèn theo quy luật như sau:
Khóa thứ K sẽ được nối vào các bóng đèn thứ K+n(K+1) (n>=0; 0<=K+n(K+1) <=N).
Ví dụ:
Khóa thứ 1 sẽ nối vào các bóng đèn số 1, 3, 5, 7,9…
Khóa thứ 2 sẽ nối vào các bóng đèn số 2, 5, 8, 11,…
Khóa thứ 3 sẽ nối vào các bóng đèn số 3, 7, 11, 15,…
Nếu khóa thứ k được thay đổi trạng thái, tất cả các bóng đèn đang nối với khóa k sẽ chuyển trạng thái (Bật->Tắt, tắt->bật).
Ngô Tất Tố mỗi lần ra khỏi nhà sẽ đóng khóa sao cho số lượng bóng đèn được tắt là lớn nhất. Anh ta phát hiện ra rằng sự thay đổi trạng thái các khóa khác nhau để tắt có thể có số lượng đèn khác nhau được tắt. Anh ta đang nghĩ đến làm sao nếu chỉ thay đổi trạng thái khóa tối đa 3 lần sẽ tắt được nhiều bóng điện nhất. Mặc dù là một nhà toán học nhưng anh ấy đang bận sáng tác thơ cho cho kỳ thi sắp tới. Nên anh ấy cần các bạn nhân viên tìm ra phương pháp tối ưu để tắt đèn với tối đa 3 lần tác động vào khóa^.^
Input:
Dòng 1 chứa số T là số TC.
Mỗi testcase bao gồm các thông tin sau:
- Dòng đầu tiên chứa số lượng bóng đèn N và số Khóa K (10<=N<=100, 3<=K<=10);
- Dòng tiếp theo là N bóng đèn, mỗi bóng đèn nhận 1 trong 2 trạng thái: 1 là bật, 0 là tắt.
OutPut:
In ra số lượng bóng đèn tối đa có thể tắt tại mỗi case.
Đáp số của mỗi TC in ra trên 1 dòng theo định dạng:
# TC Answer
Ví dụ:
Input
1
10 3 (10 bóng đèn và 3 khóa)
0 0 1 1 1 1 0 0 1 0 (lần lượt là 10 trạng thái của 10 bóng đèn, 1 là đang bật, 0 là đang tắt)
Output:
#1 6
Giải thích: Chọn tác động vào công tắc thứ 1, các bóng đèn sau sẽ bị thay đổi trạng thái:1 3 5 7 9
=================================================================
hugo thi chay
#include <iostream>;
using namespace std;
int M,D,tg,MIN;
int A[2][6];
void BackTrack(int index, int tgc, int nangluong, int d)
{
if(tgc>MIN || nangluong<=0 ||index>5)
{
return;
}
if(d<=0)
{
if(MIN>tgc)
{
MIN = tgc;
}
return;
}
int sobuoc = nangluong/A[1][index];
if(sobuoc>=d)
{
int thoigian = tgc+ d*A[0][index];
if(MIN>thoigian)
{
MIN = thoigian;
}
return;
}
for(int i=sobuoc;i>=0;i--)
{
int chayduoc = i;
int nangluongmat = i*A[1][index];
int thoigianchay = i*A[0][index];
BackTrack(index+1, tgc+thoigianchay, nangluong-nangluongmat, d-chayduoc);
}
}
int main()
{
// freopen("Text.txt","r",stdin);
int T;
cin>>T;
for(int tc=1;tc<=T;tc++)
{
cin>>M>>D;
for(int i=1;i<=5;i++)
{
int a,b;
cin>>a>>b;
A[0][i] = a*60 +b;
cin>>A[1][i];
}
for(int i=1;i<=5;i++)
{
for(int j=i+1;j<=5;j++)
{
if(A[0][i]>A[0][j])
{
int tg = A[0][i];
A[0][i] = A[0][j];
A[0][j] = tg;
int tg1 = A[1][i];
A[1][i] = A[1][j];
A[1][j] = tg1;
}
}
}
MIN = 999999;
BackTrack(1,0,M,D);
cout<<"Case #"<<tc<<endl;
if(MIN == 999999)
{
cout<<"-1"<<endl;
}else
{
cout<<MIN/60<<" "<<MIN%60<<endl;
}
}
return 0;
}
////////
Hugo thi chạy
Sắp tới công ty nên Hugo làm việc tổ chức sự kiện Olympic dành cho toàn bộ nhân viên. Có rất nhiều bộ môn thi đấu như Bóng bàn, cầu long, cờ vua, cờ tướng, bơi lội, và có cả thể thao điện tử nữa. Là một người quan tâm tới sức khỏe của bản thân vì vậy Hugo thường xuyên chạy bộ để rèn luyện sức khỏe. Thật may trong các môn thi đấu Olympic có hạng mục này. Trong quá trình tập luyện Hugo đã luyện cho mình được 5 kiểu chạy khác nhau, mỗi kiểu chạy sẽ tiêu tốn số lượng năng lượng nhất định và thời gian chạy hết 1km là khác nhau. Mỗi kiểu chạy sẽ sử dụng cho 1km.
Năng lượng của Hugo là có hạn, nếu sử dụng vượt Hugo sẽ bị bệnh.
Sau khi tham khảo thông tin Hugo biết được quãng đường cần chạy bộ D của cuộc thi. Nhân viên y tế có thể giúp Hugo tính toán được số năng lượng tối đa của Hugo.
Cho thông tin của 5 kiểu chạy của Hugo bao gồm số phút, số giây (số phút <= 6 và số giây <= 60) và số năng lượng tiêu tốn.
Hãy tính thời gian ngắn nhất để Hugo về đích mà không bị bệnh.
Input
Dòng đầu số test T (T<=50)
Mỗi test bao gồm 2 dòng
Dòng 1 chứa số năng lượng tối đa M <=60 và chiều dài quãng đường D<=40km
Dòng thứ 2 chứa thông tin của 5 kiểu chạy lần lượt là số phút, số giây, số năng lượng tiêu tốn
Output
In ra thời gian ngắn nhất để Hugo về đích mà không bị bệnh theo dạng số phút, số giây. Nếu không thể hãy in ra -1
Input
4
297 10
5 38 23 5 22 12 4 16 6 5 38 20 0 20 17
192 10
2 6 12 6 5 24 2 22 22 4 13 12 4 30 16
503 10
1 42 20 1 8 14 0 33 15 2 6 6 5 3 16
122 10
2 37 21 3 59 22 6 0 22 4 56 5 0 9 10
Output
Case #1
3 20
Case #2
21 0
Case #3
5 30
Case #4
1 30
=======================================================================
prime ring
#include <iostream>;
using namespace std;
int N,dem;
int A[20],V[20];
bool checkSoNT(int n)
{
if(n<2) return false;
for(int i=2;i<n;i++)
{
if (n % i == 0)
return false;
}
return true;
}
void BackTrack(int index, int a)
{
if(index==N)
{
if(checkSoNT(A[0]+a))
{
dem++;
}
return;
}
for(int i=0;i<N;i++)
{
int x = A[i]+a;
if(V[i]==0 && checkSoNT(x))
{
V[i]=1;
BackTrack(index+1, A[i]);
V[i]=0;
}
}
}
int main()
{
// freopen("Text.txt","r",stdin);
int T;
cin>>T;
for(int tc=1;tc<=T;tc++)
{
cin>>N;
for(int i=0;i<N;i++)
{
cin>>A[i];
V[i]=0;
}
V[0]=1;
dem =0;
BackTrack(1,A[0]);
cout<<"Case "<<tc<<": ";
cout<<dem<<endl;
}
return 0;
}
//////
Một vòng gồm N phần tử hình tròn. Trong mỗi hình tròn sẽ chứa một số nguyên P và tổng hai số nguyên trong hai hình tròn cạnh nhau trên vòng tròn tạo thành một số nguyên tố. Nhiệm vụ của bạn là với một chuỗi gồm N phần tử số nguyên, đưa ta tổng số cách xếp N phần tử đó vào vòng tròn thỏa mãn yêu cầu trên.
Ví dụ
Ta có đầu vào là một dãy gồm 6 phần tử: 1, 2, 3, 4, 5, 6. Thì đầu ra sẽ có 2 cách xếp là cách 1: 1 - 4 - 3 - 2 - 5 - 6 và cách 2: 1 - 6 - 5 - 2 - 3 - 4
Input
Dòng đầu liên là T chính là số testcase (T ≤ 100). Mỗi testcase sẽ bao gồm 2 dòng:
Dòng đầu tiên là N chính là số lượng phần tử các số nguyên. (3 ≤ N ≤ 16)\
Dòng thứ hai là một dãy gồm N số nguyên P ( 1 ≤ P ≤ 50)
Output
Kết quả được in ra trên một dòng theo định sạng sau: “Case number_testcase: answer”
Sample
Input
2
8
1 2 3 4 5 6 7 8
6
1 2 3 4 5 6
Output
Case 1: 4
Case 2: 2
=================================================================
sum it up
#include<iostream>
using namespace std;
int tong,n;
int A[15];
int used[15];
int dem;
int mangkiemtra[1000][15];
int stt;
void reset()
{
for(int i=0;i<1000;i++)
for(int j=0;j<15;j++) mangkiemtra[i][j]=0;
}
bool kiemtratrunglap(int temp[],int sopt)
{
for(int i=0;i<stt;i++)
{
if(mangkiemtra[i][0]==sopt)
{
bool flag=true;
for(int j=1;j<=sopt;j++)
{
if(temp[j]!=mangkiemtra[i][j])
{
flag=false;
break;
}
}
if(flag)
{
return false;
}
}
}
return true;
}
void back(int idx)
{
for(int i=0;i<=1;i++)
{
used[idx]=i;
if(idx==n-1)
{
//
int tmp=0;
for(int j=0;j<n;j++) tmp+=used[j]*A[j];
if(tmp==tong)
{
//tao mang temp luu gia tra A[used[i]==1] va dem sl phan tu(temp luu tu 1)
//sap xep lai mang va dua vao ham kiemtratrung lap
//neu true: dem++, dua tmp vao mangkiemtra[stt] va stt++;
//neu false: ko lam gi ca
int temp[15],sopt=0;
for(int a=0;a<n;a++)
{
if(used[a]==1)
{
sopt++;
temp[sopt]=A[a];
}
}
//sapxep
/*for(int a=1;a<=sopt;a++)
{
for(int b=a+1;b<=sopt;b++)
{
if(temp[a]>temp[b])
{
int x=temp[a];temp[a]=temp[b];temp[b]=x;
}
}
}*/
//
if(kiemtratrunglap(temp,sopt))
{
dem++;
mangkiemtra[stt][0]=sopt;
for(int a=1;a<=sopt;a++) mangkiemtra[stt][a]=temp[a];
stt++;
}
}
}
else
{
back(idx+1);
}
}
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
cin>>tong>>n;
for(int i=0;i<n;i++)
{
cin>>A[i];
used[i]=0;
}
//
dem=0;
stt=0;
reset();
//
back(0);
//
cout<<"#"<<tc<<" ";
if(dem==0) cout<<-1<<endl;
else cout<<dem<<endl;
}
return 0;
}
////
Cho Một tổng t đã xác định và một danh sách n số nguyên, tìm tất cả các tổng riêng biệt bằng cách sử dụng Các số từ danh sách cộng lại với T. Ví dụ: nếu t = 4, n = 6 và danh sách là [4, 3, 2, 2, 1, 1], sau đó có bốn tổng khác nhau bằng 4: 4, 3+1, 2+2 và 2+1+1. (Một số có thể được sử dụng trong một tổng nhiều lần như nó xuất hiện trong danh sách và một num ber duy nhất được tính là một tổng.) Công việc của bạn là giải quyết vấn đề này nói chung.
Nhập
Các Tệp đầu vào sẽ chứa một hoặc nhiều trường hợp kiểm thử, một trường hợp trên mỗi dòng. Mỗi trường hợp kiểm thử chứa tổng, tiếp theo là n, số nguyên trong danh sách, tiếp theo là n Số nguyên x1, . . . ,xn. t sẽ là một số nguyên dương nhỏ hơn 1000, n sẽ là Một số nguyên từ 1 đến 12 (bao gồm) và x1, . . . , xn sẽ dương số nguyên nhỏ hơn 100. Tất cả các số sẽ được phân tách bằng chính xác một khoảng trắng. Các Các số trong mỗi danh sách có thể là sự lặp lại.
Ra
Cho Mỗi trường hợp kiểm thử, xuất ra tổng cách, nếu không phải là đầu ra -1.
Mẫu
Nhập
4
4 6
4 3 2 2 1 1
5 3
2 1 1
400 12
50 50 50 50 50 50 25 25 25 25 25 25
20 10
1 2 3 4 5 6 7 8 9 10
Ra
#1 4
#2 -1
#3 2
#4 31
Giải thích
#1
4
3+1
2+2
2+1+1
(neu co 3 o cuoi thi ta se co them truong hop 1 3 thoa man)
===========================================================================================Editor is loading...
Leave a Comment