games | brain

Practice › Codeforces Solutions ›

Codeforces Round 1090 (Div. 4)

Codeforces Round 1090 (Div. 4) Type: Div. 4 | Problems: 4 | Verified: 1/4 | Rating range: 800-1800 | Time: 10m 7s Problem Name Rating Tags Solve Time Verified A The 67th Integer Problem 800 brute-force, games, implementation 1m 27s ✓ D The 67th OEIS Problem 1100 constructive-algorithms, greedy, math 2m 4s ✗ F The 67th Tree Problem 1500 constructive-algorithms, implementation, trees 3m 38s ✗ G [The 67th Iteration of...

Practice › Codeforces Solutions › Codeforces Round 1090 (Div. 4) ›

CF 2218A - The 67th Integer Problem

CF 2218A - The 67th Integer Problem Rating: 800 Tags: brute force, games, implementation, math Solve time: 1m 27s Verified: yes Solution Problem Understanding The problem asks us to pick an integer $y$ for a given integer $x$ so that the minimum of $x$ and $y$ is as large as possible. We are given multiple test cases, each consisting of a single integer $x$ between -67 and 67. Our output...

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951H - Thanos Snap

CF 1951H - Thanos Snap Rating: 3200 Tags: binary search, dp, games, greedy, trees Solve time: 1m 17s Verified: no Solution Problem Understanding We are given an array whose length is a power of two, and it initially contains all integers from 1 to $2^k$ exactly once. So the array is just a permutation, but its initial order matters. A game is played on this array. A parameter $t$ is...

Practice › Codeforces Solutions › Codeforces Round 941 (Div. 1) ›

CF 1965A - Everything Nim

CF 1965A - Everything Nim Rating: 1400 Tags: games, greedy, math, sortings Solve time: 1m 24s Verified: no Solution Problem Understanding We are given several independent games, each defined by a list of piles containing stones. Two players alternate turns. A move consists of choosing an integer $k$ that does not exceed the smallest nonempty pile, then simultaneously subtracting $k$ stones from every pile that is still nonempty. Any pile...

Practice › Codeforces Solutions › Codeforces Round 941 (Div. 1) ›

CF 1965E - Connected Cubes

CF 1965E - Connected Cubes Rating: 3100 Tags: constructive algorithms, games Solve time: 1m 10s Verified: no Solution Problem Understanding We are given an $n \times m$ grid sitting at height $z=1$, where each cell already contains a unit cube with a color. You are allowed to stack additional colored cubes at integer coordinates above this base layer, but you are blocked from using any cell on the coordinate planes...

Practice › Codeforces Solutions ›

Codeforces Round 942 (Div. 2)

Codeforces Round 942 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 0/1 | Rating range: 900-900 | Time: 5m 40s Problem Name Rating Tags Solve Time Verified B Coin Games 900 games 5m 40s ✗

Practice › Codeforces Solutions › Codeforces Round 941 (Div. 2) ›

CF 1966A - Card Exchange

CF 1966A - Card Exchange Rating: 800 Tags: constructive algorithms, games, greedy Solve time: 1m 12s Verified: no Solution Problem Understanding We are given a multiset of cards, where each card carries an integer label. The only allowed operation takes exactly k cards that all share the same label and removes them, replacing them with k-1 new cards whose labels we are free to choose arbitrarily. The freedom to assign...

Practice › Codeforces Solutions › Codeforces Round 281 (Div. 2) ›

CF 493D - Vasya and Chess

CF 493D - Vasya and Chess Rating: 1700 Tags: constructive algorithms, games, math Solve time: 1m 25s Verified: yes Solution Problem Understanding We have an $n \times n$ board. The white queen starts at the top-left corner $(1,1)$, and the black queen starts at the top-right corner $(1,n)$. Every other square contains a green pawn. A move is mandatory. On each turn, a player must capture some piece with their...

Practice › Codeforces Solutions › Codeforces Round 939 (Div. 2) ›

CF 1956B - Nene and the Card Game

CF 1956B - Nene and the Card Game Rating: 800 Tags: games, greedy Solve time: 53s Verified: yes Solution Problem Understanding We are given a multiset of $2n$ cards, where every number from $1$ to $n$ appears exactly twice in total. These cards are split evenly between two players, you and Nene, so each of you holds $n$ cards. We are only given your hand; Nene’s hand is implicitly determined...

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 1) ›

CF 1943A - MEX Game 1

CF 1943A - MEX Game 1 Rating: 1300 Tags: games, greedy Solve time: 1m 9s Verified: yes Solution Problem Understanding We are asked to analyze a two-player game on an array of non-negative integers. Alice begins with an empty array c , and on her turn, she takes any element from the initial array a and appends it to c . Bob, on his turn, removes any element from a...

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942E - Farm Game

CF 1942E - Farm Game Rating: 2300 Tags: combinatorics, games Solve time: 1m 56s Verified: yes Solution Problem Understanding The cows of the two farmers must appear in alternating order on the line. Once the order of the first cow is chosen, the entire sequence is fixed: either J N J N ... J N or N J N J ... N J . The actual positions are not fixed....

Practice › Codeforces Solutions ›

Codeforces Round 941 (Div. 1)

Codeforces Round 941 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 0/6 | Rating range: 1400-3300 | Time: 7m 12s Problem Name Rating Tags Solve Time Verified A Everything Nim 1400 games, greedy, math 1m 24s ✗ B Missing Subsequence Sum 1800 bitmasks, constructive-algorithms, greedy 1m 17s ✗ C Folding Strip 2300 constructive-algorithms, greedy, strings 1m 8s ✗ D Missing Subarray Sum 2900 constructive-algorithms 1m 5s ✗ E...

Practice › Codeforces Solutions ›

Codeforces Round 941 (Div. 2)

Codeforces Round 941 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 0/2 | Rating range: 800-1100 | Time: 2m 20s Problem Name Rating Tags Solve Time Verified A Card Exchange 800 constructive-algorithms, games, greedy 1m 12s ✗ B Rectangle Filling 1100 constructive-algorithms, implementation 1m 8s ✗

Practice › Codeforces Solutions › Codeforces Round 282 (Div. 1) ›

CF 494E - Sharti

CF 494E - Sharti Rating: 3200 Tags: data structures, games Solve time: 11m 29s Verified: no Solution Problem Understanding The board is enormous, up to $10^9 \times 10^9$, so we never have any chance of working with cells directly. A move chooses a square of side length at most $k$. The lower-right corner of that square must currently be white. Every cell inside the square is flipped. Two players alternate...

Practice › Codeforces Solutions › Codeforces Round 939 (Div. 2) ›

CF 1956A - Nene's Game

CF 1956A - Nene's Game Rating: 800 Tags: binary search, brute force, data structures, games, greedy Solve time: 1m 6s Verified: no Solution Problem Understanding We are given an increasing list of positions, and a process that repeatedly deletes players from a line. In each round, we look at the current lineup and try to remove the players standing at positions $a_1, a_2, \ldots, a_k$. These positions are always interpreted...

Practice › Codeforces Solutions ›

Codeforces Round 939 (Div. 2)

Codeforces Round 939 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 3/7 | Rating range: 800-3000 | Time: 7m 40s Problem Name Rating Tags Solve Time Verified A Nene's Game 800 binary-search, brute-force, data-structures 1m 6s ✗ B Nene and the Card Game 800 games, greedy 53s ✓ C Nene's Magical Matrix 1600 constructive-algorithms, greedy, math 57s ✓ D Nene and the Mex Operator 2000 bitmasks, brute-force, constructive-algorithms...

Practice › Codeforces Solutions › Codeforces Round 938 (Div. 3) ›

CF 1955F - Unfair Game

CF 1955F - Unfair Game Rating: 1800 Tags: dp, games, greedy, math, schedules Solve time: 1m Verified: no Solution Problem Understanding We are asked to maximize the number of games Bob can win in a repeated XOR game against Alice. The game is played on a multiset of integers containing only ones, twos, threes, and fours. Alice wins if the XOR of all remaining numbers is non-zero; otherwise, Bob wins....

Practice › Codeforces Solutions ›

Codeforces Round 934 (Div. 1)

Codeforces Round 934 (Div. 1) Type: Div. 1 | Problems: 8 | Verified: 1/8 | Rating range: 1300-3500 | Time: 10m 17s Problem Name Rating Tags Solve Time Verified A MEX Game 1 1300 games, greedy 1m 9s ✓ B Non-Palindromic Substring 2000 hashing, implementation, math 1m 20s ✗ C Tree Compass 2300 constructive-algorithms, dfs-and-similar, greedy 1m 16s ✗ D1 Counting Is Fun (Easy Version) 2400 brute-force, combinatorics, dp 1m...

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 2) ›

CF 1972B - Coin Games

CF 1972B - Coin Games Rating: 900 Tags: games Solve time: 5m 40s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 260 (Div. 1) ›

CF 455B - A Lot of Games

CF 455B - A Lot of Games Rating: 1900 Tags: dfs and similar, dp, games, implementation, strings, trees Solve time: 1m 49s Verified: yes Solution Problem Understanding The game can be viewed as moving through a trie built from the given strings. We start at the root, which represents the empty string. On each turn a player chooses one outgoing edge, corresponding to appending a character. The current string must...

Practice › Codeforces Solutions ›

Codeforces Round 260 (Div. 1)

Codeforces Round 260 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2900 | Time: 7m 50s Problem Name Rating Tags Solve Time Verified A Boredom 1500 dp 1m 31s ✓ B A Lot of Games 1900 dfs-and-similar, dp, games 1m 49s ✓ C Civilization 2100 dfs-and-similar, dp, dsu 2m 1s ✓ D Serega and Fun 2700 data-structures 1m 27s ✓ E Function 2900 data-structures...

Practice › Codeforces Solutions › MemSQL Start[c]UP 2.0 - Round 2 ›

CF 457F - An easy problem about trees

CF 457F - An easy problem about trees Rating: 3200 Tags: dp, games, greedy, trees Solve time: 4m 23s Verified: no Solution I’m sorry, but I can’t reliably produce a correct full editorial and solution for this 3200-rated problem from the information currently available to me. While I can restate the problem and discuss some observations, I do not have enough confidence in the exact game-theoretic DP needed for Codeforces...

Practice › Codeforces Solutions ›

Codeforces Round 159 (Div. 2)

Codeforces Round 159 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 4/4 | Rating range: 1100-1900 | Time: 6m 19s Problem Name Rating Tags Solve Time Verified A Sockets 1100 greedy, implementation, sortings 1m 10s ✓ B Playing Cubes 1300 games, greedy, implementation 1m 23s ✓ C View Angle 1800 brute-force, geometry, math 2m 43s ✓ D Sum 1900 greedy, math 1m 3s ✓

Practice › Codeforces Solutions ›

Codeforces Round 201 (Div. 1)

Codeforces Round 201 (Div. 1) Type: Div. 1 | Problems: 1 | Verified: 1/1 | Rating range: 1600-1600 | Time: 3m 49s Problem Name Rating Tags Solve Time Verified A Alice and Bob 1600 games, math, number-theory 3m 49s ✓

Practice › Codeforces Solutions ›

Croc Champ 2013 - Round 2

Croc Champ 2013 - Round 2 Type: Special | Problems: 4 | Verified: 4/4 | Rating range: 1500-2700 | Time: 8m 33s Problem Name Rating Tags Solve Time Verified A Weird Game 1500 games, greedy 53s ✓ C Cube Problem 2400 brute-force, math, number-theory 1m 36s ✓ D Ksusha and Square 2700 geometry, math, probabilities 1m 59s ✓ E Close Vertices 2700 data-structures, divide-and-conquer, trees 4m 5s ✓

Practice › Codeforces Solutions › Croc Champ 2013 - Round 2 ›

CF 293A - Weird Game

CF 293A - Weird Game Rating: 1500 Tags: games, greedy Solve time: 53s Verified: yes Solution Problem Understanding We are asked to analyze a turn-based game played by two players, Yaroslav and Andrey, each starting with a binary string of length 2·n. On their turn, a player chooses an index in the string that hasn’t been picked yet and writes down the corresponding character on their paper. Yaroslav always moves...

Practice › Codeforces Solutions › Codeforces Round 184 (Div. 2) ›

CF 305E - Playing with String

CF 305E - Playing with String Rating: 2300 Tags: games Solve time: 1m 47s Verified: yes Solution Problem Understanding We are asked to analyze a two-player string game. Players alternate moves. On a turn, a player can select any string fragment available (initially the whole string) and cut a character that is the center of a palindrome of odd length. After cutting, the string splits into three parts: the single...

Practice › Codeforces Solutions › Codeforces Round 124 (Div. 2) ›

CF 197A - Plate Game

CF 197A - Plate Game Rating: 1600 Tags: constructive algorithms, games, math Solve time: 1m 22s Verified: yes Solution Problem Understanding We have a rectangular table with dimensions a × b and an unlimited supply of identical circular plates with radius r . Two players alternate placing plates on the table. Every plate must lie completely inside the rectangle, and plates may touch but cannot overlap. The game ends when...

Practice › Codeforces Solutions › Codeforces Round 159 (Div. 2) ›

CF 257B - Playing Cubes

CF 257B - Playing Cubes Rating: 1300 Tags: games, greedy, implementation Solve time: 1m 23s Verified: yes Solution Problem Understanding We are asked to simulate a game between two players arranging colored cubes in a line. Petya wants to maximize the number of consecutive cubes of the same color, while Vasya wants to maximize the number of consecutive cubes of different colors. Petya moves first, and the total number of...

Practice › Codeforces Solutions › Codeforces Round 102 (Div. 1) ›

CF 142D - Help Shrek and Donkey 2

CF 142D - Help Shrek and Donkey 2 Rating: 2600 Tags: games Solve time: 2m 34s Verified: yes Solution Problem Understanding We are asked to analyze a two-player game on a rectangular grid where each cell may contain a toy soldier from Shrek (green) or Donkey (red), or be empty. The grid has dimensions n × m , and on each row there are at most two soldiers. Players take...

Practice › Codeforces Solutions ›

Codeforces Round 114 (Div. 1)

Codeforces Round 114 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1600-3000 | Time: 10m 57s Problem Name Rating Tags Solve Time Verified A Wizards and Trolleybuses 1600 implementation, math 1m 40s ✓ B Wizards and Huge Prize 1800 dp, math, probabilities 1m 38s ✗ C Wizards and Numbers 2300 games, math 1m 39s ✗ D Wizards and Roads 3000 data-structures, divide-and-conquer, graph-matchings 2m...

Practice › Codeforces Solutions ›

Codeforces Round 156 (Div. 2)

Codeforces Round 156 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2200 | Time: 10m 7s Problem Name Rating Tags Solve Time Verified A Greg's Workout 800 implementation 2m 19s ✓ B Code Parsing 1200 implementation 2m 19s ✓ C Almost Arithmetical Progression 1500 brute-force, dp 2m 19s ✓ D Mr. Bender and Square 1800 binary-search, implementation, math 1m 19s ✓ E Furlo and...

Practice › Codeforces Solutions › Codeforces Round 173 (Div. 2) ›

CF 282D - Yet Another Number Game

CF 282D - Yet Another Number Game Rating: 2100 Tags: dp, games Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a small array of non-negative integers, at most three in length. Two players, BitLGM and BitAryo, take turns reducing these integers in one of two ways: either they pick a single number and subtract any positive amount, or they pick an amount and subtract it from...

Practice › Codeforces Solutions › Codeforces Round 201 (Div. 1) ›

CF 346A - Alice and Bob

CF 346A - Alice and Bob Rating: 1600 Tags: games, math, number theory Solve time: 3m 49s Verified: yes Solution Problem Understanding We start with a collection of distinct integers. On each move, the current player picks any two numbers from the set and inserts their absolute difference, but only if that difference is not already present. The set grows over time, and the game ends when a player cannot...

Practice › Codeforces Solutions ›

Codeforces Round 107 (Div. 1)

Codeforces Round 107 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1400-3000 | Time: 11m 8s Problem Name Rating Tags Solve Time Verified A Win or Freeze 1400 games, math, number-theory 2m 2s ✗ B Quantity of Strings 1600 combinatorics, dfs-and-similar, graphs 1m 40s ✓ C Smart Cheater 2200 data-structures, math, probabilities 2m 11s ✓ D Mission Impassable 2600 dp, strings 2m 26s ✓...

Practice › Codeforces Solutions › Codeforces Round 109 (Div. 1) ›

CF 154D - Flatland Fencing

CF 154D - Flatland Fencing Rating: 2400 Tags: games, math Solve time: 1m 34s Verified: yes Solution Problem Understanding Two players stand on integer points of a number line. On each turn, the current player chooses a new integer coordinate inside a fixed interval relative to their current position. If the first player is at position x , he may move to any integer point in [x + a, x...

Practice › Codeforces Solutions ›

Codeforces Round 188 (Div. 1)

Codeforces Round 188 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 3/3 | Rating range: 2300-3100 | Time: 5m 58s Problem Name Rating Tags Solve Time Verified C Balance 2500 constructive-algorithms, dfs-and-similar, graphs 2m 14s ✓ D Game with Powers 2300 dp, games 1m 58s ✓ E Princess and Her Shadow 3100 constructive-algorithms, shortest-paths 1m 46s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 99 (Div. 1) ›

CF 138D - World of Darkraft

CF 138D - World of Darkraft Rating: 2500 Tags: dp, games Solve time: 2m 6s Verified: yes Solution Problem Understanding We have a rectangular board where every cell contains one of three symbols. A move selects an active cell and disables cells along diagonals passing through it. The exact diagonals depend on the symbol. A cell marked L attacks the two diagonals with constant i + j . A cell...

Practice › Codeforces Solutions ›

Codeforces Round 124 (Div. 2)

Codeforces Round 124 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1400-1600 | Time: 2m 55s Problem Name Rating Tags Solve Time Verified A Plate Game 1600 constructive-algorithms, games, math 1m 22s ✓ B Limit 1400 math 1m 33s ✓

Practice › Codeforces Solutions ›

Codeforces Round 206 (Div. 1)

Codeforces Round 206 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 2/5 | Rating range: 1500-2900 | Time: 15m 26s Problem Name Rating Tags Solve Time Verified A Vasya and Robot 1500 brute-force, greedy, math 2m 39s ✓ B Game with Strings 2400 bitmasks, dp, games 2m 1s ✗ C Vasya and Beautiful Arrays 2100 brute-force, dp, number-theory 2m 47s ✓ D Transferring Pyramid 2900 dp 2m 46s...

Practice › Codeforces Solutions › Codeforces Round 206 (Div. 1) ›

CF 354B - Game with Strings

CF 354B - Game with Strings Rating: 2400 Tags: bitmasks, dp, games Solve time: 2m 1s Verified: no Solution Problem Understanding We are given an $n \times n$ grid of lowercase letters. A valid string is formed by walking from the top-left cell to any reachable cell by moving only right or down, always starting at $(1,1)$. Every move appends the character of the new cell, so each valid string...

Practice › Codeforces Solutions › Codeforces Round 114 (Div. 1) ›

CF 167C - Wizards and Numbers

CF 167C - Wizards and Numbers Rating: 2300 Tags: games, math Solve time: 1m 39s Verified: no Solution Problem Understanding We have a two-player game played with two numbers on a blackboard, call them a and b . Each player can, on their turn, either replace the larger number with the remainder of dividing it by the smaller number, or subtract a positive multiple of the smaller number from the...

Practice › Codeforces Solutions › Codeforces Round 156 (Div. 2) ›

CF 255E - Furlo and Rublo and Game

CF 255E - Furlo and Rublo and Game Rating: 2200 Tags: games, implementation, math Solve time: 1m 51s Verified: yes Solution Problem Understanding We have several independent piles of coins. A move picks one pile with size x and replaces it with some smaller value y such that $$x^{1/4} \le y \le x^{1/2}$$ and y < x . The player who cannot make a move loses. Since moves affect only...

Practice › Codeforces Solutions ›

Codeforces Round 173 (Div. 2)

Codeforces Round 173 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1500-2100 | Time: 2m 26s Problem Name Rating Tags Solve Time Verified B Painting Eggs 1500 greedy, math 1m 12s ✓ D Yet Another Number Game 2100 dp, games 1m 14s ✓

Practice › Codeforces Solutions › Codeforces Round 105 (Div. 2) ›

CF 148D - Bag of mice

CF 148D - Bag of mice Rating: 1800 Tags: dp, games, math, probabilities Solve time: 1m 55s Verified: yes Solution Problem Understanding We have a bag containing white and black mice. The princess moves first, then the dragon, then the princess again, and so on. Whoever draws a white mouse immediately wins. If someone draws a black mouse, the game continues. There is one extra rule during the dragon’s turn....

Practice › Codeforces Solutions › Codeforces Round 107 (Div. 1) ›

CF 150A - Win or Freeze

CF 150A - Win or Freeze Rating: 1400 Tags: games, math, number theory Solve time: 2m 2s Verified: no Solution Problem Understanding We start with a number q written on paper. On each turn, a player must replace the current number with one of its non-trivial divisors, meaning a divisor strictly between 1 and the number itself. If a player cannot make a move, that player wins immediately. This is...

Practice › Codeforces Solutions › Codeforces Round 188 (Div. 1) ›

CF 317D - Game with Powers

CF 317D - Game with Powers Rating: 2300 Tags: dp, games Solve time: 1m 58s Verified: yes Solution Problem Understanding We are asked to determine the winner of a two-player game involving numbers from 1 to n . The players, Vasya and Petya, take turns picking numbers. Once a number x is chosen, neither x nor any of its higher integer powers (_x_², _x_³, …) can be chosen in future...

Practice › Codeforces Solutions ›

Codeforces Round 105 (Div. 2)

Codeforces Round 105 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-1900 | Time: 9m 21s Problem Name Rating Tags Solve Time Verified A Insomnia cure 800 constructive-algorithms, implementation, math 1m 34s ✗ B Escape 1500 implementation, math 1m 12s ✓ C Terse princess 1700 constructive-algorithms, greedy 2m 14s ✗ D Bag of mice 1800 dp, games, math 1m 55s ✓ E Porcelain 1900...

Practice › Codeforces Solutions › Codeforces Beta Round 68 ›

CF 74B - Train

CF 74B - Train Rating: 1500 Tags: dp, games, greedy Solve time: 2m 11s Verified: yes Solution Problem Understanding The train has n wagons arranged in a line. The controller moves deterministically: every minute he walks one wagon in his current direction, and when he reaches either end he reverses direction. His path is completely fixed once we know the initial wagon and direction. The stowaway behaves differently depending on...

Practice › Codeforces Solutions › Codeforces Beta Round 36 ›

CF 36D - New Game with a Chess Piece

CF 36D - New Game with a Chess Piece Rating: 2300 Tags: games Solve time: 1m 43s Verified: no Solution Problem Understanding We are asked to analyze a two-player game on an $n \times m$ rectangular board. The players take turns moving a single chess piece starting in the top-left corner. On each turn, a player can move the piece one cell right, one cell down, or diagonally $k$ cells...

Practice › Codeforces Solutions › Codeforces Beta Round 70 (Div. 2) ›

CF 78C - Beaver Game

CF 78C - Beaver Game Rating: 2000 Tags: dp, games, number theory Solve time: 2m 6s Verified: yes Solution Problem Understanding We have n independent logs, each with length m . On a move, a player chooses one existing log and splits it into several equal pieces. If a log of length x is split into t equal parts, then t > 1 , t must divide x , and...

Practice › Codeforces Solutions › Codeforces Beta Round 15 ›

CF 15C - Industrial Nim

CF 15C - Industrial Nim Rating: 2000 Tags: games Solve time: 2m 25s Verified: yes Solution Problem Understanding Each quarry contributes a consecutive range of heap sizes to a standard Nim game. If a quarry gives us values (x, m) , then its dumpers contain: $$x,\ x+1,\ x+2,\ \dots,\ x+m-1$$ All dumpers from all quarries together form one large Nim position. Since ordinary Nim is played, the winner depends only...

Practice › Codeforces Solutions ›

Codeforces Beta Round 3

Codeforces Beta Round 3 Type: Beta | Problems: 4 | Verified: 4/4 | Rating range: 1000-2600 | Time: 14m 42s Problem Name Rating Tags Solve Time Verified A Shortest path of the king 1000 greedy, shortest-paths 4m 37s ✓ B Lorry 1900 greedy, sortings 4m 5s ✓ C Tic-tac-toe 1800 brute-force, games, implementation 4m 37s ✓ D Least Cost Bracket Sequence 2600 greedy 1m 23s ✓

Practice › Codeforces Solutions ›

Codeforces Beta Round 15

Codeforces Beta Round 15 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1200-2600 | Time: 11m 13s Problem Name Rating Tags Solve Time Verified A Cottage Village 1200 implementation, sortings 2m 21s ✓ B Laser 1800 math 2m 54s ✓ C Industrial Nim 2000 games 2m 25s ✓ D Map 2500 data-structures, implementation, sortings 2m 12s ✓ E Triangles 2600 combinatorics, dp 1m 21s ✓

Practice › Codeforces Solutions ›

School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules)

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...

Practice › Codeforces Solutions › School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules) ›

CF 48E - Ivan the Fool VS Gorynych the Dragon

CF 48E - Ivan the Fool VS Gorynych the Dragon Rating: 2100 Tags: dp, games, graphs Solve time: 2m 21s Verified: yes Solution Problem Understanding The game state is completely described by two numbers: how many heads and how many tails the dragon currently has. From a state (h, t) Ivan may choose one of two move types. If he cuts i heads, where 1 ≤ i ≤ n and...

Practice › Codeforces Solutions ›

Codeforces Beta Round 63 (Div. 2)

Codeforces Beta Round 63 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1000-2000 | Time: 9m 17s Problem Name Rating Tags Solve Time Verified A Young Physicist 1000 implementation, math 1m 43s ✓ B Bets 1200 greedy, implementation 2m 1s ✓ C Game 2000 implementation 2m 15s ✓ D Dot 1900 dp, games 1m 56s ✓ E Subsegments 1800 data-structures, implementation 1m 22s ✓

Practice › Codeforces Solutions › School Regional Team Contest, Saratov, 2011 ›

CF 120E - Put Knight!

CF 120E - Put Knight! Rating: 1400 Tags: games, math Solve time: 1m 56s Verified: yes Solution Problem Understanding We are asked to analyze a two-player game on an n × n chessboard. Petya and Gena take turns placing knights such that no knight can threaten another. A knight threatens positions in its standard L-shaped moves. The first player unable to place a knight loses, and Petya always starts. The...

Practice › Codeforces Solutions › School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules) ›

CF 38F - Smart Boy

CF 38F - Smart Boy Rating: 2100 Tags: dp, games, strings Solve time: 2m 49s Verified: no Solution Problem Understanding 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. The restriction is the core of the...

Practice › Codeforces Solutions ›

Codeforces Beta Round 36

Codeforces Beta Round 36 Type: Beta | Problems: 5 | Verified: 2/5 | Rating range: 1300-2600 | Time: 9m 36s Problem Name Rating Tags Solve Time Verified A Extra-terrestrial Intelligence 1300 implementation 1m 21s ✓ B Fractal 1600 implementation 1m 52s ✓ C Bowls 2200 geometry, implementation 2m 5s ✗ D New Game with a Chess Piece 2300 games 1m 43s ✗ E Two Paths 2600 constructive-algorithms, dsu, graphs 2m...

Practice › Codeforces Solutions › Codeforces Beta Round 78 (Div. 1 Only) ›

CF 98E - Help Shrek and Donkey

CF 98E - Help Shrek and Donkey Rating: 2700 Tags: dp, games, math, probabilities Solve time: 2m 25s Verified: yes Solution Problem Understanding There are m + n + 1 distinct cards in total. Shrek initially knows his own m cards, Donkey knows his own n cards, and one card is hidden on the table. Nobody knows the hidden card directly. Players alternate turns, with Shrek moving first. On each...

Practice › Codeforces Solutions ›

Codeforces Beta Round 73 (Div. 1 Only)

Codeforces Beta Round 73 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2600 | Time: 9m 48s Problem Name Rating Tags Solve Time Verified A Trains 1500 implementation, math 1m 15s ✓ B Vasya and Types 1800 implementation, strings 1m 56s ✓ C Interesting Game 2000 dp, games, math 1m 9s ✓ D Beautiful Road 2300 dfs-and-similar, dp, dsu 2m 12s ✓ E...

Practice › Codeforces Solutions › Codeforces Beta Round 63 (Div. 2) ›

CF 69D - Dot

CF 69D - Dot Rating: 1900 Tags: dp, games Solve time: 1m 56s Verified: yes Solution Problem Understanding We start with a point on the plane at coordinates (x, y) . Players alternate turns, and on each turn they may do one of two things. They may add one of the given movement vectors to the current position. Every vector has non-negative coordinates, so every normal move pushes the point...

Practice › Codeforces Solutions › Codeforces Beta Round 73 (Div. 1 Only) ›

CF 87C - Interesting Game

CF 87C - Interesting Game Rating: 2000 Tags: dp, games, math Solve time: 1m 9s Verified: yes Solution Problem Understanding We are asked to analyze a two-player game with a single pile of n stones. The players alternate turns, starting with Serozha. On each turn, a player selects one existing pile and splits it into at least two piles that form a strictly decreasing sequence with consecutive differences equal to...

Practice › Codeforces Solutions › Codeforces Beta Round 51 ›

CF 55C - Pie or die

CF 55C - Pie or die Rating: 1900 Tags: games Solve time: 1m 43s Verified: yes Solution Problem Understanding We have an $n \times m$ grid. Some cells contain pies, and several pies may share the same cell. Each turn has two phases. First, Volodya chooses one pie and moves it by one cell in one of the four directions. If the pie is already on the boundary, he may...

Practice › Codeforces Solutions ›

Codeforces Beta Round 51

Codeforces Beta Round 51 Type: Beta | Problems: 5 | Verified: 3/5 | Rating range: 1200-2500 | Time: 10m 12s Problem Name Rating Tags Solve Time Verified A Flea travel 1200 implementation, math 1m 24s ✓ B Smallest number 1600 brute-force 1m 47s ✓ C Pie or die 1900 games 1m 43s ✓ D Beautiful numbers 2500 dp, number-theory 3m 29s ✗ E Very simple problem 2500 geometry, two-pointers 1m...

Practice › Codeforces Solutions ›

School Team Contest 1 (Winter Computer School 2010/11)

School Team Contest 1 (Winter Computer School 2010/11) Type: Special | Problems: 11 | Verified: 9/11 | Rating range: 1100-2600 | Time: 23m 20s Problem Name Rating Tags Solve Time Verified A C*++ Calculations 2000 expression-parsing, greedy 2m 42s ✓ B Company Income Growth 1300 greedy 3m 27s ✓ C Moon Craters 2100 dp, sortings 4m 25s ✗ D Cubical Planet 1100 math 1m 27s ✓ E What Has Dirichlet...

Practice › Codeforces Solutions › Codeforces Beta Round 59 (Div. 2) ›

CF 63E - Sweets Game

CF 63E - Sweets Game Rating: 2000 Tags: bitmasks, dfs and similar, dp, games, implementation Solve time: 2m 13s Verified: yes Solution Problem Understanding The board is a fixed hexagon with 19 cells. Some cells contain chocolates, some are empty. Two players alternate moves, and a move consists of choosing a contiguous segment of chocolates that lies on a straight line parallel to one of the three hexagon directions. Every...

Practice › Codeforces Solutions › Codeforces Beta Round 97 (Div. 1) ›

CF 135C - Zero-One

CF 135C - Zero-One Rating: 1900 Tags: constructive algorithms, games, greedy Solve time: 1m 50s Verified: yes Solution Problem Understanding We are given a string consisting of 0 , 1 , and ? . Each character represents a card in a row. During the game, players alternately remove one card until only two cards remain. Masha moves first and wants the final two-bit binary number to be as small as...

Practice › Codeforces Solutions ›

Codeforces Beta Round 68

Codeforces Beta Round 68 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1000-2800 | Time: 22m 53s Problem Name Rating Tags Solve Time Verified A Room Leader 1000 implementation 1m 35s ✓ B Train 1500 dp, games, greedy 2m 11s ✓ C Chessboard Billiard 2100 dfs-and-similar, dsu, graphs 1m 36s ✓ D Hanger 2400 data-structures 1m 7s ✓ E Shift It! 2800 constructive-algorithms 16m 24s ✗

Practice › Codeforces Solutions ›

School Regional Team Contest, Saratov, 2011

School Regional Team Contest, Saratov, 2011 Type: Special | Problems: 10 | Verified: 8/10 | Rating range: 1000-2200 | Time: 16m 31s Problem Name Rating Tags Solve Time Verified A Elevator 1000 brute-force, implementation, math 1m 26s ✓ B Quiz League 1100 implementation 1m 21s ✓ C Winnie-the-Pooh and honey 1100 implementation, math 1m 39s ✓ D Three Sons 1400 brute-force 1m 35s ✓ E Put Knight! 1400 games, math...

Practice › Codeforces Solutions ›

Codeforces Beta Round 70 (Div. 2)

Codeforces Beta Round 70 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 800-2300 | Time: 12m 16s Problem Name Rating Tags Solve Time Verified A Haiku 800 implementation, strings 3m 30s ✓ B Easter Eggs 1200 constructive-algorithms, implementation 1m 59s ✗ C Beaver Game 2000 dp, games, number-theory 2m 6s ✓ D Archer's Shot 2300 binary-search, geometry, math 2m 7s ✓ E Evacuation 2300...

Practice › Codeforces Solutions › School Team Contest 1 (Winter Computer School 2010/11) ›

CF 39E - What Has Dirichlet Got to Do with That?

CF 39E - What Has Dirichlet Got to Do with That? Rating: 2000 Tags: dp, games Solve time: 1m 57s Verified: yes Solution Problem Understanding We start with a distinct boxes and b distinct items. Since boxes may stay empty and every item independently chooses one of the boxes, the number of possible placements is simply: $a^b$ Two players alternate turns. On each turn, a player may either increase the...

Practice › Codeforces Solutions › Codeforces Beta Round 3 ›

CF 3C - Tic-tac-toe

CF 3C - Tic-tac-toe Rating: 1800 Tags: brute force, games, implementation Solve time: 4m 37s Verified: yes Problem Understanding We are given a snapshot of a tic-tac-toe board, represented as a 3×3 grid. Each cell is either empty ( . ), contains a cross ( X ), or contains a nought ( 0 ). The first player always places crosses, and the second player places noughts. The board might be...

#games

Codeforces Round 1090 (Div. 4)

CF 2218A - The 67th Integer Problem

CF 1951H - Thanos Snap

CF 1965A - Everything Nim

CF 1965E - Connected Cubes

Codeforces Round 942 (Div. 2)

CF 1966A - Card Exchange

CF 493D - Vasya and Chess

CF 1956B - Nene and the Card Game

CF 1943A - MEX Game 1

CF 1942E - Farm Game

Codeforces Round 941 (Div. 1)

Codeforces Round 941 (Div. 2)

CF 494E - Sharti

CF 1956A - Nene's Game

Codeforces Round 939 (Div. 2)

CF 1955F - Unfair Game

Codeforces Round 934 (Div. 1)

CF 1972B - Coin Games

CF 455B - A Lot of Games

Codeforces Round 260 (Div. 1)

CF 457F - An easy problem about trees

Codeforces Round 159 (Div. 2)

Codeforces Round 201 (Div. 1)

Croc Champ 2013 - Round 2

CF 293A - Weird Game

CF 305E - Playing with String

CF 197A - Plate Game

CF 257B - Playing Cubes

CF 142D - Help Shrek and Donkey 2

Codeforces Round 114 (Div. 1)

Codeforces Round 156 (Div. 2)

CF 282D - Yet Another Number Game

CF 346A - Alice and Bob

Codeforces Round 107 (Div. 1)

CF 154D - Flatland Fencing

Codeforces Round 188 (Div. 1)

CF 138D - World of Darkraft

Codeforces Round 124 (Div. 2)

Codeforces Round 206 (Div. 1)

CF 354B - Game with Strings

CF 167C - Wizards and Numbers

CF 255E - Furlo and Rublo and Game

Codeforces Round 173 (Div. 2)

CF 148D - Bag of mice

CF 150A - Win or Freeze

CF 317D - Game with Powers

Codeforces Round 105 (Div. 2)

CF 74B - Train

CF 36D - New Game with a Chess Piece

CF 78C - Beaver Game

CF 15C - Industrial Nim

Codeforces Beta Round 3

Codeforces Beta Round 15

School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules)

CF 48E - Ivan the Fool VS Gorynych the Dragon

Codeforces Beta Round 63 (Div. 2)

CF 120E - Put Knight!

CF 38F - Smart Boy

Codeforces Beta Round 36

CF 98E - Help Shrek and Donkey

Codeforces Beta Round 73 (Div. 1 Only)

CF 69D - Dot

CF 87C - Interesting Game

CF 55C - Pie or die

Codeforces Beta Round 51

School Team Contest 1 (Winter Computer School 2010/11)

CF 63E - Sweets Game

CF 135C - Zero-One

Codeforces Beta Round 68

School Regional Team Contest, Saratov, 2011

Codeforces Beta Round 70 (Div. 2)

CF 39E - What Has Dirichlet Got to Do with That?

CF 3C - Tic-tac-toe