2019-2020 Saint-Petersburg Open High School Programming Contest (SpbKOSHP 19)
11 problems from 2019-2020 Saint-Petersburg Open High School Programming Contest (SpbKOSHP 19) (contest 102396), difficulty -. 8/11 solutions verified against sample I/O.
2019-2020 Saint-Petersburg Open High School Programming Contest (SpbKOSHP 19)
Special | 11 problems | 8/11 verified | Difficulty - | 1h 21m
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | King's Inspection | 13m 13s | ✓ | |||
| B | Cash Gap | 10m 58s | ✓ | |||
| C | Jet Trains | 4m 51s | ||||
| D | Cutting Pizza | 11m 2s | ✓ | |||
| E | Unique Solution | 6m 52s | ||||
| F | Metro 2345 | 3m 11s | ✓ | |||
| G | Weight Overflow | 3m 16s | ||||
| H | Checking Answers to Test | 14m 30s | ✓ | |||
| I | Magic Trick | 3m 25s | ✓ | |||
| J | Superpermutations | 7m 28s | ✓ | |||
| K | Preparing Tests | 2m 43s | ✓ |
CF 102396E - Unique Solution
We are given a target vector (a) of length (n), where every coordinate is (-1), (0), or (1), and at least one coordinate is nonzero.
CF 102396C - Jet Trains
Think of the cities as vertices of an undirected graph whose edges are the currently available train routes. Since routes are bidirectional, two cities can reach each other exactly when they belong to the same connected component of this graph.
CF 102396G - Weight Overflow
We have up to 25 weights, and each weight may be placed on the first plate, the second plate, or left unused. The scale does not compare the ordinary sums. Instead, it reduces both plate sums modulo (m), and reports balance when those two residues are equal.
CF 102396D - Cutting Pizza
We have a circular pizza and (n) people. Person (i) needs one sector whose angle is exactly (alphai) degrees. The sectors can be placed anywhere on the pizza and do not have to appear in the input order. Any unused part of the pizza can stay in the box.
CF 102396I - Magic Trick
Artem starts with a cyclic permutation of the numbers from (1) to (n). For every position, he looks at that position and the next two positions, wrapping around at the end. Thus, from a permutation [ [a1,a2,ldots,an] ] he produces the (n) unordered triples [ {ai,a{i+1},a{i+2}}.
CF 102396H - Checking Answers to Test
We have a correct-answer string of length (n), and (m) students, each represented by another string of the same length. At every question, a student's answer is either correct or incorrect according to the corresponding character of the answer key.
CF 102396B - Cash Gap
We have an initial account balance s and n transactions that must all happen during the next m days. Transaction i changes the balance by count[i], but its exact day can be any day in the inclusive interval [from[i], to[i]].
CF 102396K - Preparing Tests
A subarray is interpreted as one complete multitest input. Its first value is the number m of graph edges, and the next 2m values are grouped into m unordered vertex pairs.
CF 102396J - Superpermutations
The construction starts with the sequence [1]. To move from order m to order m+1, we scan every length-m window of the current sequence. Whenever such a window is a permutation of 1..m, we insert the new value m+1 followed by that same permutation immediately after the window.
CF 102396F - Metro 2345
Think of the metro system as a weighted graph. Every station is a vertex, consecutive stations on the same line are connected by an edge, and the edge weight is the travel time between those stations.
CF 102396A - King's Inspection
We have three chests containing a, b, and c coins. In one second, we choose exactly two different chests and add one coin to each chosen chest. We need all three chests to end with the same number of coins, and we want the minimum number of seconds.