School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules)
Solutions for School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules) (contest 38). 5/8 problems verified against sample I/O. Difficulty range: 800-2400.
School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules)
Type: Beta | Problems: 8 | Verified: 5/8 | Rating range: 800-2400 | Time: 13m 48s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Army | 800 | implementation | 1m 18s | ✓ |
| B | Chess | 1200 | brute-force, implementation, math | 2m | ✗ |
| C | Blinds | 1400 | brute-force | 1m 7s | ✓ |
| D | Vasya the Architect | 1900 | implementation | 1m 38s | ✓ |
| E | Let's Go Rolling! | 1800 | dp, sortings | 1m 24s | ✓ |
| F | Smart Boy | 2100 | dp, games, strings | 2m 49s | ✗ |
| G | Queue | 2300 | data-structures | 1m 1s | ✓ |
| H | The Great Marathon | 2400 | dp | 2m 31s | ✗ |
CF 38A - Army
Vasya currently holds rank a in the army and wants to eventually reach rank b. Moving from rank i to rank i + 1 requires a fixed number of years, stored in the array d.
CF 38B - Chess
We are given the positions of two chess pieces on a standard 8 × 8 board, one rook and one knight. Their starting positions are guaranteed to be safe, meaning the rook does not attack the knight and the knight does not attack the rook.
CF 38C - Blinds
We have a set of horizontal blind stripes of varying lengths, and our goal is to construct a rectangular blind for a window using these stripes. Each stripe can be cut into smaller pieces, but pieces cannot be shorter than a given minimum length, l.
CF 38D - Vasya the Architect
We stack cubes one by one. Every cube is axis-aligned, and its projection on the ground is a square. Since the cubes are actual cubes, the side length is determined by the square base.
CF 38E - Let's Go Rolling!
We are given n marbles on a one-dimensional axis, each with a position x[i] and a pin cost c[i]. You can stick a pin in some marbles, paying the associated cost, and unpinned marbles will roll left until they hit the nearest pinned marble.
CF 38F - Smart Boy
We start with an empty string. The first player picks any single letter that appears somewhere inside at least one dictionary word. After that, players alternately extend the current string by adding exactly one character either to the front or to the back.
CF 38G - Queue
We are asked to simulate a queue of people where each person has two properties: an importance value a[i] and a patience limit c[i].
CF 38H - The Great Marathon
We have a connected weighted graph of cities. Runner i starts from city i and finishes in some other city. The finish city is chosen independently for every runner, and several runners may share the same destination.