Codeforces Round #573 (Div. 2)（ABCD）
Tokitsukaze and Enhancement CodeForces - 1191A
Tokitsukaze is one of the characters in the game “Kantai Collection”. In this game, every character has a common attribute — health points, shortened to HP.
In general, different values of HP are grouped into 4 categories:
Category A if HP is in the form of (4n+1), that is, when divided by 4, the remainder is 1;
Category B if HP is in the form of (4n+3), that is, when divided by 4, the remainder is 3;
Category C if HP is in the form of (4n+2), that is, when divided by 4, the remainder is 2;
Category D if HP is in the form of 4n, that is, when divided by 4, the remainder is 0.
The above-mentioned n can be any integer.
These 4 categories ordered from highest to lowest as A>B>C>D, which means category A is the highest and category D is the lowest.
While playing the game, players can increase the HP of the character. Now, Tokitsukaze wants you to increase her HP by at most 2 (that is, either by 0, 1 or 2). How much should she increase her HP so that it has the highest possible category?
Input
The only line contains a single integer x (30≤x≤100) — the value Tokitsukaze’s HP currently.
Output
Print an integer a (0≤a≤2) and an uppercase letter b (b∈{A,B,C,D}), representing that the best way is to increase her HP by a, and then the category becomes b.
Note that the output characters are case-sensitive.
Examples
Input
33
Output
0 A
Input
98
Output
1 B
Note
For the first example, the category of Tokitsukaze’s HP is already A, so you don’t need to enhance her ability.
For the second example:
If you don’t increase her HP, its value is still 98, which equals to (4×24+2), and its category is C.
If you increase her HP by 1, its value becomes 99, which equals to (4×24+3), and its category becomes B.
If you increase her HP by 2, its value becomes 100, which equals to (4×25), and its category becomes D.
Therefore, the best way is to increase her HP by 1 so that the category of her HP becomes B.
水題，盡量往等級高的地方弄就行了。
代碼如下：
Tokitsukaze and Mahjong CodeForces - 1191B
Tokitsukaze is playing a game derivated from Japanese mahjong. In this game, she has three tiles in her hand. Each tile she owns is a suited tile, which means it has a suit (manzu, pinzu or souzu) and a number (a digit ranged from 1 to 9). In this problem, we use one digit and one lowercase letter, which is the first character of the suit, to represent a suited tile. All possible suited tiles are represented as 1m, 2m, …, 9m, 1p, 2p, …, 9p, 1s, 2s, …, 9s.
In order to win the game, she must have at least one mentsu (described below) in her hand, so sometimes she should draw extra suited tiles. After drawing a tile, the number of her tiles increases by one. She can draw any tiles she wants, including those already in her hand.
Do you know the minimum number of extra suited tiles she needs to draw so that she can win?
Here are some useful definitions in this game:
A mentsu, also known as meld, is formed by a koutsu or a shuntsu;
A koutsu, also known as triplet, is made of three identical tiles, such as [1m, 1m, 1m], however, [1m, 1p, 1s] or [1m, 4m, 7m] is NOT a koutsu;
A shuntsu, also known as sequence, is made of three sequential numbered tiles in the same suit, such as [1m, 2m, 3m] and [5s, 7s, 6s], however, [9m, 1m, 2m] or [1m, 2p, 3s] is NOT a shuntsu.
Some examples:
[2m, 3p, 2s, 4m, 1s, 2s, 4s] — it contains no koutsu or shuntsu, so it includes no mentsu;
[4s, 3m, 3p, 4s, 5p, 4s, 5p] — it contains a koutsu, [4s, 4s, 4s], but no shuntsu, so it includes a mentsu;
[5p, 5s, 9m, 4p, 1s, 7p, 7m, 6p] — it contains no koutsu but a shuntsu, [5p, 4p, 6p] or [5p, 7p, 6p], so it includes a mentsu.
Note that the order of tiles is unnecessary and you can assume the number of each type of suited tiles she can draw is infinite.
Input
The only line contains three strings — the tiles in Tokitsukaze’s hand. For each string, the first character is a digit ranged from 1 to 9 and the second character is m, p or s.
Output
Print a single integer — the minimum number of extra suited tiles she needs to draw.
Examples
Input
1s 2s 3s
Output
0
Input
9m 9m 9m
Output
0
Input
3p 9m 2p
Output
1
Note
In the first example, Tokitsukaze already has a shuntsu.
In the second example, Tokitsukaze already has a koutsu.
In the third example, Tokitsukaze can get a shuntsu by drawing one suited tile — 1p or 4p. The resulting tiles will be [3p, 9m, 2p, 1p] or [3p, 9m, 2p, 4p].
跟打麻將差不多吧。要把最后結(jié)果弄成同花順，三個(gè)數(shù)相同，問應(yīng)該操作多少步。
代碼如下：
Tokitsukaze and Discard Items CodeForces - 1191C
Recently, Tokitsukaze found an interesting game. Tokitsukaze had n items at the beginning of this game. However, she thought there were too many items, so now she wants to discard m (1≤m≤n) special items of them.
These n items are marked with indices from 1 to n. In the beginning, the item with index i is placed on the i-th position. Items are divided into several pages orderly, such that each page contains exactly k positions and the last positions on the last page may be left empty.
Tokitsukaze would do the following operation: focus on the first special page that contains at least one special item, and at one time, Tokitsukaze would discard all special items on this page. After an item is discarded or moved, its old position would be empty, and then the item below it, if exists, would move up to this empty position. The movement may bring many items forward and even into previous pages, so Tokitsukaze would keep waiting until all the items stop moving, and then do the operation (i.e. check the special page and discard the special items) repeatedly until there is no item need to be discarded.
Consider the first example from the statement: n=10, m=4, k=5, p=[3,5,7,10]. The are two pages. Initially, the first page is special (since it is the first page containing a special item). So Tokitsukaze discards the special items with indices 3 and 5. After, the first page remains to be special. It contains [1,2,4,6,7], Tokitsukaze discards the special item with index 7. After, the second page is special (since it is the first page containing a special item). It contains [9,10], Tokitsukaze discards the special item with index 10.
Tokitsukaze wants to know the number of operations she would do in total.
Input
The first line contains three integers n, m and k (1≤n≤1018, 1≤m≤105, 1≤m,k≤n) — the number of items, the number of special items to be discarded and the number of positions in each page.
The second line contains m distinct integers p1,p2,…,pm (1≤p1<p2<…<pm≤n) — the indices of special items which should be discarded.
Output
Print a single integer — the number of operations that Tokitsukaze would do in total.
Examples
Input
10 4 5
3 5 7 10
Output
3
Input
13 4 5
7 8 9 10
Output
1
Note
For the first example:
In the first operation, Tokitsukaze would focus on the first page [1,2,3,4,5] and discard items with indices 3 and 5;
In the second operation, Tokitsukaze would focus on the first page [1,2,4,6,7] and discard item with index 7;
In the third operation, Tokitsukaze would focus on the second page [9,10] and discard item with index 10.
For the second example, Tokitsukaze would focus on the second page [6,7,8,9,10] and discard all special items at once.
一個(gè)序列，分成幾頁，每頁都有k個(gè)數(shù)，現(xiàn)在要移除一些數(shù)。每一次移除處在相同頁上的數(shù)字，問要操作幾次。
一個(gè)模擬，沒有什么技巧。記錄移動(dòng)的步數(shù)，處在相同頁上的數(shù)字，除以k之后是相等的。
代碼如下：
Tokitsukaze, CSL and Stone Game CodeForces - 1191D
Tokitsukaze and CSL are playing a little game of stones.
In the beginning, there are n piles of stones, the i-th pile of which has ai stones. The two players take turns making moves. Tokitsukaze moves first. On each turn the player chooses a nonempty pile and removes exactly one stone from the pile. A player loses if all of the piles are empty before his turn, or if after removing the stone, two piles (possibly empty) contain the same number of stones. Supposing that both players play optimally, who will win the game?
Consider an example: n=3 and sizes of piles are a1=2, a2=3, a3=0. It is impossible to choose the empty pile, so Tokitsukaze has two choices: the first and the second piles. If she chooses the first pile then the state will be [1,3,0] and it is a good move. But if she chooses the second pile then the state will be [2,2,0] and she immediately loses. So the only good move for her is to choose the first pile.
Supposing that both players always take their best moves and never make mistakes, who will win the game?
Note that even if there are two piles with the same number of stones at the beginning, Tokitsukaze may still be able to make a valid first move. It is only necessary that there are no two piles with the same number of stones after she moves.
Input
The first line contains a single integer n (1≤n≤105) — the number of piles.
The second line contains n integers a1,a2,…,an (0≤a1,a2,…,an≤109), which mean the i-th pile has ai stones.
Output
Print “sjfnb” (without quotes) if Tokitsukaze will win, or “cslnb” (without quotes) if CSL will win. Note the output characters are case-sensitive.
Examples
Input
1
0
Output
cslnb
Input
2
1 0
Output
cslnb
Input
2
2 2
Output
sjfnb
Input
3
2 3 1
Output
sjfnb
Note
In the first example, Tokitsukaze cannot take any stone, so CSL will win.
In the second example, Tokitsukaze can only take a stone from the first pile, and then, even though they have no stone, these two piles will have the same number of stones, which implies CSL will win.
In the third example, Tokitsukaze will win. Here is one of the optimal ways:
Firstly, Tokitsukaze can choose the first pile and take a stone from that pile.
Then, CSL can only choose the first pile, because if he chooses the second pile, he will lose immediately.
Finally, Tokitsukaze can choose the second pile, and then CSL will have no choice but to lose.
In the fourth example, they only have one good choice at any time, so Tokitsukaze can make the game lasting as long as possible and finally win.
一個(gè)博弈論。n堆石子，兩個(gè)人每次拿一個(gè)，如果拿完之后出現(xiàn)兩堆石子數(shù)相等或者沒有石子可以拿了，就輸了。問誰會(huì)贏。
先來分析先手必?cái)〉那闆r：
①有三堆或以上石子數(shù)目相同。
②有兩堆或以上石子數(shù)目為零。
③有兩堆石子數(shù)目相同，這樣的有多個(gè)。例如 3 3 4 4 7。
④有兩堆石子數(shù)目相同，而且還有一堆石子的數(shù)目比它少一。例如 4 5 5。
除去這些情況，就是倆個(gè)人公平競爭大的時(shí)候了。
先來分析一下必?cái)B(tài)，就是0，1，2，3，，，，n-1。誰遇到這樣的情況，誰肯定就輸了。那么每個(gè)人拿一個(gè)石頭，誰會(huì)遇到這種情況呢。分析（sum-n*(n-1)/2）的奇偶性就可以了。
代碼如下：
后兩道題沒出來，嚶嚶嚶
努力加油a啊，(o)/~
總結(jié)
以上是生活随笔為你收集整理的Codeforces Round #573 (Div. 2)（ABCD）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Codeforces Round #57
- 下一篇： Doom HDU - 5239（线段树+