devquiz2011一人ゲーム用コード
#!/usr/bin/env ruby | |
# -*- coding: utf-8 -*- | |
input =<<EOS | |
100 | |
2 | |
10 11 | |
3 | |
0 9 9 | |
4 | |
81 67 83 86 | |
3 | |
11 22 30 | |
1 | |
0 | |
1 | |
5 | |
1 | |
999999 | |
1 | |
1000000 | |
2 | |
5 10 | |
3 | |
0 10 11 | |
5 | |
10 20 21 22 23 | |
5 | |
422808 211404 761062 845625 491519 | |
5 | |
24 54 75 27 18 | |
5 | |
10 21 8 25 29 | |
5 | |
11 23 21 89 13 | |
5 | |
13 86 53 4 59 | |
5 | |
81 88 53 39 17 | |
5 | |
90 96 50 35 47 | |
5 | |
63 92 78 84 7 | |
5 | |
67 17 45 81 63 | |
5 | |
86 28 65 92 78 | |
5 | |
52 4 66 74 35 | |
10 | |
16 30 51 96 93 36 32 82 19 6 | |
10 | |
96 70 83 27 60 95 36 68 80 97 | |
10 | |
47 97 5 22 19 66 17 61 0 34 | |
10 | |
28 97 19 76 53 25 83 9 90 70 | |
10 | |
90 28 37 57 41 79 39 11 45 8 | |
10 | |
65 40 1 17 24 45 84 77 85 62 | |
10 | |
21 64 25 90 8 18 100 80 31 95 | |
10 | |
39 92 43 75 25 48 82 24 56 24 | |
10 | |
99 94 79 93 93 29 76 49 35 60 | |
10 | |
42 36 24 96 62 38 66 69 37 81 | |
5 | |
878546 833290 859990 901827 997883 | |
5 | |
882609 921316 884088 919180 971489 | |
5 | |
803261 959543 861386 944216 933681 | |
5 | |
856446 898082 982081 811265 818375 | |
5 | |
988179 938849 923030 902281 838159 | |
5 | |
857625 932594 969673 820230 937885 | |
5 | |
842973 950994 961886 884636 939067 | |
5 | |
932634 996356 807612 965147 818999 | |
5 | |
963992 945945 899766 815339 987537 | |
5 | |
859669 987987 933901 850189 987330 | |
10 | |
859181 920637 928596 851760 872323 962899 852568 973727 864435 820313 | |
10 | |
897313 960076 829055 834209 917861 895274 821667 886530 991239 914149 | |
10 | |
849102 836520 812238 855063 963664 806346 874784 916634 945953 812674 | |
10 | |
914770 918872 884410 839556 903087 819878 809109 891594 978246 997436 | |
10 | |
843724 876070 867784 882002 910688 908322 903475 839459 995304 985716 | |
10 | |
890189 855256 864823 891857 954870 848470 839665 890793 804064 909211 | |
10 | |
836021 962036 873103 996078 880755 881990 895993 974534 963869 966806 | |
10 | |
842256 963467 830833 881073 902486 914286 917355 819978 992176 888810 | |
10 | |
974268 813204 934511 989573 973616 886676 974725 986658 813410 823383 | |
10 | |
943408 982810 952382 875708 855586 858828 979454 841478 957062 864959 | |
10 | |
45 947581 93 834668 826312 90 56 846647 874169 65 | |
10 | |
939763 18 94 5 907041 43 32 912381 814991 884662 | |
10 | |
6 92 0 825180 24 45 884776 844929 977748 872658 | |
10 | |
936244 43 30 987077 883909 83 886344 41 84 843377 | |
10 | |
96 999667 922636 38 978811 17 869426 69 809144 5 | |
10 | |
833824 72 985827 940766 83 1 993359 80 85 956096 | |
10 | |
20 896646 840694 55 99 826974 59 913747 899983 46 | |
10 | |
23 928628 945503 0 1 969410 845638 800170 69 44 | |
10 | |
908116 837559 47 813445 83 839072 15 995967 20 6 | |
10 | |
972737 805116 864308 984081 95 927752 18 25 17 12 | |
10 | |
915630 962737 7 972162 98 965206 10 40 94 982094 | |
10 | |
811794 45 842651 885392 39 896135 69 21 73 803342 | |
10 | |
917123 804650 803514 84 95 976186 98 850082 9 26 | |
10 | |
953222 30 74 962640 811115 869095 869415 41 54 87 | |
10 | |
859456 79 828111 828454 69 24 72 843247 48 921221 | |
10 | |
80 993999 965121 875309 33 969429 92 32 86 954224 | |
10 | |
95 995270 936296 801246 26 26 803722 11 876810 20 | |
10 | |
819963 82 809179 64 17 964599 42 850260 916629 6 | |
10 | |
892877 820467 939589 0 952527 90 10 56 908984 52 | |
10 | |
851314 97 910522 12 878539 33 803422 1 95 960228 | |
7 | |
304381 908445 89763 266780 574664 549955 520185 | |
10 | |
180633 814350 750065 53835 849760 842454 843745 49635 906524 145420 | |
7 | |
712770 323455 185575 467185 66860 206495 934740 | |
9 | |
35596 445605 306175 505975 770480 919316 872270 964913 508165 | |
9 | |
992385 925320 991220 962170 759415 132750 435220 11730 566301 | |
8 | |
327080 643790 776045 526575 105900 246960 242450 264464 | |
7 | |
781490 782250 13898 291265 389427 271450 683070 | |
9 | |
786740 339970 552150 106620 599289 12875 902570 22350 363840 | |
9 | |
376756 110825 362085 690145 704493 823323 566410 398280 553220 | |
8 | |
490076 876075 22875 842670 841820 994355 848440 308215 | |
7 | |
294015 498545 638175 528185 305670 345895 17565 | |
9 | |
240095 909625 774960 740360 11910 346884 449710 870730 398025 | |
8 | |
214965 885906 566296 393615 417485 361652 980540 422320 | |
9 | |
709285 714120 885330 71310 810185 690957 512301 139135 136696 | |
9 | |
322665 161600 429025 246720 34795 195470 510705 348777 591870 | |
9 | |
918690 570811 238035 974195 987488 257200 329569 811110 329250 | |
10 | |
405415 32060 885133 351600 324380 232085 437000 364495 689513 122578 | |
9 | |
684710 849517 940245 120585 789114 846547 521980 365745 987295 | |
10 | |
255585 560975 637790 99400 471785 176193 120175 807050 735086 436595 | |
10 | |
831305 311265 272880 28350 886180 697950 287433 36130 481620 530215 | |
7 | |
705684 402498 988035 592238 777159 86773 686523 | |
5 | |
450201 323049 430105 505129 505560 | |
3 | |
481703 309470 960909 | |
6 | |
233019 316825 109802 654983 487388 61316 | |
8 | |
686956 571655 375523 107167 11841 266023 521703 155801 | |
9 | |
373792 667186 284163 389712 328654 782893 615081 497321 900203 | |
10 | |
107857 545540 507559 985279 683835 674321 165410 371606 184547 583383 | |
5 | |
554460 815349 676853 326778 817251 | |
EOS | |
rv = [] | |
case_number = 0 | |
number = 0 | |
def try(ary, count, half_turn) | |
(1..count).each do |i| | |
if half_turn.include?(i) | |
ary.map! {|x| x / 2} | |
else | |
return false unless ary.reject! {|x| x % 5 == 0 } | |
end | |
end | |
ary.empty? | |
end | |
def try_all(ary, count) | |
(0..count).each do |half_count| | |
(1..count).to_a.combination(half_count).each do |half_turn| | |
if try(Marshal.load(Marshal.dump(ary)), count, half_turn) | |
return true | |
end | |
end | |
end | |
false | |
end | |
def calc(ary) | |
return 1 if ary.max == 0 | |
max_count = Math.log2(ary.max).ceil + 2 | |
(1..max_count).each do |count| | |
return count if try_all(ary, count) | |
end | |
raise | |
end | |
input.each_line.each_with_index do |line, i| | |
if i == 0 | |
case_number = line.to_i | |
elsif i % 2 == 1 | |
number = line.to_i | |
else | |
ary = line.split(" ").map(&:to_i) | |
puts calc(ary) | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment