UOJ Logo Universal Online Judge

UOJ

#359. 【JOISC2017】Broken Device

附件下载 统计

考古学者的安娜和布鲁诺正在伊朗进行遗址调查。他们的角色分配是安娜前往遗址进行挖掘,而布鲁诺则在基地营进行挖掘结果的分析。

挖掘将持续 $Q(=1000)$ 天。每天,安娜使用通信设备将挖掘结果传达给布鲁诺。一天的挖掘结果用一个整数 $X$ 表示。

安娜每天只能使用通信设备一次,设备一次可以发送长度为 $N(=150)$ 的由 $0$ 和 $1$ 组成的数列。

然而,通信设备出现故障,发送的长度 $N$ 的数列中,某些位置无法正常工作,这些位置的值总是被发送为 $0$。安娜在发送前可以确认哪些位置失效,但布鲁诺无法确认。此外,失效的位置及其数量每天可能不同。

为了不延误遗址调查,安娜和布鲁诺请求正在伊朗举办的国际编程比赛的候选人你,编写一个程序来传达挖掘结果。

通信方式

你需要实现两个函数 void Anna(int N,long long X,int K,int P[])long long Bruno(int N,int A[]) 来实现以下功能:

  • Anna 将得到一个长为 $N=150$ 的空白序列和一个不大于 $10^{18}$ 的数字 $X$,这个函数需要为每一位赋予一个 $0$ 或 $1$ 的值来保存 $X$,其中序列中有 $K$ 个位置是损坏的:无论设置为 $0$ 还是 $1$,这些位置的值都恒为 $0$,$P$ 数组保存着这些位置的下标;
  • Bruno 将得到 Anna 操作后的序列,这个函数需要依靠这个序列来还原 Anna 得到的数字 $X$。

仅支持 C++ 语言提交。

你需要实现两个函数。

void Anna( int N, long long X, int K, int P[] ):这是编码程序,$N$ 代表序列 $S$ 的长度,$X$ 为需要传输的数,$K$ 为损坏位置的数量,$P[]$ 为一个长度为 $K$ 的数组表示损坏的位置编号。
在这个函数中,你可以调用 void Set( int pos, int bit ),表示把序列 $S$ 的第 $pos$ 位置设置为 $bit$。

long long Bruno( int N, int A[] ):这是解码程序,其中 $N$ 代表序列长度,而 $A$ 则是 Anna(...) 中调用 Set(...) 的结果。你需要返回解码得到的数。

请注意,这里的数组开头下标皆为 $0$ 。