깊은 심연

시간 제한1초메모리 제한2048 MB

요약

128비트 해시 함수를 Frog 프로그램으로 주면 h(x)가 x와 같은 가장 작은 고정점을 찾거나, 고정점이 없으면 :(를 출력합니다.

난이도: 어려움10점 중 9점
유형: 비트 연산, 구현, 수학
정답자: 아직 제출이 없습니다

문제

Kieray에게 해시 함수 $h(x)$ 가 있다. 그녀는 $h(x_0) = x_0$ 를 만족하는 $h$ 의 고정점 $x_0$ 를 찾는 일을 도와주기를 바란다.

입력

입력에는 $h(x)$ 의 설명이 주어진다.

함수 $h(x)$ 는 Frog 언어로 작성된 프로시저로 기술된다. 이 언어에서 $x$ , $y$ , $z$ 같은 변수는 128비트 부호 없는 정수이다. 시작할 때 변수 $x$ 에는 $h$ 의 입력값이 들어 있고, 나머지 변수는 모두 0으로 초기화되어 있다. $h(x)$ 의 결과는 프로시저를 실행한 뒤의 $x$ 값이다.

프로시저는 최대 500줄이다. 각 줄은 식의 결과를 변수에 저장하는 대입문이다. Frog 언어는 비트 부정(~), 비트 AND(&), 비트 OR(|), XOR(^), 왼쪽 시프트와 오른쪽 시프트(<<, >>)를 지원한다. 의미는 C/C++와 비슷하다.

각 대입문에는 이항 연산이 최대 하나만 들어 있다. 식에는 (16진수) 상수를 쓸 수 있다. 비트 부정(~)은 각 변수나 상수에 최대 한 번만 적용할 수 있다. XOR(^) 식을 제외한 모든 식에는 변수가 최대 하나만 들어 있다. 시프트 연산의 오른쪽 피연산자(시프트 양)는 0 이상 128 이하이다.

Frog 언어의 확장 BNF 명세는 다음과 같다.

참고: "*"는 앞의 토큰이 0번 이상 나타남을, "{1,4}"는 앞의 토큰이 1번에서 4번까지 나타남을 뜻한다. 기호 "␣"는 공백 문자 하나를 나타낸다.

출력

$h(x)$ 의 고정점을 16진수로, 앞에 0을 붙이지 않고 출력한다. 형식은 확장 BNF 명세의 Hexadecimal을 따른다. 고정점이 여러 개이면 가장 작은 값을 출력한다. 고정점이 없으면 :(를 출력한다.

힌트

이것은 Kieray가 그린 일러스트이다. 아주 예쁘다.

예제4

예제 1
입력
```
x = x | 0x19260817
```
예상 출력
```
0x19260817
```
예제 2
입력
```
x = x ^ 0xdeadbeef
```
예상 출력
```
:(
```

예제 3

입력

y = ~x << 3
z = ~x >> 2
w = x & ~0xa
k = ~x ^ 0xc
k = k << 1
k = k >> 2
x = y ^ z
p = k ^ w
x = x ^ p

예상 출력

0x9a83dcd41ee6a0f73507b9a83dcd41ef

예제 4
입력
```
x = x | 0x1
x = x << 128
```
예상 출력
```
0x0
```