oneperson.py

in1.txt

4
2
10 21
3
0 9 9
4
81 67 83 86
3
11 22 30

in2.txt

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
15 83 80 56 56
5
32 37 80 54 36
5
81 85 50 49 23
5
75 58 99 64 69
5
33 86 36 0 71
5
84 15 53 16 43
5
61 65 14 20 68
5
81 39 45 79 89
5
16 40 59 70 90
5
78 40 94 23 33
10
7 52 49 67 58 55 100 14 17 15
10
0 26 48 78 24 33 98 2 76 65
10
24 91 35 40 70 39 15 33 91 35
10
0 64 15 12 42 12 74 42 35 23
10
30 90 18 59 24 2 73 34 13 44
10
84 52 67 57 100 50 55 33 58 86
10
2 37 99 61 79 20 45 44 66 95
10
83 3 82 55 91 40 46 27 18 68
10
73 1 96 99 79 81 79 39 70 53
10
72 85 48 63 55 51 52 69 17 82
5
867289 883061 979316 938591 807148
5
843700 876047 857962 850660 943537
5
894905 975687 902632 862709 935484
5
848397 941134 831509 893234 815865
5
824010 823901 823177 893675 960950
5
967813 828020 842138 888913 811531
5
853452 982605 937610 906263 816343
5
961307 921285 869224 983428 827746
5
938491 899918 889979 882136 870774
5
886927 924942 843090 983239 947225
10
896934 961371 864108 807996 823939 956651 879599 925949 961258 986139
10
957975 875784 861149 896693 930167 912945 915285 994409 933372 991270
10
879361 832212 885663 808490 967298 886184 863468 808702 819421 871652
10
830302 881620 885331 801056 822117 889281 962501 839494 949503 828675
10
890528 900531 946072 891051 841346 897977 820825 818238 945815 800218
10
825030 805932 997277 856987 977797 817488 838973 817358 956433 920324
10
861127 852829 961480 841815 822987 914820 836105 851082 974030 829216
10
909074 962176 817683 940730 836760 837788 921876 932174 828093 930018
10
839556 801283 935807 815082 835694 843378 836280 964814 925881 975378
10
913029 810131 841760 981263 940781 926760 926686 959915 913063 854890
10
995574 994339 815566 850731 3 87 98 966451 84 47
10
919172 89 866541 27 30 53 74 863959 858030 885101
10
935605 95 939073 15 49 812005 834352 911443 81 11
10
887723 802966 97 828644 62 998479 54 11 95 921773
10
50 99 71 977136 897585 920333 839154 930414 88 13
10
5 29 23 902672 982536 948077 936694 68 16 985045
10
77 919029 99 81 844954 73 843481 56 929928 845206
10
29 60 865523 68 948251 69 837792 805004 994705 17
10
98 810553 17 990264 917093 870546 967961 57 16 14
10
37 44 889716 812490 906785 982531 981236 26 57 18
10
12 907500 96 863069 82 2 84 995902 930583 883693
10
850182 805146 34 57 947805 75 3 874674 911191 39
10
834793 850470 23 76 13 95 24 900263 911897 808679
10
20 812403 99 859705 928070 976577 823721 82 12 50
10
957771 859233 63 31 23 96 908854 973795 74 968447
10
35 890937 99 21 13 906469 816635 15 996592 932314
10
891457 823210 78 5 91 67 878370 973872 821355 82
10
60 69 809167 16 35 993424 833276 893903 98 938494
10
57 972273 55 844113 60 911816 861787 36 61 937324
10
29 83 887324 808958 996276 819459 99 842772 75 74
10
920651 830405 112385 23060 175692 32885 522362 166470 374725 136615
10
350681 404375 513980 456425 3312 672960 187215 509815 915765 28890
9
780205 75815 64910 430904 390895 872325 57465 882125 106900
8
602691 439345 64730 110545 192163 527540 905235 227235
8
375590 960535 589550 43335 856690 860235 898880 664400
9
644759 180040 153921 862646 157950 237145 821685 854600 71924
10
640289 621485 23868 701340 854327 244495 161395 447672 642875 274270
7
587835 420950 186695 390340 633300 274170 350910
9
831270 566000 729433 631110 751725 45169 844168 649420 815956
8
589780 595657 37843 72270 144130 244361 323115 735118
9
85635 509975 148600 301320 61060 989645 659875 81080 353695
7
789450 38405 976859 329527 440311 849300 875629
10
36555 944350 424850 659014 542890 977020 7375 528500 60355 184650
10
856605 462055 878355 381794 153556 368385 920765 314875 547700 633955
7
403550 216735 241180 718230 352155 532820 672260
9
944680 676340 456370 617345 785205 767510 717975 669305 753371
8
777470 39175 959798 874700 936952 201385 901949 334820
10
704957 82540 890844 407155 730855 793940 241335 446538 513905 365150
7
67830 55915 21970 757965 252935 828875 782725
9
81590 110115 668935 566865 240840 577170 943480 146535 1185
10
694212 901045 253084 760442 333442 976292 31148 44922 295391 996884
10
418723 744780 988 838681 232285 512524 11043 541509 452204 748509
9
762488 344985 858068 554758 334562 916206 936852 510892 902858
8
66727 354055 325526 428763 425656 117722 734653 678504
7
725132 43751 583660 838614 263720 982972 455774
10
263846 866788 550978 145873 612034 857038 764859 925429 19722 122118
8
330591 472669 513144 599924 27508 592224 533566 698841
9
910886 949462 980748 267401 267426 566889 909106 23294 977921

oneperson.py

# coding: utf8

import sys

def do_harf(probrem):
    """ 全要素を1/2 """
    return map(lambda n: int(n/2), probrem)

def do_five(probrem):
    """ 5の倍数要素を削除 """
    ret = [n for n in probrem if n % 5 != 0]
    if len(ret) == len(probrem):    #無駄
        return None
    return ret

action_map = {'H': do_harf, '5': do_five}

def check(probrem, solver, skips):
    for action in solver:
        probrem = action_map[action](probrem)
        if probrem is None:
            skips.add(solver)  #枝切り対象
            return False

    return len(probrem) == 0

def gen_solver(skips):
    solvers=['']
    for solver in (s for s in solvers if s not in skips):
        for c in 'H5':
            new_solver=solver+c
            solvers.append(new_solver)
            yield new_solver

def solve(probrem):
    skips = set()
    for solver in gen_solver(skips):
        if check(probrem, solver, skips):
            return solver

for line in sys.stdin.readlines()[2::2]:
    probrem = map(int, line.rstrip().split(' '))
    print len(solve(probrem))

out2.txt

2
5
8
4
1
1
16
1
1
2
4
21
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
9
8
15
21
10
21
7
17
10
12
21
13
21
19
21
21
18
21
18
15
14
15
21
9
10
21
21
11
14
10
10
21
13
21
9
12
13
17
19
21
7
10
7
5
1
21
21
1
21
15
1
11
14
21
1
3
21
21
1
1
21
11
21
11
11
21
21
14