Codeforces Global Round 10 E. Omkar and Duck（构造，二进制）

题意：
交互题，实质是要求构成一个n*m的矩形，使得起点到终点只能往左下走的任意一条路径权值和不同。

思路：

按这样排列矩阵就好了（图自官方题解）。
那么可以发现，当$i$为奇数时，$a[i][j]=0$。否则$a[i][j]=2^{i+j}$

---

那么假设到了位置$(x,y)$，且满足$a[x][y]!=0$，从$(1,1)$到$(x-1,y)$的路径和从$(1,1)$到$(x,y-1)$的路径中$i+j<x+y$，所以不存在$a[i][j]=2^{x+y}$。

对于$(x,y)$到$(n,m)$的路径也同理

所以从$(1,1)$到$(n,m)$的任意一条路径，所经过的非0方格权值是不重复的。

---

而当你在位置$(x,y)$的时候，下一个位置为$(x+1,y)$或者$(x,y+1)$。
如果$a[x+1][y]=0$，则$a[x][y+1]=2^{x+y+1}$那么到了$(x+1,y)$后，至少再多走一格才能遇到有权值的格子，此时所在的$(i,j)$一定满足$i+j>x+y+1$，所以不可能再遇到$2^{x+y+1}$的这个权值的格子。

如果$a[x][y+1]=0$也是同样的考虑。

所以可以保证从$(x,y)$出发的路径的二进制数幂次不同，所以权值和一定不同。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>using namespace std;typedef long long ll;
ll a[35][35];int main() {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {if(i % 2 == 0) {a[i][j] = 1ll << (i + j - 1);printf("%lld ",a[i][j]);} else {printf("0 ");}}printf("\n");}fflush(stdout);int q;scanf("%d",&q);while(q--) {ll k;scanf("%lld",&k);int x = 1, y = 1;for(int i = 1;i <= 2 * n - 1;i++) {printf("%d %d\n",x,y);if(x <= n - 1 && (k >> (i + 1) & 1) == (a[x + 1][y] > 0)) {x++;} else {y++;}}fflush(stdout);}return 0;
}