B. Lost Number【CF交互题 暴力】
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.
Example
inputCopy
16
64
345
672
outputCopy
? 1 1
? 2 2
? 3 5
? 4 6
! 4 8 15 16 23 42
Hint
If you want to submit a hack for this problem, your test should
contain exactly six space-separated integers a1, a2, …, a6. Each of 6
special numbers should occur exactly once in the test. The test should
be ended with a line break character.
思路如下
这是第一次写CF交互题，虽然没有做出来，不过看完题解之后这题是真的简单。
- 题意：一个数组有 4 ，8 ，15，16，32，42 这6个数子组成，且每个元素在该数组中仅出现一次，让你通过4 提问，得出这个 数组各个位置的元素是什么并输出出来。（每次提问方式如下： 设 i ， j 为所求数组的元素下标（i 与 j 可以相同），通过提问 i ，j 则系统会返回 i ，j 位置元素的乘积）
- 思路：固定提问位置 + 暴力枚举。
题解一（别人的）
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef long long LL;
const int inf = 1<<30;
const LL maxn = 1e5+10;
int main()
{
int n[6] = {4,8,15,16,23,42}, ans[6];
bool used[10];
int a, b, c, d;
ms(used, 0);
printf("? 1 2\n");
fflush(stdout);
scanf("%d",&a);
printf("? 2 3\n");
fflush(stdout);
scanf("%d",&b);
printf("? 3 4\n");
fflush(stdout);
scanf("%d",&c);
printf("? 4 5\n");
fflush(stdout);
scanf("%d",&d);
for(int i = 0; i < 6; ++i){
if(!used[i]){
used[i] = true;
for(int j = 0; j < 6; ++j){
if(!used[j]){
used[j] = true;
for(int k = 0; k < 6; ++k){
if(!used[k]){
used[k] = true;
for(int l = 0; l < 6; ++l){
if(!used[l]){
used[l] = true;
for(int p = 0; p < 6; ++p){
if(!used[p] && n[i]*n[j]==a&&n[j]*n[k]==b&&n[k]*n[l]==c&&n[l]*n[p]==d){
used[p] = true;
ans[0]=n[i], ans[1]=n[j], ans[2]=n[k], ans[3]=n[l], ans[4]=n[p];
int t = 0;
for(; t < 6; ++t)
if(!used[t]) break;
ans[5] = n[t];
i=j=k=l=p=9; break;
}
}
used[l] = false;
}
}
used[k] = false;
}
}
used[j] = false;
}
}
used[i] = false;
}
}
printf("! %d %d %d %d %d %d\n", ans[0], ans[1], ans[2], ans[3], ans[4], ans[5]);
return 0;
}
题解二（改编后的题解）
经题解一改编后
#include<iostream>
using namespace std;
int res[7];
int mark[7];
int map[7] = {4,8,15,16,23,42};
int ar[7];
//暴力搜索回溯
int flag = 0;
void dfs(int k,int last_val)
{
if(flag == 1)
return;
if(k == 5)
{
for(int i = 0; i < 6; i ++)
{
if(! mark[i])
{
res[k] = map[i];
flag = 1;
return;
}
}
}
for(int i = 0; i < 6; i ++)
{
if(k == 0 && !mark[i])
{
if(flag == 1)
return;
mark[i] = 1;
res[k] = map[i];
dfs(k + 1 , map[i]);
mark[i] = 0;
}
else if(k > 0 && !mark[i] && ar[k] == last_val * map[i])
{
if(flag == 1)
return;
mark[i] = 1;
res[k] = map[i];
dfs(k + 1 , map[i]);
mark[i] = 0;
}
}
}
int main()
{
//freopen("test.txt","r",stdin);
printf("? 1 2\n");
fflush(stdout);
scanf("%d",&ar[1]);
printf("? 2 3\n");
fflush(stdout);
scanf("%d",&ar[2]);
printf("? 3 4\n");
fflush(stdout);
scanf("%d",&ar[3]);
printf("? 4 5\n");
fflush(stdout);
scanf("%d",&ar[4]);
dfs(0 , 1);
printf("! %d %d %d %d %d %d\n", res[0], res[1], res[2], res[3], res[4], res[5]);
return 0;
}