Contest Duration: ~ (local time) (120 minutes) Back to Home

Submission #433992

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:
if cho_max < cho or (cho_max == cho and nao_max > nao):
cho_max = cho
nao_max = nao
elif turn == 2:
if nao_max < nao or (nao_max == nao and cho_max > cho):
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
print nao
```

#### Submission Info

Submission Time 2015-06-27 22:33:20+0900 C - 双子と○×ゲーム sash Python (2.7.3) 0 1957 Byte WA 109 ms 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 108 ms 3888 KB
sample-02.txt 106 ms 3876 KB
test-01.txt 106 ms 3884 KB
test-02.txt 106 ms 3880 KB
test-03.txt 105 ms 3880 KB
test-04.txt 108 ms 3880 KB
test-05.txt 105 ms 3876 KB
test-06.txt 107 ms 3880 KB
test-07.txt 106 ms 3876 KB
test-08.txt 105 ms 3824 KB
test-09.txt 105 ms 3888 KB
test-10.txt 108 ms 3816 KB
test-11.txt 109 ms 3892 KB
test-12.txt 107 ms 3812 KB
test-13.txt 109 ms 3840 KB
test-14.txt 106 ms 3888 KB
test-15.txt 107 ms 3884 KB
test-16.txt 106 ms 3876 KB
test-17.txt 107 ms 3884 KB
test-18.txt 107 ms 3872 KB
test-19.txt 109 ms 3884 KB
test-20.txt 108 ms 3888 KB