UOJ Logo Universal Online Judge

UOJ

#454. 【UER #8】打雪仗

附件下载 统计

这是一道通信题

UOJ 又来到了新的一年,今年鸽子们不出意外的把比赛鸽到了12月月底。今年鸽子们决定玩点不一样的:它们要来打(tong)雪(xin)仗(ti)。

小 $A$ (Alice),小 $ B $ (Bob) 和小 $ C $ (Cplusplus) 计划进行一场打雪仗比赛,第二名的将要请其他人一顿饭。为了不取得第二名,三人都付出了自己的努力:小 $ A $ 和小 $ B $ 为了获得第三名,每天在家睡觉,水平不断退步;而小 $ C $ 勤加苦练,为了取得第一名而努力着。直到比赛将至,小 $ A $ 和小 $ B $ 才意识到第二名很大概率要在两人之间诞生。因此,小 $ A $ 和小 $ B $ 决定齐心协力,将小 $ C $ 安排到第二名!

为了完成这样的伟业,小 $ A $ 和小 $ B $ 打算窃取小 $ C $ 的作战计划。比赛时,小 $B$ 将打败小 $C$ 获得冠军,而小 $A$ 将继续睡大觉获得第三。

小 $ C $ 的作战计划可以视为长度为 $2n$ 的一个 01 串,下标从 $1, \dots, 2n$ 编号。小 $ C $ 选取了这 $2n$ 个下标中的 $n$ 个,并只在这 $n$ 个位置中存储了作战计划的相关信息,而其他的位置都是用来混淆视听的。不幸的是,小 $ A $ 和小 $ B $ 只来得及分别完成了自己的任务——小 $ A $ 得到了长度为 $2n$ 的字符串,而小 $ B $ 得到了 $n$ 个下标,而他们已经来不及将信息汇总到一起了!好在,他们可以通过打雪仗前的热身赛传递信息:热身赛中每个人有恰好 $m$ 个雪球,如果向上向对方抛球表示传递字符 "1",而向下向对方抛球可以传递字符 "0"。只要你设计一种传递信息的方式,使得小 $B$ 最终知道了他所拿到的 $n$ 个下标所对应的字符,他们的计划就可以得逞了!

简要题意: 小 $ A $ 有一个长度为 $ 2n $ 的 $ 01 $ 字符串 $ S $ ,小 $ B $ 有 $\{1, \dots, 2n\}$ 这些下标中的 $ n $ 个:$p_1, \dots, p_n$。小 $A$ 和 小 $B$ 可以相互之间可以发送字符(但只能发送 "0" 或者 "1" 两种)。请为小 $A$ 和小 $B$ 设计一种通信方式,使得小 $ B $ 最终能知道这 $n$ 个下标所对应的字符 $S[p_1], S[p_2], \dots, S[p_n]$。两人中发送字符数较多的那一个不应发送超过 $m$ 个字符。

任务

你需要提交两个源文件。

Alice

第一个源文件名为 alice,该程序将扮演小 $ A $ 的角色,该程序从 alice.in 中读取小 $ A $ 已有的信息,输入格式如下:

  • 第一行包括两个正整数 $n$ 和 $m$;
  • 第二行包括一个长度为 $ 2n$ 的字符串 $ S $,仅包含 0/1 两种字符。

你可以通过向 stdout 写入数据来向小 $B$ 发送信息,通过从 stdin 读入数据来读取小 B 传递的信息。

Bob

第二个源文件名为 bob,该程序将扮演小 $ B $ 的角色,该程序从 bob.in 中读取小 $ B $ 已有的信息,并将答案输出至 bob.outbob.in 输入格式如下:

  • 第一行包括两个正整数 $n$ 和 $m$;
  • 第二行包括 $n$ 个 $ [1, 2n]$ 间的正整数,表示 $n$ 个下标 $p_1, \dots, p_n$ ,保证这些下标按照升序排列。

bob.out 输出格式如下:

  • 一行,一个字符串,其中第 $ i $ 个字符表示 $ S[p_i] $ 的值。

你可以通过向 stdout 写入数据来向小 A 发送信息,通过从 stdin 读入数据来读取小 A 传递的信息。

通信说明

你发送的信息必须是由 "0" 和 "1" 构成的字符串,且两人中发送字符数较多的那一个不应发送超过 $m$ 个字符。

请注意:在传递任意信息后,请添加以下语句,否则可能导致 TLE:

对于 C++: fflush(stdout)cout.flush()

对于 Java: System.out.flush()

对于 Pascal: flush(output)

对于 Python: stdout.flush()

你可以参考我们给出的示例程序对以上内容进行理解,并在示例程序的基础上完成任务。

另外请注意:如果你使用了其他的方法传输信息,或尝试对评测机发起攻击,可能会得到 0 分。

小例子

设 $n = 2, S = 1001$,下标集合为 $\{1, 4\}$,你应该在 bob.out 中输出一行一个字符串 "11" 表示答案。

样例一

见样例数据及样例程序下载。

限制与约定

Subtask 1 (20 分):$n = 1000, m = 2000$;

Subtask 2 (30 分):$n = 1000, m = 1600$;

Subtask 3 (50 分):$n = 1000, m = 1350$。

时间限制:两个程序各自使用时间的最大值不超过 $\texttt{1s}$

空间限制:两个程序各自使用空间的最大值不超过 $\texttt{256MB}$

下载

样例数据及样例程序下载