Problem Statement
We want to build a new phone network between numPoints points. A number of possible cables is available to construct the network. Each of the cables connects two of the points and has an associated quality and cost. We want to select a number of these cables such that:
1) All the points are connected to each other, either directly or via other points.
and
2) The quality/cost ratio (i.e., the sum of the qualities divided by the sum of the costs) is as high as possible.
What is the best achievable ratio? If it is impossible to connect all the points, return -1.
The available cables are described by a
Definition
- Class:
- PhoneNetwork
- Method:
- bestQuality
- Parameters:
- int, String[]
- Returns:
- double
- Method signature:
- double bestQuality(int numPoints, String[] cables)
- (be sure your method is public)
Notes
- Your return must have relative or absolute error less than 1e-9.
Constraints
- numPoints is between 2 and 50, inclusive.
- cables has between 0 and 50 elements, inclusive.
- Each element of cables has length between 0 and 50, inclusive.
- Each element of cables consists of four integers with no leading zeroes, separated by single spaces.
- The first two integers of each element of cables are between 1 and numPoints, inclusive.
- The first two integers of each element of cables are not equal.
- The third and fourth integers of each element of cables are between 1 and 100,000, inclusive.
Examples
4
{"1 2 6 5","2 3 3 4","3 4 5 2","4 1 3 3"}
Returns: 1.4
By taking cables 1, 2 and 4, we obtain a quality/cost ratio of (6+5+3)/(5+2+3) = 1.4.
5
{"1 2 6 5","2 3 3 4","3 4 5 2","4 1 3 3"}
Returns: -1.0
It's impossible to connect point 5 to the others.
4
{"1 2 1 10","2 3 3 3","2 4 3 2","3 4 3 1","3 4 2 1"}
Returns: 0.7058823529411765
The cable needed to connect point 1 to the rest is so bad that it pays off to use all the other cables, including the two different cables connecting points 3 and 4.
2
{}
Returns: -1.0
50
{}
Returns: -1.0
2
{"1 2 1 100000"}
Returns: 1.0E-5
2
{"2 1 100000 1"}
Returns: 100000.0
3
{"2 3 1 1"}
Returns: -1.0
2
{"1 2 1 4","1 2 5 2","1 2 7 3","1 2 3 3","1 2 8 3","1 2 2 1","1 2 3 4"}
Returns: 2.6666666666666665
3
{"1 2 1 4","1 2 5 2","1 2 7 3","1 2 3 3","1 2 8 3","1 2 2 1","1 2 3 4","1 3 1 1000"}
Returns: 0.029411764705882353
4
{"1 2 4 3","1 3 6 4","1 4 6 3","2 3 3 4","2 4 6 3","3 4 6 5"}
Returns: 1.8
10
{"1 2 4 3","2 3 7 5","3 4 65 2","4 5 8 2","5 6 16 7","6 7 4 12","7 8 9 52","8 9 12 43","9 10 1 1"}
Returns: 0.9921259842519685
8
{"1 2 1 1","1 3 1 1","1 4 1 1","2 3 1 1","2 4 1 1","3 4 1 1","5 6 1 1","5 7 1 1","5 8 1 1","6 7 1 1","6 8 1 1","7 8 1 1"}
Returns: -1.0
3
{"1 2 1 100","1 2 2 110","2 3 100 100"}
Returns: 0.505
50
{"1 2 56 77","2 3 11 13","3 4 80 40","4 5 14 70","5 6 60 11","6 7 75 34","7 8 43 88","8 9 72 51","9 10 31 33","10 11 97 21","11 12 72 68","12 13 74 82","13 14 2 44","14 15 23 7","15 16 19 6","16 17 38 15","17 18 30 28","18 19 78 15","19 20 76 39","20 21 55 48","21 22 78 44","22 23 86 92","23 24 82 67","24 25 43 60","25 26 53 56","26 27 80 88","27 28 66 99","28 29 34 15","29 30 53 87","30 31 10 9","31 32 86 28","32 33 31 24","33 34 64 88","34 35 44 60","35 36 73 95","36 37 84 72","37 38 80 27","38 39 48 91","39 40 87 13","40 41 72 78","41 42 99 30","42 43 95 65","43 44 97 93","44 45 20 73","45 46 98 85","46 47 96 83","47 48 38 60","48 49 53 8","49 50 39 1","50 1 25 96"}
Returns: 1.1668681983071343
50
{"1 2 24629 94634","2 3 25134 221","3 4 57211 66394","4 5 48530 17450","5 6 52298 51038","6 7 17761 75039","7 8 78048 96287","8 9 71890 90365","9 10 65451 88013","10 11 44898 84928","11 12 30975 88560","12 13 41908 37947","13 14 54179 92364","14 15 54073 91697","15 16 1990 65807","16 17 82219 24045","17 18 35055 15227","18 19 96051 25055","19 20 70674 12619","20 21 92554 62644","21 22 19742 66691","22 23 94877 44624","23 24 91091 46168","24 25 95945 38411","25 26 73457 31929","26 27 96998 72901","27 28 85707 35897","28 29 86241 48935","29 30 76219 74554","30 31 45121 53880","31 32 33263 53944","32 33 45130 53304","33 34 88257 80431","34 35 63104 57629","35 36 40196 51721","36 37 50467 29479","37 38 32090 82760","38 39 14585 65698","39 40 3074 69069","40 41 58058 42200","41 42 2415 71874","42 43 12677 67952","43 44 73876 78794","44 45 99071 33383","45 46 98524 44579","46 47 44955 32329","47 48 99446 53077","48 49 1669 43692","49 50 73965 15162"}
Returns: 1.008946494838504
50
{"1 2 66252 9081","2 3 88242 88829","3 4 50056 2085","4 5 1376 22803","5 6 83502 83390","6 7 19518 22943","7 8 39391 70807","8 9 23013 30385","9 10 74788 18304","10 11 74533 35176","11 12 29802 54352","12 13 42793 83317","13 14 58429 58782","14 15 15426 25944","15 16 23872 7440","16 17 99730 67398","17 18 86502 30826","18 19 70904 76556","19 20 95953 85832","20 21 13011 68109","21 22 7397 52583","22 23 94100 18759","23 24 5319 67581","25 26 95351 50729","26 27 49775 81645","27 28 46055 37509","28 29 74381 2600","29 30 39159 37656","30 31 3595 38498","31 32 37295 86088","32 33 6554 67319","33 34 10584 63500","34 35 92371 21774","35 36 63991 71520","36 37 19077 51122","37 38 62919 59057","38 39 20189 4827","39 40 52850 99993","40 41 73553 60876","41 42 29004 88901","42 43 41833 1365","43 44 63276 70545","44 45 94410 72056","45 46 3399 92117","46 47 14688 98440","47 48 46954 13368","48 49 64552 72142","49 50 65716 30467"}
Returns: -1.0
10
{"7 3 557 34","5 2 751 16","7 2 569 73","2 8 696 65","7 2 506 4","1 3 667 18","7 9 798 59","8 2 559 8","7 5 737 96","1 4 679 66","8 10 296 88","6 3 853 19","5 2 645 75","4 6 963 61","10 6 742 34","10 9 541 64","4 10 621 94","8 7 688 81","3 9 196 82","9 3 29 1","5 9 136 19","1 10 325 95","6 3 487 99","4 7 356 37","3 10 956 90","8 1 124 96","2 4 624 12","8 10 309 69","2 8 839 23","5 7 203 85","5 6 818 39","2 5 272 20","4 3 169 34","1 5 654 58","4 3 323 10","2 4 245 62","3 6 432 41","7 8 837 74","2 1 262 61","10 3 189 61","6 2 243 16","2 10 704 34","1 3 492 55","10 7 332 18","1 4 752 15","5 6 514 27","6 7 817 47","10 3 539 75","4 1 673 86","4 2 936 57"}
Returns: 45.9126213592233
15
{"7 3 557 34","5 2 751 16","12 2 569 73","12 8 696 65","7 12 506 4","11 13 667 18","2 14 798 59","13 3 552 59","8 12 985 37","6 9 679 66","13 15 296 88","1 3 853 19","15 7 645 75","4 11 963 61","15 6 742 34","5 14 541 64","14 5 621 94","13 7 688 81","3 4 196 82","9 13 29 1","5 4 136 19","11 10 325 95","6 13 487 99","14 2 356 37","8 10 956 90","3 13 831 24","1 12 784 24","12 3 648 30","14 4 272 68","4 3 815 7","3 10 995 6","13 4 192 45","12 5 314 13","14 4 1 85","9 3 784 73","13 10 482 12","9 5 562 53","6 12 341 27","8 2 574 2","1 7 461 70","3 4 461 86","12 3 616 22","15 4 34 41","8 2 655 10","7 12 418 91","9 2 515 5","1 9 627 96","12 2 247 50","13 9 975 34","11 3 986 94"}
Returns: 40.833333333333336
25
{"10 21 88197 201","23 21 72035 6","18 22 2368 514","6 25 39305 974","17 15 11745 808","1 19 25486 553","19 2 12787 755","5 20 31454 516","11 3 81432 643","23 8 36122 46","13 18 49279 878","24 25 7508 143","7 3 84779 120","7 9 31759 915","21 23 18354 922","6 9 86594 175","5 2 65787 469","11 22 40720 723","3 12 91454 437","2 1 10121 61","16 12 46466 653","24 9 1507 683","25 14 91320 342","25 18 27851 457","7 11 31691 421","24 8 62969 670","5 9 62863 868","16 5 55597 721","4 17 2817 546","2 24 56594 879","3 14 59658 436","20 4 77149 754","24 21 93082 440","24 6 55661 194","12 17 68622 172","3 15 96970 568","4 14 61387 987","17 1 76949 360","17 5 78255 354","15 9 95559 309","25 5 84439 555","21 24 74344 482","17 10 5061 137","18 15 91446 239","18 17 69850 274","2 15 53415 729","21 15 32359 76","1 12 33843 5","3 7 45098 959","24 15 37518 44"}
Returns: 189.7882242331649
40
{"2 24 71 47402","19 1 48 54492","10 26 17 48034","34 18 22 4630","14 39 98 89503","4 38 26 64639","7 39 6 60505","7 2 35 45660","36 25 21 99281","40 12 61 79901","18 3 92 79507","6 12 66 75385","9 33 37 45621","27 13 47 18197","37 11 31 48408","2 10 92 35995","2 9 55 51428","2 27 66 13765","23 15 91 29613","8 16 44 66801","36 27 70 4530","24 34 81 50891","3 12 70 52698","29 38 12 17800","17 35 25 46199","36 3 16 35239","30 27 31 41732","37 16 55 1328","40 9 30 80041","1 17 10 36406","12 30 96 25523","36 17 43 43638","5 10 46 33214","20 31 30 3736","2 24 40 76461","23 27 56 48427","28 31 38 70925","25 31 34 10698","13 29 20 99811","24 18 90 71889","3 31 65 46724","3 8 47 57976","13 22 78 68172","2 26 89 91594","33 21 12 92067","15 19 98 33945","37 1 43 86134","29 12 72 99322","18 32 13 85842","28 10 33 49859"}
Returns: 0.0011311798981681355
45
{"10 35 39 11478","34 25 68 47635","38 36 96 48172","36 30 30 93075","14 1 78 34694","17 37 55 27453","28 16 12 40189","45 24 13 53994","38 6 88 86457","43 44 21 14819","40 2 72 14421","20 45 54 7812","40 12 19 72766","12 30 50 30172","8 9 62 1236","13 24 22 35211","27 15 89 23624","3 43 88 92643","25 26 45 72284","37 38 48 71816","38 27 9 97349","37 21 9 83087","41 28 70 52812","44 3 35 36225","19 29 53 82472","20 11 4 76729","4 36 21 18181","40 36 97 84769","5 6 95 24319","31 25 80 48121","41 35 76 22055","7 15 28 60080","25 26 7 20892","41 28 30 52872","18 32 89 33171","33 42 100 42581","14 27 58 75216","29 17 90 48926","25 28 48 77546","3 43 94 68539","23 8 72 23274","12 39 37 87316","16 23 73 28107","19 2 61 47336","28 7 59 82907","13 27 31 5923","22 17 17 55288","5 32 72 83462","43 26 28 70132","26 33 6 38242"}
Returns: 0.0011148486582120368
43
{"14 18 20 72519","35 43 50 19111","3 41 10 62838","28 42 76 20208","27 39 39 31671","8 6 37 50620","1 7 39 42220","42 34 2 6714","12 22 67 57541","25 42 17 32965","21 34 56 59800","24 21 10 38947","35 25 6 17479","11 3 3 53282","7 9 6 56639","2 12 84 36507","33 23 71 35765","2 9 98 95697","6 12 17 6248","26 1 8 36752","28 6 29 54660","6 38 60 98224","30 2 90 50427","39 32 14 10160","8 7 41 77803","18 10 2 76253","20 2 10 47420","12 17 36 93163","29 24 71 93601","8 6 15 59000","32 7 87 83444","37 27 30 26861","36 5 81 66683","7 5 4 20958","40 33 100 31143","22 1 32 6887","41 13 94 13010","31 22 85 25486","11 31 65 2590","5 36 34 42454","2 30 50 43187","34 20 7 97377","16 22 38 40043","21 19 40 95517","4 25 63 80583","1 29 60 794","10 30 85 41775","15 23 46 97767","42 19 43 18061","7 23 29 34616"}
Returns: 0.0010571108906159254
45
{"36 15 40 38155","29 39 93 98980","36 3 67 38657","11 34 11 67065","25 18 23 39764","38 37 71 45926","10 4 27 69321","35 1 91 57398","42 24 75 75039","12 19 82 70060","14 8 77 37200","35 16 78 98023","27 38 32 85423","18 39 2 26591","13 17 55 38632","27 6 4 23655","9 8 77 7812","11 15 12 84875","22 16 84 21860","22 6 30 24145","36 11 92 6541","33 21 54 66015","3 25 71 27722","3 12 87 12363","43 26 70 9830","37 30 98 74971","6 23 67 87640","27 29 64 12872","1 36 4 11753","31 18 53 92315","10 40 18 2773","23 40 1 25265","16 17 81 49575","40 28 48 29368","36 17 19 82945","14 23 19 4111","19 32 14 98385","3 32 23 46729","15 19 25 83581","25 44 42 46154","34 28 61 24088","15 4 97 29192","34 6 29 27529","34 30 50 29099","42 36 12 17259","43 13 49 22348","23 9 47 1287","1 22 9 67321","13 17 98 43803","10 36 86 43055"}
Returns: -1.0
37
{"15 8 46712 70592","7 19 70207 42490","14 18 72024 89834","31 14 23440 39901","25 37 14326 21005","19 29 16274 86893","22 9 62453 15250","19 35 89676 42909","27 28 22990 76905","15 11 61557 92237","25 3 41545 7855","34 4 33911 75622","32 10 78986 21024","16 25 3034 77944","10 34 54889 68927","31 1 8646 38584","15 5 35814 58489","19 10 4304 31338","17 36 83013 29836","32 19 91018 81174","34 33 50612 36443","18 23 17455 53864","35 15 48939 83977","23 9 57187 94987","30 18 37227 15164","32 7 36373 5935","2 9 19264 87227","5 25 85695 7171","7 28 75617 51920","20 23 70081 78939","32 24 88524 18439","11 28 363 44906","10 35 96652 26412","27 7 79505 38569","31 34 81141 94801","22 23 76918 43438","34 2 72036 40997","29 19 8964 38837","9 19 28097 13565","28 20 38608 76282","16 13 93790 7790","3 10 2136 11132","18 4 75030 26192","30 36 65702 63772","21 33 89873 52828","1 12 2796 68987","26 33 48732 31919","2 9 24134 34175","6 3 40260 49549","20 27 5549 87048"}
Returns: 1.344774570130345
25
{"7 4 937 100","7 5 852 407","4 7 737 864","4 1 278 380","4 2 608 733","7 2 821 870","4 1 108 435","2 6 625 693","4 6 857 547","4 7 782 668","4 1 335 769","3 6 56 456","2 1 377 450","3 6 341 294","6 4 697 719","1 3 815 608","13 10 415 648","11 14 665 287","11 10 122 755","9 15 644 703","10 11 251 736","12 10 52 332","13 9 14 149","15 14 328 943","11 12 665 937","12 9 264 138","12 13 225 568","13 10 195 543","10 15 806 906","15 12 250 512","9 14 970 446","9 14 294 545","20 23 249 656","22 17 750 348","18 22 735 165","18 23 196 793","21 17 238 40","23 20 658 184","21 18 913 851","18 19 179 892","24 18 371 45","22 18 293 448","22 19 851 637","21 17 579 170","22 24 270 136","24 20 997 875","20 17 15 323","19 18 317 851"}
Returns: -1.0
30
{"11 15 292 634","11 7 748 582","4 1 424 434","6 2 848 139","9 6 837 11","3 11 340 46","10 9 174 857","13 11 346 296","5 1 452 899","9 6 598 260","10 9 756 183","3 9 934 550","10 6 791 544","3 4 59 846","7 5 549 10","2 1 413 212","11 4 929 954","14 13 539 883","15 5 432 888","14 2 144 319","15 5 545 390","6 12 630 721","15 3 453 175","8 9 406 239","25 27 459 690","18 27 526 775","22 27 903 633","28 23 866 600","29 27 911 692","26 24 530 155","27 16 862 458","20 16 214 83","28 23 42 764","30 17 880 210","29 19 287 11","20 16 57 950","20 25 79 194","26 27 490 625","21 28 877 223","17 25 901 639","23 19 898 356","24 20 421 833","23 28 457 687","29 26 886 969","24 20 904 868","16 20 222 304","21 27 551 285","28 20 975 860","3 17 454 7612"}
Returns: 1.0817100935997976
40
{"5 3 597 590","11 2 8 803","7 3 599 954","20 3 835 242","6 16 262 911","4 3 922 74","16 9 623 456","12 17 644 796","4 15 455 97","18 12 503 432","17 19 598 115","3 14 557 196","2 6 196 877","1 19 420 228","6 8 41 972","8 15 847 224","6 1 292 690","2 13 908 710","10 7 253 851","11 4 189 737","10 20 540 178","11 19 468 399","8 1 88 755","15 14 38 348","21 34 733 100","21 33 201 637","25 23 499 751","32 25 569 199","25 30 366 989","26 25 926 867","33 40 332 677","29 25 888 798","29 38 852 475","38 26 517 253","28 35 719 577","39 24 908 385","25 24 989 355","32 28 171 929","26 24 287 671","31 26 24 798","32 31 801 773","32 22 609 224","35 36 703 355","30 23 488 928","27 40 879 716","34 32 975 951","28 39 696 90","36 37 995 139","4 25 12 71364"}
Returns: 0.2757360449742559
30
{"5 1 288 349","1 7 202 488","6 2 219 913","4 3 821 700","7 4 144 177","4 6 338 199","6 5 477 192","1 7 789 240","5 3 668 935","2 3 28 886","5 1 273 398","14 15 169 883","12 14 472 95","9 15 445 645","14 8 75 215","14 10 237 838","10 9 835 698","13 12 922 31","13 12 504 211","11 12 100 327","9 14 50 93","11 14 199 787","16 19 82 549","16 18 367 519","22 16 991 970","20 16 969 89","20 18 700 920","19 18 418 997","21 18 215 747","18 20 936 468","21 18 245 331","19 17 492 347","18 19 625 388","30 29 761 57","30 28 594 169","27 24 209 763","29 26 539 629","26 25 523 393","27 23 650 509","26 29 133 6","30 24 472 104","27 23 393 763","29 30 807 534","28 24 360 473","1 10 450 53674","15 21 937 9822","21 26 23 68937"}
Returns: 0.13841333927588287
20
{"3 1 6698 8","2 4 6558 68","2 5 7271 64","4 1 5733 63","5 2 5663 39","4 2 1871 39","3 4 1443 97","1 2 668 57","2 5 8327 100","3 4 2597 88","1 3 7037 92","6 9 1021 36","6 7 7510 98","7 6 2657 26","9 8 991 46","10 9 3789 6","8 6 7469 81","10 8 3455 72","10 7 628 90","6 10 282 20","8 9 3414 93","7 10 3079 6","14 12 7993 50","12 15 7289 2","15 14 3602 14","12 11 564 93","14 11 4945 52","12 13 2833 83","12 11 936 73","14 11 2977 47","14 13 4713 91","14 15 8876 10","13 11 2436 92","19 16 6191 11","20 18 7471 12","19 18 1034 30","18 17 8018 39","17 20 9167 9","19 18 1144 30","20 19 4497 6","18 16 7315 64","18 19 7337 26","18 19 9705 95","19 17 763 56","2 6 2298 419","7 14 5738 857","15 20 6757 932"}
Returns: 55.11662237968704
10
{"1 5 7140 155","4 3 9567 657","1 4 6411 65","5 3 2823 764","3 2 3571 926","5 4 9927 321","5 1 2691 398","2 4 6375 39","2 4 8782 60","4 3 6277 200","5 1 3178 23","2 3 7632 423","3 4 1502 591","3 2 55 632","2 1 4004 655","4 3 2877 812","1 5 9512 875","2 1 6984 860","2 1 7430 145","1 3 1492 541","3 1 954 15","3 5 7271 722","3 2 3087 363","3 1 6270 830","7 10 6998 971","6 8 7667 640","7 9 7964 872","6 7 7658 553","10 6 1418 773","8 10 5201 265","6 7 2881 575","10 8 8048 368","6 7 7919 945","9 8 219 111","9 7 2814 385","8 7 5523 729","10 9 3925 581","10 9 242 154","9 8 2561 88","10 9 8397 192","9 6 2829 529","9 10 850 99","7 6 7612 259","8 9 2348 308","9 7 1287 891","7 9 7321 23","7 8 3803 440","6 9 4162 129","4 6 7594 5352"}
Returns: 14.189429319968106
38
{"3 1 2889 614","4 3 7863 691","4 3 2079 197","2 3 6602 32","4 3 6022 407","8 5 7775 289","9 5 9385 113","5 8 6376 648","9 7 9922 169","7 6 6044 72","11 13 426 52","10 12 1834 52","14 10 8304 348","14 10 9935 13","13 12 7178 63","17 18 8350 973","17 15 4015 934","16 18 5225 186","19 16 6478 115","18 19 4678 161","22 20 6930 47","20 21 9237 310","23 22 9847 670","20 21 8448 994","23 22 1225 753","28 24 4112 526","27 25 3837 834","26 24 1688 423","28 24 245 276","27 26 1227 335","29 32 7593 151","33 29 5515 359","30 31 2100 913","32 31 1387 856","31 32 9035 9","36 34 3053 446","37 35 121 197","36 37 4650 161","36 35 7904 968","35 38 7587 547","1 8 1160 4486","9 11 4053 3665","14 17 86 6313","15 21 8471 5616","21 26 3355 900","28 32 5563 2061","30 36 8350 3312"}
Returns: 6.102825140012445
32
{"3 1 5978 168","2 1 3874 135","3 2 719 598","1 2 6792 383","5 4 9181 202","4 6 7805 500","5 6 8444 663","5 4 3487 219","8 7 2531 202","9 7 1386 241","7 8 4835 427","7 8 3605 784","12 10 8770 840","12 11 7584 349","10 12 3355 743","11 10 3195 506","16 14 5058 803","14 16 1086 297","15 13 8659 817","14 15 8969 659","17 18 9568 425","17 19 6849 532","18 17 8331 930","17 18 9711 623","20 21 4548 79","21 20 9509 101","22 21 2808 929","22 20 4418 196","25 24 8828 425","24 23 3867 535","25 23 4208 205","25 23 5305 320","28 26 8396 356","27 26 7103 386","27 26 4826 492","26 27 2424 269","30 29 1621 667","32 29 6476 266","29 31 9332 455","31 29 2291 238","2 4 6203 9749","6 9 1285 2249","8 11 4831 9386","12 13 9567 412","16 18 1479 1679","17 22 487 4250","21 23 6365 6868","25 28 8999 6862","26 30 8169 4992"}
Returns: 4.290023646705439
15
{"3 2 68 8438","3 4 91 3874","5 2 63 1711","4 3 79 9336","2 3 77 3215","1 2 1 6970","5 4 32 8444","3 2 62 3487","4 3 4 2531","2 5 78 1386","1 4 12 4835","2 5 49 3605","4 2 89 1464","5 1 64 7584","4 2 55 1743","2 3 37 3195","6 8 54 5058","8 10 67 1086","7 8 83 3538","9 7 81 402","8 9 59 5915","6 7 68 9425","7 9 49 2532","8 6 26 9550","6 10 73 1196","6 8 96 2262","8 6 88 8962","10 7 66 9509","6 9 8 929","9 6 98 4418","6 10 70 8828","10 8 67 2535","11 15 8 1205","13 11 5 2320","13 14 96 8356","11 13 76 7103","11 12 50 3961","11 12 98 4629","14 12 21 9113","11 12 25 7060","14 11 66 9184","13 11 32 8455","14 13 11 5286","12 11 38 8114","14 13 49 1908","12 15 49 181","11 13 69 9132","12 14 89 1479","4 6 4 487","10 14 20 6365"}
Returns: 0.028818986626483332
21
{"1 5 34 4218","4 2 29 903","5 2 80 1641","2 3 18 1110","2 3 63 2523","1 4 86 1218","5 2 12 3228","3 1 7 907","5 1 4 2568","2 4 7 4864","2 5 16 2362","10 6 7 240","7 9 99 4314","9 6 56 2285","9 7 60 4505","6 10 33 901","10 6 43 2631","10 6 18 1139","9 8 27 2421","7 9 2 222","8 9 18 2664","7 8 69 3505","12 13 24 939","13 14 56 4812","11 12 81 1979","15 11 65 1007","12 11 23 2390","11 15 74 420","14 12 43 1253","13 15 97 2285","11 14 56 4036","14 13 78 1048","15 13 42 3823","19 21 96 351","17 16 83 4564","21 18 66 828","16 20 39 3871","17 16 84 3940","18 21 16 4822","20 21 74 4955","16 17 5 4557","16 19 3 1948","21 17 42 1111","20 19 72 802","5 6 21 2540","8 12 27 72627","14 16 14 80734"}
Returns: 0.008469894245953201
22
{"3 2 88 3863","5 8 38 45924","2 1 55 652","15 16 79 3791","3 2 23 4850","3 1 26 1993","2 3 99 4732","1 2 78 2258","1 3 88 2513","4 6 77 3814","7 6 47 999","6 4 6 3806","5 4 10 580","9 14 5 87615","6 4 78 2752","7 5 33 3498","5 6 74 4330","11 8 18 2676","10 9 56 1747","8 9 66 3234","10 9 61 2754","10 9 41 1328","11 10 97 3744","11 8 8 3555","14 12 68 2065","14 12 5 1697","14 13 26 3152","16 19 35 88583","12 13 71 4737","13 14 94 4661","12 13 6 2222","13 12 50 1630","3 5 37 44431","15 18 19 2054","16 15 73 1623","17 16 3 2408","18 15 93 4853","17 16 19 4527","15 16 88 1945","22 21 17 4310","19 21 10 2064","20 21 68 512","21 22 46 2066","22 19 64 57","21 20 80 263","19 21 86 899","12 16 3 8484"}
Returns: 0.006182559867603552
23
{"4 3 6 37","1 3 10 87","4 2 6 79","6 8 1 119","3 4 7 49","6 5 4 76","2 1 7 82","5 1 7 41","7 5 10 24","3 1 8 24","2 7 6 20","3 6 1 90","5 2 4 77","2 3 4 96","1 6 7 34","5 3 9 56","6 5 9 43","12 13 7 40","15 9 5 77","9 14 5 41","9 12 5 43","13 11 6 55","13 15 10 23","11 12 3 24","10 9 1 72","9 10 3 48","11 13 8 86","11 8 7 65","14 12 6 45","15 13 8 33","13 14 9 31","15 8 7 18","9 14 8 19","18 22 3 16","17 23 6 90","23 20 3 23","22 18 2 35","18 17 4 18","22 17 7 91","18 20 7 40","17 22 3 75","23 16 9 29","19 22 1 96","18 21 5 69","19 20 7 38","20 16 1 54","16 20 9 6","16 19 10 49","20 17 5 98","15 20 5 233"}
Returns: 0.15636042402826855
27
{"1 2 33 38","3 1 74 68","3 2 32 8","4 1 45 3","4 3 76 34","2 1 54 90","3 2 89 48","7 8 61 54","6 7 21 38","9 8 13 53","8 9 75 93","5 6 17 81","9 5 71 74","6 7 36 10","10 12 47 98","10 13 78 45","12 13 30 53","11 13 9 67","13 10 94 30","10 12 99 76","10 12 87 44","17 16 45 92","18 16 33 69","16 15 62 44","15 17 17 94","14 17 100 72","18 16 34 97","17 18 47 52","22 21 34 75","19 22 17 77","22 20 39 97","21 19 96 69","19 21 21 75","20 21 47 38","22 19 2 46","24 23 92 47","27 25 32 36","24 27 90 59","27 25 97 26","26 25 94 100","24 27 55 74","24 25 27 31","1 6 60 45","7 12 24 214","12 16 13 203","16 22 16 181","22 23 15 77"}
Returns: 0.9116049382716049
33
{"3 1 34186 30","2 3 21757 39","2 4 63902 35","4 2 85956 11","1 5 31869 20","4 5 64675 50","2 3 50845 20","8 7 36949 79","11 9 74929 85","9 6 71440 22","9 11 67395 98","11 7 77414 57","9 10 69478 65","6 7 28987 66","16 15 81323 47","16 13 62491 60","13 15 97761 96","13 14 55678 100","12 15 89621 56","14 12 97011 22","15 12 23344 86","18 21 50619 80","22 17 96488 27","17 18 40200 82","20 18 56517 69","17 19 83479 81","21 18 45702 92","19 17 13212 28","25 27 64166 16","27 23 64135 20","25 24 90873 33","24 25 2657 48","23 25 47245 89","26 25 81485 54","23 26 67756 42","31 32 19465 76","28 33 32182 3","31 30 15884 15","32 33 97001 67","29 28 95042 93","33 32 4902 82","30 31 64388 33","1 7 54853 67","9 16 45945 236","16 18 55525 149","21 25 19512 82","25 30 42268 110"}
Returns: 1064.9292929292928
33
{"2 5 94885 6","3 4 22330 4","4 1 29096 1","2 1 20776 6","1 2 52614 7","1 3 32844 6","3 5 44233 9","11 7 91165 3","10 11 25732 3","8 11 18972 9","11 6 23669 2","7 6 22805 8","7 9 83588 6","11 9 75771 2","16 15 88100 8","12 14 55117 1","16 15 52943 9","16 14 97078 1","14 15 28140 5","16 14 32902 2","13 12 97034 4","18 17 88347 1","21 20 34307 4","19 21 10858 3","17 18 84412 1","17 20 3490 3","19 18 51212 1","18 22 87960 4","27 23 66514 5","26 27 41521 9","27 26 21206 5","26 25 72481 3","24 25 29465 9","25 23 52456 2","23 25 65063 3","28 29 3227 10","28 30 21346 5","31 32 22879 3","33 32 82087 5","33 32 681 3","32 31 22808 1","30 31 84150 4","2 7 86494 27","10 14 206 4","16 19 14992 23","18 23 58083 2","27 32 6730 3"}
Returns: 10677.379888268157
30
{"23 18 642 59","7 25 525 92","9 18 425 73","2 11 206 9","22 20 433 66","7 15 902 37","16 1 255 47","1 8 998 48","6 22 29 24","25 28 215 58","20 7 362 7","24 15 108 61","27 15 15 17","19 23 291 74","2 4 126 86","2 29 738 20","21 18 99 36","2 18 43 61","26 4 341 93","16 23 106 42","15 12 659 24","9 16 851 22","8 27 232 99","21 20 31 3","26 22 209 44","20 10 789 55","1 9 307 83","1 14 490 55","9 2 783 25","28 29 588 19","28 5 768 43","20 2 592 100","6 4 834 39","26 2 865 76","27 12 442 45","15 14 509 96","13 15 827 37","5 9 802 17","23 18 101 100","11 10 840 8","6 10 874 28","17 18 966 97","13 3 176 47","14 16 93 61","3 7 650 84","23 25 661 93","28 22 80 27","26 5 210 39","8 10 427 55","3 30 1 100000"}
Returns: 0.2196018765056422
3
{"1 2 10000 1", "2 3 1 2", "2 3 5 5" }
Returns: 3333.6666666666665