Untitled
unknown
plain_text
2 years ago
17 kB
52
Indexable
https://send.zcyph.cc/download/176a93f1bd17dfd9/#XnvufzFaR0be0tiMQIXwyg
Given the map of BTS consists of N x M cells. Each cell in map have a cost and can connect to other 6 cells around it. Two cells are connected if they share a same edge.
We call a group of 4 connected cells a cluster. Your program should find the cluster with highest cost sum and print out the square value of its sum
[Input]
- The first line is the number of test cases T (T <= 50)
- In each TC :
+ The first line give the size of the map M, N ( 3 ≤ N, M ≤ 15 )
+ In the next N lines, the cost C (0 ≤ C ≤ 1000) of each cell is given as below rule
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
[Output]
Print out the square value of maximum cluster's sum
Case #1
2250000
Case #2
3748096
Case #3
3928324
Case #4
7236100
Case #5
13104400
#include<iostream>
using namespace std;
enum parity {EVEN = 0, ODD = 1};
int N; // number rows
int M; // number colums
int map[20][20]; // map mat ong
int dxEven[6] = {0,-1,0,1,1,1};
int dyEven[6] = {-1,0,1,1,0,-1};
int dxOdd[6] = {-1,-1,-1,0,1,0};
int dyOdd[6] = {-1,0,1,1,0,-1};
bool visited[20][20];
parity isParity(int i)
{
if(i % 2 == 0)
return ODD; // vi tri le
return EVEN;
}
bool isSafe(int x, int y)
{
if(x >= 0 && x < N && y >= 0 && y < M)
return true;
return false;
}
int maxSum;
void backTrack(int k,int x, int y, int sum)
{
if(k == 3)
{
if(sum > maxSum)
{
maxSum = sum;
}
return;
}
for(int i = 0; i < 6; i++)
{
int xx, yy;
if(isParity(y) == EVEN)
{
xx = x + dxEven[i];
yy = y + dyEven[i];
}
else if(isParity(y) == ODD)
{
xx = x + dxOdd[i];
yy = y + dyOdd[i];
}
if(isSafe(xx,yy) && !visited[xx][yy])
{
visited[xx][yy] = true;
backTrack(k+1,xx,yy, sum + map[xx][yy]);
backTrack(k+1,x,y, sum + map[xx][yy]);
visited[xx][yy] = false;
}
}
}
void input()
{
cin>>M>>N;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
cin>>map[i][j];
}
}
}
void reset()
{
for(int i =0; i< 20; i++)
for(int j =0; j< 20; j++)
{
visited[i][j] = false;
}
}
int main()
{
//freopen("Text.txt","r",stdin);
int T;
cin>>T;
for(int tc = 1; tc <= T; tc++)
{
input(); // nhap input N, M, ma tran value mat ong
reset();
maxSum = 0;
for(int i = 0; i < N; i++)
for(int j = 0; j< M; j++)
{
visited[i][j] = true;
backTrack(0,i,j,map[i][j]);
reset();
}
int ans = maxSum*maxSum;
cout<<"Case #"<<tc<<endl;
cout<<ans<<endl;
}
return 0;
}
Hugo Giao Hàng
Hugo Giao Hàng
Hugo đang làm việc cho công ty Samsung, tuy mức lương ở Samsung không hề nhỏ nhưng vì Hugo là lao động duy nhất trong nhà, vợ của Hugo mới sinh em bé. Hugo muốn kiếm thêm thu nhập để có thể có thêm tiền sữa, bỉm cho con. Hugo quyết định nhận giao bánh pizza ngoài giờ làm. Mỗi ngày, sau khi tan ca Hugo sẽ nhận N chiếc bánh pizza để giao tới N địa điểm khác nhau sau đó trở về nhà. Tuy nhiên do giá xăng dầu đang leo thang, Hugo cần phải giảm tối đang lượng xăng phải tiêu thụ, vì vậy Hugo muốn tính toán xem quãng đường đi giao bánh pizza từ công ty sau đó về nhà là ngắn nhất.
Hãy giúp Hugo với nhé.
Đầu vào
T test case <=50
Dòng đầu tiên chưa 4 số Sx, Sy, Hx, Hy tương ứng là vị trí của công ty và nhà của Hugo trên hệ trục tọa độ Oxy
Dòng tiếp theo bao gồm số N và N cặp số liên tiếp tương ứng là tọa độ các điểm mà Hugo cần giao pizza.
N<=10
Cách tính khoảng cách giữa 2 điểm x1,y1 x2,y2 D = |x1-x2|+|y1-y2|
Đầu ra
In ra quãng đường ngắn nhất Hugo di chuyển từ công ty để giao bánh sau đó trở về nhà.
10
57 61 50 61
5 86 53 4 104 27 3 55 34 69 0
96 47 60 28
5 0 6 43 84 84 35 44 57 95 50
48 32 67 42
5 53 51 92 1 48 19 8 3 82 37
97 28 66 41
5 93 72 9 79 46 31 12 66 54 11
38 62 93 86
5 87 83 40 83 83 26 98 11 74 103
23 42 71 16
5 12 76 47 74 24 5 88 82 45 85
96 85 14 6
5 86 91 104 60 72 35 59 22 58 39
99 49 68 1
5 48 80 96 101 56 88 75 56 25 81
51 14 75 51
5 29 62 103 15 75 84 67 94 96 57
87 39 57 77
5 105 85 31 40 1 88 83 89 29 18
Case #1 393
Case #2 323
Case #3 267
Case #4 294
Case #5 281
Case #6 300
Case #7 219
Case #8 283
Case #9 295
Case #10 344
Cach 1:
#include<iostream>
using namespace std;
int N;
int Edge[15][2];
int visit[15];
int map[15][15];
int Answer;
void BackTrack(int k, int i, int value){
if (value > Answer) return;
if (k == N) Answer = Answer > value + map[i][N+1] ? value + map[i][N+1] : Answer;
for (int j = 1; j<= N; j++) {
if (visit[j] == 0){
visit[j] = 1;
BackTrack(k+1,j,value + map[i][j]);
visit[j] = 0;
}
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = 99999999;
int xa,ya;
cin >> Edge[0][0] >> Edge[0][1] >> xa >> ya;
cin >> N;
Edge[N+1][0] = xa;
Edge[N+1][1] = ya;
for (int i = 1; i <= N; i++){
cin >> Edge[i][0] >> Edge[i][1];
visit[i] = 0;
}
for (int i = 0; i<= N+1; i++){
for (int j = 0; j<= N+1; j++){
map[i][j] = 0;
map[i][j] += Edge[i][0] - Edge[j][0] > 0 ? Edge[i][0] - Edge[j][0] : Edge[j][0] - Edge[i][0];
map[i][j] += Edge[i][1] - Edge[j][1] > 0 ? Edge[i][1] - Edge[j][1] : Edge[j][1] - Edge[i][1];
}
}
for (int i = 1; i<= N; i++){
visit[i] = 1;
BackTrack(1,i,map[0][i]);
visit[i] = 0;
}
// Print the answer to standard output(screen).
cout << "#" << test_case << " " << Answer << endl;
}
return 0;//Your program should return 0 on normal termination.
}
//Cach 2
#include <iostream>
using namespace std;
int kieu[5][3];
int sx,sy,hx,hy;
int n;
int nx[10];
int ny[10];
int kq;
int vis[10];
int abs(int x, int y){
if(x>y) return x-y;
else return y-x;
}
int qd(int x1,int y1, int x2, int y2){
return abs(x1,x2)+abs(y1,y2);
}
void backtrack(int k,int dis,int x, int y){
if(kq<dis+qd(x,y,hx,hy)) return;
if(k==n) {
if(kq>dis+qd(x,y,hx,hy)) kq=dis+qd(x,y,hx,hy);
return;
}
for(int i=0; i<n; i++){
if(vis[i]==0){
vis[i]=1;
backtrack(k+1,dis+qd(x,y,nx[i],ny[i]),nx[i],ny[i]);
vis[i]=0;
}
}
}
int main(){
//freopen("input.txt","r",stdin);
int t;
cin>>t;
for (int tc=1; tc<=t;tc++){
cout<<"Case #"<<tc<<" ";
cin>>sx>>sy>>hx>>hy;
cin>>n;
kq=1000000000;
for(int i=0; i<n; i++){
cin>>nx[i]>>ny[i];
}
backtrack(0,0,sx,sy);
cout<<kq<<endl;
}
return 0;
}
Hugo Bán Dầu
Hugo được giao bán dầu trên một mạng lưới đường ống dẫn dầu, mỗi một vị trí sẽ thiết lập một loại đường ống khác nhau dựa vào địa hình. Sau khi đi khảo sát, Hugo biết rằng mạng lưới đường ống được tạo thành từ 7 loại ống như bên dưới.
1. Dầu có thể đi từ trái sang phải từ trên xuống dưới và ngược lại.
2. Dầu có thể đi từ trên xuống dưới và ngược lại
3. Dầu có thể đi từ trái sang phải và ngược lại
4. Dầu có thể đi từ trên sang phải và ngược lại
5. Dầu có thể đi từ dưới sang phải và ngược lại
6. Dầu có thể đi từ dưới sang trái và ngược lại
7. Dầu có thể đi từ trên sang trái và ngược lại
Chỉ các đường ống có kết nối mới cho phép dầu đi qua. Hai đường ống được gọi là có kết nối nếu chúng có chung điểm cuối. Ví dụ:
Tuy nhiên, để bán dầu, Hugo cần phải bơm dầu vào đường ống. Sức người có hạn, Hugo chỉ có thể bơm dầu trong một khoảng thời gian nhất định, mỗi một giờ dầu mới chảy được hết một đường ống. Ví dụ: Hugo có thể bơm dầu trong 3 giờ, điều đó có nghĩa là từ vị trí bơm dầu, dầu chỉ có thể chảy đến tối đa xa nhất cách đó 3 ô. Dầu có thể chảy theo bất kỳ hướng nào miễn là có kết nối
Đưa ra một ma trận mạng lưới đường ống và vị trí bơm dầu của Hugo, giới hạn thể lực của Hugo, hãy tính toán và in ra tổng số đường ống mà dầu đã chảy qua.
[Constraints]
- Hugo luôn được đặt tại ô có đường ống dẫn dầu
[Input]
- Số trường hợp thử nghiệm T (T <= 50)
- Mỗi trường hợp thử nghiệp dòng đầu tiên chứa :
+ kích thước ma trận N x M (5 <= N, M <= 50)
+ vị trí Hugo (chỉ số bắt đầu từ 0)
+ thể lực của Hugo P (1 <= P <= 20)
- Chi tiết của ma trận được cho trong N hàng tiếp theo. Giá trị C trong mỗi ô là giá trị đại diện cho loại đường ống, tổng số 7 loại, 0<=C<=7, giá trị 0 nghĩa là không có đường ống.
//c1
#include <iostream>
using namespace std;
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
int n,m,sx,sy,e;
int vis[50][50];
int a[50][50];
int qx[10000000];
int qy[10000000];
int qz[10000000];
int f,r;
void push(int x, int y){
r++;
qx[r]=x;
qy[r]=y;
//qz[r]=z;
}
void pop(int &x, int &y){
f++;
x=qx[f];
y=qy[f];
//z=qz[f];
}
bool check(int x, int y, int i){
int xx=x+dx[i];
int yy=y+dy[i];
if(a[xx][yy]==0) return false;
if(xx<0||xx>=n||yy<0||yy>=m) return false;
if(a[x][y]==1){
if(a[xx][yy]==1) return true;
if(i==0){
if(a[xx][yy]==2||a[xx][yy]==4||a[xx][yy]==7) return true;
}
if(i==1){
if(a[xx][yy]==3||a[xx][yy]==4||a[xx][yy]==5) return true;
}
if(i==2){
if(a[xx][yy]==3||a[xx][yy]==6||a[xx][yy]==7) return true;
}
if(i==3){
if(a[xx][yy]==2||a[xx][yy]==5||a[xx][yy]==6) return true;
}
}
if(a[x][y]==2){
if(i==0){
if(a[xx][yy]==1||a[xx][yy]==4||a[xx][yy]==7||a[xx][yy]==2) return true;
}
if(i==3){
if(a[xx][yy]==1||a[xx][yy]==5||a[xx][yy]==6||a[xx][yy]==2) return true;
}
}
if(a[x][y]==3){
if(i==1){
if(a[xx][yy]==1||a[xx][yy]==4||a[xx][yy]==3||a[xx][yy]==5) return true;
}
if(i==2){
if(a[xx][yy]==1||a[xx][yy]==3||a[xx][yy]==6||a[xx][yy]==7) return true;
}
}
if(a[x][y]==4){
if(i==3){
if(a[xx][yy]==1||a[xx][yy]==5||a[xx][yy]==6||a[xx][yy]==2) return true;
}
if(i==2){
if(a[xx][yy]==1||a[xx][yy]==3||a[xx][yy]==6||a[xx][yy]==7) return true;
}
}
if(a[x][y]==5){
if(i==0){
if(a[xx][yy]==1||a[xx][yy]==4||a[xx][yy]==7||a[xx][yy]==2) return true;
}
if(i==2){
if(a[xx][yy]==1||a[xx][yy]==3||a[xx][yy]==6||a[xx][yy]==7) return true;
}
}
if(a[x][y]==6){
if(i==0){
if(a[xx][yy]==1||a[xx][yy]==4||a[xx][yy]==7||a[xx][yy]==2) return true;
}
if(i==1){
if(a[xx][yy]==1||a[xx][yy]==4||a[xx][yy]==3||a[xx][yy]==5) return true;
}
}
if(a[x][y]==7){
if(i==1){
if(a[xx][yy]==1||a[xx][yy]==4||a[xx][yy]==3||a[xx][yy]==5) return true;
}
if(i==3){
if(a[xx][yy]==1||a[xx][yy]==5||a[xx][yy]==6||a[xx][yy]==2) return true;
}
}
return false;
}
int main(){
// freopen("input.txt", "r", stdin);
//nhap lieu
int t;
cin>>t;
for(int tc=1; tc<=t; tc++){
cout<<"Case #"<<tc<<endl;
f=r=-1;
cin>>n>>m;
cin>>sx>>sy>>e;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin>>a[i][j];
vis[i][j]=1000000;
}
}
int dem=0;
push(sx,sy);
vis[sx][sy]=1;
while(f!=r){
pop(sx,sy);
if(vis[sx][sy]==e) break;
for(int i=0; i<4; i++){
if(check(sx,sy,i)){
if(vis[sx+dx[i]][sy+dy[i]]>vis[sx][sy]+1){
vis[sx+dx[i]][sy+dy[i]]=vis[sx][sy]+1;
push(sx+dx[i],sy+dy[i]);
}
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(vis[i][j]!=1000000) dem++;
}
}
cout<<dem<<endl;
}
return 0;
}
/// cach2
#include<iostream>
using namespace std;
int dirict[55][55][5];
int visit[55][55];
int N,M,xStart,yStart,times;
int Answer;
int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0,-1};
int startQ,endQ,Queue[1005][2];
void push(int x, int y){
Queue[endQ][0] = x;
Queue[endQ][1] = y;
endQ++;
}
void BFS(){
while (startQ < endQ) {
int x = Queue[startQ][0];
int y = Queue[startQ][1];
startQ++;
if (visit[x][y] == times) break;
Answer++;
for(int i = 0; i< 4; i++){
int xNext = x+dx[i];
int yNext = y+dy[i];
if (xNext >= 0 && yNext >=0){
if (visit[xNext][yNext] == -1){
int check = false;
if( (i == 0 && dirict[x][y][1] + dirict[xNext][yNext][4] == 5)
|| (i == 1 && dirict[x][y][3] + dirict[xNext][yNext][2] == 5)
|| (i == 2 && dirict[x][y][4] + dirict[xNext][yNext][1] == 5)
|| (i == 3 && dirict[x][y][2] + dirict[xNext][yNext][3] == 5) ) {
check = true;
}
if (check) {
visit[xNext][yNext] = visit[x][y] + 1;
push(xNext,yNext);
}
}
}
}
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
ios::sync_with_stdio(false);
/*
The freopen function below opens input.txt in read only mode and
sets your standard input to work with the opened file.
When you test your code with the sample data, you can use the function
below to read in from the sample data file instead of the standard input.
So. you can uncomment the following line for your local test. But you
have to comment the following line when you submit for your scores.
*/
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> T;
/*
Read each test case from standard input.
*/
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = 0;
/////////////////////////////////////////////////////////////////////////////////////////////
/*
Please, implement your algorithm from this section.
*/
/////////////////////////////////////////////////////////////////////////////////////////////
cin >> N >> M >> xStart >> yStart >> time;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
visit[i][j] = -1;
int t;
dirict[i][j][1] = 0;
dirict[i][j][2] = 0;
dirict[i][j][3] = 0;
dirict[i][j][4] = 0;
cin >> t;
switch (t){
case 1:
dirict[i][j][1] = 1;
dirict[i][j][2] = 2;
dirict[i][j][3] = 3;
dirict[i][j][4] = 4;
break;
case 2:
dirict[i][j][1] = 1;
dirict[i][j][4] = 4;
break;
case 3:
dirict[i][j][2] = 2;
dirict[i][j][3] = 3;
break;
case 4:
dirict[i][j][1] = 1;
dirict[i][j][3] = 3;
break;
case 5:
dirict[i][j][3] = 3;
dirict[i][j][4] = 4;
break;
case 6:
dirict[i][j][2] = 2;
dirict[i][j][4] = 4;
break;
case 7:
dirict[i][j][1] = 1;
dirict[i][j][2] = 2;
break;
}
}
}
startQ = 0;
endQ = 0;
for(int i = 0; i < N; i++){
dirict[i][M][1] = 0;
dirict[i][M][2] = 0;
dirict[i][M][3] = 0;
dirict[i][M][4] = 0;
}
for(int i = 0; i < M; i++){
dirict[N][i][1] = 0;
dirict[N][i][2] = 0;
dirict[N][i][3] = 0;
dirict[N][i][4] = 0;
}
push(xStart,yStart);
visit[xStart][yStart] = 0;
BFS();
// Print the answer to standard output(screen).
cout << "Case #" << test_case << endl << Answer << endl;
}
return 0;//Your program should return 0 on normal termination.
}
Hugo thi chạy
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.
#include <iostream>
using namespace std;
int kieu[5][3];
int en,d;
int kq;
void backtrack(int k,int time,int en,int v){
if(kq<time) return;
if(en<=0) return;
if(k==d) {
if(kq>time) kq=time;
return;
}
for(int i=v; i<5; i++){
backtrack(k+1,time+kieu[i][0]*60+kieu[i][1],en-kieu[i][2],i);
}
}
int main(){
// freopen("input.txt","r",stdin);
int t;
cin>>t;
for (int tc=1; tc<=t;tc++){
cout<<"Case #"<<tc<<endl;
cin>>en>>d;
kq=1000000000;
for(int i=0; i<5; i++){
cin>>kieu[i][0]>>kieu[i][1]>>kieu[i][2];
}
backtrack(0,0,en,0);
if(kq==1000000000) {
cout<<"-1"<<endl;
continue;
}
cout<<kq/60<<" "<<kq%60<<endl;
}
return 0;
}
Editor is loading...