#2074. 魔法小程序

    ID: 2074 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest982来源:qoj.ac数据:公开样例分治递归

魔法小程序

魔法小程序

题目描述

标题: 魔法小程序 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

有这样一段魔法的程序:(其中所有的数组下标从 0 开始,所有的除法的结果为整数,且向 0 取整)

定义数组 a[], b[], c[]
定义函数 魔法(x, y, z):
{
    如果 a 的长度 == z:
        返回 x >= y
    如果 x % a[z] < y % a[z]:
        返回 假
    返回 魔法(x / a[z], y / a[z], z + 1)
}
定义函数 主程序():
{
    读入 a[], b[]
    令 c[] 的长度与 b[] 的长度相同,且 c[] 的每个元素均为 0
    令 变量 i 从 0 循环至 b 的长度 - 1:
        令 变量 j 从 0 循环至 i:
            如果 魔法(i, j, 0):
                c[i] += b[j]
    输出 a[], c[]
}

这个程序目前十分低效(显然时间复杂度至少是平方量级的),无法快速完成百万级别的计算,但我们现在的任务不仅是优化它。

现在我们给出这段程序的输出,你需要完成一个“非确定机”的工作,给出一个可能的输入。

请注意本题的空间限制。

输入格式

第一行输入 a 的长度。第二行输入一些空格隔开的正整数,依次表示 a 的每一项。

第三行输入 c 的长度。第四行输入一些空格隔开的整数,依次表示 c 的每一项。

每一行相邻的两个数,恰好用一个空格隔开。

a 的长度不会超过 104。a 的每一个元素不会超过 109。

c 的长度不会超过 106。对 c 的元素的范围没有直接的保证,但是保证存在一个解 b,使得 b 的每一个元素的绝对值都不超过 109。

a 和 c 都至少拥有一个元素。

输出格式

第一行输出 a 的长度。第二行输入一些空格隔开的正整数,依次表示 a 的每一项。

第三行输出 b 的长度。第四行输入一些空格隔开的整数,依次表示 b 的每一项。

每一行相邻的两个数,恰好用一个空格隔开。

你必须保证你输出的 b 的每一个元素的绝对值都不超过 109。保证存在一个可行的解满足这个条件。如果有多个可行的解,你可以输出任意一个。

样例一

input

3
2 3 3
10
1 0 2 9 3 8 4 7 5 6

output

3
2 3 3
10
1 -1 1 8 1 -2 3 4 0 -10

限制与约定

本题分为若干个子任务,但是不采用捆绑测试。每个子任务中有若干个测试点,只要你对于某个测试点的输出正确,即可获得该测试点的分数。某个子任务的分数是指其各个测试点的分数之和。

我们设 n 为 c 的长度,设 m 为 a 的长度,则:

子任务 1(4分)

n=1,m≤100。

子任务 2(22分)

n≤100,m≤100。

子任务 3(6分)

n≤1000,m≤1000。

子任务 4(8分)

n≤104。

子任务 5(21分)

n=2m,a 中所有元素均为 2。

子任务 6(9分)

a 中所有元素均为 2。

子任务 7(7分)

m=1。

子任务 8(12分)

m≤20。

子任务 9(11分)

没有特殊的约定。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
2 3 3
10
1 0 2 9 3 8 4 7 5 6
3
2 3 3
10
1 -1 1 8 1 -2 3 4 0 -10