向后端赛道的参与者颁发奖品
我们正在完成对第二届编程冠军的一系列分析。 最近几周，我们发布了对以下三个方面的分析：ML，前端和移动开发。 仍然需要解析后端的轨道。 事实证明，最受欢迎的是：2682人参加了资格赛，其中320人进入了决赛。 Yandex.Taxi团队发明了后端开发人员的任务。
火星促销代码
作者：Maxim Pedchenko自Yandex.Taxi在火星上发射以来已经过去了六个月。 在火星新年前，Yandex.Taxi决定向火星人提供促销代码。 但是事实证明，火星人无法使用地球促销代码，因为火星上的服务器无法按照地球规则工作。 因此，Yandex.Taxi提出了特殊的火星促销代码。
火星促销代码生成如下：
- 生成一个加密密钥。
- 加密密钥分为随机长度的子字符串。
- 在所有子串中，选择长度为L的子串。
- 选定的子字符串被混合并连接在一起。
- 串联的结果是促销代码。
挑战：
必须检查输入的促销代码是否有效。 如果促销代码有效，则需要打印“是”。 如果无效，则为“否”。
I / O格式，示例和注释输入格式
<促销代码长度>
<促销代码>
<密钥长度>
<键>
<子串长度L>
输出格式
促销代码有效期：是或否。
例子1
例子2
例子3
注意事项
长度L> 1。
促销代码字母[AZ，0-9]。
促销代码的长度在[6，30]范围内。
密钥长度在[6，30]范围内。
子串长度L <密钥长度。
促销代码的长度是L的倍数。
解决方案
我们需要考虑将加密密钥的所有可能分区分成长度为L的子字符串，并检查此促销代码是否可以由可能的分区组成。
提示隐藏在条件注释中：
促销代码的长度在[6，30]范围内。
密钥长度在[6，30]范围内。
较小的限制表明不需要有效的解决方案，这意味着您无需花费时间搜索优化-最好直接解决问题。
这种情况是产品后端开发的典型情况。 通常情况下，您可能需要花费数周的时间来研究最佳算法，但如果权衡了这些限制，很显然，最好使用快速而不是最佳的解决方案。
因此，我们将带有促销代码的行视为长度为L的子串S的序列。对于每个子串S，我们从加密密钥中找到与其相等的所有子串S
k 。 对于每个S
k，记住其用法，移至下一个子串S并重复该算法。
如果对于子字符串S不可能找到未使用的S
k ，则有必要尝试另一种拆分方法，如果没有其他变量，则促销代码无效。
如果对于每个S至少有一种情况发现了S
k ，则促销代码有效。
火星运输系统优化
作者：德米特里·波兰丘克（Dmitry Polishchuk）和安东·托杜（Anton Todua）那是2058年。 最早的定居者殖民地已经登陆火星并开始在火星上居住，Yandex.Taxi开始部署穿梭站系统。
为了正常运行，穿梭站需要从能源网络持续供电。 要为电站供电，您必须在电站本身内部建造铀核能发生器，或将电缆铺设到另一个（已供电的）穿梭电站。 在不同的穿梭站内建造发电机的成本可能会有所不同。 穿梭站之间的电缆布线成本也不尽相同，而且并非总是可行。 电缆连接是双向的。
任务是为所有穿梭站组织高效（最低成本）的电力。
该程序在入口处接收穿梭站的总数，为每个穿梭站建造发电机的成本以及对穿梭站之间所有可能的电缆的描述（已连接站的数量和铺设电缆的成本）。
I / O格式，示例和注释输入格式
第一行包含单个非负数的穿梭站N≤1000。
第二行包含N个数字，这些数字指定了在相应站点内构建发电机的成本。
第三行在穿梭站之间包含一个非负数的可能电缆K≤100000。
接下来的K条线 （从第四
条开始）包含对一根电缆的描述-三个整数非负数：
第一个站的
数量，第二个站的
数量和实施
成本 。
输出格式
对于给定的配置，所有往返站的最低电源成本为一个整数。
例子1
例子2
注意事项
工作站从一开始编号。
行内的数字用单个空格分隔。
不需要检查输入数据的正确性。
解决方案
首先，有必要从精美的描述变为无方向的加权图，在该图中，穿梭站的位置将出现峰顶，电缆将变成边缘，而建筑电缆的成本将变成相应边缘的权重。 但是问题仍然存在-如何考虑在车站（峰值）内部建造铀发生器的成本？ 这个问题的答案是问题的实质。
假设存在另一个顶点-能源，并且从该顶点到图形的每个顶点绘制一条边，其权重等于在相应站点（顶点）中建造铀发生器的成本。 这个假设使我们得到一个需要变成一棵树的连接图，以使图中的边的权重之和成为最小。 这无非是在图中找到最小生成树的问题。 您可以使用任何已知算法（例如Prima或Kraskal）构建最小生成树。
带有注释的示例代码 #include <algorithm> #include <iostream> #include <tuple> #include <vector> using Price = std::size_t; using Vertex = std::size_t; using Transition = std::tuple<Price, Vertex, Vertex>; using Graph = std::vector<Transition>; // ( ). class Equals { public: // . explicit Equals(std::size_t size) { equals_.resize(size); // . for (std::size_t i = 0; i < size; i++) { equals_[i] = i; } } // v1 v2 true, // . bool Emplace(std::size_t v1, std::size_t v2) { while (v1 != v2) { if (v2 < v1) { std::swap(v1, v2); } auto& next_v2 = equals_[v2]; if (next_v2 == v2) { next_v2 = v1; return true; } v2 = next_v2; } return false; } private: std::vector<size_t> equals_; }; int main() { // . std::size_t vertex_count = 0; std::cin >> vertex_count; if (vertex_count == 0) { std::cout << 0 << std::endl; return 0; } // — — . vertex_count++; // . Graph graph; graph.reserve(vertex_count); // . for (Vertex i = 1; i < vertex_count; i++) { Price price = 0; std::cin >> price; graph.emplace_back(price, 0, i); } // . std::size_t edge_count = 0; std::cin >> edge_count; for (std::size_t i = 0; i < edge_count; i++) { Price price = 0; Vertex from = 0, to = 0; std::cin >> from >> to >> price; graph.emplace_back(price, from, to); } // . std::sort(graph.begin(), graph.end()); // . // https://ru.wikipedia.org/wiki/_ Price result = 0; Equals equals{vertex_count}; for (const auto& [price, from, to] : graph) { if (equals.Emplace(from, to)) { result += price; } } // . std::cout << result << std::endl; return 0; }
禁止停车
作者：Ilya Mescherin和Artyom Serebriysky在一个城市中，除登车外，禁止汽车停车。 乘客不同意等待超过3分钟。 在这个城市，行人命令出租车到达X点，并指出间隔为180秒。 驾驶员必须恰好在此间隔到达。 如果您提前到达，您将无法期待乘客。 如果您来不及，生气的乘客将取消订单。
由于这样的限制，只有Z个驾驶员留在了这个城市，每个人在任务开始时都处于流量图表的顶部。 控制系统应从设法到达指定时间间隔的人员中任命最佳驾驶员。 最好的驱动程序是在时间间隔的开始附近订购的驱动程序。 如果有几个这样的驱动程序，那么任何一个。
每个驾驶员有必要确定他是否有时间到达指示的时间间隔，如果是，则确定他可以在指示的时间间隔最早到达的时间。
形式描述鉴于：
- 定向图形G具有N个顶点和K个边，这些顶点的编号从0到N – 1，0≤N≤10 4，0≤K≤10 4 。 每个边沿都对应于其中的传播时间-整数W，10≤W≤10 4 。
- 订单在ID 目标列上的排名。
- 驱动程序在IDsource列2中的Z位置，1≤Z≤10 4 。
- 时间t 0，0≤t0≤600是整数。
每个驾驶员有必要找到这样的t
min ：
- 从驾驶员IDsource z到ID target的路线有一条，使得驾驶员在t min到达，
- t min∈[t 0 ; t 0 + 180]，
- 这是最早的t min ：对于满足点1和2的任何t i ，t min≤t i
- 或确保这样的t min不存在。
I / O格式，示例和注释输入格式
该图形以三元组-顶部-顶端-时间-旅行三元组的形式设置。
输入数据，每个项目单独一行：
1. K是边数。
2. K的三倍ID ID重量-肋骨的初始顶点，肋骨的最终顶点，汽车驱动肋骨的量。
3. ID
目标 t
0-需要到达时范围顶部的顺序[空格]。
4. Z-驱动程序数。
5.（Z倍）ID
z是下一个驱动程序
的顶部。
输出格式
对于每个驱动程序，按照它们输入的顺序，在单独的行上打印计算出的t
min；如果不存在该t
min ，则打印–1。
例子1
例子2
例子3
注意事项
1.顶点A到顶点B可以有多个边，包括那些权重相同的边。
2.允许从A到A的肋骨。
3.允许同时存在边（A-> B）和（B-> A）（长度为2的循环）。
解决方案
单驱动首先，我们将分析一个驱动程序的简单情况。 肋骨的度量是[行驶时间]，光洁度的限制以相同单位表示，因此我们可以重新定义问题：“驾驶员根据图表从A点移至B点。 找到一条最小路径，使其长度位于线段[T，U]中。”
最简单的方法是从A到B运行修改后的dijkstra：
- 修改1.假设我们从minQ处获得顶部，并且已经将其标记为黑色（也就是说，已经找到与其的最小距离）。 然后我们不忽略它，而是以标准方式处理它-将所有具有新距离的相邻顶点放回minQ中。
- 仅当到当前顶点的距离minQ严格大于U时，我们才停止它。
- 假设我们在遍历过程中遇到了峰值B，那么，如果当前距离≥T，请记住它作为答案R。在这一点上，dijkstra也可以被打断。
因此，如果我们有R，这是长度在所需间隔内的最小路径。
许多司机前额的解决方案是为每个驱动程序运行一个算法。 但是，这种解决方案并不能通过限制时间来解决。 我们必须学会为O（1）的每个驱动器给出答案。
为此，我们为一个驱动程序修改了算法：
- 代替从驱动程序到订单点的dijkstra，我们根据带有倒置（！）边的图形从订单点开始dijkstra。
- 我们利用这样一个事实，即顶点的数量也限制为一万。 让我们得到一个答案数组R-对于每个顶点，这是可以从A到达[T，U]范围内的最短时间。
- 在遍历修改后的dijkstroy的图形的过程中，当我们遇到顶点j时，如果当前顶点与顶点j的距离在所需间隔[T，U]中，则输入R：R j = min（R j ，dist）。
然后，对于顶点J处的每个驱动程序，可以查询R
j以确定是否存在满足条件的路径及其长度。
MinQ优化路径长度始终是整数，并且从顶部开始一直限制为781-对于在t
0 = 600处执行的命令，驾驶员到达的最后一个有效秒数是780。在这种情况下，要实现dijkstra，您需要使用以下minQ实现。
我们有一个大小为[781]的边缘数组。 在边缘
I的每个元素中，有一个unordered_set，用于存储路径长度为i的所有顶点的id。
1.添加一个距离为D的顶点：
fringe[D].insert(vertex);
2.根据条件，边缘的最小权重>0。因此，您不必遍历整个minQ中的元素，而可以遍历整个切片：
for(int i = 0; i < fringe.size(); ++i) { if(fringe[i].empty()) { continue; } for(auto& vertex : fringe[i]) {
旅行费用计算器
作者：尼古拉·菲尔琴科（Nikolay Filchenko）必须根据给定的公式计算出差旅费用。 每个行程均由K个整数参数表示。 该公式以相反的波兰语表示法给出。
允许的操作：
- +--加减法；
- * / -乘法和整数除法；
- <= -比较；
- ？ -条件运算符。 如果第一个参数为true，则返回第二个参数，否则，返回第三个参数。
公式
中还使用了变量[az]和-10
9到10
9的整数。
我们可以假定公式中所有运算的结果绝对值不超过10
9 。 比较操作的结果仅用作条件运算符的参数。
I / O格式和示例输入格式
在第一行，一个数字1≤K≤26-变量数。
第二行包含用于计算价格的公式（不超过3⋅104
个元素）。 所有元素都由空格分隔。
第三行，测试数为1≤N≤10 4。
接下来的N行各包含K个整数（–10 9≤v≤10
9 ）-变量的值按字母顺序排列。
输出格式
N行包含一个整数-每组值的替换结果。 保证表达式的结果是有限的和定义的
例子1
例子2
解决方案
这是需要认真执行和关注的任务。 解决方案中有两个要点：
- 原始表达式本身必须转换为数字和运算的数组，以免将字符串解析为每组变量。
- 必须记住，整数除以零会导致SIGFPE，因此在除法运算中，有必要明确检查分母是否不为零。 基于整个表达式结果的确定性和确定性的保证，我们可以理解：此类除法的结果不涉及最终结果，而是位于条件运算符的未使用分支中，因此您可以接受任何值（例如零）。
关于这个话题的争论：