devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

交互题--

作者：凡人多烦事01 | 2024-02-10 19:04:45

赞

踩

交互题

文章目录

Guess the Number

题

This is a bit unusual problem — here you need to implement the interactive communication with the testing system. It means you have to make queries and get responses online. As usual, standard input/output is used. After printing each query you need to use special function to flush the output stream, because it is possible that some part of your output is left in the buffer. For example, you can use fflush(stdout) in C++, System.out.flush() in Java, flush(output) in Pascal and stdout.flush() in Python.

In this problem there is some hidden number and you have to interactively guess it. The hidden number is always an integer from 1 and to 1 000 000.

You can make queries to the testing system. Each query is one integer from 1 to 1 000 000. Flush output stream after printing each query. There are two different responses testing program can provide:

string “<” (without quotes), if the hidden number is less than the integer in your query;
string “>=” (without quotes), if the hidden number is greater than or equal to the integer in your query.
When your program is sure that guessed the hidden number, print string “! x”, where x is the answer, and terminate your program immediately after flushing the output stream.

Your program is allowed to make no more than 25 queries (not including printing the answer) to the testing system.

Input

Use standard input to read the responses to the queries.

The input will contain responses to your queries — strings “<” and “>=”. The i-th string is a response to the i-th your query. When your program will guess the number print “! x”, where x is the answer and terminate your program.

The testing system will allow you to read the response on the query only after your program print the query for the system and perform flush operation.

Output

To make the queries your program must use standard output.

Your program must print the queries — integer numbers xi (1 ≤ xi ≤ 106), one query per line. After printing each line your program must perform operation flush.

Each of the values xi mean the query to the testing system. The response to the query will be given in the input file after you flush output. In case your program guessed the number x, print string “! x”, where x — is the answer, and terminate your program.

在这里插入图片描述

Note

In the first sample, the hidden number is 12. In the provided example of the communication process, you can see six queries. Note that the answer is known even after the fifth query but you are allowed to ask unnecessary queries (unless you exceed the limit of 25 queries).

In the second sample, the hidden number is 43. After the provided three queries there are many possible answers but it’s fine to guess — if you guess correctly.

代码

#include<bits/stdc++.h>

using namespace std;
//往大爬意思是4变成了5，
int main(){
    int l=1,r=1000000;
    while (l<r){
        int mid=(l+r+1)/2;//不加1的话往大爬爬不动，如(9+10)/2=9,向10爬爬不动，
	//向小的爬，正常的不+1，不-1，四舍五入就是向小爬，但这而有+1，和下面的-1刚好互相抵消
        printf("%d\n",mid);
        fflush(stdout);
        char s[3];
        scanf("%s",s);
        if(s[0]=='<')  r=mid-1;//  <  小于，故mid-1, l符合'<' 
        else l=mid;//>= 可能等于    l符合'>=' 
    }
    printf("! %d\n",l);
    fflush(stdout);
}
/*
fflush(stdout);
在使用多个输出函数连续进行多次输出时，
有可能发现输出错误。
因为下一个数据再上一个数据还没输出完毕，
还在输出缓冲区中时，下
一个printf就把另一个数据加入输出缓冲区，
结果冲掉了原来的数据，出现输出错误。 
在 prinf（）；后加上fflush(stdout);
 强制马上输出，避免错误。
*/

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

Lost Numbers

题

This is an interactive problem. Remember to flush your output while communicating with the testing program. You may use fflush(stdout) in C++, system.out.flush() in Java, stdout.flush() in Python or flush(output) in Pascal to flush the output. If you use some other programming language, consult its documentation. You may also refer to the guide on interactive problems:
https://codeforces.com/blog/entry/45307.
The jury guessed some array a consisting of 6 integers. There are 6 special numbers — 4, 8, 15, 16, 23, 42 — and each of these numbers occurs in a exactly once (so, a is some permutation of these numbers).

You don’t know anything about their order, but you are allowed to ask up to 4 queries. In each query, you may choose two indices i and j (1≤i,j≤6, i and j are not necessarily distinct), and you will get the value of ai*aj
in return.

Can you guess the array a?

The array a is fixed beforehand in each test, the interaction program doesn’t try to adapt to your queries.

Interaction

Before submitting the answer, you may ask up to 4 queries. To ask a query, print one line in the following format: ? i j, where i and j should be two integers such that 1≤i,j≤6. The line should be ended with a line break character. After submitting a query, flush the output and read the answer to your query — one line containing one integer ai *aj. If you submit an incorrect query (or ask more than 4 queries), the answer to it will be one string 0. After receiving such an answer, your program should terminate immediately — otherwise you may receive verdict “Runtime error”, “Time limit exceeded” or some other verdict instead of “Wrong answer”.

To give the answer, your program should print one line
! a1 a2 a3 a4 a5 a6 with a line break in the end. After that, it should flush the output and terminate gracefully.

在这里插入图片描述

Note

If you want to submit a hack for this problem, your test should contain exactly six space-separated integers a1 a2 a3 a4 a5 a6. Each of 6 special numbers should occur exactly once in the test. The test should be ended with a line break character.

题意

总共有六个数字 4, 8, 15, 16, 23, 42 系统随便排序，你可以询问它4次，询问形式为 ？ai aj，例如 ？1 2代表的意思是下标为1的数字和下标为2的数字乘积为多少，要你输出系统给的 4, 8, 15, 16, 23, 42 这6数字的排序

代码

#include<bits/stdc++.h>

using namespace std;
int a[10];
int b[10]={4,8,15,16,23,42} ;
int book[10];
int sum[10]; 
int main(){
    int l=4,i=0,j; int t;
   
        printf("? 1 2\n");
        fflush(stdout);
        scanf("%d",&sum[i]);
        i++;
    
        printf("? 2 3\n");
        fflush(stdout);
        scanf("%d",&sum[i]);
        i++;
        
        printf("? 3 4\n");
        fflush(stdout);
        scanf("%d",&sum[i]);
        i++;
        
        printf("? 5 4\n");
        fflush(stdout);
        scanf("%d",&sum[i]);
        i++;
        
    do
    {
    	if(b[1]*b[2]==sum[1]&&b[0]*b[1]==sum[0]&&b[2]*b[3]==sum[2]&&b[3]*b[4]==sum[3])
			break; 
	 } while(next_permutation(b,b+6));
    printf("!");
    for(int i=0;i<6;i++)
    	printf(" %d",b[i]);
    fflush(stdout);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40

Bear and Prime 100

题

This is an interactive problem. In the output section below you will see the information about flushing the output.

Bear Limak thinks of some hidden number — an integer from interval [2, 100]. Your task is to say if the hidden number is prime or composite.

Integer x > 1 is called prime if it has exactly two distinct divisors, 1 and x. If integer x > 1 is not prime, it’s called composite.

You can ask up to 20 queries about divisors of the hidden number. In each query you should print an integer from interval [2, 100]. The system will answer “yes” if your integer is a divisor of the hidden number. Otherwise, the answer will be “no”.

For example, if the hidden number is 14 then the system will answer “yes” only if you print 2, 7 or 14.

When you are done asking queries, print “prime” or “composite” and terminate your program.

You will get the Wrong Answer verdict if you ask more than 20 queries, or if you print an integer not from the range [2, 100]. Also, you will get the Wrong Answer verdict if the printed answer isn’t correct.

You will get the Idleness Limit Exceeded verdict if you don’t print anything (but you should) or if you forget about flushing the output (more info below).

Input

After each query you should read one string from the input. It will be “yes” if the printed integer is a divisor of the hidden number, and “no” otherwise.

Output

Up to 20 times you can ask a query — print an integer from interval [2, 100] in one line. You have to both print the end-of-line character and flush the output. After flushing you should read a response from the input.

In any moment you can print the answer “prime” or “composite” (without the quotes). After that, flush the output and terminate your program.

To flush you can use (just after printing an integer and end-of-line):

fflush(stdout) in C++;
System.out.flush() in Java;
stdout.flush() in Python;
flush(output) in Pascal;
See the documentation for other languages.
Hacking. To hack someone, as the input you should print the hidden number — one integer from the interval [2, 100]. Of course, his/her solution won’t be able to read the hidden number from the input.

在这里插入图片描述

Note

The hidden number in the first query is 30. In a table below you can see a better form of the provided example of the communication process.

在这里插入图片描述

The hidden number is divisible by both 2 and 5. Thus, it must be composite. Note that it isn’t necessary to know the exact value of the hidden number. In this test, the hidden number is 30.

题意

系统随机给出区间[2, 100]的一个整数，你最多可以请求20次查询，查询形式为 你直接输出一个数字，意思为这个数字是系统给出的整数的因子吗，是的话系统输出yes，不是则no,你的最终回答是系统给出的数字是质数，还是合数

代码

#include<bits/stdc++.h>

using namespace std;
//任何合数都可以用质数相乘得来
int a[55],b[55],book[55],l=0;
int ppp()
{
	for(int i=2;i<=50;i++)
	{
		if(a[i]==0)
		{
			b[l++]=i;
			for(int j=i+i;j<=50;j+=i)
				a[j]=1; 
		 } 
	}
}
int main()
{
	ppp();
	int t,i,k=0; 
	char s[10];
	for(i=0;i<l;i++)
	{
		printf("%d\n",b[i]);
		fflush(stdout);
		scanf("%s",s);
		if(s[0]=='y')
		{
			k++;
			t=b[i]*b[i];//这是为了确定只有三个因数的合数，如4，9，……
			if(t<=100)
			{
				printf("%d\n",t);
				fflush(stdout);
				scanf("%s",s);
				if(s[0]=='y')
					k++;
			}
		}
		if(k>=2)
			break;
	}
	if(k>=2)
		printf("composite");
	else
		printf("prime");
 } 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

Guessing the Greatest (easy version)

题

The only difference between the easy and the hard version is the limit to the number of queries.

This is an interactive problem.

There is an array a of n different numbers. In one query you can ask the position of the second maximum element in a subsegment a[l…r]. Find the position of the maximum element in the array in no more than 40 queries.

A subsegment a[l…r] is all the elements al, a{l + 1},…ar,…. After asking this subsegment you will be given the position of the second maximum from this subsegment in the whole array.

Input

The first line contains a single integer n (2≤n≤105 ) — the number of elements in the array.

Interaction

You can ask queries by printing “? l r” (1≤l<r≤n). The answer is the index of the second maximum of all elements al, a{l + 1}, ……ar. Array aa is fixed beforehand and can’t be changed in time of interaction.

You can output the answer by printing “! p”, where p is the index of the maximum element in the array.

You can ask no more than 40 queries. Printing the answer doesn’t count as a query.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

fflush(stdout) or cout.flush() in C++;
System.out.flush() in Java;
flush(output) in Pascal;
stdout.flush() in Python;
see documentation for other languages
Hacks

To make a hack, use the following test format.

In the first line output a single integer n (2≤n≤105 ). In the second line output a permutation of nn integers 1 to n. The position of nn in the permutation is the position of the maximum
在这里插入图片描述

Note

In the sample suppose a is [5, 1, 4, 2, 3] So after asking the [1…5] subsegment 4 is second to max value, and it’s position is 3. After asking the [4…5] subsegment 2 is second to max value and it’s position in the whole array is 4.

Note that there are other arrays aa that would produce the same interaction, and the answer for them might be different. Example output is given in purpose of understanding the interaction.

题意

给你一个n,是数组的长度，叫你求出数组中最大的数字的位子，你最多可以向系统询问40次，询问方式 ? l r，l和r是数组的下标，意思是区间[l,r]中第二大的数字的位子

代码

//二分
#include "stdio.h"
//我说的往上爬是向数字往大的地方前进如4变成了5，就是往上爬，
//往下爬，同理 
int n,res;
int arr(int l,int r)
{
	int t;
	printf("? %d %d\n",l,r);
	fflush(stdout);
	scanf("%d",&t);
	return t;
}
int main()
{
	int l,r,mid;
	scanf("%d",&n);
	res=arr(1,n);
	if(res>1&&arr(1,res)==res)//res在区间[1,res]最右面,mid是确定这区间的最左边区间 
	{
		l=1; 
		r=res-1;
		while(l<r)
		{
			mid=(l+r+1)/2;
			//这儿加1是为了mid能爬上去如(9+10)/2=9,
			//if条件满足,l还是等于9,爬不到10,加1就爬得上去 
			//记住+1就是为了往上爬 
			if(arr(mid,res)==res)
				l=mid;
			else
				r=mid-1; //上面+1这儿-1，就能往下爬，四舍五入往下爬，正常情况不加也不减 
		}
		printf("! %d\n",l);
	}
	else//res在这个区间的最左边 ，mid是确定这区间的最右边区间  
	{
		l=res+1;
		r=n;
		while(l<r)
		{
			mid=(l+r)/2;//这儿就不用加1, else里l有+1，可以往上爬 
			if(arr(res,mid)==res) 
				r=mid;
			else
				l=mid+1;
					
		}
		printf("! %d\n",l);
		
	}
	
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

Guessing the Greatest (hard version)

题

The only difference between the easy and the hard version is the limit to the number of queries.

This is an interactive problem.

There is an array a of n different numbers. In one query you can ask the position of the second maximum element in a subsegment a[l…r]. Find the position of the maximum element in the array in no more than 20 queries.

A subsegment a[l…r] is all the elements al, a{l + 1},…ar,…. After asking this subsegment you will be given the position of the second maximum from this subsegment in the whole array.

Input

The first line contains a single integer n (2≤n≤105 ) — the number of elements in the array.

Interaction

You can ask queries by printing “? l r” (1≤l<r≤n). The answer is the index of the second maximum of all elements al, a{l + 1}, ……ar. Array aa is fixed beforehand and can’t be changed in time of interaction.

You can output the answer by printing “! p”, where p is the index of the maximum element in the array.

You can ask no more than 20 queries. Printing the answer doesn’t count as a query.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

fflush(stdout) or cout.flush() in C++;
System.out.flush() in Java;
flush(output) in Pascal;
stdout.flush() in Python;
see documentation for other languages
Hacks

To make a hack, use the following test format.

In the first line output a single integer n (2≤n≤105 ). In the second line output a permutation of nn integers 1 to n. The position of nn in the permutation is the position of the maximum
在这里插入图片描述

Note

In the sample suppose a is [5, 1, 4, 2, 3] So after asking the [1…5] subsegment 4 is second to max value, and it’s position is 3. After asking the [4…5] subsegment 2 is second to max value and it’s position in the whole array is 4.

Note that there are other arrays aa that would produce the same interaction, and the answer for them might be different. Example output is given in purpose of understanding the interaction.

题意

给你一个n,是数组的长度，叫你求出数组中最大的数字的位子，你最多可以向系统询问20次，询问方式 ? l r，l和r是数组的下标，意思是区间[l,r]中第二大的数字的位子

代码

//二分
#include "stdio.h"
//我说的往上爬是向数字往大的地方前进如4变成了5，就是往上爬，
//往下爬，同理 
int n,res;
int arr(int l,int r)
{
	int t;
	printf("? %d %d\n",l,r);
	fflush(stdout);
	scanf("%d",&t);
	return t;
}
int main()
{
	int l,r,mid;
	scanf("%d",&n);
	res=arr(1,n);
	if(res>1&&arr(1,res)==res)//res在区间[1,res]最右面,mid是确定这区间的最左边区间 
	{
		l=1; 
		r=res-1;
		while(l<r)
		{
			mid=(l+r+1)/2;
			//这儿加1是为了mid能爬上去如(9+10)/2=9,
			//if条件满足,l还是等于9,爬不到10,加1就爬得上去 
			//记住+1就是为了往上爬 
			if(arr(mid,res)==res)
				l=mid;
			else
				r=mid-1; //上面+1这儿-1，就能往下爬，四舍五入往下爬，正常情况不加也不减 
		}
		printf("! %d\n",l);
	}
	else//res在这个区间的最左边 ，mid是确定这区间的最右边区间  
	{
		l=res+1;
		r=n;
		while(l<r)
		{
			mid=(l+r)/2;//这儿就不用加1, else里l有+1，可以往上爬 
			if(arr(res,mid)==res) 
				r=mid;
			else
				l=mid+1;
					
		}
		printf("! %d\n",l);
		
	}
	
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

Guess the Cycle Size

题

This is an interactive problem.

I want to play a game with you…

We hid from you a cyclic graph of n vertices (3≤n≤1018). A cyclic graph is an undirected graph of n vertices that form one cycle. Each vertex belongs to the cycle, i.e. the length of the cycle (the number of edges in it) is exactly n. The order of the vertices in the cycle is arbitrary.

You can make queries in the following way:

“? a b” where 1≤a,b≤10 18 and a !=b. In response to the query, the interactor outputs on a separate line the length of random of two paths from vertex a to vertex b, or -1 if max(a, b) > n. The interactor chooses one of the two paths with equal probability. The length of the path —is the number of edges in it.
You win if you guess the number of vertices in the hidden graph (number n) by making no more than 50 queries.

Note that the interactor is implemented in such a way that for any ordered pair (a,b), it always returns the same value for query “? a b”, no matter how many such queries. Note that the “? b a” query may be answered differently by the interactor.

The vertices in the graph are randomly placed, and their positions are fixed in advance.

Hacks are forbidden in this problem. The number of tests the jury has is 50.

Interaction

You can make no more than 50 of queries. To make a query, output on a separate line:

“? a b”, where 1≤a,b≤1018and a !=b. In response to the query, the interactor will output on a separate line the length of a random simple path from vertex a to vertex b (not to be confused with the path from bb to aa), or -1 if max(a, b) > n. The interactor chooses one of the two paths with equal probability.
If your program gets a number 0 as a result of a query, it means that the verdict for your solution is already defined as “wrong answer” (for example, you made more than 50 queries or made an invalid query). In this case, your program should terminate immediately. Otherwise, in this scenario you may get a random verdict “Execution error”, “Exceeded time limit” or some other verdict instead of “Wrong answer”.

The answer, like queries, print on a separate line. The output of the answer is not counted as a query when counting them. To print it, use the following format:

“! n”: the expected size of the hidden graph (3≤n≤1018).After that, your program should terminate.

After the output of the next query, be sure to use stream cleaning functions so that some of your output is not left in some buffer. For example, in C++ you should use function flush(stdout), in Java call System.out.flush(), in Pascal flush(output) and stdout.flush() for Python.

Note that the interactor is implemented in such a way that for any ordered pair (a, b), it always returns the same value for query “? a b”, no matter how many such queries. Note that the “? b a” query may be answered differently by the interactor.

The vertices in the graph are randomly placed, and their positions are fixed in advance.

Hacks are forbidden in this problem. The number of tests the jury has is 50.
在这里插入图片描述

Note

In the first example, the graph could look like this
在这里插入图片描述

The lengths of the simple paths between all pairs of vertices in this case are 1 or 2.

The first query finds out that one of the simple paths from vertex 1 to vertex 2 has a length of 1.
With the second query, we find out that one of the simple paths from vertex 1 to vertex 3 has length 2.
In the third query, we find out that vertex 4 is not in the graph. Consequently, the size of the graph is 3.

题意

这儿有一个有n个顶点组成的的一个环（无向图），需要你答出这个环是由多少个顶点组成的，你可以向系统最多提问50次，询问方式为 ? a b，意思是顶点a到顶点b有多远（a到b要走几条边），有两条路径可以走，系统给出任意一个答案（都是50%概率），注意 不管问多少次? a b 的答案都一样，但? b a 的答案和? a b不一定一样，若你问的? a b超出n，则系统回答-1

代码

#include "stdio.h"
#define ll long long
ll arr(int a,int b)
{
	printf("? %d %d\n",a,b);
	fflush(stdout);
	ll l;
	scanf("%lld",&l);
	return l;
}
int main()
{
	ll la,lb,n; 
	for(int i=2;i<=26;i++)
	{
		la=arr(1,i);
		lb=arr(i,1);
		if(la!=lb)
		{
			n=la+lb;
			break; 
		}
		if(la==-1)
		{
			n=i-1;
			break;
		}
	}
	printf("! %lld",n);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/75139
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号