# Frog

quoc14
c_cpp
24 days ago
11 kB
4
Indexable
Never
PrimDijktra
```Level 4
The Frog

Mot dam nuoc co n chiec la nam sat mat nuoc. 1 con ech dang ngoi tren chiec la thu 1 va can di chuyen toi chiec la thu n.
Nhung chiec la nay co hinh tron va con ech di chuyen giua 2 chiec la theo quy tac:
Neu kc giua 2 diem gan nhat cua 2 chiec la <= 40cm: con ech co the nhay gan.
Neu kc giua 2 gan nhat cua 2 chiec la > 40cm vaf <= 90cm: con ech co the nhay xa.
neu kc giua 2 diem gan nhat cua 2 chiec la > 90cm: con ech khong the nhay sang.
1 lan nhay gan hau nhu ko ton nang luong nhung 1 lan nhay xa ton rat nhieu nang luong.
Boi vay duong di tu chiec la nay sang chiec la khac cang tot neu so lan nhay xa cang it, trong truong hop so lan nhay xa bang nhau, duong di co so lan nhay gan it hon se tot hon.

Tim duong di tot nhat cho con ech, dua ra so lan nhay xa va so lan nhay gan tren duong di do

Input:
Dong 1: so luong testcase T (<= 10)
Cac testcase duoc dua ra lan luot tu 1 -> T. Moi testcase bao gom cac du lieu:
Dong thu 1 chua so nguyen n (<= 200)
Dong thu i trong n dong tiep theo chua cac so nguyen xi, yi, ri voi (xi, yi) la toa do cua chiec la thu i, ri la ban kinh cua chiec la thu i (0 <= xi, yi, ri <= 10000cm).

Output:
Gom T dong, dong thu i chua output cua testcase thu i: dua ra 2 so nguyen la so lan nhay xa vaf s lan nhay gan tren duong di tot nhat.
Trong truong hop khong co duong di, dua ra -1.

9
2
1 10 10
100 100 15
4
0 10 10
20 60 12
30 10 10
70 10 8
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

-1
0 2
1 1

-1
0 2
1 1
0 5
-1
3 0
11 3
3 8
6 8
//input
9
2
1 10 10
100 100 15
4
0 10 10
20 60 12
30 10 10
70 10 8
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
40
41 67 7
100 169 3
78 158 6
64 105 6
81 27 1
91 195 1
27 36 3
4 102 7
21 116 7
95 47 6
171 138 1
112 67 1
35 94 4
133 73 3
141 111 2
157 37 1
123 141 6
178 116 5
190 42 2
48 46 6
90 129 4
150 6 1
193 148 2
154 156 4
166 176 2
115 39 7
73 186 3
72 70 6
97 112 5
36 155 2
55 174 7
124 166 1
7 137 2
109 9 1
21 188 4
30 13 7
162 55 2
150 91 2
174 20 5
199 68 6
70
41 467 21
100 1169 22
678 558 26
464 905 20
481 27 40
491 595 12
27 636 2
204 302 31
292 382 38
695 647 38
371 738 25
712 467 19
1103 1011 40
333 873 32
653 868 5
44 262 40
837 859 32
778 316 2
590 642 2
1005 290 6
606 1101 40
1148 429 37
84 754 20
1040 166 38
731 1108 12
523 737 14
129 941 37
858 1104 9
221 1145 29
1029 377 35
1186 90 19
636 755 4
950 1150 9
191 7 22
545 509 25
588 422 19
900 191 26
359 24 38
2 350 1
836 974 33
996 21 2
399 468 8
1081 1134 13
799 18 18
127 467 39
617 13 3
935 651 19
356 1198 5
224 208 23
209 589 26
514 1103 28
618 180 35
538 292 12
857 758 1
1156 711 8
876 292 36
200 110 12
189 855 24
182 685 29
226 1017 19
569 954 15
955 1034 27
1087 529 41
1113 874 20
968 818 10
25 77 28
372 959 26
724 223 2
705 1193 12
86 1064 29
86
41 467 21
400 269 17
678 558 13
164 305 8
781 627 18
491 295 19
327 36 8
682 321 17
818 95 14
126 371 11
69 112 16
199 835 17
803 411 17
164 741 12
353 568 6
644 262 22
237 259 12
741 529 9
616 335 15
42 288 11
40 842 15
148 446 2
590 429 17
50 606 16
93 848 6
23 684 1
756 140 17
523 137 1
818 282 6
341 333 8
204 30 8
845 824 21
870 429 4
273 597 13
586 690 10
636 755 18
431 352 5
250 741 11
466 730 22
491 7 8
157 587 12
483 545 22
709 758 22
588 122 21
506 430 2
755 310 2
848 183 8
441 2 19
374 220 21
184 181 5
53 199 19
188 127 6
128 493 9
883 707 2
313 514 10
351 800 14
444 209 8
685 393 22
823 687 11
503 248 11
780 896 15
157 672 17
538 592 11
779 190 2
758 791 16
711 2 17
872 255 1
386 875 10
422 651 12
299 857 9
892 89 16
288 801 22
832 332 12
723 79 15
487 829 22
82 755 17
114 1 11
253 12 7
246 82 20
361 135 13
586 213 9
25 377 15
534 674 19
77 673 19
413 427 7
124 223 9
100
41 467 35
100 1169 17
678 558 41
464 905 6
481 27 8
491 595 15
27 636 10
204 302 28
292 382 34
695 647 13
371 738 22
712 467 8
1103 1011 33
333 873 3
653 868 12
44 262 40
837 859 30
778 316 12
590 642 37
1005 290 10
606 1101 34
1148 429 24
84 754 25
1040 166 27
731 1108 19
523 737 35
129 941 4
858 1104 19
221 1145 3
1173 297 7
1186 90 6
636 755 30
950 1150 16
191 7 40
221 588 39
1030 813 21
900 191 31
359 24 42
2 350 2
836 974 17
996 21 7
399 468 41
1081 1134 12
799 18 9
1110 617 8
651 200 42
224 208 7
1143 523 34
514 1103 15
596 398 36
538 292 33
857 758 18
615 88 5
876 292 30
200 110 4
226 1017 28
776 129 17
955 1034 2
949 637 1
505 488 29
1185 853 31
25 77 5
1033 470 12
1193 1125 12
235 833 14
560 896 6
140 494 8
94 1058 11
123 596 42
524 188 8
677 0 19
835 467 1
805 583 37
1197 749 31
689 344 10
326 211 26
542 1196 25
436 336 36
317 613 20
76 843 30
374 1071 36
230 492 27
715 975 27
211 741 4
415 209 19
347 1177 4
743 754 4
1067 913 12
1164 181 1
978 931 37
377 117 14
906 56 26
1197 2 9
1040 379 8
923 540 36
6 984 20
1093 72 35
464 1003 16
579 1011 16
324 966 42
150
41 467 23
500 169 5
478 358 11
464 705 18
281 827 2
491 995 15
827 436 16
604 902 10
292 382 22
716 718 24
771 538 22
912 667 20
35 894 24
811 322 22
673 664 22
711 253 5
547 644 23
757 37 20
529 778 5
35 190 19
288 106 17
942 264 17
446 805 3
729 370 15
6 101 10
623 84 11
756 840 23
376 931 5
944 439 3
323 537 11
118 82 10
541 833 12
704 930 10
306 673 19
21 745 21
72 270 22
97 512 11
290 161 13
355 767 16
574 31 5
350 150 22
430 107 24
7 337 2
287 753 16
945 909 2
588 422 11
506 30 22
168 900 24
762 655 11
359 624 18
548 483 20
41 602 15
374 20 13
199 668 5
53 999 19
788 127 12
648 483 24
421 310 18
600 249 8
303 224 17
844 609 14
702 195 14
93 343 20
587 314 24
448 200 19
618 580 21
472 622 11
292 38 12
958 191 16
888 156 16
881 998 3
651 21 12
892 389 12
712 600 15
861 688 10
789 255 8
182 285 17
154 721 6
976 329 17
692 425 20
434 549 2
996 687 2
193 195 10
282 455 7
185 53 1
808 832 18
646 982 2
222 129 2
173 466 21
659 292 16
787 905 7
391 202 2
477 414 3
159 833 15
487 297 7
177 773 15
192 985 7
627 802 20
543 924 8
972 61 22
187 360 22
125 576 23
371 466 23
926 10 6
882 86 22
962 123 21
195 525 17
116 30 23
940 851 15
578 365 24
357 324 22
887 801 3
993 384 14
540 111 1
584 734 7
963 607 12
221 870 19
534 556 2
962 548 18
72 818 11
685 90 10
589 990 2
651 740 13
759 192 22
292 997 6
992 824 10
289 944 10
540 245 21
28 543 4
88 943 14
49 681 5
359 257 23
142 196 13
606 173 22
404 705 11
812 375 22
736 141 23
994 256 5
8 262 10
369 878 4
37 410 22
710 484 7
941 790 20
268 318 11
136 630 19
114 439 15
292 600 7
448 882 13
774 779 23
552 182 24
200
41 467 10
334 500 10
169 724 10
478 358 10
962 464 10
705 145 10
281 827 10
995 942 10
827 436 10
391 604 10
902 153 10
292 382 10
421 716 10
718 895 10
771 538 10
869 912 10
667 299 10
35 894 10
703 811 10
322 333 10
673 664 10
253 868 10
547 644 10
662 757 10
37 859 10
723 741 10
529 778 10
316 35 10
190 842 10
288 106 10
40 942 10
264 648 10
446 805 10
890 729 10
370 350 10
6 101 10
393 548 10
629 623 10
84 954 10
756 840 10
966 376 10
931 308 10
626 323 10
537 538 10
118 82 10
929 541 10
833 115 10
639 658 10
704 930 10
977 306 10
673 386 10
21 745 10
924 72 10
777 573 10
97 512 10
161 636 10
355 767 10
655 574 10
31 52 10
350 150 10
941 724 10
966 430 10
107 191 10
7 337 10
457 287 10
753 383 10
945 909 10
209 758 10
221 588 10
422 946 10
506 30 10
413 168 10
900 591 10
762 655 10
410 359 10
624 537 10
548 483 10
595 41 10
374 20 10
348 199 10
668 484 10
281 734 10
53 999 10
900 788 10
127 467 10
310 617 10
813 514 10
600 249 10
798 303 10
224 8 10
844 609 10
989 702 10
195 485 10
93 343 10
523 587 10
448 200 10
458 618 10
580 796 10
9 157 10
538 292 10
958 191 10
815 888 10
156 511 10
202 634 10
272 55 10
362 886 10
875 433 10
869 142 10
881 998 10
322 651 10
21 699 10
892 389 10
75 712 10
3 869 10
861 688 10
401 789 10
255 423 10
2 585 10
182 285 10
88 426 10
617 757 10
832 932 10
169 154 10
721 189 10
368 692 10
425 555 10
441 512 10
139 423 10
279 996 10
687 529 10
549 437 10
866 949 10
193 195 10
297 416 10
488 282 10
455 734 10
114 701 10
786 263 10
185 53 10
313 756 10
321 558 10
646 982 10
481 144 10
44 659 10
474 22 10
168 18 10
477 414 10
314 824 10
833 70 10
518 177 10
192 985 10
802 99 10
543 924 10
61 181 10
3 432 10
725 31 10
222 286 10
187 360 10
270 170 10
235 833 10
896 667 10
285 550 10
695 624 10
576 694 10
371 466 10
851 484 10
119 152 10
164 109 10
882 86 10
629 928 10
902 962 10
123 596 10
737 261 10
195 525 10
264 260 10
202 116 10
790 924 10
940 851 10
662 829 10
958 578 10
477 108 10
113 887 10
801 850 10
835 356 10
556 216 10
626 357 10
526 357 10
337 271 10
896 22 10
617 112 10
717 696 10
423 129 10
584 734 10
532 963 10
607 483 10
911 635 10
221 870 10
850 398 10
279 701 10
881 300 10
#include <iostream>
using namespace std;

int T, n, L, S;
int mp[201][3], cnt[201][2];
bool vs[201];
bool noWay;
int MAX = 2000000000;

int calcDis(int a, int b){
int d = (mp[a][0] - mp[b][0]) * (mp[a][0] - mp[b][0]) + (mp[a][1] - mp[b][1]) * (mp[a][1] - mp[b][1]);
int l = 1, r = d;
while(l < r){
int m = (l+r)/2;
if(m == l && l*l < d && r*r > d) return r;
if(m*m == d) {
return m;
}
else if(m*m < d) l = m;
else r = m;
}
return 0;
}

void dikstra(){
for(int i = 0; i < n; i++){
vs[i] = false;
cnt[i][0] = MAX, cnt[i][1] = MAX;
}
cnt[0][0] = 0, cnt[0][1] = 0;
int selected = 0;
while(selected < n){
int minI, minL = MAX, minS = MAX;
for(int i = 0; i < n; i++){
if(!vs[i] && ((cnt[i][0] < minL) || (cnt[i][0] == minL && cnt[i][1] < minS))){
minL = cnt[i][0], minS = cnt[i][1], minI = i;
}
}
if(minI == n-1 || (minL == MAX && minS == MAX)) return;

vs[minI] = true;
selected++;

int count = 0, countV = 0;
for(int i = 0; i < n; i++){
if(!vs[i]){
countV++;
int dis = calcDis(minI, i) - mp[minI][2] - mp[i][2];
int jL = MAX, jS = MAX;
if(dis <= 40){
jS = 1, jL = 0;
} else if(dis <= 90){
jL = 1, jS = 0;
}
if((cnt[minI][0] + jL < cnt[i][0])
|| ((cnt[minI][0] + jL == cnt[i][0]) && (cnt[minI][1] + jS < cnt[i][1]))){
cnt[i][0] = cnt[minI][0] + jL;
cnt[i][1] = cnt[minI][1] + jS;
}
if(cnt[i][0] == MAX && cnt[i][1] == MAX) count++;
}
}
if(count > 0 && count == countV){
noWay = true;
return;
}
}
}

int main(){
freopen("input.txt", "r", stdin);
cin >> T;

for(int tc = 1; tc <= T; tc++){
// Input
cin >> n;
for(int i = 0; i < n; i++){
cin >> mp[i][0] >> mp[i][1] >> mp[i][2];
}

// Initial
L = 0, S = 0, noWay = false;

// Solve Problem
dikstra();

// Output
if(noWay) cout << -1 << endl;
else cout << cnt[n-1][0] << " " << cnt[n-1][1] << endl;
}

return 0;
}```