devquiz2011一人ゲーム用コード

hitorigame.rb

#!/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