AtCoder Beginner Contest 224
23532 단어 Python시합 프로그램 설계AtCodertech
A - Tires
def main():
s = input()
print('er' if s[::-1][:2]=='re' else 'ist')
if __name__ == '__main__':
main()
입력 문자열의 어미를 보고 판정하면 된다.문자열의 길이를 고려하는 것은 매우 번거롭기 때문에 문자열이 반전된 후에 처음의 문자로 구분되었다.
B - Mongeness
def main():
h,w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
flg = True
for i1 in range(h-1):
for i2 in range(i1+1, h):
for j1 in range(w-1):
for j2 in range(j1+1, w):
if a[i1][j1]+a[i2][j2] > a[i2][j1]+a[i1][j2]:
flg = False
print("Yes" if flg else "No")
if __name__ == '__main__':
main()
종횡 격자 크기가 50 정도이기 때문에 전체 탐색도 늦지 않다.C - Triangle?
def func(xs, ys):
return abs((xs[0]-xs[2])*(ys[1]-ys[2]) - (xs[1]-xs[2])*(ys[0]-ys[2]))/2
def main():
n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
ret = func([lst[i][0], lst[j][0], lst[k][0]], [lst[i][1], lst[j][1], lst[k][1]])
if ret!=0:
ans += 1
print(ans)
if __name__ == '__main__':
main()
정점 3점 좌표를 제시할 때의 삼각형 면적을 고려하면 된다.여기 기사. 간단하고 이해하기 쉬우며 실제 계산된 면적 S가 0도 안 되는 상황을 모두 열거하면 된다.
D - 8 Puzzle on Graph
import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def to_str(lst):
return ''.join(list(map(str, lst)))
def main():
m = int(input())
g = [[] for _ in range(10)]
for _ in range(m):
u,v = map(int, input().split())
g[u].append(v)
g[v].append(u)
p = list(map(int, input().split()))
pos = [0]+[9]*9
for i,x in enumerate(p):
pos[x] = i+1
goal = [i for i in range(10)]
used = set()
que = deque([(pos, 0)])
ans = inf
while que:
state, cnt = que.popleft()
if state==goal:
ans = min(ans, cnt)
else:
emp_idx = state.index(9)
for nx in g[emp_idx]:
nx_state = state[:]
nx_state[emp_idx], nx_state[nx] = nx_state[nx], nx_state[emp_idx]
txt = to_str(nx_state)
if txt not in used:
used.add(txt)
que.append((nx_state, cnt+1))
print(ans if ans!=inf else -1)
if __name__ == '__main__':
main()
처음 보면 풀 수가 없어...!순환 구조와 집합에 관심을 가질 줄 알았는데 계산량을 고려하면 BFS로 해결할 수 있다고 한다.참고 자료
디스크의 상태를 관리하는 BFS는 되지만 스풀보드 객체는 컬렉션에 추가할 수 없으므로 문자열로 변환하여 기존 상태를 판단합니다.
그나저나 복사 상태일 때,cope.deepcopy 를 사용하면 TLE 가 됩니다.
Reference
이 문제에 관하여(AtCoder Beginner Contest 224), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://zenn.dev/ohnuma/articles/5577ce667850c9텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)