Description
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 ai + aj.
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.
Sample Input
5 9 7 9 11 6
? 1 5 ? 2 3 ? 4 1 ? 5 2 ? 3 4 ! 4 6 1 5 5
Hint
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 a1, a2, ..., an (1 ≤ ai ≤ 105) — the elements of the array to guess.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
ll a[5005];
ll b[5005];
ll n;
int main()
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
ll sum=0,sum1=0;;
cin >> n;
if(n%2)
{
for(ll i=1;i<n;i++)
{
cout <<"? " << i<<" "<< i+1<<endl;
cin >> b[i];
}
cout << "? " << 1 <<" "<< n<<endl;
cin >> b[n];
for(ll i=1;i<=n;i++)
{
sum += b[i];
}
sum = sum/2;
for(ll j=2;j<=n-1;j+=2)
{
sum1+=b[j];
}
a[1] = sum - sum1;
for(ll i=1;i<n;i++)
{
a[i+1] = b[i] - a[i];
}
}
else
{
n--;
for(ll i=1;i<n;i++)
{
cout << "? " << i <<" "<< i+1<<endl;
cin >> b[i];
}
cout << "? " << 1 <<" "<< n<<endl;
cin >> b[n];
cout << "? " << n <<" "<< n+1<<endl;
cin >> b[n+1];
for(ll i=1;i<=n;i++)
{
sum += b[i];
}
sum = sum/2;
for(ll j=2;j<=n-1;j+=2)
{
sum1+=b[j];
}
a[1] = sum - sum1;
for(ll i=1;i<n;i++)
{
a[i+1] = b[i] - a[i];
}
a[n+1] = b[n+1] - a[n];
n++;
}
cout << "!";
for(ll i=1;i<=n;i++)
{
cout << " " << a[i];
}
cout <<endl;
return 0;
}