Submission #433903


Source Code Expand

Copy
b = []
c = []
b.extend(map(int, raw_input().split()))
b.extend(map(int, raw_input().split()))
c.extend(map(int, raw_input().split()))
c.extend(map(int, raw_input().split()))
c.extend(map(int, raw_input().split()))

pow3 = [pow(3, pos) for pos in xrange(9)]
cho_list = [-1 for _ in xrange(pow(3, 9)+1)]
nao_list = [-1 for _ in xrange(pow(3, 9)+1)]
ys = [0, 1, 3, 4, 6, 7]

def calc_id(map_id, pos, turn):
    return map_id + pow3[pos] * turn

def point(map_id):
    maps = [0 for _ in xrange(9)]
    tmp_map_id = map_id
    for i in xrange(9):
        maps[i] = tmp_map_id % 3
        tmp_map_id /= 3
    cho = 0
    nao = 0
    for x in xrange(6):
        if maps[x+3] != maps[x]:
            nao += b[x]
        else:
            cho += b[x]
        y = ys[x]
        if maps[y+1] != maps[y]:
            nao += c[x]
        else:
            cho += c[x]
    return cho, nao

def put(map_id, pos):
    return (map_id / pow3[pos]) % 3 != 0

# turn=1: chokudai, 2: naoko
def search(map_id, turn=1, num_put=0):
    if cho_list[map_id] > -1:
        return cho_list[map_id], nao_list[map_id]
    if num_put == 9:
        cho_list[map_id], nao_list[map_id] = point(map_id)
        return cho_list[map_id], nao_list[map_id]
    cho_max = 0
    nao_max = 0
    for pos in xrange(9):
        if put(map_id, pos):
            continue
        next_map_id = calc_id(map_id, pos, turn)
        cho, nao = search(next_map_id, 3 - turn, num_put+1)
        if turn == 1 and cho_max < cho:
            cho_max = cho
            nao_max = nao
        elif turn == 2 and nao_max < nao:
            cho_max = cho
            nao_max = nao
    cho_list[map_id] = cho_max
    nao_list[map_id] = nao_max
    return cho_list[map_id], nao_list[map_id]

cho, nao =  search(0)
print cho, nao

Submission Info

Submission Time
Task C - 双子と○×ゲーム
User sash
Language Python (2.7.3)
Score 0
Code Size 1833 Byte
Status
Exec Time 108 ms
Memory 3892 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt
All 0 / 100 test-01.txt, test-02.txt, test-03.txt, test-04.txt, test-05.txt, test-06.txt, test-07.txt, test-08.txt, test-09.txt, test-10.txt, test-11.txt, test-12.txt, test-13.txt, test-14.txt, test-15.txt, test-16.txt, test-17.txt, test-18.txt, test-19.txt, test-20.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
sample-01.txt 106 ms 3876 KB
sample-02.txt 106 ms 3880 KB
test-01.txt 105 ms 3880 KB
test-02.txt 105 ms 3876 KB
test-03.txt 107 ms 3880 KB
test-04.txt 105 ms 3892 KB
test-05.txt 107 ms 3884 KB
test-06.txt 106 ms 3880 KB
test-07.txt 105 ms 3880 KB
test-08.txt 106 ms 3872 KB
test-09.txt 106 ms 3880 KB
test-10.txt 105 ms 3880 KB
test-11.txt 104 ms 3880 KB
test-12.txt 107 ms 3704 KB
test-13.txt 104 ms 3876 KB
test-14.txt 105 ms 3888 KB
test-15.txt 108 ms 3880 KB
test-16.txt 107 ms 3892 KB
test-17.txt 106 ms 3880 KB
test-18.txt 105 ms 3884 KB
test-19.txt 105 ms 3876 KB
test-20.txt 105 ms 3876 KB