1407C. Chocolate Bunny(互動,推導)

互動題還是很難搞呀~

C. Chocolate Bunny(互動,推導)

假 設 a i % a j = x 假設a_i\%a_j=x 假設ai?%aj?=x

a j % a i = y a_j\%a_i=y aj?%ai?=y

其實就能得到一些東西了

假 設 a i > a j 假設a_i>a_j 假設ai?>aj?

那 么 y = a j 那么y=a_j 那么y=aj?

那 么 x < a j 那么x<a_j 那么x<aj?

那 么 x < y 且 a j = y 那么x<y且a_j=y 那么x<y且aj?=y

所 以 , 經 過 ( i , j ) 得 到 x , 經 過 ( j , i ) 得 到 y 所以,經過(i,j)得到x,經過(j,i)得到y 所以,經過(i,j)得到x,經過(j,i)得到y

x 和 y 的 較 大 值 就 是 a i 和 a j 的 較 小 值 x和y的較大值就是a_i和a_j的較小值 x和y的較大值就是ai?和aj?的較小值

比 如 y 比 較 大 , 那 么 通 過 a j % a i = y 比如y比較大,那么通過a_j\%a_i=y 比如y比較大,那么通過aj?%ai?=y

所 以 唯 一 確 定 a j = y 所以唯一確定a_j=y 所以唯一確定aj?=y

綜 上 所 訴 , 2 次 操 作 可 以 求 得 兩 個 數 中 的 較 小 值 綜上所訴,2次操作可以求得兩個數中的較小值 綜上所訴,2次操作可以求得兩個數中的較小值

2 n ? 2 次 操 作 得 到 n ? 1 個 數 , 剩 下 那 個 是 n ( 因 為 n 永 遠 不 會 當 作 較 小 值 求 出 來 ) 2n-2次操作得到n-1個數,剩下那個是n(因為n永遠不會當作較小值求出來) 2n?2次操作得到n?1個數,剩下那個是n(因為n永遠不會當作較小值求出來)

#include <bits/stdc++.h>
using namespace std;
int a[10009];
void print(int q,int w){
	cout << "? " << q << " " << w << '\n';
}
int main()
{
	int n;
	cin >> n;
	int last=1;
	for(int i=2;i<=n;i++)
	{
		int q,w;
		print(last,i);
		fflush(stdout);
		cin >> q;
		print(i,last);
		fflush(stdout);
		cin >> w;
		if( q<w )	a[i]=w;	//較大值不改變 
		else 	a[last]=q,last=i;
	}
	a[last]=n;
	cout << "! ";
	for(int i=1;i<=n;i++)
		cout << a[i] << " ";
	fflush(stdout);
}