| Problem description | | Progress |
|
Темы:
Dynamic Table Programming
Simple games
There is a pawn in the lower left cell of the NxN chessboard. Two players take turns moving it, and each player can move it one space up or one space to the right. The numbers a1, a2, …, aN are written on the diagonal of the board. When the pawn hits the diagonal, the game ends and the payoff of the first player is equal to the value of the number written in the square with the stopped pawn. Write a program to determine the guaranteed payoff of the first player.
Input
The first line contains the number N (1 ≤ N ≤ 100). The second line contains natural numbers a1, a2, …, aN (1 ≤ ai ≤100).
Output
Print one number – first player wins.
|
Enter |
Output |
|
8
3 1 4 1 5 9 2 6
|
5 |
| |
![]()
|
|
Темы:
Simple games
At the initial moment of time, the Snark is located at a point of a straight line with an integer non-negative coordinate X. During the move, he can be at any point with an integer Y coordinate, provided that |X-Y| <= S. Also, the Snark doesn't like buns, so he'll never jump into a cage with one of those nasty things in it. The baker doesn't want the Snark to get home. After each move of the Snark, the Baker can place the bun at any point on the line, provided that it is not the origin (Snark's home) and there is no Snark in that cell. Determine if the Baker can stop the Snark from getting home. Initially, some cells contain buns.
Input
The first line contains integers 0 <= X < 10000, 0 < S <= 100 and 0 <= N < max(X-1, 0) - the number of buns that already lie on the line. Next come N different numbers 0 < bi < X - coordinates of the points where the muck lies.
Output
Print "YES" if the Baker can realize his dirty plans, "NO" - if the Snark can jump home with any actions of the enemy.
|
Enter |
Output |
|
1 1 0
|
NO |
|
|
YES |
| |
![]()
|
|
Темы:
Simple games
Recall the contents of the first series. Two people play this game: in front of them is an NxM chocolate bar. During a turn, you can break the existing piece of chocolate along one of the sides into 2 "non-empty" ones.
However, you can't break pieces no larger than 1k (pieces can be rotated; we consider one piece "at most" another if it is equal to it or part of it). Thus, it is impossible to break pieces of size 11, 12, , 1k, but other pieces can be broken.
Now the pieces that cannot be broken can be eaten (no more than one at a time).
In one move, you can either break a piece of a suitable size, or eat it.
The one who cannot make a move loses. Determine who will be the winner in the game if the initial dimensions of the chocolate are known.
Input
Enter integers 0 < N, M, K <= 100.
Output
Print 1 or 2 - the number of the player who will win if the game is correct.
|
Enter |
Output |
|
1 1 1
|
1 |
|
1 1 100
|
1 |
| |
![]()
|
|
Темы:
Simple games
Petya received a gold medal at IOI, for which he received a thank you from the government in the form of a chocolate bar. At the moment, there are N types of chocolates, which are produced by the state chocolate factory. Each chocolate bar has a value. In addition, each species, except for the Yulka chocolate bar, has a progenitor species. It is known that only a chocolate bar that was released chronologically earlier can be the progenitor. Historically, the very first species is "Yulka". The official and Petya choose a chocolate bar for him as a gift. At the same time, the goal of the first is to save money, the second is to get as expensive a chocolate bar as possible. The choice begins with "Yulka". Petya either takes the current chocolate bar or changes his choice to a descendant chocolate bar (if possible). It seems to the official that the types released later are worse and cheaper, so he changes his choice to a descendant chocolate bar (if possible), or buys Petya a chocolate bar (if there are no descendants). They walk in turn, Petya is the first. Determine what price Petya can claim for a chocolate bar.
Input
First enter the number 0 < N <= 200000 - number of species. "Yulka" has number 1. Next come N lines with pairs of numbers 0 <= Pi <= N - the number of the ancestor variety > 0) and 0 < Ci <= 1000000000 - the cost of the i-th grade.
Output
Print the cost of a chocolate that Petya can guarantee himself if he does the right thing.
|
Enter |
Output |
|
8
04
5 3
1 2
5 1
15
48
36
37
|
6 |
| |
![]()
|
|
Темы:
Simple games
Two people are playing a game. There are several piles of matches. In one move, it is allowed to take any non-zero number of matches from any pile, whoever cannot make a move loses. Determine who wins when played correctly.
Input
The first line of the input file contains a natural number N — number of heaps. The second line contains N integers — the number of matches in piles. All numbers in the input file do not exceed 100000.
Output
Print "1" if the first player wins or "2" if the second player wins.
|
Enter |
Output |
1
10 |
1 |
2
1 1
|
2 |
| |
![]()
|
|
Темы:
Simple games
Two people are playing a game. There are several piles of matches. In one move, it is allowed to take any non-zero number of matches from any pile, whoever cannot make a move loses. Determine who wins when played correctly.
Input
The first line of the input file contains a natural number N — number of heaps. The second line contains N integers — the number of matches in piles. All numbers in the input file do not exceed 100000.
Output
Print "1" if the first player wins or "2" if the second player wins. If the first player wins, in the second line print the number K — the total number of winning moves. In the following K lines print information about the winning moves — pairs of numbers listed in ascending order of the first coordinate, and if equal, in ascending order of the second coordinate. In each such pair, the first number should indicate the number of the pile, and the second — the number of matches to take from this pile.
|
Enter |
Output |
1
10 |
1
1
1 10
|
2
1 1
|
2 |
| |
![]()
|
|
Темы:
Dynamic Programming: One Parameter
Simple games
There are N stones on the table. During a move a player can take:
- 1 or 2 stones if N is divisible by 3;
- 1 or 3 if N when divided by 3 gives remainder one;
- 1, 2 or 3 if N when divided by 3 leaves a remainder of two.
Each move can be made if there are enough stones. The one who cannot make a move loses.
Input: Enter an integer \(0 < N <= 100\).
Output: print 1 or 2 – the number of the player who will win if played correctly.
Examples
| # |
Input |
Output |
| 1 |
1 |
1 |
| 2 |
3 |
2 |
| |
![]()
|
|
Темы:
Simple games
When winter came and there was little to do in Prostokvashino, Sharik and Matroskin spent all their days playing board games. But they quickly got tired of chess, checkers, crosses and dominoes, and they had no other games. So they came up with a new game.
They write out 100 numbers on the stove with charcoal. Then, in turn, each of them selects a number from the right or left edge, adds it to their sum, and erases the number. Starts the game Matroskin. He wins if he can collect an amount no less than Sharik. Based on the given numbers, determine who will win in the optimal game.
Input
A single line contains 100 space-separated numbers ai (1≤ai≤1000)
Imprint
In response, print Matroskin if Matroskin wins, otherwise print Sharik. If Matroskin wins, then on the next line print Matroskin's optimal first move: if he must take the leftmost number, then print "left", if he must take the rightmost number — print "right". If it doesn't matter to Matroskin which number to take, print any of the words «left» and «right».
Examples
| # |
Input |
Output |
| 1 |
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
| Matroskin
right |
| |
![]()
|
|
Темы:
Simple games
Vasya and Petya are playing the following game. They take a deck of 36 cards. Each card has a number from 1 to 9 written on it and each card is painted in one of 4 colors so that there are exactly 9 cards of each color, and they are numbered from 1 to 9. The cards are shuffled and players are dealt several (no more than 18) cards.
Then the players take turns making moves. In one move, a player can put one or several cards consecutively on the table according to the following rules. A card with the number 5 of any color can be laid out on the table without additional conditions. A card with a different number can be laid out only if a card of the same color has already been laid out on the table, on which a number is written 1 more or 1 less than this one, or a card with the same number, but of a different color (it does not matter whether it was this card was placed by you or your opponent, and whether it was placed on or before the previous turn). If a player cannot lay out a single card, he skips a turn.
Write a program that, based on information about which cards are already on the table and which ones the player has, will determine the maximum number of cards that this player can lay out on a given move.
Input
The input file contains first the number K — the number of cards already laid out on the table. Next comes K pairs of numbers describing these cards. Then the number N — the number of cards in the hand of the player who must now make a move. Next, there are N pairs of numbers describing these cards.
Each card is described by two numbers — color number (from 1 to 4) and the number that is written on the card (from 1 to 9).
Limits: 0≤K≤35, 1≤N≤36, N+K≤36, all cards are different.
Imprint
In the output file print a single number — the maximum number of cards that can be played on a given turn.
Examples
| # |
Input |
Output |
Comments |
| 1 |
2
15
14
3
1 3
16
28 |
2 |
These are cards 1 3 (because there are 1 4 on the table) and 1 6 (because there are 1 5 on the table) |
| 2 |
0
4
28
15
36
16 |
3 |
In the first move, we can play 1 5, after that we have the right to play 1 6, after which we play 3 6 |
| 3 |
3
14
15
16
2
28
29 |
0 |
Can't post any cards |
| |
![]()
|
|
Темы:
Simple games
Case Study
Antoninus, Balbinus and Caesar play the game "Cards for three", the algorithm of which is as follows:
- first, each of the three players has a deck consisting of a certain number of cards. Each card has the letter a, b or c written on it. The order of cards in decks cannot be changed;
- The players take turns. Antonin goes first;
- if there is at least one card in the current player's deck, he must discard the top card in the deck;
- The next turn goes to the player whose name begins with the letter on the discarded card (a - Antoninus, b - Balbinus, c - Caesar );
- if the current player's deck is empty, the game ends and the current player wins the game.
You are given the starting player decks (Sa, Sb, Sc). The state of Antonin's deck is written in the line Sa, where i-th (\(1<=i<=len(S_a)\ )) character is the letter in the i-th card in the deck. The Balbin string (Sb) and the Caesar string (Sс) are described in the same way.
Determine the winner of the game.
Input
The input is three non-zero strings Sa, Sb and Sc, each on a new line. The length of each line is no more than 100 characters. Each line consists only of the letters a, b, or c.
Imprint
If Antonin won. then print the letter A, if Balbin - the letter B, if Caesar - the letter C.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
aca
accc
ca
|
A
|
The game will evolve as follows:
Antoninus discards the top card of his deck, a. Antonin makes his next move.
Antoninus discards the top card of his deck, c. Caesar is next.
Caesar discards the top card of his deck, c. Caesar is next.
Caesar discards the top card of his deck: a. Antonin makes his next move.
Antoninus discards the top card of his deck: a. Antonin makes his next move.
Antonin's deck is empty. The game ends and Antonin wins the game. |
| 2 |
abcb
aacb
bcc
|
C
|
|
| |
![]()
|
|
Темы:
Games and winning strategies
Simple games
Tree Data Structures
Error
| |
![]()
|
|
Темы:
Simple games
Two players, Petya and Vanya, play the following game. There is a string s that is 3 or more characters long. No two adjacent characters in s are equal. The players take turns. Peter goes first. In one move, you need to remove one of the characters from the string s, except for the extreme ones (the first and last). A symbol cannot be removed if the removal of the symbol would result in two adjacent identical symbols appearing in the line. A player who cannot complete the operation loses the game. Determine which player will win if they play optimally.
Input
The input is s (\(3 <= len(s) <= 10^5\)). The string consists only of lowercase English letters (a-z). No two adjacent characters in s are equal.
Imprint
If Petya wins, print First. If Vanya wins, print Second.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
aba
|
Second
|
Peter cannot perform the operation because deleting b, which is the only character that can be deleted, will cause s to become aa, two identical characters will be adjacent. |
| 2 |
abc
|
First
|
When Petya removes b from s, the string becomes ac and Vanya will not be able to perform the operation, because in s has no other characters except the outermost ones. |
| 3 |
abcab
|
First
|
|
| |
![]()
|
|
Темы:
Computer science
Simple games
Alice and Captain Buran play poker with one card. Single Card Poker is a game for two players with playing cards. Each card in this game shows an integer from 1 to 13 inclusive. The strength of a card is determined by the number written on it, as follows:
Weak 2 <3 <4 <5 <6 <7 <8 <9 <10 <11 <12 <13 <1 Strong< /strong>
One card poker is played like this:
- Each player draws one card from the deck.
- The selected card becomes the player's hand.
- Players open their hands to each other.
- The player with the stronger card wins the game.
- If their cards are equally strong, the game ends in a draw.
You watch Alice and Captain Buran play a game and you can see their hands. The number written on Alice's card is A and the number written on Captain Buran's card is B.
Write a program to determine the outcome of a game.
| |
![]()
|