CODE FESTIVAL 2017 qual A B - fLIP
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time import numpy as np from numpy import linalg as LA # 時々使う # import numpy as np # from decimal import Decimal, ROUND_HALF_UP # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) # MOD = 10 ** 9 + 7 MOD = 998244353 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, M, K = il() for i in range(N+1): for j in range(M+1): if j * (N - i) + i * (M - j) == K: print('Yes') else: print('No') if __name__ == '__main__': main()
考え方
N
(行)のボタンを押すと、M
(列)個のボタンに対して、反転が発生する。
M
(列)のボタンを押すと、N
(行)個のボタンに対して、反転が発生する。
このとき、黒くなるボタンは、X - Xのボタンが押された回数
だけ反転する。
あとはM
とN
の取りうる範囲を全探索して、作ることができる黒いマスの個数を全て求める。