AtCoder Grand Contest 020 (2/6)

maksyuki 发表于比赛分类，标签: 比赛-atcoder

14 1月 2018

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赢

/**************************************************
filename       :A.cpp
author         :maksyuki
created time   :2018/1/14 19:46:35
last modified  :2018/1/14 20:06:53
file location  :C:\Users\abcd\Desktop\atcoder
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int n, a, b;
    while(cin >> n >> a >> b) {
        if(abs(a - b) % 2 == 0) puts("Alice");
        else puts("Borys");
    }
    return 0;
}

/**************************************************

filename :A.cpp

author :maksyuki

created time :2018/1/14 19:46:35

last modified :2018/1/14 20:06:53

file location :C:\Users\abcd\Desktop\atcoder

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int n, a, b;

while(cin >> n >> a >> b) {

if(abs(a - b) % 2 == 0) puts("Alice");

else puts("Borys");

}

return 0;

}

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的范围

/**************************************************
filename       :B.cpp
author         :maksyuki
created time   :2018/1/14 20:06:54
last modified  :2018/1/16 12:13:31
file location  :C:\Users\abcd\Desktop\atcoder
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

LL aa[maxn];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int n;
    while(cin >> n) {
        for(int i = 1; i <= n; i++) cin >> aa[i];
        
        LL Li = 2, Ri = 2;
        bool ok = true; 
        for(int i = n; i >= 1; i--) {
            if(Li % aa[i]) Li += aa[i] - (Li % aa[i]);

            Ri -= Ri % aa[i];
            if(Li > Ri) {
                ok = false;
                break;
            }
            Ri += aa[i] - 1;
        }

        if(!ok) puts("-1");
        else cout << Li << " " << Ri << endl;
    }
    return 0;
}