CF727C Guess the Array

    • 25通过
    • 61提交
  • 题目来源 CodeForces 727C
  • 评测方式 RemoteJudge
  • 标签 交互题
  • 难度 普及/提高-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    这是一道交互题。 你有一个长度为n的数组a,你可以向交互库询问任意两个数的和,你至多可以询问n次,你的目标是根据询问结果算出数组里的每个数。 询问格式如下: 1.你输出 ? x y 2.交互库将会告诉你a[x]与a[y]的和 交互库将会将你查询的结果输出到你程序的标准输入中,你询问完直接读入即可。 每做出一次询问,你需要使用flush,具体用法参见CF679A的翻译 当你计算出结果后,需要先输出一个"! ",接下来输出a[1],a[2],a[3]...a[n],每输出一个数空一格。 具体格式可参考样例理解。

    感谢U20158 Ebola 提供的翻译

    题目描述

    This is an interactive problem. You should use flush operation after each printed line. For example, in C++ you should use fflush(stdout), in Java you should use System.out.flush(), and in Pascal — flush(output).

    In this problem you should guess an array $ a $ which is unknown for you. The only information you have initially is the length $ n $ of the array $ a $ .

    The only allowed action is to ask the sum of two elements by their indices. Formally, you can print two indices $ i $ and $ j $ (the indices should be distinct). Then your program should read the response: the single integer equals to $ a_{i}+a_{j} $ .

    It is easy to prove that it is always possible to guess the array using at most $ n $ requests.

    Write a program that will guess the array $ a $ by making at most $ n $ requests.

    输入输出格式

    输入格式:

    输出格式:

    In each test your program should guess a single array.

    The input starts with a line containing integer $ n $ ( $ 3<=n<=5000 $ ) — the length of the array. Your program should read it at first.

    After that your program should print to the standard output the requests about the sum of two elements or inform that the array is guessed.

    • In case your program is making a request to ask the sum of two elements, it should print line in the format "? i j" ( $ i $ and $ j $ are distinct integers between $ 1 $ and $ n $ ), where $ i $ and $ j $ are indices in the array $ a $ .
    • In case your program informs that the array is guessed, it should print line in the format " $ ! a_{1} a_{2} ... a_{n} $ " (it is guaranteed that all $ a_{i} $ are positive integers not exceeding $ 10^{5} $ ), where $ a_{i} $ is the $ i $ -th element of the array $ a $ .

    The response on a request is a single integer equal to $ a_{i}+a_{j} $ , printed on a separate line.

    Your program can do at most $ n $ requests. Note that the final line « $ ! a_{1} a_{2} ... a_{n} $ » is not counted as a request.

    Do not forget about flush operation after each printed line.

    After you program prints the guessed array, it should terminate normally.

    输入输出样例

    输入样例#1: 复制
    5
     
    9
     
    7
     
    9
     
    11
     
    6
     
    输出样例#1: 复制
     
    ? 1 5
     
    ? 2 3
     
    ? 4 1
     
    ? 5 2
     
    ? 3 4
     
    ! 4 6 1 5 5

    说明

    The format of a test to make a hack is:

    • The first line contains an integer number $ n $ ( $ 3<=n<=5000 $ ) — the length of the array.
    • The second line contains $ n $ numbers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{5} $ ) — the elements of the array to guess.
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。