시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB203912051.282%

문제

초콜릿은 2차원 프로그래밍 언어의 일종이다. 아래는 초콜릿 언어의 동작 정의이다.

초콜릿 프로그램에서는 같은 글자가 상하좌우로 연결된 블록이 실행 단위이다. 빈 칸(아스키 32)은 실행되지 않는다. 맨 처음 실행되는 블록은 맨 왼쪽 위의 글자가 포함된 블록이며, 맨 왼쪽 위 글자가 빈 칸이면 프로그램이 실행되지 않는다.

블록 간 이동

한 블록에서 다음 실행할 블록을 결정하기 위해 $DP$와 $CC$의 두 가지 값이 존재한다. $DP$는 프로그램의 진행 방향(오른쪽, 아래, 왼쪽, 위)을 나타내며, $CC$는 그 방향을 바라봤을 때 어느 쪽 (맨 왼쪽이나 오른쪽) 블록을 선택할지를 나타낸다. 프로그램 시작 시에 $DP$는 오른쪽, $CC$는 왼쪽으로 초기화된다. $DP$와 $CC$가 주어졌을 때 다음 실행될 블록은 다음과 같이 결정된다.

  • 현재 블록의 글자들 중에서 $DP$의 방향으로 가장 멀리 있는 글자들을 찾는다.
  • 그 글자들 중에서 $DP$ 방향을 바라봤을 때 $CC$ 방향으로 가장 끝에 있는 글자를 고른다.
  • 그 글자에서 $DP$ 방향으로 이동한다.

예를 들어, 아래 그림에서 P 명령을 실행한 후 이동할 위치는 $DP$와 $CC$의 상태에 따라 표시된 8가지 중 하나가 된다. $DP$가 오른쪽, $CC$가 왼쪽이면 1로 이동하며, $DP$가 아래, $CC$가 오른쪽이면 4로 이동하게 된다.

이때 이동할 칸이 빈 칸이거나 프로그램 영역 밖이면 이동할 수 없으며, 다음과 같이 $DP$와 $CC$를 바꿔가며 이동할 칸을 찾는다.

  • $CC$를 왼쪽이면 오른쪽으로, 오른쪽이면 왼쪽으로 바꿔서 시도한다.
  • 그래도 이동할 수 없으면 $DP$를 시계 방향으로 90도 돌려서 다시 시도한다.
  • 이동할 수 있는 방향을 찾거나 8가지 조합을 모두 시도할 때까지 $CC$와 $DP$ 순서로 바꾸기를 계속 시도한다.

예를 들어 위 그림의 P 영역에서 현재 $DP$가 오른쪽, $CC$가 왼쪽일 때, 이동을 시도하는 순서는 1, 2, 4, 3, 5, 6, 8, 7 순이다.

8가지 조합을 모두 시도했는데 이동할 곳이 없으면 프로그램이 종료된다. 이것이 프로그램이 정상적으로 종료되는 유일한 방법이다.

명령 목록

초콜릿 언어에서 모든 데이터는 하나의 스택에 저장되고, 스택의 원소는 $[-2^{63}, 2^{63}-1]$ 범위 내의 정수이다.

초콜릿 언어에는 여러 가지 명령이 있으며, 각 블록에 진입할 때마다 그 블록의 글자 종류에 해당하는 명령이 실행된다. 다음은 명령의 목록이다. 모든 명령에 대해서, 동작이 불가능한 경우 (스택에 정수가 부족하거나 0으로 나누는 경우, 입력받을 글자가 없는 경우 등) 아무 일도 일어나지 않고 프로그램이 계속 실행된다.

  • I: stdin에서 1글자를 입력받아 그 글자의 아스키 코드를 스택에 넣는다. 더 이상 받을 글자가 없으면 무시한다.
  • O: 스택에서 정수 하나를 꺼내 256으로 나눈 나머지(0 이상 255 이하의 값)를 아스키 코드로 갖는 글자를 stdout으로 출력한다.
  • P: 현재 영역의 면적에 해당하는 정수를 스택에 넣는다.
  • p: 스택에서 정수 하나를 꺼내 버린다.
  • +: 스택에서 정수 $x$, $y$를 꺼내 $y+x$를 스택에 넣는다.
  • -: 스택에서 정수 $x$, $y$를 꺼내 $y-x$를 스택에 넣는다.
  • *: 스택에서 정수 $x$, $y$를 꺼내 $y \times x$를 스택에 넣는다.
  • /: 스택에서 정수 $x$, $y$를 꺼내 $\lfloor y/x \rfloor$를 스택에 넣는다.
  • %: 스택에서 정수 $x$, $y$를 꺼내 $y\%x$를 스택에 넣는다. 이 값은 $\lfloor y/x \rfloor \times x + y\%x = y$를 만족한다.
  • !: 스택에서 정수 $x$를 꺼내 $x$가 0이면 1, 아니면 0을 스택에 넣는다.
  • >: 스택에서 정수 $x$, $y$를 꺼내 $y>x$이면 1, 아니면 0을 스택에 넣는다.
  • D: 스택에서 정수 $x$를 꺼내 $DP$를 $x$번 시계 방향으로 90도 회전한다. $x$가 음수이면 반대 방향으로 $-x$번 회전한다.
  • C: 스택에서 정수 $x$를 꺼내 $CC$를 $|x|$번 반대로 바꾼다.
  • d: 스택에서 정수 $x$를 꺼내 $x$를 스택에 두 번 넣는다.
  • r: 스택에서 정수 $x$, $y$를 꺼낸 다음, 스택의 맨 위 $y$개 원소를 $x$번 "회전"한다. 여기서 회전이란, 가장 위에 있는 원소를 가장 아래로 이동하고 나머지를 한 칸씩 위로 올리는 동작이다. $x$가 음수이면 반대 동작을 $-x$번 반복한다. $y \le 0$이거나 $y$가 $x$와 $y$를 제거한 후의 스택의 길이보다 크면 회전 동작을 하지 않고 $y$와 $x$를 원래대로 다시 스택에 넣는다.

명령이 정의되지 않은 글자가 실행되면 런타임 에러가 발생한다. 스페셜 저지는 이 경우 "틀렸습니다"를 출력한다.

정의되지 않은 동작 (Undefined behavior)

다음의 경우에는 동작이 정의되어 있지 않다.

  • 코드에 아스키 범위를 벗어난 문자가 포함된 경우
  • 산술 연산에서 오버플로가 발생한 경우

이 경우 스페셜 저지는 C++ 인터프리터(아래 참조)의 동작을 따른다.

다음은 Hello World! 문제를 푸는 초콜릿 언어 코드의 예시이다.

PPPPPPdP+*d
PP        dO
  Ppd+PPd* Od
 dd    P -- dP
OO dOPPd+ ++ P
d ++  P +- P /
* P PP/O d p +
+ P P OO O P d
P P O   PP p P
PPO d-+dPP dPP
P d+  P   POPP
dP +*+PdPPP PP
 PP  P     --
  PO+PPOdOdO

이제 초콜릿 언어로 별 찍기 - 1 문제를 풀어보자. 문제의 내용은 아래의 입출력 설명을 참조하라.

입력

정수 $N$ ($1 \le N \le 100$)이 주어진다. 입력 끝에는 줄바꿈(아스키 코드 10)이 있다.

출력

첫째 줄부터 $N$번째 줄까지 별(아스키 코드 42)을 출력한다. $i$번째 줄에는 빈 칸 없이 별을 $i$개 출력한다. 줄과 줄 사이에는 줄바꿈(아스키 코드 10)을 출력해야 함에 유의하라.

예제 입력 1

5

예제 출력 1

*
**
***
****
*****

노트

코드의 길이가 524,288B를 초과하는 코드는 제출할 수 없다.

제출한 코드가 다음 중 하나에 해당하는 경우에는 코드의 출력과 상관없이 "틀렸습니다"를 받는다.

  • 코드의 가로와 세로 크기의 곱이 1,000,000을 초과
  • 어떤 입력에 대해 명령이 정의되지 않은 글자를 실행
  • 어떤 입력에 대해 1,000,000개의 명령을 실행할 때까지 코드가 종료되지 않음
  • 어떤 입력에 대해 성공적으로 수행된 r 명령의 $y$값의 합이 1,000,000을 초과

아래 링크에서 초콜릿 언어의 인터프리터를 다운받아 실행해 볼 수 있다.

chocolate.cpp

chocolate.py

실행 방법은 chocolate.exe src.txt < input.txt 또는 python chocolate.py src.txt < input.txt 이다.

출처

Contest > BOJ User Contest > 초콜릿컵 > 제1회 초콜릿컵 🍫번

제출할 수 있는 언어

Text

채점 및 기타 정보

  • 예제는 채점하지 않는다.