CF Global Round 10-E

E.Omkar and Duck

(Description:)

（交互题）先告诉你 (n)，让你给出 (n imes n) 的矩阵，然后 (q) 组询问，每次会给出矩阵中从左上到右下的某一路径上的数字之和，输出路径长什么样

(Solution:)

一开始以为随便构造一个全为(1)的矩阵，然后乱输出路径就可以了（雾

看完题才发现原来要求输出的路径得是唯一的。。。

那就必须构造一个矩阵，使得从左上到右下的每一条不同路径的路径和是不一样的，然后还得在(O(n))的复杂度下输出路径

考虑二进制，给每一个从右上到左下的对角线赋一个二的次幂，然后(01)交替即可

(Code:)

#include<bits/stdc++.h>
using namespace std;
typedef long long lol;
const int N=30;
int t,n,m;
lol a[N][N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		if(i&1){
			for(int j=1;j<=n;j++){
				a[i][j]=1ll<<(i+j-2);
				printf("%lld ",a[i][j]);
			}
		}
		else{
			for(int j=1;j<=n;j++)
				printf("0 ");
		}
		puts("");
	}
	fflush(stdout);
	scanf("%d",&m);
	while(m--){
		lol tmp;
		scanf("%lld",&tmp);
		for(int x=1,y=1;x<n||y<n;){
			printf("%d %d
",x,y);
			if(x==n){y++;continue;}
			if(y==n){x++;continue;}
			lol s=1ll<<(x+y-1);
			if(tmp&s){
				if(a[x+1][y]>0)x++;
				else y++;
			}
			else{
				if(a[x+1][y]>0)y++;
				else x++;
			}
		}
		printf("%d %d
",n,n);
		fflush(stdout);
	}
	return 0;
}