Codeforces Round 937 (Div. 4)
2년만에 친구랑 코포
결과는 개같이 멸망
결과
A번 풀이
문제
https://codeforces.com/contest/1950/problem/A
Problem - A - Codeforces
codeforces.com
알고리즘 분류
구현
풀이
a,b,c 값이 3개이므로 단순히 대소비교만 해주면 된다.
from sys import stdin
input=stdin.readline
for i in range(int(input())):
a,b,c=map(int,input().split())
if a<b<c:
print("STAIR")
elif a<b and b>c:
print("PEAK")
else:
print("NONE")B번 풀이
문제
https://codeforces.com/contest/1950/problem/B
Problem - B - Codeforces
codeforces.com
알고리즘 분류
구현
풀이
조금 고민을 했다. 예전에 푼 별찍기와 같이 재귀적으로 구현을 해야 하나 고민을 했는데, 굳이 그럴 필요 없이 단순 구현으로 풀릴 거 같아서 단순 구현으로 풀었다. 그런데 제대로 생각 안하고 제출했다가 1WA 적립..
from sys import stdin
input=stdin.readline
for i in range(int(input())):
n=int(input())
p1=""
p2=""
for i in range(n):
if i%2==0:
p1+="##"
p2+=".."
else:
p2+="##"
p1+=".."
for i in range(2*n):
if i%4<2:
print(p1)
else:
print(p2)C번 풀이
문제
https://codeforces.com/contest/1950/problem/C
Problem - C - Codeforces
codeforces.com
알고리즘 분류
구현, 수학
풀이
출력 형식 잘 기억 안나서 그냥 문자열로 바꾼 뒤 해결했다. 문제 자체는 어려울 것 없었던 것 같다.
from sys import stdin
input=stdin.readline
for i in range(int(input())):
h,m=map(int,input().split(':'))
if h>=12:
if h!=12:
h-=12
if h<10:
h='0'+str(h)
if m<10:
m='0'+str(m)
print(h,":",m," PM",sep="")
else:
if h==0:
h+=12
if h<10:
h='0'+str(h)
if m<10:
m='0'+str(m)
print(h,":",m," AM",sep="")D번 풀이
문제
https://codeforces.com/contest/1950/problem/D
Problem - D - Codeforces
codeforces.com
알고리즘 분류
구현, 브루트포스
풀이
1을 제외한 1과 0으로 이루어진 수 (<50000)을 모두 구한 뒤 각 수에 대해 소수 판별하듯이 나눠지는지 확인하면 되는 문제, 몇개 안되서 하나하나 타이핑 해볼까 하다가 뇌절와서 그냥 코드를 짜서 구해줬다.
from sys import stdin
input=stdin.readline
bi=[int(bin(i)[2:]) for i in range(2,32)][::-1]
def check(n):
while n!=1:
able=False
for i in bi:
if n%i==0:
able=True
n//=i
if not able:
return 0
return 1
for i in range(int(input())):
n=int(input())
if n==1:
print("YES")
else:
if check(n):
print("YES")
else:
print("NO")
E번 풀이
못풀었다! 사실 해석도 못했다! 해석이 안되서 그냥 넘기고 F부터 풀었다. 놀랍게도 D까진 굉장히 빨리 풀어서 E번도 쉽게 풀 수 있을 줄 알았다!
F번 풀이
문제
https://codeforces.com/contest/1950/problem/F
Problem - F - Codeforces
codeforces.com
알고리즘 분류
그리디, 구현, 브루트포
풀이
3종류의 노드가 있다, A노드는 자식노드가 무조건 2개, B는 1개, C는 0개이다. 해당 노드들의 개수가 주어졌을 때 트리를 구성할 수 있는지를 확인하고 가능하다면 높이를 출력하는 문제였다. 높이는 리프 노드에서 루트 노드까지의 거리중 최대값이다. 한참 고민하다 수많은 조건들을 거는 것 외에는 풀이가 떠오르지 않아서 구현을 시작했다. 아이디어는 간단했다.
A타입 노드의 개수가 중요했다. A타입 노드에는 2개의 자식 노드를 가질 수 있다. 따라서 트리의 맨 밑에 오게되는 c의 개수는 A노드의 개수에 따라 영향을 받는다. 최종 바닥에 올 수 있는 노드의 개수는 A+1개이다 (A가 1개면 2개,A가 2개면 A에 A를 붙이므로 3개) 이런 식으로,
일단 A노드로만 이어진 트리를 구성해준다. 왜냐하면 같은 개수로 트리를 구성하였을 때 A로 이루어진 트리가 가장 높이가 낮다. 그렇게 구성하면 맨 밑줄은 A노드가 차있거나 비어있을 것이다. 일단 b 노드가 존재한다면 비어있는 부분을 채워주면 된다. 그렇다면 이제 트리의 맨 밑에 올 수 있는 노드들의 개수를 알 수 있고, b노드 c노드 순서로 채워준다.
그리고 a노드의 개수가 0일때와 같은 상황들을 예외처리 해주면 풀 수 있었다. 2번 WA 받고 통과했다.
from sys import stdin,setrecursionlimit
input=stdin.readline
for i in range(int(input())):
a,b,c=map(int,input().split())
bo=a
h=-1
if a==0:
if c!=1:
print(-1)
else:
print(b+c-1)
elif a+1!=c:
print(-1)
else:
i=0
while True:
if a>=2**i:
a-=2**i
h+=1
i+=1
else:
break
notfill=2**i-a if a!=0 else 0
if notfill:
if b!=0 and notfill>b:
print(h+2)
elif b>=notfill:
b-=notfill
h+=1
h+=b//(bo+1)
if b%(bo+1):
h+=1
print(h+1)
else:
print(h+1 if notfill==0 else h+2)
else:
h+=b//(bo+1)
if b%(bo+1):
h+=1
print(h+1)더럽고 더러운 코드..
결과
아 어렵다 코딩