시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB49113611128.682%

문제

이 게임은 똥냄새가 너무 나서 도저히 볼 수가 없다! 따라서 당신은 직접 똥게임을 하지 않고 프로그램한테 똥게임을 시킬 것이다. 처음에는 사람 1명으로 시작한다. 당신에게는 총 $N$번의 턴이 주어지며, 각 턴마다 다음 선택지 4개중 2개가 주어진다. 같은 선택지가 주어질 수도 있다. 각 선택지는 $+x, -x, *x, /x \, (1 \leq x \leq 9)$ 중 하나로 주어진다.

  1. $+x$를 선택할 경우, 사람의 수가 $x$명만큼 증가한다.
  2. $-x$를 선택할 경우, 사람의 수가 $x$명만큼 감소한다.
  3. $*x$를 선택할 경우, 사람의 수가 $x$배가 된다.
  4. $/x$를 선택할 경우, 사람의 수가 $x$만큼 나눠진다. 만약 현재 사람 수가 x로 나눠지지 않을 경우 나머지는 버린다.

$N$개의 선택지 중 1번에 한해 광고를 보고 선택지를 건너뛸 수 있다. 광고를 보지 않고 선택지를 건너뛰지 않아도 된다. 만약 각 턴이 끝난 뒤 현재 사람이 0명 이하가 되면 게임 오버가 된다. 당신은 $N$번의 선택지를 거친 후 사람의 수를 최대로 만들어야 한다. 어떠한 선택을 하더라도 중간에 사람의 수가 32비트 정수 범위를 넘지 않음을 보장한다.

입력

첫 번째 줄에 선택지의 개수 $N \, (1 \leq N \leq 100,000)$가 주어진다. 

그 이후 $N$개의 줄에 걸쳐 2개의 선택지가 공백을 사이로 두고 주어진다.

각 선택지는 $+x, -x, *x, /x$ 중 하나로 주어진다 ($1 \leq x \leq 9$).

출력

$N$개의 선택지를 거친 후 최대 사람의 수를 출력한다. 

만약 어떤 선택을 하더라도 게임 오버가 된다면 ddong game을 출력한다.

예제 입력 1

3
+5 *2
+4 *2
-5 /2

예제 출력 1

12

예제 입력 2

3
+3 *6
-8 -9
-9 -9

예제 출력 2

ddong game

힌트

첫번째 예제에서는 $+5$, $*2$를 선택하고 3번째 선택지를 건너뛸 경우, 12명으로 최대가 된다.

두번째 예제에서는 어떤 선택지를 고르더라도 게임 오버가 된다.

출처

University > POSTECH > 2021 POSTECH Programming Contest C번