시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB56171436.842%

문제

This problem is interactive. Refer to the Interaction section below for a better understanding.

Today was the first class of CS999.

First, you have learned non-negative integer less than or equal to $4 \times 10^{18}$.
You have also learned the addition, subtraction, and comparison of two integers.

The homework is to compare two fractions $\frac{A}{B}$ and $\frac{C}{D}$. Professor told you that you can solve homework only using classroom materials.

You are only allowed to use the following operations:

  • Addition: For two integers $a$ and $b$, you can calculate $a+b$. The result should be less than or equal to $4 \times 10^{18}$.
  • Subtraction: For two integers $a$ and $b$, you can calculate $a-b$. The result should be non-negative.
  • Comparison: For two integers $a$ and $b$, you can know whether two elements are equal or which one is greater.

By using these operations, you have to compare two fractions.

제한

  • $1 \leq A, B, C, D \leq 10^9$

서브태스크 1 (5점)

This subtask has an additional constraint:

  • $\{A,B,C,D\} = \{1,2,3,4\}$

Your program should satisfy:

  • $n_{op} \le 200\,000$
 

서브태스크 2 (13점)

This subtask has an additional constraint:

  • $A, B, C, D \leq 10\,000$

Your program should satisfy:

  • $i_{max} \le 100$
  • $n_{op} \le 100\,000$
  • $X_{max} \le 10^9$
 

서브태스크 3 (21점)

This subtask has an additional constraint:

  • $A, B, C, D \leq 10^6$

Your program should satisfy:

  • $i_{max} \le 100$
  • $n_{op} \le 10\,000$
  • $X_{max} \le 2 \times 10^9$
 

서브태스크 4 (22점)

This subtask has no additional constraint.

Your program should satisfy:

  • $i_{max} \le 100$
  • $n_{op} \le 1\,000$

서브태스크 5 (18점)

This subtask has no additional constraint.

Your program should satisfy:

  • $i_{max} \le 100$
  • $n_{op} \le 1\,000$
  • $X_{max} \le 2 \times 10^9$
 

서브태스크 6 (21점)

This subtask has no additional constraint.

  • $i_{max} \le 100$
  • $n_{op} \le 1\,000$
  • $X_{max} \le 10^9$
 

예제 입력 1

-1

예제 출력 1

+ 5 3 1
- 1 2 1
< 1 5
! 0

For the first example, $A=1$, $B=1$, $C=2$, $D=2$. It satisfies the constraint of subtask 2,3,4,5,6.

 

예제 입력 2

1
-1
0

예제 출력 2

< 1 2
< 4 3
< 2 2
! -1

For the second example, $A=1$, $B=2$, $C=3$, $D=4$. It satisfies the constraint of every subtask.

 

노트

Interaction Protocol

You cannot get $A$, $B$, $C$, nor $D$ directly in this problem.
Instead, you can use some operations to a hidden array of length $10^6$; $X_1, X_2, \cdots, X_{10^6}$.

Initially, $X$ satisfies $X_1=A$, $X_2=B$, $X_3=C$, $X_4=D$, and $X_i=0$ for $i$ greater than $4$.

You can use the following commands to do operations:

  • To add two elements of $X$, print a string "+ i j k" ($1 \le i, j, k \le 10^6$). $X_i$ will be replaced with a value of $X_j+X_k$.
    To perform this operation, $X_j + X_k$ must be less than or equal to $4 \times 10^{18}$. If not, you will receive a verdict of "Wrong Answer". Nothing will be given to the input.
  • To subtract two elements of $X$, print a string "- i j k" ($1 \le i, j, k \le 10^6$). $X_i$ will be replaced with a value of $X_j-X_k$.
    To perform this operation, $X_j \ge X_k$ must be satisfied. If not, you will receive a verdict of "Wrong Answer". Nothing will be given to the input.
  • To compare two elements of $X$, print a string "< i j" ($1 \le i, j \le 10^6$). A line containing one integer will be given to the input. 
    • "-1" will be given when $X_i<X_j$.
    • "0" will be given when $X_i=X_j$.
    • "1" will be given when $X_i>X_j$.

After successfully comparing $\frac{A}{B}$ and $\frac{C}{D}$,

  • If $\frac{A}{B} < \frac{C}{D}$, print "! -1".
  • If $\frac{A}{B} = \frac{C}{D}$, print "! 0".
  • If $\frac{A}{B} > \frac{C}{D}$, print "! 1".

If you ask more than $200\,001$ commands or make an invalid query, the interactor will terminate immediately and your program will receive the verdict "Wrong Answer".

Scoring

If your comparison is incorrect, your score will be $0$.

Otherwise, the score of the program will be graded with three factors:

  • $i_{max}$, the maximum index of the array $X$ you have used in operations.
  • $n_{op}$, the number of operations you have done. Answer command will not be counted.
  • $X_{max}$, the maximum number in the array $X$ during operations.

출처

University > KAIST > 2022 KAIST RUN Spring Contest E번

채점 및 기타 정보

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