Codeforces Round #483 (Div. 2)

A. Game

time limit per test：2 seconds
memory limit per test：256 megabytes

Two players play a game.

Initially there are nn integers a1,a2,…,an written on the board. Each turn a player selects one number and erases it from the board. This continues until there is only one number left on the board, i. e. n−1 turns are made. The first player makes the first move, then players alternate turns.

The first player wants to minimize the last number that would be left on the board, while the second player wants to maximize it.

You want to know what number will be left on the board after n−1 turns if both players make optimal moves.

Input

The first line contains one integer nn (1≤n≤1000) — the number of numbers on the board.

The second line contains nn integers a1,a2,…,an ($1≤a_i≤10^6$).

Output

Print one number that will be left on the board.

Examples

input

3
2 1 3

output

input

3
2 2 2

output

Note

In the first sample, the first player erases 3 and the second erases 1. 2 is left on the board.

In the second sample, 2 is left on the board regardless of the actions of the players.

链接

http://codeforces.com/contest/984/problem/A

题意

给定n个数字，先去掉一个最大值，然后去掉最小值，n-1个回合后剩下一个数，问最后留下的最小的数。

题解

排序后a[(n-1)/2]。

代码

Accepted
31 ms
3400 KB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int a[maxn];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    sort(a, a + n);
    printf("%d\n", a[(n-1)/2]);
    return 0;
}

B. Minesweeper

time limit per test：1 second
memory limit per test：256 megabytes

One day Alex decided to remember childhood when computers were not too powerful and lots of people played only default games. Alex enjoyed playing Minesweeper that time. He imagined that he saved world from bombs planted by terrorists, but he rarely won.

Alex has grown up since then, so he easily wins the most difficult levels. This quickly bored him, and he thought: what if the computer gave him invalid fields in the childhood and Alex could not win because of it?

He needs your help to check it.

A Minesweeper field is a rectangle n×m, where each cell is either empty, or contains a digit from 1 to 8, or a bomb. The field is valid if for each cell:

if there is a digit k in the cell, then exactly k neighboring cells have bombs.
if the cell is empty, then all neighboring cells have no bombs.

Two cells are neighbors if they have a common side or a corner (i. e. a cell has at most 8 neighboring cells).

Input

The first line contains two integers nn and mm (1≤n,m≤100) — the sizes of the field.

The next nn lines contain the description of the field. Each line contains mm characters, each of them is "." (if this cell is empty), "*" (if there is bomb in this cell), or a digit from 1 to 8, inclusive.

Output

Print "YES", if the field is valid and "NO" otherwise.

You can choose the case (lower or upper) for each letter arbitrarily.

Examples

input

output

YES

input

2 4
*.*.
1211

output

NO

Note

In the second example the answer is "NO" because, if the positions of the bombs are preserved, the first line of the field should be *2*1.

You can read more about Minesweeper in Wikipedia's article.

链接

http://codeforces.com/contest/984/problem/B

题意

扫雷游戏，问给定的棋局是否符合游戏规则。

题解

n和m的范围都只有100，暴搜统计一下每个非炸弹的点周围八个方向的炸弹数量，和给定的相比看是否相同。

代码

Accepted
31 ms
0 KB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
char s[maxn][maxn];
int dir[8][2] = {{-1, 0}, {-1, -1}, {-1, 1}, {1, 0}, {1, -1}, {1, 1}, {0, 1}, {0, -1}};
int n, m;

bool check()
{
    int sum;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            sum = 0;
            if (s[i][j] != '*')
            {
                for (int k = 0; k < 8; ++k)
                {
                    int ii = dir[k][0] + i, jj = dir[k][1] + j;
                    if (ii < 0 || ii >= n || jj < 0 || jj >= m)
                        continue;
                    if (s[ii][jj] == '*')
                        sum++;
                }
                if (s[i][j] == '.')
                {
                    if (sum != 0)
                        return false;
                }
                else
                {
                    if (sum != (s[i][j] - '0'))
                        return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%s", s[i]);
    if (check())
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

C. Finite or not?

time limit per test：1 second
memory limit per test：256 megabytes

You are given several queries. Each query consists of three integers p, q and b. You need to answer whether the result of p/q in notation with base b is a finite fraction.

A fraction in notation with base b is finite if it contains finite number of numerals after the decimal point. It is also possible that a fraction has zero numerals after the decimal point.

Input

The first line contains a single integer n ($1≤n≤10^5$) — the number of queries.

Next n lines contain queries, one per line. Each line contains three integers p, q, and b ($0≤p≤10^{18}, \ 1≤q≤10^{18}, \ 2≤b≤10^{18}$). All numbers are given in notation with base 10.

Output

For each question, in a separate line, print Finite if the fraction is finite and Infinite otherwise.

Examples

input

2
6 12 10
4 3 10

output

Finite
Infinite

Input

output

Finite
Finite
Finite
Infinite

Note

$6/12=1/2=0,5_{10}$

$4/3=1,(3)_{10} $

$9/36=1/4=0,01_{2}$

$4/12=1/3=0,1_3$

链接

http://codeforces.com/contest/984/problem/C

题意

给定三个数p, q, b，问分数p/q的结果在b进制下是否是有限的。

题解

利用gcd，先把p/q化简，然后求gcd(q, b)，q /= gcd(q, b)，看最后q能否化为1。

注意为了防止超时，b每次变为它们的最大公约数，具体实现参见代码。

代码

Accepted
327 ms
0 KB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b)
{
    ll c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main()
{
    int n;
    ll a, b, c, tmp;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%lld%lld%lld", &a, &b, &c);
        tmp= gcd(a, b);
        a = a / tmp;
        b = b / tmp;
        tmp = gcd(b, c);
        while (tmp != 1)
        {
            b = b / tmp;
            c = tmp; // 没有这个的话就会超时，c需要进行压缩
            tmp = gcd(b, c);
        }
        if (b == 1)
            printf("Finite\n");
        else
            printf("Infinite\n");
    }
    return 0;
}

在队友的指导下完成了C题，目前确实只有div2AB水平。

The end.
2018-05-18 星期五