help with a DP problem.

Правка en3, от kofhearts, 2015-12-14 07:05:45

hello codeforces,

I have come here to ask help to dp experts. I will highly appreciate it if you can help solve this dilemma. I have been struggling with this for a while now.

The problem can be found here.

http://codeforces.net/contest/69/problem/D

I have stepped through the logic of my DP formulation and i dont seem to spot the fallacy. So, can you please point out the point where my logic fails. I will highly appreciate it. Thanks for your time. I have commented out parts of my code for legibility.

The test case that fails is the following


-100 -100 10 200 0 1 1 0 1 1 31 41 3 4 5 2 1 2 3 3 9 8 10 2

Code starts below


import math vectors = [] line_parts = raw_input().split() x = int(line_parts[0]) y = int(line_parts[1]) n = int(line_parts[2]) d = int(line_parts[3]) for i in range(n): l = raw_input().split() vectors.append((int(l[0]), int(l[1]))) mp = {} def canWin(x, y, t, fs, ss): if math.sqrt(math.pow(x, 2) + math.pow(y, 2)) > float(d): return False if (x, y, t) in mp: return mp[(x, y, t)] result = True if t == False and ss == False: #if Dasha turn and if dasha hasnt swapped then can swap 1 time for v in vectors: result = result and (not (canWin(x + v[0], y + v[1], not t, fs, ss))) result = result and (not canWin(y, x, not t, fs, True)) #swap step elif t == True and fs == False: #if Anton turn and if Anton hasnt swapped then can swap 1 time for v in vectors: result = result and (not (canWin(x + v[0], y + v[1], not t, fs, ss))) result = result and (not canWin(y, x, not t, True, ss)) #swap step else: #since both has swapped 1 time now cannot swap further for v in vectors: result = result and (not (canWin(x + v[0], y + v[1], not t, fs, ss))) mp[(x, y, t)] = result return result result = False for v in vectors: result = result or canWin(x + v[0], y + v[1], False, False, False) if result == True: print "Anton" else: print "Dasha"
Теги factorisation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский kofhearts 2015-12-18 11:48:03 1070
en4 Английский kofhearts 2015-12-14 17:18:49 2111 solved
en3 Английский kofhearts 2015-12-14 07:05:45 1465 added full code
en2 Английский kofhearts 2015-12-14 06:14:07 228 added a clarification
en1 Английский kofhearts 2015-12-14 06:06:59 1978 Initial revision (published)