UOJ Logo Universal Online Judge

UOJ

统计

在 DoubleDog 和SinglePig 所在的宇宙中,物理法则与我们并不相同。在年复一年的宅化过程中,SinglePig 开发出了简单的 pig 计算机,DoubleDog 通过揣摩其变化,观察出其数学模型如下:

这些 pig 计算机有且仅有一个长为 $ n(n\ge 3) $ 的布尔数组 $ a $ (下标从 $ 0 $ 开始),操作者可以为计算机写一个程序,程序即为一个固定长度的操作序列,每个操作形如:从 $ a $ 中选择三个不同的位置 $ i,j,k $ ,对他们执行一个门操作 $ g $ ,其中 $ g $ 是一个输入三个布尔值且输出三个布尔值的一一映射(即对于不同的两组输入, $ g $ 产生不同的两组输出)。

DoubleDog 也想使用 pig 计算机来进行加法运算,但是苦于没有 SinglePig 们提供的程序,于是只好拜托你。如果我们视数组 $ a $ 的前 $ l $ 位为一个二进制数的话,其数值为 $ \sum_{i = 0}^{l - 1} a_i 2^i $ 。现在 DoubleDog 想实现一个程序,完成对数组 $ a $ 的前 $ l $ 位所表示的二进制数进行模 $ 2^l $ 的意义下加一个常数 $ c $ 的操作。你需要对 DoubleDog 提供的常数 $ c $ 设计出一个 pig 计算机上的程序。

根据测试点的不同,数组 $ a $ 的后 $ n-l $ 位中的初值和输出值为不同类型的值。对于每个测试点,你都需要提供一个给定格式的长度不超过 $ m $ 的程序。有数个测试数据作为输入,如果你的程序能通过该测试点下的所有测试数据,则你通过此测试点。

输入格式

第一行包括一个正整数,表示子任务编号。

第二行包括三个正整数 $ n, m, l ​$,表示数组的长度,你的输出的最多行数和数字的长度。

接下来一行一个长度为 $ l $ 的 01 字符串,从低到高表示 $ c $ 的每一位。

输出格式

输出第一行包含一个数 $ L ​$,表示你的程序的行数,你必须保证 $ L \le m ​$ 。

接下来共输出 $ L $ 行,每行四个整数,前三个为操作位 $ i,j,k $,你必须保证 $ i, j, k $ 互不相同。第四个整数由一个长度 $ 24 ​$ 的 01 串表示,每三位表示真值表中一个输入的对应输出。

给定一个输入三个布尔值 $ a, b, c ​$ 且输出三个布尔值 $ x, y, z ​$ 的门 gate,我们可以通过以下函数得到该门所对应的输出:

void gate(bool a, bool b, bool c, bool &x, bool &y, bool &z);
string gate_str(){
    string res = "";
    for (int w = 0; w < 8; ++w) {
        bool a = (w & 4) > 0;
        bool b = (w & 2) > 0;
        bool c = (w & 1) > 0;
        bool x, y, z;
        gate(a, b, c, x, y, z);
        res += char(x) + '0';
        res += char(y) + '0';
        res += char(z) + '0';
    }
    return res;
}

样例一

input

0
10 50000 1
1

output

1
0 1 2 100101110111000001010011

explanation

对于任意的 $ a $,该程序都会将 $ a_0 $ 取反 (0 变 1, 1 变 0)。

限制与约定

对于 $ 100\% ​$ 的数据,$ l = 100, c < 2^l ​$ 。

子任务编号$n=$$m=$输入后$n-l$位输出后$n-l$位约定分值
$1$$300$$50000$为$0$不限$13$
$2$$200$$20000$为$0$不限$8$
$3$$300$$50000$为$0$为$0$$20$
$4$$200$$20000$为$0$为$0$$c=1$$17$
$5$$200$$20000$未知与输入相同$c=1$$13$
$6$$101$$20000$为$0$为$0$$19$
$7$$101$$20000$未知与输入相同$10$

在下发文件中我们下发了模拟器的源代码。

模拟器从 in.txt 中读入一个数 $ n $ 和一个长度为 $ n $ 的数组 $ a $ 表示输入,从 out.txt 中读入你的程序,向 ans.txt 输出最终的 $ a $ 数组。

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$

下载

样例数据及模拟器下载