https://www.acmicpc.net/problem/18867
| 시간 제한 | 메모리 제한 |
| 0.1초 (추가 시간 없음) | 1024MB |
문제
욱제는 2020년 04월 02일 목요일 14시 00분에 논산 육군훈련소에 입소했다. 욱제는 2020년 04월 29일 수요일에 사회로 돌아온다. 욱제에게 격려의 메세지를 남겨주자.
단, 편지의 내용은 아래의 조건을 만족해야 한다.
답안은 [A-Za-z0-9 ] ASCII 문자로 구성하는 것을 권장하며, 이를 이용해 문제를 해결할 수 있음이 보장된다. 단, 문제의 체커(#)를 보고 이해한다면, 한글, 이모지 등 어떤 문자를 제출해도 상관이 없다.
1. 답안의 크기는 990316byte 이하여야 한다.
2. 채점기는 답안을 1byte 단위로 끊어서 읽는다.
3. i번째 byte를 int로 캐스팅한 정수값을 xi라고 하자.
4. x_i^814을 모두 더하여 20200429로 나눈 나머지를 y라고 하자.
5. y = 20200402을 만족하면 정답이다.
ㅎㅎ;; ㅈㅅ.. ㅋㅋ!!
입력
욱제에게 인터넷 편지를 보낼 수 있는 정보들이 주어진다.
출력
사랑 가득한 편지를 출력한다.
풀이
18857번부터 이어지는 욱제씨의 입대 문제 중 마지막 문제입니다. 뭔 말인가... 싶은데 조건을 만족하는 편지를 출력해내면 되는 것 같습니다. 실버 1이니 만만하게 봐도 될 것 같죠?
우선 [A-Za-z0-0]의 아스키코드를 사용하도록 하고 있습니다. 편지의 각 문자를 아스키코드로 변환하고 이걸 814제곱하여 더한 값의 20200429 모듈러 값이 20200402가 되면 조건을 만족하는 편지라고 합니다. 직접 814제곱을 손으로 계산하는 건 좀 그렇고 작업을 컴퓨터한테 짬처리 해봅시다.
import sys
input = sys.stdin.readline
def solution():
t = []
a = dict()
mod = 20200429
for i in range(48, 58): t.append(i)
for i in range(65, 91): t.append(i)
for i in range(97, 123): t.append(i)
for i in range(62):
k = t[i]
a[i] = chr(k)
for j in range(813):
t[i] *= k
t[i] %= mod
def dfs(d, y, path):
if d == 5:
if y == 20200402:
print(path)
exit()
return
for i in range(62):
dfs(d + 1, (y + t[i]) % mod, path + a[i])
return
dfs(0, 0, '')
print("there is no answer")
solution()이런 코드를 짜봤습니다. dfs로 길이 d의 문자열을 생성해 이게 20200429로 나눈 나머지가 20200402인지 확인합니다. 하나라도 있다면 그걸 출력하고, 하나도 없다면 "there is no answer"을 출력합니다.
d를 1~4로 설정했을 때 조건을 만족하는 해가 없음을 확인했습니다. d = 5일 때 조건을 만족하는 해를 찾을 수 있습니다. 그리고 긴 해를 찾아보기 위해 d = 6으로 설정해서 실행해보았으나 실행시간이 너무 길어져 그만뒀습니다. (62^6 = 56,800,235,584)
참고로 출력에 개행 문자가 들어가면 안됩니다. 파이썬의 경우, print("answer", end = '')로 개행 문자 없이 출력하도록 해야 정답이 뜹니다.
정답 코드
# 위에 코드 한 번 돌려보세용
