[BOJ 25621] 이상한 프로그래밍 언어

View as PDF
Submit solution
Points: 3
Time limit: 2.0s
Memory limit: 1G
Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

키파는 새로운 프로그래밍 언어를 만들었습니다. 이 프로그래밍 언어의 변수는 정확히 하나인데 지금부터 K라고 부르겠습니다. 최초에 K는 입력 값으로 설정됩니다.</p>

이 변수에 시행하는 연산은 다음과 같이 정의됩니다.

  • +x: K에 x를 더합니다.
  • -x: K에서 x를 뺍니다. 단, 이 프로그래밍 언어는 음이 아닌 정수만 처리할 수 있어서, 만일 K ≤ x이면 K는 0이 됩니다.
  • *x: K에 x를 곱합니다.

이 프로그래밍 언어의 특이한 점은 각 줄에 두 개의 연산을 받는다는 점입니다. 실행은 다음과 같은 식으로 이루어집니다.

  1. 수 하나를 입력받고, K를 입력받은 값으로 설정합니다.
  2. 각 줄에 있는 두 개의 연산 중 하나를 아무렇게나 선택합니다.
  3. 각 줄에 있는 연산을 K에 순서대로 적용합니다.
  4. 마지막 연산까지 시행한 후 K의 값을 출력합니다.

키파는 N개의 줄로 구성된 프로그램을 짰습니다. 이 프로그램의 가능한 출력 중 가장 큰 값은 무엇일까요?

입력 형식

첫째 줄에 N과 입력값 K0가 공백을 사이에 두고 주어집니다. (1 ≤ N ≤ 300 000, 0 ≤ K0 ≤ 109)</p>

둘째 줄부터 N개의 줄에 프로그램이 주어집니다. 구체적으로, (i + 1)번째 줄에 위에서 설명한 형식으로 된 연산 두 개가 공백을 사이에 두고 주어집니다.

연산에 쓰이는 수 x는 모두 0 이상 109 이하의 정수입니다.

출력 형식

첫째 줄에 가능한 출력 중 가장 큰 값을 109 + 7로 나눈 나머지를 출력합니다.</p>

가능한 출력을 109 + 7로 나눈 나머지를 최대화하는 것이 아님에 주의하세요.</strong>

예제 입력

3 15
+5 +10
-20 -30
*20 *10

예제 출력

100

힌트

가능한 실행 방법 중 하나는 다음과 같습니다.</p>

  1. K0 = 15를 입력받고, K를 그 값으로 설정합니다. 따라서 K := K0 = 15가 됩니다.
  2. 각 줄에서 연산을 하나씩 고르는데, 구체적으로 첫째 줄에서는 +10, 둘째 줄에서는 -20, 셋째 줄에서는 *20을 고릅니다.
  3. 각 연산을 순서대로 시행하면, 첫째 줄 시행 이후 K := 15 + 10 = 25, 둘째 줄 시행 이후 K := 25 − 20 = 5, 셋째 줄 시행 이후 K := 5 × 20 = 100이 됩니다.
  4. 100을 출력합니다.

이렇게 실행하는 방법이 다른 방법에 비해 가장 큰 값을 출력함을 알 수 있습니다. 가장 큰 출력값인 100을 109 + 7로 나눈 나머지인 100을 출력합니다.

Comments

There are no comments at the moment.