6月1日，我们的编程冠军决赛进入了决赛。 获奖者的名字是已知的。 不久他们将获得奖项，与此同时，我们开始发布冠军任务的分析报告。 首先，我们将分析后端开发人员中资格认证阶段的任务。
资格鉴定持续一周，成千上万的参与者数量，因此事实证明，准备任务并非易事。 总共，我们必须执行24个任务，并将它们划分在四个选项之间，以使这些选项在复杂性上相当。
这次我们提出了六项任务，每项任务都有可能提出几种替代方案：一项发明的任务一次产生了四项！ 因此，事实证明这些选择尽可能地具有可比性。
因此，我不会发布所有24个问题的分析。 取而代之的是，我将分析其中一个资格选项的六个任务：以类似方式解决其他任务。
A.警报
任务条件在大多数IT公司中工作具有许多优点：没有着装要求，有时您可以远程工作，很酷很聪明的同事，当然还有免费的日程表！ 但是，免费的日程安排和远程工作能力需要很大的意志力。
程序员Alexei喜欢在晚上工作，不喜欢迟到。 为了准确地在早晨醒来，阿列克谢每晚开始 N 手机上的闹钟。 每个闹钟都已设置好，因此每响一次 X 从他带来的时间点开始。 例如，如果在某个时间点设置了警报 ti然后他有时会打电话 ti ， ti+X ， ti+2 cdotX 同时，如果任何两个警报同时开始响起，则仅显示其中一个。
众所周知，在醒来之前，阿列克谢每天早上都会听 K 闹钟，然后唤醒。 确定Alex醒来的时间点。
所有警报在整数次响铃，并且所有警报具有相同的呼叫暂停时间。 如果在时间点设置了两个警报 ti 和 tj ，并且这些时间点除以 X ，您只能留下一个闹钟-会响第一个的闹钟。
因此，第一步是消除不必要的警报：我们将按除法其余部分的值将它们分组 X 而且在每个组中，我们最早都只会设置一个闹钟。
现在，我们将学习如何确定在某个时间点响起了多少警报 T 。 如果闹钟设置为准时 ti ，按时间的通话次数 T 将相等
max Big（ fracT−tiX，0 Big）
将所有警报的这些值相加，我们将按时间获得响铃警报的总数 T 。
之后，最初的问题通过二进制搜索解决 T ：随着增加 T 响铃警报的数量不会减少（即功能是单调的）; 您可以选择0作为初始的左边界，并选择右边界最大的答案。
B.体育比赛
任务条件在玛莎休假期间，她的同事们在奥林匹克体系中组织了一场国际象棋比赛。 在剩下的时间里，玛莎（Masha）并没有对这项事业给予太多关注，因此她几乎记不清是谁和谁一起玩的（甚至没有关于游戏顺序的字眼）。 突然，玛莎想到将假期的纪念品带给比赛的获胜者会很高兴。 玛莎不知道谁赢了最后一场比赛，但是，只要她能正确记住比赛对，她就能轻松弄清楚谁参加了比赛。 帮助她检查是否存在这种情况，并确定获奖者的可能候选人。
这个问题可以通过恢复锦标赛游戏图来解决。 首先，很明显，每个参与者都已经进入比赛的哪个阶段：这取决于他参加比赛的次数。
之后，您可以在游览中分发游戏。 假设在第一轮的所有比赛中，一个参与者在第一轮中起飞，而另一名参与者则不早于第二轮。 处理带有数字的旅游游戏时 x 有必要检查此游戏的所有参与者当前是否玩过与该数字对应的相同数量的游戏 x 否则比赛无效。
恢复比赛计划后，仅保留打印答案。
C.有趣的游戏
任务条件Petya和Vasya在玩有趣的游戏。 首先，Vasya宣布要结束游戏需要得分。 然后Petya取出上面写有非负整数的卡片，并开始将它们一张一张地摆在桌子上。 如果卡上有5的倍数，则Vasya得1分。 如果卡上有3的倍数，则获得Petya得1分。 如果卡上的数字不是三或五的倍数，或者不是三或五的倍数，反之亦然。
一旦参与者之一获得了Vasya在游戏开始时指定的分数，游戏就会停止，并且该玩家成为获胜者。 如果没有一个参与者获得要求的分数，但是所有纸牌都结束了，那么获胜者就是得分最高的玩家。 如果所有牌都结束了，并且点均分，那么将宣布平局。
Petya和Vasya有时会赶时间，因此他们不想完全玩游戏，但要立即找出谁将以已知的初始数据获胜。 他们要求您编写一个程序来帮助回答这个问题。
此任务中最重要的事情是从条件中正确了解哪个玩家以及每次新举动后会获得多少积分，以及玩家在什么条件下获得积分。
该问题以直接的方式解决。 由于这些限制不仅仅适用于温和的情况，如果下一步的一名玩家获得了所需的分数，则足以一次浏览数据，中断其处理。 如果任何一个球员都没有得分所需的最低分数，则在循环结束时确定获胜者。
在此任务的某些版本中，有必要进一步处理玩家可以为同一张牌同时获得积分的情况。
预期该任务是所有资格认证任务中最简单的。
D.异常分析器
任务条件我们描述一种编程语言的语法 EX ：
func f() {...} -函数声明（在方括号中-正文）maybethrow Exc是一个可能抛出Exc类型异常或不抛出异常的命令。try {...} suppress Exc如果此块内部发生Exc类型的异常，则将其抑制。f()是对f的调用。
语言 EX 除函数声明外，所有指令只能在函数体内。 不能在其他函数中声明函数。 可以在定义函数之前以及在其自身中调用函数。 语言中的函数名称和异常 EX 必须匹配正则表达式 [a−zA−Z0−9 ]+ ，必须唯一并且不与关键字func匹配， try ， suppress ，可能maybethrow 。
输入语言程序 EX 和数字 x 。 对于程序的每个功能，不超过 x 可能会产生的异常。 应该输出 x 词典最小的例外。
事实证明，该任务是所有资格认证任务中最困难的。
为了解决这个问题，可以通过构造函数调用图来语法分析程序：在该图中，每个函数都对应一个顶点，而函数对应一个边。 之后，有必要直接在整个图上实现异常分布的逻辑-为此，适合在宽度上遍历图。
我们将选择一些异常以及所有可能引起异常的功能。 这些功能是从其他功能中调用的。 调用可能在try {...} suppress块内-在这种情况下，异常不适用于调用发生的函数。 因此，可以通过使用图形宽度遍历来确定可引发此异常的所有函数。
在针对所有可能的异常执行绕过之后，它仅保留为一个答案。
E.解码
任务条件一项新服务已出现在Internet上。 不幸的是，他没有文档。 根据经验，从服务器接收到字符串s 。 但是，此行中的某些字符已编码-为了获得真实答案，您需要对该行进行多次解码。 由于没有该服务的文档，因此为进行进一步的实验，有必要确定该行可以以不平凡的方式进行解码的最大次数。 解码过程如下：您需要找到〜XY形式的所有子字符串，其中X和Y是大或小的十六进制数字，并同时用ASCII码字符替换它们 16X+Y （每个子字符串都有自己的）。 如果没有这种子字符串，则解码称为平凡的。
在单行中打印原始字符串的最大连续连续非平凡解码数。
我们将从左到右依次考虑源字符串的字符。 如果添加另一个字符导致可以解码的序列，则需要执行此操作。 解码应尽可能长地重复，即 在当前行的末尾有一个由任务条件定义的形式的序列。
对于生成的解码字符串的每个字符，您必须记住必须解码原始字符串多少次。 显然，添加到字符串的字符被解码零次。 如果已解码的符号参与下一个解码操作 r1，r2，...，rk 时间，那么他们形成的符号就需要 max（r1，r2，...，rk）+1 解码操作。
让最终的解码字符串包含字符 a1，...，ak ，以获得分别进行解码所必需的 r1，...，rk 次。 那么答案就是数量
max（r1，...，rk）
F.找到一个断断续续的提交
任务条件Yandex Search实施所谓的“绿色主干”策略：进入存储库的任何代码（带有一些警告）都应保证不会破坏程序集和测试。
但是，测试非常困难，并且在每次提交时都运行它们都是不切实际的。 因此，对于特别困难的情况，将执行以下过程：以一定的规律运行测试，并立即检查一组提交。 因此，一段时间以来，n个未经测试的提交可能会落入主干，其中至少有一个包含错误。
在这种情况下，测试系统应检测到破坏测试的第一次提交的数量m。 该编号具有以下属性：编号小于m的所有提交均成功通过测试，且编号大于或等于m的失败测试均已提交。 该任务确保具有指定属性的提交必定存在并且是唯一的。
为了节省资源，测试系统一次只能检查一次提交。 您需要编写一个确定数字m的程序。
该任务在我们的产品中有一个原型：搜索组件的某些测试确实太复杂了，它们对于每次提交来说都太昂贵了，并且为他们执行了类似于任务中所述的查找故障的过程。 当然，开发人员可以使用审核前验证，并且通常可以执行此操作，因此通常不需要此过程。
任务的不同版本在需要同时检查的提交次数上有所不同。
这里的解决方案非常简单：您需要实现稍微复杂一点的二进制搜索版本。 假设，如果要一次检查四个提交，则需要用四个数字平均分割当前段。 在实现期间，当段的长度小于同时检查的提交的数量时，必须注意避免循环。 还值得注意的是，根据问题的情况，您可以多次检查同一提交-有时您必须这样做，例如，如果总共提交了两次，则需要一次检查三个提交。
讨论的资格回合任务可作为Codeforce培训获得 。 我们还对决赛的任务进行了培训 。