A問題のsmallとlarge、C問題のsmallとlarge 1を解きました。
Problem A. Tic-Tac-Toe-Tomek
4かける4のマス目がある。
各プレイヤーの駒(O, X)が縦横斜め一列に並んでいる場合にそのプレイヤーは勝利となる。
ただし一列のうち、ひとつの駒がTであっても勝利となる。
このゲームの勝敗を答える。
ただしどちらかの勝利以外に引き分けの場合と、ゲームが終わってない場合が考えられる。
やるだけ問題。
import sys T = int(raw_input()) for i in xrange(1, T + 1): board = [] for j in xrange(4): board.append(list(raw_input().strip())) empty = 0 winX = False winO = False for j in xrange(4): countX = 0 countO = 0 countT = 0 for k in xrange(4): if board[j][k] == '.': empty += 1 elif board[j][k] == 'X': countX += 1 elif board[j][k] == 'O': countO += 1 elif board[j][k] == 'T': countT += 1 if countX == 4 or (countX == 3 and countT == 1): winX = True elif countO == 4 or (countO == 3 and countT == 1): winO = True for k in xrange(4): countX = 0 countO = 0 countT = 0 for j in xrange(4): if board[j][k] == '.': empty += 1 elif board[j][k] == 'X': countX += 1 elif board[j][k] == 'O': countO += 1 elif board[j][k] == 'T': countT += 1 if countX == 4 or (countX == 3 and countT == 1): winX = True elif countO == 4 or (countO == 3 and countT == 1): winO = True countX = 0 countO = 0 countT = 0 for j in xrange(4): if board[j][j] == '.': empty += 1 elif board[j][j] == 'X': countX += 1 elif board[j][j] == 'O': countO += 1 elif board[j][j] == 'T': countT += 1 if countX == 4 or (countX == 3 and countT == 1): winX = True elif countO == 4 or (countO == 3 and countT == 1): winO = True countX = 0 countO = 0 countT = 0 for j in xrange(4): if board[j][3 - j] == '.': empty += 1 elif board[j][3 - j] == 'X': countX += 1 elif board[j][3 - j] == 'O': countO += 1 elif board[j][3 - j] == 'T': countT += 1 if countX == 4 or (countX == 3 and countT == 1): winX = True elif countO == 4 or (countO == 3 and countT == 1): winO = True if winX: result = 'X won' elif winO: result = 'O won' elif empty == 0: result = 'Draw' else: result = 'Game has not completed' print "Case #{0}: {1}".format(i, result) raw_input()
Problem C. Fair and Square
与えられた範囲内の数について、以下の条件を満たす個数を答える。
large 1では探索する数の範囲の最大値がである。
求めるべき数は二乗であるからまでの数の二乗を調べて、回文数になっていれば列挙しておけばいい。
(二乗する前の数も回文数なことを使えば更に調べる範囲を減らせる)
あとは列挙した条件を満たす数の中から、入力として与えられた範囲を二分探索して、その間の個数を返せばよい。
(条件を満たす数が少ないから、普通に線形探索しても通るかも)
import sys import bisect palindrome = [] valid = [] for i in xrange(1, 10**7 + 1): s = str(i) r = s[::-1] if s == r: palindrome.append(i) for i in palindrome: square = i * i if square > 10 ** 14: break s = str(square) r = s[::-1] if s == r: valid.append(square) T = int(raw_input()) for i in xrange(1, T + 1): A, B = map(int, raw_input().split()) start = bisect.bisect_left(valid, A) end = bisect.bisect_right(valid, B) print "Case #{0}: {1}".format(i, end - start)