No.3084 Identify f(x)
タグ : / 解いたユーザー数 141
作問者 :
寝癖
👑
amentorimaru
👑 Notes for those new to interactive problems
Collapsed (click to expand)
This problem is an interactive problem.
This is a type of problem in which your program and the judge communicate with each other through standard input and output.
Therefore, your program needs to receive input after producing output. If you do not flush the output at that point, the judge may be unable to read your program's output, and a deadlock may occur in which your program is trying to receive input while the judge has not provided it.
For flushing the output, refer to the collapsed section below along with the Problem Statement and the Input and Output section.
Examples (If you use the proconio crate in Rust, checking this section is recommended.)
For C++
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)#include<iostream>
using namespace std;
int main(){
int x = 0;
cout << "? " << x << endl;//endlを使用すると自動的にflushされる。
int R;
cin >> R;//R=f(x)を満たすRを受け取る
return 0;
}
For Python
The following code asks $1$ question using a declared integer $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
import sys
x = 0
print(f"? {x}")# 改行あり(通常は自動でflushされる)
R = int(input())# R=f(x)を満たすRを受け取るFor Java
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);// 標準入力の設定
int x = 0;
System.out.println("? " + x); // 改行あり(通常は自動でflushされる)
int R = sc.nextInt();// R=f(x)を満たすRを受け取る
}
}For C
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
#include <stdio.h>
int main() {
int x = 0;
printf("? %d\n", x);// この命令ではflushは行われない
fflush(stdout);// flushを行う
int R;
scanf("%d", R)// R=f(x)を満たすRを受け取る
return 0;
}
For Rust
Rust users are expected to often use the proconio crate; in that case, the judge environment uses a release build.
In this case, input is "read all at once", and the judge result for an interactive problem may become TLE.
This can be avoided by using the input_interactive! macro.
The following code uses the input_interactive! macro, asks $1$ question using a declared integer $x$, and receives the corresponding $R$. (This is not a solution to this problem.)
use proconio::input_interactive;
fn main() {
let mut x = 0;
println!("? {}", x);// 改行あり(通常は自動でflushされる)
input_interactive!(R: i64);// R=f(x)を満たすRを受け取る
}
For Nim
The following code asks $1$ question using a declared integer $x$. (This is not a solution to this problem.)
import strutils var x = 0 echo "? ", x # 改行あり(通常は自動でflushされる) var R = readLine(stdin).parseInt()# R=f(x)を満たすRを受け取る
Story
Yu-san is a student studying at Virtual Koyaso Academy. Today, it seems she will study linear functions using a textbook called "Mathematics 2".
While studying, Yu-san suddenly murmured:
"Hmm, I'm tired... I want to take a break..."
Hearing this, the teacher said:
"Well then, let's try something called the 'function guessing game'. While we're at it, I'll make it a competitive programming problem. Competitive programming is a way to take a break, right?"
Problem Statement
This problem is an interactive problem (a problem in which the program you write and the judge program communicate through standard input and output).
It is known that the function $f$ can be expressed as $f(x) = ax+b$ using integers $a,b$.
The values of $a,b$ are not given, but the constraints guarantee that both $a,b$ are between $-100$ and $100$, inclusive.
You may ask questions of the following form at most $100$ times. Identify $a,b$.
- Choose one integer between $-1000$ and $1000$, inclusive, as $x$. Ask for the value of $f(x)$.
Input and Output
This problem is an interactive problem (a problem in which the program you write and the judge program communicate through standard input and output).
Initially, no input is given.
You may ask the following question at most $100$ times.
- Print the value of an integer $x$ between $-1000$ and $1000$, inclusive. This asks the judge for the value of $f(x)$.
To ask the above question, print in the following format. In particular, note that you must print ? (a question mark and a space) before $x$.
? $x$
Then, flush the output.
What does it mean to flush the output?
Normally, a program's standard output is buffered and is not output until a certain amount of data has accumulated. However, in an interactive problem, "output must reach the judge immediately when it is made".
Therefore, you need to flush manually so that the output is made without waiting for data to accumulate.
Examples (If you use the proconio crate in Rust, checking this section is recommended.)
For C++
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)#include<iostream>
using namespace std;
int main(){
int x = 0;
cout << "? " << x << endl;//endlを使用すると自動的にflushされる。
int R;
cin >> R;//R=f(x)を満たすRを受け取る
return 0;
}
For Python
The following code asks $1$ question using a declared integer $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
import sys
x = 0
print(f"? {x}")# 改行あり(通常は自動でflushされる)
R = int(input())# R=f(x)を満たすRを受け取るFor Java
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);// 標準入力の設定
int x = 0;
System.out.println("? " + x); // 改行あり(通常は自動でflushされる)
int R = sc.nextInt();// R=f(x)を満たすRを受け取る
}
}For C
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
#include <stdio.h>
int main() {
int x = 0;
printf("? %d\n", x);// この命令ではflushは行われない
fflush(stdout);// flushを行う
int R;
scanf("%d", R)// R=f(x)を満たすRを受け取る
return 0;
}
For Rust
Rust users are expected to often use the proconio crate; in that case, the judge environment uses a release build.
In this case, input is "read all at once", and the judge result for an interactive problem may become TLE.
This can be avoided by using the input_interactive! macro.
The following code uses the input_interactive! macro, asks $1$ question using a declared integer $x$, and receives the corresponding $R$. (This is not a solution to this problem.)
use proconio::input_interactive;
fn main() {
let mut x = 0;
println!("? {}", x);// 改行あり(通常は自動でflushされる)
input_interactive!(R: i64);// R=f(x)を満たすRを受け取る
}
For Nim
The following code asks $1$ question using a declared integer $x$. (This is not a solution to this problem.)
import strutils var x = 0 echo "? ", x # 改行あり(通常は自動でflushされる) var R = readLine(stdin).parseInt()# R=f(x)を満たすRを受け取る
See also this page.
After you ask this question, the value of $R$ satisfying $R=f(x)$ for the printed $x$ is given by the judge in the following format; receive it from standard input. (The constraints guarantee that $R$ is always an integer.)
$R$
However, if any of the following conditions holds, -1000000000 $(=-10^9)$ is given instead. (The constraints guarantee that -100000000 is never given as the answer to a valid question.)
- You printed a value that does not satisfy the conditions or is otherwise invalid.
- The number of questions exceeded $100$.
In this case, the judge has already treated your submission as WA, so terminate your program immediately.
After repeating questions and identifying $a,b$, print $a,b$ in the following format. In particular, note that you must print ! (an exclamation mark and a space) before $a$ and $b$.
! $a$ $b$
Then, flush the output and terminate your program immediately.
What does it mean to flush the output?
Normally, a program's standard output is buffered and is not output until a certain amount of data has accumulated. However, in an interactive problem, "output must reach the judge immediately when it is made".
Therefore, you need to flush manually so that the output is made without waiting for data to accumulate.
Examples (If you use the proconio crate in Rust, checking this section is recommended.)
For C++
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)#include<iostream>
using namespace std;
int main(){
int x = 0;
cout << "? " << x << endl;//endlを使用すると自動的にflushされる。
int R;
cin >> R;//R=f(x)を満たすRを受け取る
return 0;
}
For Python
The following code asks $1$ question using a declared integer $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
import sys
x = 0
print(f"? {x}")# 改行あり(通常は自動でflushされる)
R = int(input())# R=f(x)を満たすRを受け取るFor Java
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);// 標準入力の設定
int x = 0;
System.out.println("? " + x); // 改行あり(通常は自動でflushされる)
int R = sc.nextInt();// R=f(x)を満たすRを受け取る
}
}For C
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
#include <stdio.h>
int main() {
int x = 0;
printf("? %d\n", x);// この命令ではflushは行われない
fflush(stdout);// flushを行う
int R;
scanf("%d", R)// R=f(x)を満たすRを受け取る
return 0;
}
For Rust
Rust users are expected to often use the proconio crate; in that case, the judge environment uses a release build.
In this case, input is "read all at once", and the judge result for an interactive problem may become TLE.
This can be avoided by using the input_interactive! macro.
The following code uses the input_interactive! macro, asks $1$ question using a declared integer $x$, and receives the corresponding $R$. (This is not a solution to this problem.)
use proconio::input_interactive;
fn main() {
let mut x = 0;
println!("? {}", x);// 改行あり(通常は自動でflushされる)
input_interactive!(R: i64);// R=f(x)を満たすRを受け取る
}
For Nim
The following code asks $1$ question using a declared integer $x$. (This is not a solution to this problem.)
import strutils var x = 0 echo "? ", x # 改行あり(通常は自動でflushされる) var R = readLine(stdin).parseInt()# R=f(x)を満たすRを受け取る
See also this page.
Constraints
- $-100\le a,b \le 100$
- $a,b$ are integers
Notes
- Each time you print output, add a newline at the end and flush standard output. Otherwise, the judge result may be TLE.
What does it mean to flush the output?
Normally, a program's standard output is buffered and is not output until a certain amount of data has accumulated. However, in an interactive problem, "output must reach the judge immediately when it is made".
Therefore, you need to flush manually so that the output is made without waiting for data to accumulate.
Examples (If you use the proconio crate in Rust, checking this section is recommended.)
For C++
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)#include<iostream> using namespace std; int main(){ int x = 0; cout << "? " << x << endl;//endlを使用すると自動的にflushされる。 int R; cin >> R;//R=f(x)を満たすRを受け取る return 0; }For Python
The following code asks $1$ question using a declared integer $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
import sys x = 0 print(f"? {x}")# 改行あり(通常は自動でflushされる) R = int(input())# R=f(x)を満たすRを受け取るFor Java
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in);// 標準入力の設定 int x = 0; System.out.println("? " + x); // 改行あり(通常は自動でflushされる) int R = sc.nextInt();// R=f(x)を満たすRを受け取る } }For C
The following code asks $1$ question using a declared int variable $x$ and receives the corresponding $R$. (This is not a solution to this problem.)
#include <stdio.h> int main() { int x = 0; printf("? %d\n", x);// この命令ではflushは行われない fflush(stdout);// flushを行う int R; scanf("%d", R)// R=f(x)を満たすRを受け取る return 0; }For Rust
Rust users are expected to often use the proconio crate; in that case, the judge environment uses a release build.
In this case, input is "read all at once", and the judge result for an interactive problem may become
TLE.This can be avoided by using the
input_interactive!macro.The following code uses the
input_interactive!macro, asks $1$ question using a declared integer $x$, and receives the corresponding $R$. (This is not a solution to this problem.)use proconio::input_interactive; fn main() { let mut x = 0; println!("? {}", x);// 改行あり(通常は自動でflushされる) input_interactive!(R: i64);// R=f(x)を満たすRを受け取る }For Nim
The following code asks $1$ question using a declared integer $x$. (This is not a solution to this problem.)
import strutils var x = 0 echo "? ", x # 改行あり(通常は自動でflushされる) var R = readLine(stdin).parseInt()# R=f(x)を満たすRを受け取る
See also this page.
- If your program prints invalid output during the interaction or terminates midway, the judge result is undefined. In particular, note that if a runtime error occurs during the execution of your program, the judge result may be WA or TLE instead of RE.
- Terminate your program immediately after printing the answer. Otherwise, the judge result is undefined.
- The judge for this problem is not adaptive. That is, the pair $(a,b)$ satisfying $f(x)=ax+b$ is already determined at the time the program is executed.
Sample Interaction
The following is an example of an interaction with the judge. Note that this does not guarantee that asking questions like the ones below will always determine the correct $a,b$.
| Output by the program | Input from the judge | Explanation |
|---|---|---|
? 1 | Ask the judge a question with $x = 1$. | |
5 | The judge gives $5$, the answer to the question. | |
? 6 | Ask the judge a question with $x=6$. | |
20 | The judge gives $20$, the answer to the question. | |
? -5 | Ask the judge a question with $x=-5$. | |
-13 | The judge gives $-13$, the answer to the question. | |
! 3 2 | At this point, it can be shown that, among the functions possible under the constraints, every function other than $f(x) = 3x +2$ contradicts at least one of the judge's answers. Therefore, print $a=3,b=2$. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。