Untitled
unknown
plain_text
25 days ago
20 kB
5
Indexable
Never
Hugo Về Nhà
Hugo đang trền đường về nhà và cần đi qua 1 đoạn đường B.
Trên đoạn đường đi qua có N cổng. Tại mỗi cổng có 1 số lượng binh sĩ và giá để đi qua cổng đó. Muốn đi qua mỗi cổng Hugo có 3 cách lựa chọn.
1. Pass
Trả số tiền quy định ở cổng đó để được đi qua
2. Hire
Trả gấp đôi số tiền ở cổng đó để thuê số binh sĩ gộp vào đoàn quân của mình
3. battle
Điều kiện để đánh nhau là số quân của Hugo >= số lượng lính tại cổng đó. Có các lưu ý:
+ Hugo k được tính vào số lượng của quân
+ Mỗi người lính chỉ tham gia được vào tối đa 3 trận đánh. Sau 3 trận đánh nếu đi nhóm binh sĩ đó còn sống thì cũng giải tán.
+ Mỗi trận đánh thì tất cả số binh sĩ đều tham gia.
+ Đánh nhau chết theo tỉ lệ 1: 1. Ai tham gia trước sẽ bị chết trước
Input:
Dòng đầu tiên là số lượng trường hợp thử nghiệm
Mỗi trường hợp thử nghiệm sẽ có
Dòng đầu tiên chứa số lượng cổng N
N dòng tiếp theo chứa 2 số là số binh lính và chi phí tại mỗi cổng
Output: In ra chi phí nhỏ nhất Hugo có thể đi qua đoạn đường B
Điều kiện input: số cổng <=20
- 2 <=Số lính và chi phí đi qua <=1000
VD:
Input
2
7
10 100
70 5
80 15
20 60
50 90
30 80
10 10
9
600 800
300 400
300 400
1000 400
300 600
100 300
600 300
600 500
1000 300
Output:
#1 150
#2 3000
package Lesson_15;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Hugo_Di_Ve_Nha {
static int T, N;
static int door[][], numberSoliders[], count[];
static int min;
public static void backTrack(int k, int price){
if(price >= min) return;
if(k == N){
if(price < min) min = price;
return;
}
// TH: Pass
backTrack(k+1, price + door[k][1]);
///
// TH: Hire
numberSoliders[k] = door[k][0];
backTrack(k+1, price + 2*door[k][1]);
numberSoliders[k] = 0;
///
// TH: Battle
int number = 0;
int tempSoliders[] = new int[21];
int tempCount[] = new int[21];
for (int i = 0; i < k; i += 1)
{
// Phai dung mang tam de luu gia tri vi o duoi bien toan cuc numberSoliders[i]
// bi thay doi trong moi lan thuc hien BackTrack
tempSoliders[i] = numberSoliders[i];
tempCount[i] = count[i];
if (numberSoliders[i] >= 0 && count[i] < 3)
number += numberSoliders[i];
}
if (number < door[k][0]) return;
// Nen su dung bien toan cuc sumSolider gan voi gia tri kia.
// Neu thay doi door[k][0] -= numberSoliders[j] thi sai, do door dang de bien toan cuc, moi lan BackTrack ko tra lai dc ve gia tri cu
int sumSolider = door[k][0];
for(int j = 0; j < k; j++){
if (count[j] >= 3 || numberSoliders[j] <= 0) continue;
int mE = sumSolider;
sumSolider -= numberSoliders[j];
numberSoliders[j] -= mE;
if (sumSolider <= 0)
break;
}
for (int i = 0; i <k ; i += 1)
if(count[i] < 3 && numberSoliders[i] > 0)
count[i] += 1;
backTrack(k+1, price);
for(int j = 0; j < k; j++){
numberSoliders[j] = tempSoliders[j];
count[j] = tempCount[j];
}
}
public static void main(String[] args) throws FileNotFoundException{
System.setIn(new FileInputStream("Hugo_Di_Ve_Nha"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
N = scanner.nextInt();
door = new int[N][2];
numberSoliders = new int[N];
count = new int[N];
for(int i = 0; i < N; i++){
door[i][0] = scanner.nextInt(); // So linh
door[i][1] = scanner.nextInt(); // Gia tien qua cong
}
min = 123456789;
backTrack(0, 0);
System.out.println("#"+tc+ " " + min);
}
}
}
19
7
10 100
70 5
80 15
20 60
50 90
30 80
10 10
9
600 800
300 400
300 400
1000 400
300 600
100 300
600 300
600 500
1000 300
11
1000 10
700 900
400 500
300 10
900 900
300 10
50 900
50 900
700 900
500 900
50 10
20
896 546
543 216
454 310
408 367
40 602
252 582
954 627
850 234
763 479
232 278
301 538
528 508
936 154
629 443
758 336
432 700
882 256
278 738
517 882
317 136
20
410 610
831 909
675 629
421 774
386 869
544 219
492 414
996 557
499 482
231 285
804 978
304 881
489 911
75 315
927 648
252 914
330 396
937 133
495 882
813 717
14
780 374
782 572
748 240
2 733
448 676
33 434
271 348
510 743
113 690
195 846
322 560
794 555
642 923
187 830
14
920 329
986 746
32 60
385 811
146 315
479 943
164 105
387 935
135 831
178 710
227 928
203 725
389 317
783 988
14
341 212
10 563
679 198
139 33
319 106
265 611
962 132
703 185
701 747
929 416
339 131
345 463
669 975
80 602
15
620 487
479 722
516 554
44 779
683 607
718 652
46 458
54 264
170 322
200 970
574 773
964 788
793 55
905 393
592 439
15
226 926
887 434
17 257
418 214
254 86
906 363
968 479
755 40
682 136
878 735
195 671
392 110
597 490
356 123
914 927
16
544 819
810 448
561 926
692 933
287 999
104 556
781 602
357 55
3 831
780 192
66 917
515 535
94 115
761 187
894 552
342 769
15
627 654
148 989
732 126
495 51
236 271
56 297
945 731
4 324
546 211
965 111
397 825
844 100
160 15
670 287
216 335
18
826 585
37 71
866 415
639 764
696 802
632 10
530 758
659 165
32 922
475 235
806 914
268 160
371 251
653 130
315 281
143 46
933 449
58 719
19
307 167
216 90
154 513
356 339
439 622
713 435
137 976
910 414
719 837
703 331
683 507
735 846
27 667
562 118
116 405
388 336
499 326
820 515
658 569
20
443 547
881 9
89 287
215 39
31 580
439 61
952 217
746 76
949 522
882 713
928 12
813 478
495 245
60 543
806 824
594 883
300 959
662 902
667 582
854 69
20
412 397
81 799
237 391
884 756
350 928
707 715
81 636
493 617
959 588
703 916
378 48
647 467
778 592
495 204
218 348
688 948
506 776
544 363
730 526
861 817
20
94 881
892 493
452 419
20 865
15 395
275 137
571 743
857 347
434 948
629 743
66 69
327 818
19 681
447 862
198 985
328 272
596 854
475 25
342 606
779 448
20
559 274
973 447
994 369
898 149
325 855
973 983
59 306
123 41
441 399
429 848
274 132
669 864
805 944
682 522
175 509
116 18
418 675
72 430
472 718
591 511
20
595 259
981 834
193 595
856 520
126 685
210 537
252 807
937 335
501 756
157 793
66 404
363 911
380 509
215 223
366 160
666 916
337 961
52 101
370 99
435 394
// Hugo di tau
package Lesson_15;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Hugo_Di_Tau {
static int T, N, C;
static int spots[]; // Trang thai ghe ngoi tren tau
static boolean visited[]; // Status Gate đã đc duyệt hay chưa
static int gates[][]; // So luong nguoi dang wait at Gate
static int answer;
//Ham kiem tra xem cong do da mo de nguoi vao het chua
// True: Open - False: Close
public static boolean isOpened(){
for(int i = 0; i < 3; i++){
if(!visited[i]) return false;
}
return true;
}
// Khoang cach tu cong do den vi tri ben phai gan nhat
// Neu khong con cho ngoi ben phai thi tra ve gia tri rat lon
public static int distanceToRightSpot(int start){
for(int i = start; i <= N; i++){
if(spots[i] == -1 ) return i - start;
}
return 1000000;
}
// Khoang cach tu cong do den vi tri ben trai gan nhat
public static int distanceToLeftSpot(int start){
for(int i = start; 1 <= i; i--){
if(spots[i] == -1 ) return start - i;
}
return 1000000;
}
public static void backTrack(int sum){
// Kiem tra cong da mo het chua ,neu da mo het tra ve gia tri
if(isOpened()){
if(answer > sum) answer = sum;
return;
}
for(int i = 0; i < 3; i++){
// Cong da dc mo thi bo qua
if(visited[i]) continue;
// Cong chua mo thi tham cong do va danh dau da tham
visited[i] = true;
int add = gates[i][1];
// Xep het nguoi tai cong do vao vi tri. De lai 1 nguoi cuoi cung de check
for(int j = 0; j < gates[i][1] - 1; j++){
int left = distanceToLeftSpot(gates[i][0]); // Kc cong do den trai
int right = distanceToRightSpot(gates[i][0]);
// Kiem tra khoang cach khi them vao trai/ phai. Ben nao nho hon thi lay
if(left < right)
{
spots[gates[i][0] - left] = i;
add += left;
}
else
{
spots[gates[i][0] + right] = i;
add += right;
}
}
// Tra ve khoang cach nguoi cuoi cung cua cong do so voi ben trai/ phai
int left = distanceToLeftSpot(gates[i][0]);
int right = distanceToRightSpot(gates[i][0]);
// Neu khoang cach do khac nhau thi check xem ben trai hay phai nho hon de ta xep
if(left != right)
{
if(left < right)
{
spots[gates[i][0] - left] = i;
add += left;
}
else
{
spots[gates[i][0] + right] = i;
add += right;
}
backTrack(sum + add);
}
// Neu khoang cach bang nhau thi can dat thu vao ca 2 ben trai va phai
else
{
add += left;
spots[gates[i][0] + right] = i;
backTrack(sum + add);
spots[gates[i][0] + right] = -1;
spots[gates[i][0] - left] = i;
backTrack(sum + add);
spots[gates[i][0] -left] = -1;
}
// Tra lai cong chua tham de backTrack lai
visited[i] = false;
// Tra lai vi tri cong do da ngoi
for(int j = 1; j <= N; j++){
if(spots[j] == i) spots[j] = -1;
}
}
}
public static void main(String[] args) throws FileNotFoundException{
System.setIn(new FileInputStream("Hugo_Di_Tau"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
N = scanner.nextInt();
gates = new int[3][2];
for(int i = 0; i < 3; i++){
gates[i][0] = scanner.nextInt(); // Vi tri cong
gates[i][1] = scanner.nextInt(); // So luong nguoi trc cong
}
spots = new int[N+1];
visited = new boolean[N+1];
for(int i = 1; i <= N; i++){
spots[i] = -1;
}
answer = 10000;
backTrack(0);
System.out.println("Case #"+ tc );
System.out.println(answer);
}
}
}
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
// Mario
Mario cần phải di chuyển từ vị trí có giá trị bằng 2 và ăn vàng ở ô có giá trị bằng 3
0 là nhữngô Mario không thể qua
1 là nhữngô Mario có thể qua
2 là vị trícủa Mario
3 là vị trí Mario cần di chuyển đến
Các vị trí này được thể hiện bằng ma trận NxM( 2<=N,M<=50)
Mario có thểdi chuyển theo hàng ngang hoặc hàng dọc
Hàng ngang mario chỉ nhảy được tối đa 1 bước
Hàng dọc mario có thể nhảy được “h” bước
Tìm bước nhảy “h” tối thiểu để Mario có thể ăn được vàng
Sample Input
3
5 8
1 1 1 1 0 0 0 0
0 0 0 3 0 1 1 1
1 1 1 0 0 1 0 0
0 0 0 0 0 0 1 0
2 1 1 1 1 1 1 1
5 6
0 1 1 1 0 0
3 1 0 1 1 0
0 0 0 0 1 1
0 0 0 0 0 1
2 1 1 1 1 1
9 13
0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 1 3
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 1 1 1 1 1 1 1 1 1 1 1
Sample output
Case #1
2
Case #2
1
Case #3
3
package Lesson_15;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Mario {
static int T, N, M;
static int map[][];
static int startR, startC, endR, endC;
static int cr, cc, nr, nc;
static boolean visited[][];
static int dx[] = {0, -1, 0, 1};
static int dy[] = {-1, 0, 1, 0};
public static class Queue{
static int front, rear, Data[];
public Queue() {
this.front = this.rear = -1;
Data = new int[1000000];
}
public static void reset(){
front = rear = -1;
}
public static void enQueue(int value){
Data[++rear] = value;
}
public static int deQueue(){
return Data[++front];
}
public static boolean is_Empty(){
return front == rear;
}
}
public static void main(String[] args) throws FileNotFoundException{
System.setIn(new FileInputStream("Mario"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
N = scanner.nextInt();
M = scanner.nextInt();
map = new int[N][M];
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
map[i][j] = scanner.nextInt();
if(map[i][j] == 2){
startR = i;
startC = j;
}
if(map[i][j] == 3){
endR = i;
endC = j;
}
}
}
Queue rQueue = new Queue();
Queue cQueue = new Queue();
boolean check = false;
int h = 1;
while(!check){
for(int k = 1; k <= h; k++){
rQueue.reset();
cQueue.reset();
visited = new boolean[N][M];
rQueue.enQueue(startR);
cQueue.enQueue(startC);
visited[startR][startC] = true;
while(!rQueue.is_Empty()){
cr = rQueue.deQueue();
cc = cQueue.deQueue();
for(int i = 0; i < 4; i++){
nr = cr + k*dx[i];
nc = cc + k*dy[i];
if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if(map[nr][nc] == 3){
check = true;
break;
}
if(!visited[nr][nc] && map[nr][nc] == 1){
visited[nr][nc] = true;
rQueue.enQueue(nr);
cQueue.enQueue(nc);
}
}
if(check) break;
}
if(check) break;
}
if(!check) h++;
}
System.out.println("Case #" + tc);
System.out.println(h);
}
}
}
// Hugo thi chay
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.
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
50
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
313 10
5 33 22 1 27 13 3 21 11 1 24 14 0 56 12
221 10
1 21 13 4 9 17 4 18 5 4 5 13 3 49 19
415 10
1 57 10 5 39 17 5 34 17 1 30 9 5 41 23
156 10
4 24 9 3 30 10 2 54 20 3 14 12 3 27 14
220 10
1 59 21 1 30 20 1 44 7 1 32 8 1 45 8
273 10
6 11 22 6 16 23 3 42 17 4 6 13 2 49 9
442 10
0 3 21 1 59 12 3 16 24 1 25 24 4 54 17
506 11
4 12 6 0 25 22 0 15 23 2 6 13 2 44 24
370 12
3 46 17 0 26 20 6 6 22 1 14 18 2 23 23
143 13
5 4 14 3 52 20 3 56 18 4 10 15 4 27 22
142 14
0 51 5 6 15 22 4 14 6 5 35 20 1 57 21
51 15
5 30 23 6 0 14 2 23 9 5 40 15 4 32 20
110 16
3 8 6 3 52 6 3 8 5 5 29 6 4 25 21
173 17
5 34 15 1 39 23 4 21 7 1 35 21 0 59 18
215 18
4 1 9 6 22 17 5 34 22 4 6 10 3 0 24
462 19
4 2 10 5 27 24 6 35 24 1 42 17 0 26 9
156 20
0 17 18 4 8 20 1 10 22 4 22 17 5 22 8
295 21
4 54 22 6 14 12 1 42 12 5 52 7 2 52 18
239 22
0 56 12 5 17 20 2 14 24 1 48 8 4 45 15
309 23
3 0 23 4 53 23 4 46 19 0 13 11 0 20 9
162 24
0 38 8 3 2 6 5 33 9 4 18 6 0 8 5
329 25
0 37 13 0 35 9 3 24 12 2 50 13 6 56 11
548 26
2 42 17 6 47 22 0 21 6 5 18 6 5 51 5
501 27
0 32 8 3 40 5 3 58 6 1 55 16 1 57 23
254 28
0 45 23 6 59 10 6 34 8 2 24 9 2 42 23
260 29
6 52 6 3 45 15 0 21 6 4 56 9 2 1 17
261 30
3 19 19 1 40 6 0 30 13 4 28 5 6 36 15
443 31
2 13 10 3 50 5 4 52 20 2 40 14 0 45 11
122 32
0 34 17 1 52 12 1 40 11 6 21 22 0 6 9
446 33
4 12 21 4 26 18 3 50 15 2 35 8 2 53 15
283 34
0 27 15 3 19 16 6 15 15 4 26 17 5 43 10
282 35
4 39 20 0 27 6 0 44 18 0 35 9 5 2 6
388 36
1 40 17 5 5 9 2 33 16 4 23 11 4 29 8
54 37
2 9 17 4 48 10 4 57 20 6 20 5 6 7 24
232 38
4 12 11 5 28 21 6 11 6 0 45 15 1 11 5
385 39
2 38 8 4 28 5 2 42 8 3 20 21 2 34 9
383 40
1 36 24 0 52 14 4 39 8 5 55 6 1 28 10
363 40
2 56 6 0 47 14 0 4 23 1 32 17 2 14 17
395 40
4 41 18 3 52 21 6 34 23 6 24 11 1 1 12
592 40
1 52 20 5 59 15 4 57 10 1 36 18 1 31 5
174 40
0 7 7 2 8 11 4 28 9 2 35 19 6 0 18
545 40
5 37 20 3 31 20 6 20 7 0 39 11 0 12 7
551 40
2 44 18 4 3 17 2 23 5 5 55 12 6 32 6
186 40
5 56 15 3 9 24 1 30 12 6 19 15 0 55 22
216 40
5 9 22 5 21 11 5 22 9 4 31 6 5 34 19
442 40
0 25 13 5 14 6 1 23 8 2 15 12 0 58 6Leave a Comment