CADDi 2018

C - Product and GCD

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 個の 1 以上の整数 a_1, a_2, ..., a_N があります． a_1, a_2, ..., a_N の値はわかりませんが，a_1 \times a_2 \times ... \times a_N = P がわかっています．

a_1, a_2, ..., a_N の最大公約数として考えられるもののうち，最も大きいものを求めてください．

制約

1 \leq N \leq 10^{12}
1 \leq P \leq 10^{12}

入力

入力は以下の形式で標準入力から与えられる．

N P

出力

答えを出力せよ．

入力例 1

3 24

出力例 1

例えば a_1=2, a_2=6, a_3=2 の場合，最大公約数は 2 となります．

入力例 2

5 1

出力例 2

a_i は正の整数なので，a_1 = a_2 = a_3 = a_4 = a_5 = 1 以外にはありえません．

入力例 3

1 111

出力例 3

入力例 4

4 972439611840

出力例 4

Score : 300 points

Problem Statement

There are N integers a_1, a_2, ..., a_N not less than 1. The values of a_1, a_2, ..., a_N are not known, but it is known that a_1 \times a_2 \times ... \times a_N = P.

Find the maximum possible greatest common divisor of a_1, a_2, ..., a_N.

Constraints

1 \leq N \leq 10^{12}
1 \leq P \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N P

Output

Print the answer.

Sample Input 1

3 24

Sample Output 1

The greatest common divisor would be 2 when, for example, a_1=2, a_2=6 and a_3=2.

Sample Input 2

5 1

Sample Output 2

As a_i are positive integers, the only possible case is a_1 = a_2 = a_3 = a_4 = a_5 = 1.

Sample Input 3

1 111

Sample Output 3

Sample Input 4

4 972439611840

Sample Output 4

D - Harlequin

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

一本のりんごの木があり、N 色のりんごが実っています。これらのりんごの N 種類の色には 1 から N までの番号が振られており、i 番の色のりんごは a_i 個あります。

あなたとダックスフンドのルンルンは、以下の行動を交互に行います (あなたから始めます)。

木から 1 個以上のりんごを選んで食べる。ただし、一度に選ぶりんごは全て異なる色でなければならない。

木から最後のりんごを食べた者を勝者とします。あなたとルンルンがともに最善を尽くすとき、どちらが勝つでしょうか？

制約

1 ≤ N ≤ 10^5
1 ≤ a_i ≤ 10^9
入力中の値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1
a_2
:
a_N

出力

あなたが勝つなら first、ルンルンが勝つなら second と出力せよ。

入力例 1

2
1
2

出力例 1

first

1 番の色を赤、2 番の色を青とします。この例では、木には赤いりんご 1 個と青いりんご 2 個が実っています。

あなたは最初の手番で赤いりんごを食べるべきです。すると、ルンルンは青いりんごのうち片方を食べるほかなく、次の手番であなたがもう片方を食べて勝つことができます。

なお、あなたは最初の手番で両方の色のりんごを 1 個ずつ食べることもできます (勝ちには繋がりませんが)。

入力例 2

出力例 2

second

Score : 500 points

Problem Statement

There is an apple tree that bears apples of N colors. The N colors of these apples are numbered 1 to N, and there are a_i apples of Color i.

You and Lunlun the dachshund alternately perform the following operation (starting from you):

Choose one or more apples from the tree and eat them. Here, the apples chosen at the same time must all have different colors.

The one who eats the last apple from the tree will be declared winner. If both you and Lunlun play optimally, which will win?

Constraints

1 \leq N \leq 10^5
1 \leq a_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1
a_2
:
a_N

Output

If you will win, print first; if Lunlun will win, print second.

Sample Input 1

2
1
2

Sample Output 1

first

Let Color 1 be red, and Color 2 be blue. In this case, the tree bears one red apple and two blue apples.

You should eat the red apple in your first turn. Lunlun is then forced to eat one of the blue apples, and you can win by eating the other in your next turn.

Note that you are also allowed to eat two apples in your first turn, one red and one blue (not a winning move, though).

Sample Input 2

Sample Output 2

second

E - Negative Doubling

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

N 個の正の整数 A_1, A_2, ..., A_N があります．高橋君は，これらの整数に対して，次の操作を好きな回数行うことができます：

1 \leq i \leq N を選び，A_i の値を -2 倍にする．

マイナス 2 倍であることに注意してください．

高橋君は，A_1 \leq A_2 \leq ... \leq A_N が成り立つようにしたいです．このために必要な操作の回数の最小値を求めてください．ただし，不可能な場合は -1 を出力してください．

制約

1 \leq N \leq 200000
1 \leq A_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 ... A_N

出力

答えを出力せよ．

入力例 1

4
3 1 4 1

出力例 1

例えば，次のようにすればよいです．

i=4 を選び，A_4 の値を -2 倍にする．A_1, A_2, A_3, A_4 はそれぞれ 3, 1, 4, -2 になる．
i=1 を選び，A_1 の値を -2 倍にする．A_1, A_2, A_3, A_4 はそれぞれ -6, 1, 4, -2 になる．
i=4 を選び，A_4 の値を -2 倍にする．A_1, A_2, A_3, A_4 はそれぞれ -6, 1, 4, 4 になる．

入力例 2

5
1 2 3 4 5

出力例 2

操作を一切せずとも A_1 \leq A_2 \leq ... \leq A_N が成り立っています．

入力例 3

8
657312726 129662684 181537270 324043958 468214806 916875077 825989291 319670097

出力例 3

Score : 800 points

Problem Statement

There are N positive integers A_1, A_2, ..., A_N. Takahashi can perform the following operation on these integers any number of times:

Choose 1 \leq i \leq N and multiply the value of A_i by -2.

Notice that he multiplies it by minus two.

He would like to make A_1 \leq A_2 \leq ... \leq A_N holds. Find the minimum number of operations required. If it is impossible, print -1.

Constraints

1 \leq N \leq 200000
1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the answer.

Sample Input 1

4
3 1 4 1

Sample Output 1

One possible solution is:

Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now 3, 1, 4, -2.
Choose i=1 and multiply the value of A_1 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, -2.
Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, 4.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

A_1 \leq A_2 \leq ... \leq A_N holds before any operation is performed.

Sample Input 3

8
657312726 129662684 181537270 324043958 468214806 916875077 825989291 319670097

Sample Output 3

F - Square

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

高橋君は、N 行 N 列のマス目を持っています。マス目の上から i 番目、左から j 番目のマスは (i,j) で表されます。特に、マス目の左上のマスは (1,1) であり、右下のマスは (N,N) です。

高橋君の持っているマス目のうち M 個のマスには、0 または 1 の整数が書き込まれています。整数が書き込まれたマスのうち i 番目のマスの情報は 3 つの整数 a_i,b_i,c_i で表され、マス (a_i,b_i) に整数 c_i が書き込まれていることを表します。

高橋君は、以下の条件を満たすように残りのマスに 0 または 1 の整数を書き込むことにしました。書き込み方としてありうるものの個数を 998244353 で割ったあまりを求めてください。

任意の 1\leq i < j\leq N に対し、(i,i) を左上のマスとし (j,j) を右下のマスとするような正方形領域に書き込まれた 1 の個数が偶数である

制約

2 \leq N \leq 10^5
0 \leq M \leq min(5 \times 10^4,N^2)
1 \leq a_i,b_i \leq N(1\leq i\leq M)
0 \leq c_i \leq 1(1\leq i\leq M)
i \neq j ならば (a_i,b_i) \neq (a_j,b_j) である
入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 b_1 c_1
:
a_M b_M c_M

出力

書き込み方としてありうるものの個数を 998244353 で割ったあまりを出力せよ。

入力例 1

出力例 1

例えば、以下のような書き込み方が条件を満たします。

101   111
011   111
000   011

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

出力例 4

入力例 5

100000 0

出力例 5

342016343

Score : 900 points

Problem Statement

Takahashi has an N \times N grid. The square at the i-th row and the j-th column of the grid is denoted by (i,j). Particularly, the top-left square of the grid is (1,1), and the bottom-right square is (N,N).

An integer, 0 or 1, is written on M of the squares in the Takahashi's grid. Three integers a_i,b_i and c_i describe the i-th of those squares with integers written on them: the integer c_i is written on the square (a_i,b_i).

Takahashi decides to write an integer, 0 or 1, on each of the remaining squares so that the condition below is satisfied. Find the number of such ways to write integers, modulo 998244353.

For all 1\leq i < j\leq N, there are even number of 1s in the square region whose top-left square is (i,i) and whose bottom-right square is (j,j).

Constraints

2 \leq N \leq 10^5
0 \leq M \leq min(5 \times 10^4,N^2)
1 \leq a_i,b_i \leq N(1\leq i\leq M)
0 \leq c_i \leq 1(1\leq i\leq M)
If i \neq j, then (a_i,b_i) \neq (a_j,b_j).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1 c_1
:
a_M b_M c_M

Output

Print the number of possible ways to write integers, modulo 998244353.

Sample Input 1

Sample Output 1

For example, the following ways to write integers satisfy the condition:

101   111
011   111
000   011

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

Sample Input 5

100000 0

Sample Output 5

342016343