AtCoder Grand Contest 020 (2/6)

maksyuki 发表于 比赛 分类，标签:
14 1月 2018
0

A Move and Win
A game is played on a strip consisting of N cells consecutively numbered from 1 to N.

Alice has her token on cell A. Borys has his token on a different cell B.

Players take turns, Alice moves first. The moving player must shift his or her token from its current cell X to the neighboring cell on the left, cell X−1, or on the right, cell X+1. Note that it's disallowed to move the token outside the strip or to the cell with the other player's token. In one turn, the token of the moving player must be shifted exactly once.

The player who can't make a move loses, and the other player wins.

Both players want to win. Who wins if they play optimally?

Constraints
2≤N≤100
1≤A<B≤N
All input values are integers.
Input
Input is given from Standard Input in the following format:

N A B
Output
Print Alice if Alice wins, Borys if Borys wins, and Draw if nobody wins.

Sample Input 1
5 2 4
Sample Output 1
Alice
Alice can move her token to cell 3. After that, Borys will be unable to move his token to cell 3, so he will have to move his token to cell 5. Then, Alice moves her token to cell 4. Borys can't make a move and loses.

Sample Input 2
2 1 2
Sample Output 2
Borys
Alice can't make the very first move and loses.

Sample Input 3
58 23 42
Sample Output 3
Borys

 

题目类型：简单博弈

算法分析：简单分析可知只要Alice和Borys之间的距离是偶数则Alice赢，否则Borys赢

 

B Ice Rink Game
An adult game master and N children are playing a game on an ice rink. The game consists of K rounds. In the i-th round, the game master announces:

Form groups consisting of Ai children each!
Then the children who are still in the game form as many groups of Ai children as possible. One child may belong to at most one group. Those who are left without a group leave the game. The others proceed to the next round. Note that it's possible that nobody leaves the game in some round.

In the end, after the K-th round, there are exactly two children left, and they are declared the winners.

You have heard the values of A1, A2, ..., AK. You don't know N, but you want to estimate it.

Find the smallest and the largest possible number of children in the game before the start, or determine that no valid values of N exist.

Constraints
1≤K≤105
2≤Ai≤109
All input values are integers.
Input
Input is given from Standard Input in the following format:

K
A1 A2 … AK
Output
Print two integers representing the smallest and the largest possible value of N, respectively, or a single integer −1 if the described situation is impossible.

Sample Input 1
4
3 4 3 2
Sample Output 1
6 8
For example, if the game starts with 6 children, then it proceeds as follows:

In the first round, 6 children form 2 groups of 3 children, and nobody leaves the game.
In the second round, 6 children form 1 group of 4 children, and 2 children leave the game.
In the third round, 4 children form 1 group of 3 children, and 1 child leaves the game.
In the fourth round, 3 children form 1 group of 2 children, and 1 child leaves the game.
The last 2 children are declared the winners.

Sample Input 2
5
3 4 100 3 2
Sample Output 2
-1
This situation is impossible. In particular, if the game starts with less than 100 children, everyone leaves after the third round.

Sample Input 3
10
2 2 2 2 2 2 2 2 2 2
Sample Output 3
2 3

 

题目类型：简单数学

算法分析：设Li和Ri为经过Ki次操作后剩余的最少和最多的人数(不一定能够整除Ai)，Xi和Yi为[Li,Ri]中满足整除Ai的最小和最大值，易知有Xi=ceil(Li/Ai)*Ai(也就是找到一个比Li稍微大一点的能够整除Ai的值)，Yi=floor(Ri/Ai)*Ai(找到一个比Ri稍微小一点能够整除Ai的值)，然后若Xi>Yi，即表示不存在合理的结果，否则Li-1=Xi，Ri-1=Yi+Ai-1，即给出满足条件的i-1轮的Xi-1和Yi-1的范围

 

Codeforces Educational Round 36(Rated for Div. 2) (3/7)

maksyuki 发表于 比赛 分类，标签:
14 1月 2018
0

A Garden
Luba thinks about watering her garden. The garden can be represented as a segment of length k. Luba has got n buckets, the i-th bucket allows her to water some continuous subsegment of garden of length exactly ai each hour. Luba can't water any parts of the garden that were already watered, also she can't water the ground outside the garden.

Luba has to choose one of the buckets in order to water the garden as fast as possible (as mentioned above, each hour she will water some continuous subsegment of length ai if she chooses the i-th bucket). Help her to determine the minimum number of hours she has to spend watering the garden. It is guaranteed that Luba can always choose a bucket so it is possible water the garden.

See the examples for better understanding.

Input
The first line of input contains two integer numbers n and k (1 ≤ n, k ≤ 100) — the number of buckets and the length of the garden, respectively.

The second line of input contains n integer numbers ai (1 ≤ ai ≤ 100) — the length of the segment that can be watered by the i-th bucket in one hour.

It is guaranteed that there is at least one bucket such that it is possible to water the garden in integer number of hours using only this bucket.

Output
Print one integer number — the minimum number of hours required to water the garden.

Examples
input
3 6
2 3 5
output
2
input
6 7
1 2 3 4 5 6
output
7
Note
In the first test the best option is to choose the bucket that allows to water the segment of length 3. We can't choose the bucket that allows to water the segment of length 5 because then we can't water the whole garden.

In the second test we can choose only the bucket that allows us to water the segment of length 1.

 

题目类型：简单枚举+贪心

算法分析：从最大容量的桶开始枚举，直到找到能够整除garden长度的容积

 

B Browser
Luba is surfing the Internet. She currently has n opened tabs in her browser, indexed from 1 to n from left to right. The mouse cursor is currently located at the pos-th tab. Luba needs to use the tabs with indices from l to r (inclusive) for her studies, and she wants to close all the tabs that don't belong to this segment as fast as possible.

Each second Luba can either try moving the cursor to the left or to the right (if the cursor is currently at the tab i, then she can move it to the tab max(i - 1, a) or to the tab min(i + 1, b)) or try closing all the tabs to the left or to the right of the cursor (if the cursor is currently at the tab i, she can close all the tabs with indices from segment [a, i - 1] or from segment [i + 1, b]). In the aforementioned expressions a and b denote the minimum and maximum index of an unclosed tab, respectively. For example, if there were 7 tabs initially and tabs 1, 2 and 7 are closed, then a = 3, b = 6.

What is the minimum number of seconds Luba has to spend in order to leave only the tabs with initial indices from l to r inclusive opened?

Input
The only line of input contains four integer numbers n, pos, l, r (1 ≤ n ≤ 100, 1 ≤ pos ≤ n, 1 ≤ l ≤ r ≤ n) — the number of the tabs, the cursor position and the segment which Luba needs to leave opened.

Output
Print one integer equal to the minimum number of seconds required to close all the tabs outside the segment [l, r].

Examples
input
6 3 2 4
output
5
input
6 3 1 3
output
1
input
5 2 1 5
output
0
Note
In the first test Luba can do the following operations: shift the mouse cursor to the tab 2, close all the tabs to the left of it, shift the mouse cursor to the tab 3, then to the tab 4, and then close all the tabs to the right of it.

In the second test she only needs to close all the tabs to the right of the current position of the cursor.

In the third test Luba doesn't need to do anything.

 

题目类型：简单构造+贪心

算法分析：如果pos不在[l,r]之间的话，最优的操作是每次执行左移或右移使得pos到达l或者是r位置，因为del操作可以一次性删除，在还没到达l或者r之前使用del操作不是最优的。然后问题转换成pos在[l,r]之间的情况，此时若l和1，r和n之间还有tab则分类讨论，没有tab则不需要向给定方向移动+del，注意若两边都有tab，则需先向距离边界l，r小的移动

 

C Permute Digits
You are given two positive integer numbers a and b. Permute (change order) of the digits of a to construct maximal number not exceeding b. No number in input and/or output can start with the digit 0.

It is allowed to leave a as it is.

Input
The first line contains integer a (1 ≤ a ≤ 1018). The second line contains integer b (1 ≤ b ≤ 1018). Numbers don't have leading zeroes. It is guaranteed that answer exists.

Output
Print the maximum possible number that is a permutation of digits of a and is not greater than b. The answer can't have any leading zeroes. It is guaranteed that the answer exists.

The number in the output should have exactly the same length as number a. It should be a permutation of digits of a.

Examples
input
123
222
output
213
input
3921
10000
output
9321
input
4940
5000
output
4940

 

题目类型：数位构造+贪心

算法分析：若a位数小于b位数则a直接从高位开始贪心地放最大的数字。若a和b的位数相同，则需判断a每次从高位放置尽可能大的数字时是否能够构造出a。可以使用dfs递减搜索每一位并维护一个tag，若tag为false则表示a的前面高位中已经有小于对应b位的情况，此时放置数字时可以不用考虑b对应位的大小了，否则需要考虑