dlaud5379   1년 전

문제

프로그래밍 대회에 출제되는 여러 가지 문제는 어떤 면에서 극단적이라고 할 수 있다. 이런 문제를 한 번쯤 본 적이 있을 것이다.

  • 복잡한 수식을 종이로 계산하고 나온 웰노운인 수를 입력으로 주어진 자릿수에 맞추어서 반올림하고 출력하는 문제
  • 지문이 4페이지 분량을 넘어가고 비밀 요원들의 여러 가지 능력치를 추적해서 임무에 투입될 최적의 조를 편성하는 시뮬레이션을 짜는 문제
  • 올바른 답이 없음이 이미 증명되어 있지만 어쨌든 출제된 문제

이 문제 역시 가능한 테스트 케이스가 8가지밖에 없다는 점에서 극단적이고, 그런 만큼 '극'단적인 소재를 활용할 것이다.

[-10, 10] × [-10, 10]에 속하는 격자점을 입력으로 받는 함수를 생각하자. 즉, f(x, y)는 x와 y가 모두 -10 이상 10 이하의 정수일 때만 정의된다. 어떤 점 (x, y)에 대해 다음 조건이 모두 성립할 때 그 점을 함수 f의 극소점이라고 한다.

  • f(x, y) < f(x - 1, y)
  • f(x, y) < f(x + 1, y)
  • f(x, y) < f(x, y - 1)
  • f(x, y) < f(x, y + 1)

극대점 역시 위와 비슷하게 부등호의 방향을 뒤집어 정의한다. 한편, 어떤 점 (x, y)에 대해 다음 조건 중 하나가 성립할 때 그 점을 함수 f의 정류점이라고 한다.

  • f(x, y) = f(x - 1, y)
  • f(x, y) = f(x + 1, y)
  • f(x, y) = f(x, y - 1)
  • f(x, y) = f(x, y + 1)

이때 위 조건이 성립하려면 함수에 전달하는 모든 인자가 정의역인 [-10, 10] × [-10, 10] 격자에 포함되어 있어야 한다. 특히 격자의 경계 부분은 함수의 극소점이나 극대점이 될 수 없지만, 정류점은 될 수 있다.

입력으로 주어진 정보에 따라 다음 조건을 만족하거나 만족하지 않는 함수를 구하는 프로그램을 작성하여라.

  • 극대점이 2개 이상
  • 극소점이 2개 이상
  • 정류점이 존재

출력하는 함수는 출력 설명을 따라서 정의해야 한다.

입력

입력은 세 줄로 주어진다.

첫째 줄에는 문자열 "Multiple local maxima: " 다음에 "Yes"나 "No"가 주어진다. Yes일 경우 함수의 극대점이 2개 이상 존재해야 하고, No일 경우 2개 이상 존재해서는 안 된다.

둘째 줄에는 문자열 "Multiple local minima: " 다음에 "Yes"나 "No"가 주어진다. Yes일 경우 함수의 극소점이 2개 이상 존재해야 하고, No일 경우 2개 이상 존재해서는 안 된다.

셋째 줄에는 문자열 "Plateaus: " 다음에 "Yes"나 "No"가 주어진다. Yes일 경우 함수가 정류점을 가져야 하고, No일 경우 가져서는 안 된다.

출력

주어진 조건을 만족하는 함수를 한 줄로 출력한다. 단, 아래의 규칙과 주어진 조건을 만족하는 함수가 없을 경우 "No solution"을 출력한다.

함수를 출력할 때는 후위 표기법으로 출력해야 한다. 후위 표기법은 함수를 일종의 스택 머신처럼 작성하는 방식으로, 스택에 정수를 넣거나, 스택에서 정수를 빼고 새로운 정수를 계산해 넣는 여러 가지 명령으로 이루어져 있다.

함수는 최대 1000개의 명령으로 이루어져 있어야 하며, 각 명령은 공백으로 구분한다. 사용할 수 있는 명령은 다음과 같다.

  • -9 이상 +9 이하의 정수: 스택에 해당하는 정수를 넣는다.
  • x 혹은 y: 스택에 각각 매개변수 x와 y에 해당하는 값을 넣는다.
  • +, -, *, ^: 스택에서 두 수를 빼고 각각 그 수의 덧셈, 뺄셈, 곱셈, 거듭제곱을 스택에 넣는다. 처음 뺀 수가 오른쪽, 나중에 뺀 수가 왼쪽 피연산자에 해당한다. 즉, "9 5 -"는 4로, "x 2 ^"는 x2로 계산한다. 00은 1로 정의한다.

함숫값을 계산할 때 다음과 같은 경우가 발생하면 틀렸습니다를 받는다.

  • 빈 스택에서 수를 꺼내려고 할 때
  • 거듭제곱(^)의 지수로 음수가 주어졌을 때
  • 연산의 중간·최종 결과가 -231 이상 231 미만의 범위를 벗어날 때
  • 모든 명령을 실행한 뒤 스택에 남은 수가 1개가 아닐 때

힌트

예제 출력 1의 함수는 (x - 3)4 + (y + (-5))2에 해당하며, 이 함수는 극대점과 정류점이 없고 하나의 극소점을 가진다.

댓글을 작성하려면 로그인해야 합니다.