Problem

FRBSUM

Description

数集的定义为无法用的某个子集（可以为空）的和表示的最小的非负整数。
例如，，则它的子集和中包含，，，，，，但是它无法得到。因此的为。
给定一个序列，你的任务是回答该数列的一些子区间所形成的数集的是多少。

Input

输入数据的第一行包含一个整数，表示序列的长度。
接下来一行包含个数，表示给定的序列（从标号）。
接下来一行包含一个整数，表示询问的组数。
接下来行，每行一对整数，表示一组询问。

Ouput

对于每组询问，输出一行表示对应的答案。

Problem

【APIO2010】信号覆盖

Description

Input

输入第一行包含一个正整数，表示房子的总数。接下来有行，分别表示每一个房子的位置。对于，第个房子的坐标用一对整数和来表示，中间用空格隔开。

Output

输出文件包含一个实数，表示平均有多少个房子被信号所覆盖，需保证输出结果与精确值的绝对误差不超过。

Problem

【APIO2015】巴厘岛的雕塑

Description

印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。
在这条主干道上一共有座雕塑，为方便起见，我们把这些雕塑从到连续地进行标号，其中第 i 座雕塑的年龄是年。为了使这条路的环境更加优美，政府想把这些雕塑分成若干组，并通过在组与组之间种上一些树，来吸引更多的游客来巴厘岛。
下面是将雕塑分组的规则：
这些雕塑必须被分为恰好组，其中，每组必须含有至少一个雕塑，每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。
当雕塑被分好组后，对于每个组，我们首先计算出该组所有雕塑的年龄和。
计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。
请问政府能得到的最小的最终优美度是多少?

Input

输入的第一行包含三个用空格分开的整数。
第二行包含个用空格分开的整数。

Output

输出一行一个数，表示最小的最终优美度。

Problem

【APIO2015】雅加达的摩天楼

Description

印尼首都雅加达市有座摩天楼，它们排列成一条直线，我们从左到右依次将它们编号为到。除了这座摩天楼外，雅加达市没有其他摩天楼。
有只叫做的神秘生物在雅加达市居住，它们的编号依次是到。编号为的最初居住于编号为的摩天楼。每只都有一种神秘的力量，使它们能够在摩天楼之间跳跃，编号为的的跳跃能力为。
在一次跳跃中，位于摩天楼而跳跃能力为的可以跳跃到编号为（如果）或（如果）的摩天楼。
编号为的是所有的首领，它有一条紧急的消息要尽快传送给编号为的。
任何一个收到消息的有以下两个选择:

• 跳跃到其他摩天楼上
• 将消息传递给它当前所在的摩天楼上的其他

请帮助们计算将消息从号传递到号所需要的最少总跳跃步数，或者告诉它们消息永远不可能传递到号。

Input

输入的第一行包含两个整数和。
接下来行，每行包含两个整数和。

Output

输出一行，表示所需要的最少步数。
如果消息永远无法传递到号，输出。

Problem

【APIO2009】会议中心

Description

政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很感兴趣，他们希望能够在里面举行会议。
对于一个客户而言，仅当在开会时能够独自占用整个会堂，他才会租借会堂。会议中心的销售主管认为：最好的策略应该是将会堂租借给尽可能多的客户。
显然，有可能存在不止一种满足要求的策略。 例如下面的例子。总共有个公司。他们对租借会堂发出了请求，并提出了他们所需占用会堂的起止日期（如下表所示）。

上例中，最多将会堂租借给两家公司。租借策略分别是租给和， 或是和，也可以是和。注意会议中心一天最多租借给 一个公司，所以和不能同时租借会议中心，因为他们在第九天重合 了。
销售主管为了公平起见，决定按照如下的程序来确定选择何种租借策略：首先，将租借给客户数量最多的策略作为候选，将所有的公司按照他们发出请求的 顺序编号。对于候选策略，将策略中的每家公司的编号按升序排列。最后，选出其中字典序最小的候选策略作为最终的策略。
例中，会堂最终将被租借给和：个候选策略是 ，而在字典序中。
你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

Input

第一行有一个整数，表示发出租借会堂申请的公司的个数。
第到第行每行有个整数。第行的整数表示第家公司申请租借的起始和终止日期。
对于每个公司的申请，起始日期为不小于的整数，终止日期为不大于的整数。

Output

输出的第一行应有一个整数，表示最多可以租借给多少家公司。
第二行应列出个数，表示最终将会堂租借给哪些公司。

Problem

【APIO2011】方格染色

Description

和他的妹妹有一个包含个方格的表格。她们想要将其的每个方格都染成红色或蓝色。
出于个人喜好，他们想要表格中每个的方形区域都包含奇数个（个或个）红色方格。 可是昨天晚上，有人已经给表格中的一些方格染上了颜色！
现在和非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍然满足她们的要求。
如果可能的话，满足他们要求的染色方案数有多少呢？

Input

输入的第一行包含三个整数, 和，分别代表表格的行数、列数和已被染色的方格数目。
之后的行描述已被染色的方格。其中第行包含三个整数, 和，分别代表第个已被染色的方格的行编号、列编号和颜色。为表示方格被染成红色，为表示方格被染成蓝色。

Output

输出一个整数，表示可能的染色方案数目模得到的值。

Problem

【Baltic2016】Cities

Description

给定个点，条双向边的图，其中有个点是重要的，每条边都有一定的长度。
现在要你选定一些边来构成一个图，要使得个重要的点相互连通，求边的长度和的最小值。

Input

共行
第行读入，表示个点，个重要的点，条边
第行读入个重要点的编号
第至第行，每行包括个数字，表示有一条从到长度为的双向路径

Output

共行，即最小长度和

Problem

【APIO2012】Dispatching

Description

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。
在这个帮派里，有一名忍者被称之为。除了以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。
现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。
这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。
写一个程序，给定每一个忍者的上级，薪水，领导力，以及支付给忍者们的薪水总预算，输出在预算内满足上述要求时顾客满意度的最大值。

Input

从标准输入读入数据。
第一行包含两个整数和，其中表示忍者的个数，表示薪水的总预算。
接下来行描述忍者们的上级、薪水以及领导力。其中的第行包含三个整数分别表示第个忍者的上级，薪水以及领导力。满足，并且每一个忍者的老板的编号一定小于自己的编号。

Output

输出一个数，表示在预算内顾客的满意度的最大值。

Problem

【2018多省省队联测】劈配

Description

一年一度的综艺节目《中国新代码》又开始了。从小就梦想成为一名程序员，他觉得这是一个展示自己的舞台，于是他毫不犹豫地报名了。
轻车熟路的顺利地通过了海选，接下来的环节是导师盲选，这一阶段的规则是这样的：
总共名参赛选手（编号从至）每人写出一份代码并介绍自己的梦想。接着由所有导师对这些选手进行排名。
为了避免后续的麻烦，规定不存在排名并列的情况。
同时，每名选手都将独立地填写一份志愿表，来对总共位导师（编号从至）作出评价。志愿表上包含了共档志愿。对于每一档志愿，选手被允许填写最多位导师，每位导师最多被每位选手填写一次（放弃某些导师也是被允许的）。
在双方的工作都完成后，进行录取工作。每位导师都有自己战队的人数上限，这意味着可能有部分选手的较高志愿、甚至是全部志愿无法得到满足。
节目组对“前名的录取结果最优”作出如下定义：

• 前名的录取结果最优，当且仅当第名被其最高非空志愿录取（特别地，如果第名没有填写志愿表，那么该选手出局）。
• 前名的录取结果最优，当且仅当在前名的录取结果最优的情况下：第名被其理论可能的最高志愿录取（特别地，如果第i名没有填写志愿表、或其所有志愿中的导师战队均已满员，那么该选手出局）。

如果一种方案满足“前名的录取结果最优”，那么我们可以简称这种方案是最优的。
举例而言，位导师老师、老师的战队人数上限分别都是人；位选手、分列第名。那么下面种志愿表及其对应的最优录取结果如表中所示：

可以证明，对于上面的志愿表，对应的方案都是唯一的最优录取结果。
每个人都有一个自己的理想值，表示第位同学希望自己被第或更高的志愿录取，如果没有，那么他就会非常沮丧。
现在，所有选手的志愿表和排名都已公示。巧合的是，每位选手的排名都恰好与它们的编号相同。
对于每一位选手，都想知道下面两个问题的答案：

• 在最优的录取方案中，他会被第几志愿录取。
• 在其他选手相对排名不变的情况下，至少上升多少名才能使得他不沮丧。

作为《中国新代码》的实力派代码手，当然轻松地解决了这个问题。不过他还是想请你再算一遍，来检验自己计算的正确性。

Input

每个测试点包含多组测试数据，第一行个用空格隔开的非负整数，分别表示数据组数、每档志愿最多允许填写的导师数目。
接下来依次描述每组数据，对于每组数据：

• 第行两个用空格隔开的正整数。分别表示选手的数量、导师的数量。
• 第行个用空格隔开的正整数：其中第个整数为。表示编号为的导师战队人数的上限。
• 第行至第行，每行个用空格隔开的非负整数：其中第行左起第个数为
  • 表示编号为的选手将编号为的导师编排在了第志愿。特别地，如果，则表示该选手没有将该导师填入志愿表。
  • 在这一部分，保证每行中不存在某一个正数出现超过次（可能出现超过次），同时保证所有。
• 第行个用空格隔开的正整数，其中第个整数为
  • 表示编号为的选手的理想值。
  • 在这一部分，保证。

Output

按顺序输出每组数据的答案。对于每组数据，输出行：

• 第行输出个用空格隔开的正整数，其中第个整数的意义为：
  • 在最优的录取方案中，编号为的选手会被该档志愿录取。
  • 特别地，如果该选手出局，则这个数为。
• 第行输出个用空格隔开的非负整数，其中第个整数的意义为：
  • 使编号为的选手不沮丧，最少需要让他上升的排名数。
  • 特别地，如果该选手一定会沮丧，则这个数为。

Problem

【APIO2010】特别行动队

Description

Input

Output