1C
任务：FIN
决赛选手 [C]
2025年算法竞赛，第一轮。限制：1024 MB，2秒。10.03.2025
今年，你决定终于进入算法竞赛的决赛！在你实现这一目标之前，最好先了解一下决赛的具体资格规则。在竞赛的规程中，你发现了以下几点： • 经过五轮线上比赛后，竞赛将会选出20名选手进入决赛。其中，排名A+B+C前十名的选手将占据其中十个名额。剩下的十个名额将由排名靠前的选手组成，排除那些至少两次参加过算法竞赛决赛的选手。 • 只有波兰国籍选手、波兰居民或在波兰学习、工作或居住的选手才能获得资格。 • 为了选出20名决赛选手，首先需要从排名中去除那些不符合资格的选手以及那些放弃参赛的选手。然后，在剩余选手中，按照上述规则选出20名决赛选手。
你的朋友非常了解所有参赛选手，并且预测了今年的排名。给了你一份包含n名选手的名单，选手编号从1到n，按成绩从高到低排列（名单中没有平局）。对于每个选手，你知道他们是否有资格并愿意参加决赛，以及他们之前参加过多少次决赛。
请你根据规则选出20名选手，按照规定的顺序列出他们的编号。
输入 • 第一行包含一个整数n（20 ≤ n ≤ 10,000），表示排名中的选手数量。 • 接下来的n行包含选手的信息。每一行包含一个字符串s和一个整数x（s ∈ {TAK, NIE}, 0 ≤ x < 20）。字符串TAK表示该选手愿意并能够参加决赛，字符串NIE表示该选手不能或不愿意参加决赛。数字x表示该选手此前参加决赛的次数。
输出 • 输出一行，包含20个以空格分隔的整数，表示成功进入决赛的选手编号，按升序排列。
示例
输入：
35 NIE 0 NIE 0 TAK 3 TAK 0 TAK 7 TAK 5 NIE 0 NIE 0 TAK 7 TAK 1 NIE 0 TAK 8 TAK 1 TAK 3 NIE 0 TAK 2 NIE 0 TAK 1 NIE 4 TAK 2 TAK 2 TAK 1 TAK 1 TAK 0 TAK 0 TAK 0 TAK 0 TAK 0 NIE 0 TAK 1 TAK 2 TAK 0 TAK 0 TAK 0 TAK 0
输出：
3 4 5 6 9 10 12 13 14 16 18 22 23 24 25 26 27 28 30 32
解释：
选手编号1、2、7、8、11、15、17、19、29被排除，因为他们不能或不愿参加决赛。剩下的10名最好的选手分别是编号3、4、5、6、9、10、12、13、14、16。然后，去除编号20、21和31的选手，因为他们已经至少参加过两次决赛，最终选出的第二组10名决赛选手的编号为：18、22、23、24、25、26、27、28、30、32。
备注：
你的朋友预测，编号23的选手将在决赛中获胜！
1B
任务：PRA 工作 [B] 算法对决 2025，第一轮。限制：1024 MB，2秒。2025年3月10日
算法对决开始了！不幸的是，Bajtazar不能忽视他的工作，他的职责不会因为对决周而神奇地消失。Bajtazar的一天可以分为n个时间段，每个时间段持续一个bajt小时。每个时间段的工作属于以下三类之一： 1. 办公室会议 2. 远程会议 3. 无责任
在一天内，Bajtazar可以在家里、办公室或两者之间的路上。Bajtazar的工作日从家里开始并结束，他最多可以去办公室一次，只要他能在第n个bajt小时之前返回家中。从家到办公室以及从办公室回家的时间恰好为t个bajt小时。根据他的当前位置，Bajtazar可以进行不同的活动： • 在家：Bajtazar当然不能参加办公室会议，但他可以（但不一定）参加远程会议，或者他可以解决算法对决的远程题目（但不能在开会时做题）。 • 在路上：Bajtazar不能参加任何会议，也不能做题——他必须专心开车（他没有雇司机）。 • 在办公室：Bajtazar可以参加任何类型的会议，除此之外他必须工作——不能做题。
你的任务是安排Bajtazar的一天，以最大化他解决问题的bajt小时数。然而，如果Bajtazar错过超过k个会议，他可能会被解雇。那时他来年的参赛资格，以及其他生活中的事情，都可能会受到影响——我们可不希望发生这种事。
Bajtazar非常有条理，所以在每个时间段内他只会专注于一项任务，特别是家和办公室之间的路程占用他正好t个连续的时间段。
输入 第一行包含三个整数n、k和t（3 ≤ n ≤ 8000，0 ≤ k ≤ n，1 ≤ t < n²），分别表示：时间段的数量、Bajtazar可以错过的会议数、以及从家到办公室单程的旅行时间（以bajt小时为单位）。 第二行是一个长度为n的字符串，由字符1、2或3组成，表示Bajtazar在每个时间段的任务类型。字符对应上文的类别编号。
输出 输出一个整数，表示Bajtazar能够在不超过错过k个会议的情况下，最多能用来做题的bajt小时数。如果无法在不超过错过k个会议的情况下完成，输出-1。
示例 输入1：
10 1 2 3233313132
输出1：
3
输入2：
7 0 2 3313233
输出2：
0
输入3：
6 5 1 231323
输出3：
6
输入4：
4 1 1 1331
输出4：
-1
示例解释： 在第一个示例中，在一个最优的解法中，Bajtazar的日程安排如下： 1. 解题 2. 远程会议（在家） 3. 解题 4. 路上去办公室 5. 路上去办公室 6. 办公室会议 7. 路上回家 8. 路上回家（错过了一个会议） 9. 解题 10. 远程会议（在家）
在这个计划中，Bajtazar错过了一个会议，并且在3个bajt小时内解决了题目。
在第二个示例中，唯一一个不失去工作且能够完成的计划如下： 1. 路上去办公室 2. 路上去办公室 3. 办公室会议 4. 办公室工作 5. 远程会议（从办公室） 6. 路上回家 7. 路上回家
在第三个示例中，Bajtazar可以整天在家解决题目，并且错过所有的远程会议。
在第四个示例中，Bajtazar无法参加任何办公室会议，因为他无法按时到达或按时返回家中。
1A
任务：TEL 瞬间传送 [A] 算法对决 2025，第一轮。限制：1024 MB，5秒。2025年3月10日
Bajtocja是一个由n个城市组成的国家（编号从1到n），这些城市通过双向高速公路连接。通过高速公路在两个城市之间行驶需要消耗一个bajtolit燃料。Bajtazar——BajtTrans公司的总裁，对燃料的消耗非常不满，因此他计划在Bajtocja的某两个城市之间设置一个双向传送门。通过传送门的旅行是瞬时的，并且不消耗燃料！BajtTrans公司的卡车必须拥有足够大的油箱，以便能够在一次加油后从任何一个城市出发，行驶到任何其他城市（不计算城市内消耗的燃料，忽略不计）。
Bajtazar希望最小化卡车油箱的大小。给定Bajtocja高速公路的描述，求出在最优选择传送门的情况下，所需的最小油箱容量。你可以假设，通过高速公路可以在每一对城市之间行驶。
你需要为t个独立的测试用例解决这个问题。
输入
第一行包含一个整数t (1 ≤ t ≤ 21)，表示测试用例的数量。 每个测试用例的第一行包含一个整数n (3 ≤ n ≤ 400)，表示Bajtocja的城市数量。 接下来的n行描述了Bajtocja的高速公路。每一行是一个长度为n的二进制字符串，第i个字符串的第j个元素为1，表示城市i和城市j之间有一条高速公路；否则为0。 • 每条高速公路连接两个不同的城市——第i行第i列的元素总是0。 • 每条高速公路是双向的——第i行第j列的元素与第j行第i列的元素相等。 使用这些描述的高速公路，可以在Bajtocja的每一对城市之间行驶。
所有测试用例的n值的总和不超过400。
输出
输出t行，每行包含一个整数，表示每个测试用例中，在最优设置传送门的情况下，所需的最小油箱容量（单位为bajtolit）。
示例
输入：
2 4 0111 1011 1101 1110 5 01000 10100 01010 00101 00010
输出：
1 2
示例解释：
在第一个测试用例中，每一对城市之间都可以直接通过高速公路连接，不论我们在哪两个城市之间设置传送门，仍然需要至少1个bajtolit的油箱。
在第二个测试用例中，如果油箱容量为2个bajtolit，我们仍然无法通过高速公路在城市对(1, 4)，(1, 5)和(2, 5)之间行驶。然而，设置传送门（例如在城市1和城市5之间）后，就可以解决这个问题。
2C
以下是该题目的中文翻译：
⸻
题目名称：学校选址（SZK）
算法对抗赛 2025，第二轮。限制：内存 1024 MB，时间 2 秒。日期：2025年3月11日。
Algolina 和 Bajtazar 打算搬到 Byte 城镇，因此需要寻找新家。在 Byte 城镇中只有一条长长的道路，道路旁有编号从 1 到 n 的 n 座建筑物。其中一些建筑提供出租公寓，而另一些则已经住满（我们称这些建筑为“已占用”）。
已占用的建筑物可以用 m 个互不重叠的区间 [l_i, r_i] 来描述，这表示所有编号满足 l_i \leq x \leq r_i 的建筑物 x 都已占用。
Algolina 和 Bajtazar 在选择住所时考虑了很多因素，其中一个重要因素是住所与他们的儿子 Bajtek 未来就读学校的距离。该学校位于编号为 s 的建筑中（保证该建筑已经被占用）。
由于 Bajtek 年龄还小，父母不希望他上学路程太远。因此，他们希望找到距离学校最近的一座尚未占用的建筑物。假设建筑物之间的距离都是相等的，他们需要选择一个建筑物编号 p，使得 |s - p| 尽可能小。
输入格式
第一行包含三个整数 n, m, s (2 \leq n \leq 10^{12}, 1 \leq m \leq 1000, 1 \leq s \leq n)，分别表示 Byte 城镇中的建筑物总数、已占用建筑区间的数量，以及学校所在建筑物的编号。
接下来的 m 行中，每行包含两个整数 l_i, r_i (1 \leq l_i \leq r_i \leq n)，描述第 i 个已占用建筑区间。任意两个区间不重叠，即对任意 1 \leq i < j \leq m 都满足 r_i < l_j 或 r_j < l_i。另外，保证一定至少存在一座未占用的建筑物。
输出格式
输出一个整数 p，表示 Algolina 和 Bajtazar 应该入住的建筑物编号，以最小化与学校的距离 |s - p|。如果存在多个这样的编号，输出最小的那个。
样例输入 1：
10 2 7 5 9 1 2
样例输出 1：
4
样例输入 2：
15 4 9 4 5 10 13 1 1 6 9
样例输出 2：
14
样例解释： • 在第一个样例中，与学校（7号建筑）最近的未占用建筑是编号为 4 和 10 的建筑。应选择最小的编号，因此答案为 4。 • 在第二个样例中，唯一最靠近学校（编号9）的未占用建筑是编号为 14 的建筑。
2B
以下是题目的中文翻译，使用markdown格式，并用美元符号包裹数学公式：
题目：WYL 数玩具
算法挑战赛 2025，第二轮。内存限制：1024 MB，时间限制：2 秒。日期：2025年3月11日
⸻
在幼儿园里，小贝有很多玩具。有时候，她很难决定当天要玩哪一个玩具。为了简化选择过程，她决定使用一种数数游戏（类似“点兵点将”）。
假设某一天她要从 n 个玩具中选择一个玩具。她会把这 n 个玩具排成一排，从左到右依次编号为 1 到 n。然后，她从某个玩具开始，按照儿歌（或数数游戏）中的每个音节，依次移动到当前玩具的前一个或后一个位置（注意：当她在最左边的玩具 1 时，只能向右移动到玩具 2；当她在最右边的玩具 n 时，只能向左移动到玩具 n−1）。最后，她停在某个玩具上，这个玩具便是她当天要玩的。
小贝在进行数数游戏时，会记录自己指向每个玩具的次数。当数数游戏结束后，她记下了一个序列 a1,a2,…,an，表示自己第 i 个玩具一共指过 ai 次。你的任务是判断小贝的记录是否有误，即：给定序列 a1,a2,…,an，检查是否存在一种符合规则的数数游戏，使得每个玩具的指向次数恰好与序列一致。
这样的情景在 t 天中发生，每一天的玩具集合与儿歌的长度可能不同。
⸻
输入格式
第一行包含一个整数 t（1≤t≤105），表示小贝使用数数游戏选择玩具的天数。
接下来共有 t 个对各天的描述，每一天描述格式如下： • 第一天描述的第一行包含一个整数 n（1≤n≤106），表示当天参与数数游戏的玩具个数； • 第二行包含 n 个整数 a1,a2,…,an（0≤ai≤109），表示小贝记下的每个玩具被指向的次数。
你可以保证，对于每一天，至少存在一个 ai≠0。
所有 t 天中 n 的总和不会超过 106。
⸻
输出格式
输出共 t 行，每行输出一个字符串，要么是TAK（表示存在符合条件的数数游戏），要么是NIE（表示不存在）。
⸻
样例
输入样例
7 3 1 3 1 2 5 7 3 0 1 0 1 2 6 3 3 2 1 0 0 5 1 3 2 2 3 3 1 0 1
输出示例
TAK NIE TAK NIE TAK NIE NIE
⸻
样例解释 • 第一天，小贝可以依次指向玩具的顺序为：1→2→1→2→3，符合 1,3,1。 • 第二天的记录不可能实现。 • 第三天，小贝只指了一次第二个玩具，然后停止。 • 第五天的序列可以为 1→2→3→4→3→2→1。 • 其他天的情况类似。
⸻
输出格式
对于每一天的记录，输出一行，若该序列可能通过数数游戏实现，则输出 TAK，否则输出 NIE。
2A
以下是题目的中文翻译，使用Markdown格式，数学公式已用美元符号（$）包裹：
⸻
题目：考试（EGZ）
考试 [A] 算法对决2025年，第二轮。 限制：内存 1024 MB，时间 3 秒。 日期：2025年3月11日。
Marysia 正在参加一个包含 n 个问题的考试。每个问题的评分方式如下： • 回答正确得 1 分； • 不作答得 0 分； • 回答错误得 −1 分。
要通过考试，需要获得至少 t 分。
对于每个问题，Marysia 已经准备了一个可能的答案，但她不确定这些答案是否一定正确。具体地说，对于第 i 个问题，她知道自己的答案以概率 pi 是正确的。不同问题答案的正确性相互独立。
现在 Marysia 要决定哪些问题回答、哪些问题不回答，以便最大化通过考试的概率。
输入
第一行包含两个整数 n,t（1≤t≤n≤50000），分别表示问题的数量和通过考试所需的最少得分。
接下来的 n 行，每行包含一个实数 pi（0≤pi≤1），表示第 i 个问题的答案正确的概率，每个数最多有 9 位小数。
输出
输出仅一行一个实数，表示 Marysia 在采取最优策略选择作答问题的情况下，通过考试的概率。
输出必须使用十进制（非科学计数）表示，最多保留 20 位小数。
答案允许的最大绝对误差为 10−6。
样例
输入示例1
5 2 0.77 0.85 0.75 0.98 0.6
输出示例1
0.8798125
输入示例2
5 3 0.3 0.01 0.2 0.15 0
输出示例2
0.009
输入示例3
3 3 0.000001 0.000001 0.000001
输出示例3
0
样例说明： • 第一个示例中，最优策略是回答前 4 个问题，不回答最后一个问题。这样即使回答错了 1 个问题，也仍能获得 2 分及以上。 • 第二个示例中，最优策略是回答第 1、3 和 4 个问题，这样若这 3 个问题全部答对，则 Marysia 得到 3 分。这三个问题的正确性相互独立，因此通过概率为 0.3×0.2×0.15=0.009。 • 第三个示例中，成功概率只有 10−18，因此输出近似为 0。
3C
求长宽高均为整数，对角线长度也为整数，且对角线长度不超过 n 的长方体数量。不区分底边的长宽，但区分高和长宽，即 a=1,b=2,h=3 和 a=2,b=1,h=3 是同一个长方体，但是和 a=3,b=1,h=2 不同。
更新：由于题目特殊性，本题不允许在论坛中分享样例。
n≤5000。
3B
对于一个整数 x，每次将 x 修改为，x 十进制表示所有数位的乘积，直到 x 为一位数。例如 57→35→15→5，55→25→10→0。t 次询问，每次询问给定 n，对于 0 到 9 之间的每个 a，求 1 到 n 的每个正整数进行上述操作后有几个数会得到 a。
t≤1000,n≤1018。
3A
时间轴视为 [0,L)，有 n 个人，每个人在 [i,i+1) 可以是空闲的或者忙的。你需要选择一个最大的实数 T，使得可以给每个人找到一段长度为 T 的，连续的，不忙的时间用来睡觉，且每个时刻至少有一个人醒着且不忙。
读入一个 n×L 的矩阵，X 表示忙，. 表示空闲。答案以最简分数形式输出。如果不存在合法的分配方案，输出 -1。
n≤18,L≤105。
4C
你有 n 个立方体积木，编号从 1 到 n。 编号为 i 的积木的尺寸为 ai × ai × ai，并且涂有图案 wi（图案用整数标识）。你的目标是使用你选择的积木搭建一座评分最高的塔。塔由若干块积木平放堆叠而成，从底部到顶部依次为 j1, ..., jm（其中 m 是选择的积木数量）。塔的评分基于以下标准：
稳定性：如果塔中每一块积木都比它上面的积木大（即 ajx > ajx+1），则塔是稳定的。不稳定的塔得分为 0，无论其他标准如何。
高度：如果塔的高度为 h = aj1 + ... + ajm，则评分增加 h。
风格评分：相邻积木的图案不同（即 wjx ≠ wjx+1）会影响美观，因此每对这样的相邻积木会扣除 c 分。
输入 第一行包含两个整数 n 和 c（1 ≤ n, c ≤ 500,000），分别表示可用积木的数量和相邻积木图案不同时的扣分值。 接下来的 n 行 描述每个积木。第 i 行包含两个整数 ai 和 wi（1 ≤ ai, wi ≤ 500,000），分别表示立方体积木的边长和图案编号。积木按尺寸非递减顺序给出（即 ai ≤ ai+1）。 在部分测试用例中（占 5 分），保证 ai < ai+1。
输出 输出一个整数，表示使用给定积木可以搭建的最佳塔的评分。
4B
小 Algosia 有一个尺寸为 n × m 的矩形棋盘，棋盘被划分为 n · m 个正方形格子。 Algosia 喜欢在棋盘上摆放立方体积木玩耍。积木的尺寸与格子相同，因此 Algosia 总是将积木放在格子上，每个积木恰好占据一个格子。
玩完后，Algosia 总是会乖乖收拾积木。她的手很小，因此每次只能将一个积木从棋盘上移到盒子里。为了能够拿起积木，她必须能够用手指抓住积木的两个相对面，并且这两个面不能被相邻的积木挡住。换句话说，这样的积木要么左右没有邻居，要么上下没有邻居。
Algosia 今天开始玩时，棋盘上已经摆放了 k 个积木。随后，在父母的帮助下，她进行了 q 次操作，每次操作要么在棋盘上添加一个积木，要么移除一个积木（在父母的帮助下，即使积木被相邻积木挡住，也可以移除）。
Algosia 想知道，对于棋盘上的每一种积木配置（即游戏开始时以及每次操作后），她最多可以独立地依次移除多少个积木。Algosia 只是假设性地考虑这个问题——她实际上并不会移除这些积木。请编写一个程序，计算每种配置下她可以移除的积木数量。
输入 第一行包含四个整数 n、m、k 和 q（1 ≤ n, m ≤ 200,000，1 ≤ k, q ≤ 75,000），分别表示棋盘的高度、宽度、游戏开始时棋盘上的积木数量以及操作次数。 接下来的 k 行 每行包含两个整数 xi 和 yi（1 ≤ xi ≤ n，1 ≤ yi ≤ m），表示游戏开始时第 i 个积木所在的格子坐标。每个格子上最多只有一个积木。 接下来的 q 行 每行包含两个整数 xj 和 yj（1 ≤ xj ≤ n，1 ≤ yj ≤ m），表示第 j 次操作的格子坐标。如果该格子上没有积木，则操作是在该格子上添加一个积木；如果该格子上已经有积木，则操作是移除该积木。
输出 输出 q + 1 行，每行包含一个整数。第 i 行的整数表示在进行前 i - 1 次操作后，Algosia 可以独立地依次移除的积木数量。
评分 在部分测试用例中（占一定分数），保证 q = 1。
4A
经过数月充满失败的航行后，Floating Point 号的海盗们偶然发现了一笔由 m 枚相同的金币组成的宝藏。 他们决定分赃并结束这次航行。
在航行过程中，海盗们彼此熟悉。他们都知道，所有海盗都具备完美的逻辑思维能力（许多海盗的职业生涯始于破解软件安全），并且主要受贪婪驱使，尽管有些海盗比其他海盗更贪婪。此外，他们还明确建立了一个线性等级制度——海盗们被编号为 1 到 n。
为了分配宝藏，海盗们采用了一种传统的海盗技术。编号最小的海盗（在尚未被扔下船的海盗中）提出一个分配方案，即为每个未被扔下船的海盗 i 指定一个非负整数 bi，表示该海盗在提议的分配中将获得的金币数量（所有 bi 的总和为 m）。然后，所有海盗（包括提议者）对提议的分配方案进行投票。如果至少 50% 的海盗投票支持该分配方案，则宝藏将按照提议分配。否则，提出分配方案的海盗将被扔下船，不再参与后续谈判，也不会获得任何金币。然后，该过程会重复进行（由等级制度中的下一个海盗向剩余的海盗提出分配方案）。
每个海盗 i 会在以下情况下投票支持提议的分配方案：
如果分配方案被拒绝，他会被扔下船；
或者 bi ≥ di + ai，其中 di 是分配方案被拒绝后他将获得的金币数量，ai 是他的贪婪系数。
所有海盗都知道彼此的贪婪系数，并且知道所有人都会按照以下确定性策略行事：
如果不存在任何可接受的分配方案（即至少一半未被扔下船的海盗会接受的方案），则海盗会提议自己拿走所有宝藏，然后接受被扔下船的命运。
如果存在可接受的分配方案，则会提出其中一个方案（即使获得 0 枚金币也比被扔下船好）。
在多个可能的可接受方案中，海盗会选择自己获得最多金币的方案。
如果仍然存在多个方案，海盗们倾向于将更多金币分配给编号更大的海盗。具体来说，海盗 i 在选择可接受的分配方案时，会依次最小化海盗 i + 1、海盗 i + 2 等获得的金币数量。
你的任务是编写一个程序，根据上述规则确定每个海盗将获得多少金币。
输入 第一行包含两个整数 n 和 m（1 ≤ n ≤ 50,000，1 ≤ m ≤ 5,000,000），分别表示海盗的数量和需要分配的金币数量。 第二行包含 n 个整数 a1, a2, ..., an（1 ≤ ai ≤ 64），表示每个海盗的贪婪系数。
输出 输出一行，包含 n 个整数 b1, b2, ..., bn。如果第 i 个海盗在分配过程中被扔下船，则 bi = -1；否则，bi 表示该海盗获得的金币数量。