Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
0 以上 255 以下の整数 A,B が与えられます。 A \text{ xor }C=B となる 0 以上の整数 C を求めてください。
なお、そのような C はただ 1 つ存在し、0 以上 255 以下であることが証明されます。
\text{ xor } とは
整数 a, b のビットごとの排他的論理和 a \text{ xor } b は、以下のように定義されます。
- a \text{ xor } b を二進表記した際の 2^k (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 0\leq A,B \leq 255
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
3 6
出力例 1
5
3 は 二進表記で 11、5 は二進表記で 101 なので、これらの \text{xor} は二進表記で 110 であり、十進表記で 6 です。
このように、3 \text{ xor } 5 = 6 となるので、答えは 5 です。
入力例 2
10 12
出力例 2
6

Score : 100 points
Problem Statement
You are given integers A and B between 0 and 255 (inclusive). Find a non-negative integer C such that A \text{ xor }C=B.
It can be proved that there uniquely exists such C, and it will be between 0 and 255 (inclusive).
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of integers A and B, A\ \mathrm{XOR}\ B, is defined as follows:
- When A\ \mathrm{XOR}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Constraints
- 0\leq A,B \leq 255
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
3 6
Sample Output 1
5
When written in binary, 3 will be 11, and 5 will be 101. Thus, their \text{xor} will be 110 in binary, or 6 in decimal.
In short, 3 \text{ xor } 5 = 6, so the answer is 5.
Sample Input 2
10 12
Sample Output 2
6

Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
5 枚のカードがあり、それぞれのカードには整数 A,B,C,D,E が書かれています。
この 5 枚組は以下の条件を満たすとき、またそのときに限って、フルハウスであると呼ばれます。
- 同じ数が書かれたカード 3 枚と、別の同じ数が書かれたカード 2 枚からなる。
5 枚組がフルハウスであるか判定してください。
制約
- 1 \leq A,B,C,D,E\leq 13
- A,B,C,D,E 全てが同じ値ではない
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B C D E
出力
フルハウスである場合 Yes を、そうでないとき No を出力せよ。
入力例 1
1 2 1 2 1
出力例 1
Yes
1 が書かれたカード 3 枚と、2 が書かれたカード 2 枚からなるため、これはフルハウスです。
入力例 2
12 12 11 1 2
出力例 2
No
フルハウスの条件を満たしません。
Score : 100 points
Problem Statement
We have five cards with integers A, B, C, D, and E written on them, one on each card.
This set of five cards is called a Full house if and only if the following condition is satisfied:
- the set has three cards with a same number written on them, and two cards with another same number written on them.
Determine whether the set is a Full house.
Constraints
- 1 \leq A,B,C,D,E\leq 13
- Not all of A, B, C, D, and E are the same.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B C D E
Output
If the set is a Full house, print Yes; otherwise, print No.
Sample Input 1
1 2 1 2 1
Sample Output 1
Yes
The set has three cards with 1 written on them and two cards with 2 written on them, so it is a Full house.
Sample Input 2
12 12 11 1 2
Sample Output 2
No
The condition is not satisfied.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
数直線の原点に高橋君がいます。高橋君は座標 X にあるゴールに移動しようとしています。
座標 Y には壁があり、最初、高橋君は壁を超えて移動することができません。
座標 Z にあるハンマーを拾った後でなら、壁を破壊して通過できるようになります。
高橋君がゴールに到達することが可能か判定し、可能であれば移動距離の最小値を求めてください。
制約
- -1000 \leq X,Y,Z \leq 1000
- X,Y,Z は相異なり、いずれも 0 でない
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
X Y Z
出力
高橋君がゴールに到達することが可能であれば、移動距離の最小値を出力せよ。不可能であれば、かわりに -1 と出力せよ。
入力例 1
10 -10 1
出力例 1
10
高橋君はまっすぐゴールに向かうことができます。
入力例 2
20 10 -10
出力例 2
40
ゴールは壁の向こう側にあります。まずハンマーを拾い、壁を壊すことでゴールに到達することができます。
入力例 3
100 1 1000
出力例 3
-1
Score : 200 points
Problem Statement
Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.
There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.
Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.
Constraints
- -1000 \leq X,Y,Z \leq 1000
- X, Y, and Z are distinct, and none of them is 0.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
X Y Z
Output
If Takahashi can reach the goal, print the minimum total distance he needs to travel to do so. If he cannot, print -1 instead.
Sample Input 1
10 -10 1
Sample Output 1
10
Takahashi can go straight to the goal.
Sample Input 2
20 10 -10
Sample Output 2
40
The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.
Sample Input 3
100 1 1000
Sample Output 3
-1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
-10^{18} 以上 10^{18} 以下の整数 X が与えられるので、\left\lfloor \dfrac{X}{10} \right\rfloor を出力してください。
注記
実数 x に対して、「x 以下の整数の中で最大の整数」を \left\lfloor x \right\rfloor と表します。たとえば \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, \left\lfloor 5 \right\rfloor = 5 のようになります。(詳しくは入出力例にある説明を参考にしてください。)
制約
- -10^{18} \leq X \leq 10^{18}
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
X
出力
\left\lfloor \frac{X}{10} \right\rfloor を出力せよ。整数として出力する必要があることに注意せよ。
入力例 1
47
出力例 1
4
\frac{47}{10} = 4.7 以下の整数は、すべての負の整数および 0, 1, 2, 3, 4 です。この中で一番大きい整数は 4 なので、\left\lfloor \frac{47}{10} \right\rfloor = 4 となります。
入力例 2
-24
出力例 2
-3
\frac{-24}{10} = -2.4 以下の整数の中で一番大きい整数は -3 なので、 \left\lfloor \frac{-24}{10} \right\rfloor = -3 となります。
-2 は -2.4 よりも大きいので、条件を満たさないことに注意してください。
入力例 3
50
出力例 3
5
\frac{50}{10} = 5 以下の整数の中で一番大きい整数は 5 自身です。よって \left\lfloor \frac{50}{10} \right\rfloor = 5 となります。
入力例 4
-30
出力例 4
-3
上の例と同様に \left\lfloor \frac{-30}{10} \right\rfloor = -3 となります。
入力例 5
987654321987654321
出力例 5
98765432198765432
答えは 98765432198765432 となります。すべての桁が正しく合っているか確認しましょう。
なお、もしも自分で書いたプログラムが想定通りの挙動をしない場合は、使用しているプログラミング言語の仕様を調べてみることを推奨します。
また、自分の書いたコードがどのように動作するかを確認したい場合は問題文上部の「コードテスト」をご利用ください。
Score : 200 points
Problem Statement
Given an integer X between -10^{18} and 10^{18} (inclusive), print \left\lfloor \dfrac{X}{10} \right\rfloor.
Notes
For a real number x, \left\lfloor x \right\rfloor denotes "the maximum integer not exceeding x". For example, we have \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, and \left\lfloor 5 \right\rfloor = 5. (For more details, please refer to the description in the Sample Input and Output.)
Constraints
- -10^{18} \leq X \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
X
Output
Print \left\lfloor \frac{X}{10} \right\rfloor. Note that it should be output as an integer.
Sample Input 1
47
Sample Output 1
4
The integers that do not exceed \frac{47}{10} = 4.7 are all the negative integers, 0, 1, 2, 3, and 4. The maximum integer among them is 4, so we have \left\lfloor \frac{47}{10} \right\rfloor = 4.
Sample Input 2
-24
Sample Output 2
-3
Since the maximum integer not exceeding \frac{-24}{10} = -2.4 is -3, we have \left\lfloor \frac{-24}{10} \right\rfloor = -3.
Note that -2 does not satisfy the condition, as -2 exceeds -2.4.
Sample Input 3
50
Sample Output 3
5
The maximum integer that does not exceed \frac{50}{10} = 5 is 5 itself. Thus, we have \left\lfloor \frac{50}{10} \right\rfloor = 5.
Sample Input 4
-30
Sample Output 4
-3
Just like the previous example, \left\lfloor \frac{-30}{10} \right\rfloor = -3.
Sample Input 5
987654321987654321
Sample Output 5
98765432198765432
The answer is 98765432198765432. Make sure that all the digits match.
If your program does not behave as intended, we recommend you checking the specification of the programming language you use.
If you want to check how your code works, you may use "Custom Test" above the Problem Statement.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
非負整数 N が与えられるので、以下の条件を満たす非負整数 x を昇順に全て出力してください。
- x を 2 進数として表記した時に 1 となる位の集合が、 N を 2 進数として表記した時に 1 となる位の集合の部分集合となる。
- すなわち、全ての非負整数 k について、「 x の 2^k の位が 1 ならば、 N の 2^k の位は 1 」が成り立つ。
制約
- N は整数
- 0 \le N < 2^{60}
- N を 2 進数として表記した時、 1 となる位は 15 個以下である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを 1 行に 1 つずつ、10 進法の整数として昇順に出力せよ。
入力例 1
11
出力例 1
0 1 2 3 8 9 10 11
N = 11_{(10)} を 2 進数で表記すると、 1011_{(2)} となります。
条件を満たす非負整数 x は以下の通りです。
- 0000_{(2)}=0_{(10)}
- 0001_{(2)}=1_{(10)}
- 0010_{(2)}=2_{(10)}
- 0011_{(2)}=3_{(10)}
- 1000_{(2)}=8_{(10)}
- 1001_{(2)}=9_{(10)}
- 1010_{(2)}=10_{(10)}
- 1011_{(2)}=11_{(10)}
入力例 2
0
出力例 2
0
入力例 3
576461302059761664
出力例 3
0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664
入力は 32bit 符号付き整数に収まらない可能性があります。
Score : 300 points
Problem Statement
You are given a non-negative integer N. Print all non-negative integers x that satisfy the following condition in ascending order.
- The set of the digit positions containing 1 in the binary representation of x is a subset of the set of the digit positions containing 1 in the binary representation of N.
- That is, the following holds for every non-negative integer k: if the digit in the "2^ks" place of x is 1, the digit in the 2^ks place of N is 1.
Constraints
- N is an integer.
- 0 \le N < 2^{60}
- In the binary representation of N, at most 15 digit positions contain 1.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer as decimal integers in ascending order, each in its own line.
Sample Input 1
11
Sample Output 1
0 1 2 3 8 9 10 11
The binary representation of N = 11_{(10)} is 1011_{(2)}.
The non-negative integers x that satisfy the condition are:
- 0000_{(2)}=0_{(10)}
- 0001_{(2)}=1_{(10)}
- 0010_{(2)}=2_{(10)}
- 0011_{(2)}=3_{(10)}
- 1000_{(2)}=8_{(10)}
- 1001_{(2)}=9_{(10)}
- 1010_{(2)}=10_{(10)}
- 1011_{(2)}=11_{(10)}
Sample Input 2
0
Sample Output 2
0
Sample Input 3
576461302059761664
Sample Output 3
0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664
The input may not fit into a 32-bit signed integer.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の数列 A = (A_1, A_2, \ldots, A_N) が与えられます。 K = 0, 1, 2, \ldots, N-1 のそれぞれについて、下記の問題を解いてください。
1 以上 N 以下の整数 i であって、次の条件を満たすものの個数を求めよ。
- A に含まれる整数のうち A_i より大きいものはちょうど K 種類である。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
N 行出力せよ。 i = 1, 2, \ldots, N について、i 行目には K = i-1 の場合の問題の答えを出力せよ。
入力例 1
6 2 7 1 8 2 8
出力例 1
2 1 2 1 0 0
例として、K = 2 の場合の問題の答えを以下で求めます。
- A_1 = 2 に関して、A に含まれる整数のうち A_1 より大きいものは、7, 8 の 2 種類です。
- A_2 = 7 に関して、A に含まれる整数のうち A_2 より大きいものは、8 の 1 種類です。
- A_3 = 1 に関して、A に含まれる整数のうち A_3 より大きいものは、2, 7, 8 の 3 種類です。
- A_4 = 8 に関して、A に含まれる整数のうち A_4 より大きいものは、0 種類です(存在しません)。
- A_5 = 2 に関して、A に含まれる整数のうち A_5 より大きいものは、7, 8 の 2 種類です。
- A_6 = 8 に関して、A に含まれる整数のうち A_6 より大きいものは、0 種類です(存在しません)。
よって、A に含まれる整数のうちA_i より大きいものがちょうど K = 2 種類であるような i は、i = 1 と i = 5 の 2 つです。よって、K = 2 の場合の答えは 2 です。
入力例 2
1 1
出力例 2
1
入力例 3
10 979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527
出力例 3
2 1 2 1 2 1 1 0 0 0
Score : 300 points
Problem Statement
You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. For each K = 0, 1, 2, \ldots, N-1, solve the following problem.
Find the number of integers i between 1 and N (inclusive) such that:
- A contains exactly K distinct integers greater than A_i.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print N lines. For i = 1, 2, \ldots, N, the i-th line should contain the answer for K = i-1.
Sample Input 1
6 2 7 1 8 2 8
Sample Output 1
2 1 2 1 0 0
For example, we will find the answer for K=2.
- Regarding A_1 = 2, A contains 2 distinct integers greater than A_1: 7 and 8.
- Regarding A_2 = 7, A contains 1 distinct integer greater than A_2: 8.
- Regarding A_3 = 1, A contains 3 distinct integers greater than A_3: 2, 7, and 8.
- Regarding A_4 = 8, A contains 0 distinct integers greater than A_4 (there is no such integer).
- Regarding A_5 = 2, A contains 2 distinct integers greater than A_5: 7 and 8.
- Regarding A_6 = 8, A contains 0 distinct integers greater than A_6 (there is no such integer).
Thus, there are two i's, i = 1 and i = 5, such that A contains exactly K = 2 distinct integers greater than A_i. Therefore, the answer for K = 2 is 2.
Sample Input 2
1 1
Sample Output 2
1
Sample Input 3
10 979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527
Sample Output 3
2 1 2 1 2 1 1 0 0 0
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 425 点
問題文
数字のみからなる、長さ N の文字列 S が与えられます。
S を並べ替えてできる文字列を十進法の整数として解釈したもののうち、平方数であるようなものがいくつあるか求めてください。
より厳密には、次のようになります。
S の先頭から i 番目 (1\leq i\leq N) の数字に対応する数を s _ i とします。
(1, \ldots, N) の順列 P=(p _ 1,p _ 2,\ldots,p _ N) によって \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} と書ける整数のうち、平方数であるようなものがいくつあるか求めてください。
制約
- 1\leq N\leq 13
- S は数字のみからなる長さ N の文字列
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを 1 行で出力せよ。
入力例 1
4 4320
出力例 1
2
P=(4,2,3,1) とすると、s _ 4\times10 ^ 3+s _ 2\times10 ^ 2+s _ 3\times10 ^ 1+s _ 1=324=18 ^ 2 となります。
P=(3,2,4,1) とすると、s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2 となります。
これら以外の並べ替え方では平方数にならないため、2 を出力してください。
入力例 2
3 010
出力例 2
2
P=(1,3,2) もしくは P=(3,1,2) とすると、\displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2 となります。
P=(2,1,3) もしくは P=(2,3,1) とすると、\displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2 となります。
これら以外の並べ替え方では平方数にならないため、2 を出力してください。 異なる並べ替え方でも、並べ替えた結果の数が同じなら 1 つと数えることに注意してください。
入力例 3
13 8694027811503
出力例 3
840
Score : 425 points
Problem Statement
You are given a string S of length N consisting of digits.
Find the number of square numbers that can be obtained by interpreting a permutation of S as a decimal integer.
More formally, solve the following.
Let s _ i be the number corresponding to the i-th digit (1\leq i\leq N) from the beginning of S.
Find the number of square numbers that can be represented as \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} with a permutation P=(p _ 1,p _ 2,\ldots,p _ N) of (1, \dots, N).
Constraints
- 1\leq N\leq 13
- S is a string of length N consisting of digits.
- N is an integer.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the answer in a single line.
Sample Input 1
4 4320
Sample Output 1
2
For P=(4,2,3,1), we have s _ 4\times10 ^ 3+s _ 2\times10 ^ 2+s _ 3\times10 ^ 1+s _ 1=324=18 ^ 2.
For P=(3,2,4,1), we have s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2.
No other permutations result in square numbers, so you should print 2.
Sample Input 2
3 010
Sample Output 2
2
For P=(1,3,2) or P=(3,1,2), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2.
For P=(2,1,3) or P=(2,3,1), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2.
No other permutations result in square numbers, so you should print 2. Note that different permutations are not distinguished if they result in the same number.
Sample Input 3
13 8694027811503
Sample Output 3
840
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
N 個の整数 a_1,\ldots,a_N が白板に書かれています。
ここで、a_i は m_i 個の素数 p_{i,1} \lt \ldots \lt p_{i,m_i} と正整数 e_{i,1},\ldots,e_{i,m_i} を用いて a_i = p_{i,1}^{e_{i,1}} \times \ldots \times p_{i,m_i}^{e_{i,m_i}} と表せる整数です。
あなたは N 個の整数から 1 つ選んで 1 に書き換えます。
書き換えた後の N 個の整数の最小公倍数としてあり得る値の個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq m_i
- \sum{m_i} \leq 2 \times 10^5
- 2 \leq p_{i,1} \lt \ldots \lt p_{i,m_i} \leq 10^9
- p_{i,j} は素数
- 1 \leq e_{i,j} \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
m_1
p_{1,1} e_{1,1}
\vdots
p_{1,m_1} e_{1,m_1}
m_2
p_{2,1} e_{2,1}
\vdots
p_{2,m_2} e_{2,m_2}
\vdots
m_N
p_{N,1} e_{N,1}
\vdots
p_{N,m_N} e_{N,m_N}
出力
答えを出力せよ。
入力例 1
4 1 7 2 2 2 2 5 1 1 5 1 2 2 1 7 1
出力例 1
3
白板に書かれている整数は a_1 =7^2=49, a_2=2^2 \times 5^1 = 20, a_3 = 5^1 = 5, a_4=2^1 \times 7^1 = 14 です。
a_1 を 1 に書き換えると白板に書かれている整数は 1,20,5,14 となり、これらの最小公倍数は 140 です。
a_2 を 1 に書き換えると白板に書かれている整数は 49,1,5,14 となり、これらの最小公倍数は 490 です。
a_3 を 1 に書き換えると白板に書かれている整数は 49,20,1,14 となり、これらの最小公倍数は 980 です。
a_4 を 1 に書き換えると白板に書かれている整数は 49,20,5,1 となり、これらの最小公倍数は 980 です。
以上より、書き換えた後の N 個の整数の最小公倍数としてあり得る値は 140,490,980 であり、この入力における答えが 3 と分かります。
入力例 2
1 1 998244353 1000000000
出力例 2
1
白板に書かれている整数はとても大きい場合があります。
Score : 500 points
Problem Statement
There are N integers a_1,\ldots,a_N written on a whiteboard.
Here, a_i can be represented as a_i = p_{i,1}^{e_{i,1}} \times \ldots \times p_{i,m_i}^{e_{i,m_i}} using m_i prime numbers p_{i,1} \lt \ldots \lt p_{i,m_i} and positive integers e_{i,1},\ldots,e_{i,m_i}.
You will choose one of the N integers to replace it with 1.
Find the number of values that can be the least common multiple of the N integers after the replacement.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq m_i
- \sum{m_i} \leq 2 \times 10^5
- 2 \leq p_{i,1} \lt \ldots \lt p_{i,m_i} \leq 10^9
- p_{i,j} is prime.
- 1 \leq e_{i,j} \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
m_1
p_{1,1} e_{1,1}
\vdots
p_{1,m_1} e_{1,m_1}
m_2
p_{2,1} e_{2,1}
\vdots
p_{2,m_2} e_{2,m_2}
\vdots
m_N
p_{N,1} e_{N,1}
\vdots
p_{N,m_N} e_{N,m_N}
Output
Print the answer.
Sample Input 1
4 1 7 2 2 2 2 5 1 1 5 1 2 2 1 7 1
Sample Output 1
3
The integers on the whiteboard are a_1 =7^2=49, a_2=2^2 \times 5^1 = 20, a_3 = 5^1 = 5, a_4=2^1 \times 7^1 = 14.
If you replace a_1 with 1, the integers on the whiteboard become 1,20,5,14, whose least common multiple is 140.
If you replace a_2 with 1, the integers on the whiteboard become 49,1,5,14, whose least common multiple is 490.
If you replace a_3 with 1, the integers on the whiteboard become 49,20,1,14, whose least common multiple is 980.
If you replace a_4 with 1, the integers on the whiteboard become 49,20,5,1, whose least common multiple is 980.
Therefore, the least common multiple of the N integers after the replacement can be 140, 490, or 980, so the answer is 3.
Sample Input 2
1 1 998244353 1000000000
Sample Output 2
1
There may be enormous integers on the whiteboard.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
N 個の町と M 個のテレポーターがあり、
町は町 1, 町 2, \ldots, 町N と番号づけられています。
それぞれのテレポーターは 2 つの町を双方向に結んでおり、テレポーターを使用する事によってその 2 つの町の間を 1 分で移動することができます。
i 番目のテレポーターは町 U_i と町 V_i を双方向に結んでいますが、 いくつかのテレポーターについては結ぶ町の片方が決まっておらず、 U_i=0 のときそのテレポーターが結ぶ町の片方は町 V_i であるが、 もう片方が未定であることを意味します。
i=1,2,\ldots,N それぞれについて、次の問題を解いてください。
結ぶ町の片方が未定となっているテレポーターの結ぶ先をすべて町 i とする。 この時に町 1 から町 N まで移動するのに最小で何分かかるか求めよ。 町 1 から町 N までテレポーターのみを使って移動するのが不可能な場合は -1 を出力せよ。
制約
- 2 \leq N \leq 3\times 10^5
- 1\leq M\leq 3\times 10^5
- 0\leq U_i<V_i\leq N
- i \neq j ならば (U_i,V_i)\neq (U_j,V_j)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
出力
N 個の整数を空白区切りで出力せよ。 ここで、k 番目の整数は i=k とした時の問題に対する答えである.
入力例 1
3 2 0 2 1 2
出力例 1
-1 -1 2
結ぶ先が未定となっているテレポーターの結び先を町 1 としたとき、
1 番目と 2 番目のテレポーターはともに町 1 と町 2 を結びます。
このとき、町 1 から町 3 への移動はできません。
結ぶ先が未定となっているテレポーターの結び先を町 2 としたとき、
1 番目のテレポーターは町 2 同士を、 2 番目のテレポーターは町 1 と町 2 を結びます。
このときもやはり、町 1 から町 3 への移動はできません。
結ぶ先が未定となっているテレポーターの結び先を町 3 としたとき、
1 番目のテレポーターは町 3 と町 2 を、 2 番目のテレポーターは町 1 と町 2 を結びます。
この時、次のようにして町 1 から町 3 へ 2 分で移動できます。
- 2 番目のテレポーターを使用し、町 1 から町 2 まで移動する。
- 1 番目のテレポーターを使用し、町 2 から町 3 まで移動する。
よって、-1,-1,2 をこの順に出力します。
結ぶ先が未定となっているテレポーターの結び先によっては、 同じ町同士を結ぶテレポーターが存在する可能性や、 ある 2 つの町を結ぶテレポーターが複数存在する可能性がある事に注意してください。
入力例 2
5 5 1 2 1 3 3 4 4 5 0 2
出力例 2
3 3 3 3 2
Score : 500 points
Problem Statement
There are N towns
numbered Town 1, Town 2, \ldots, Town N.
There are also M Teleporters, each of which connects two towns bidirectionally so that a person can travel from one to the other in one minute.
The i-th Teleporter connects Town U_i and Town V_i bidirectionally. However, for some of the Teleporters, one of the towns it connects is undetermined; U_i=0 means that one of the towns the i-th Teleporter connects is Town V_i, but the other end is undetermined.
For i=1,2,\ldots,N, answer the following question.
When the Teleporters with undetermined ends are all determined to be connected to Town i, how many minutes is required at minimum to travel from Town 1 to Town N? If it is impossible to travel from Towns 1 to N using Teleporters only, print -1 instead.
Constraints
- 2 \leq N \leq 3\times 10^5
- 1\leq M\leq 3\times 10^5
- 0\leq U_i<V_i\leq N
- If i \neq j, then (U_i,V_i)\neq (U_j,V_j).
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
Output
Print N integers, with spaces in between. The k-th integer should be the answer to the question when i=k.
Sample Input 1
3 2 0 2 1 2
Sample Output 1
-1 -1 2
When the Teleporters with an undetermined end are all determined to be connected to Town 1,
the 1-st and the 2-nd Teleporters both connect Towns 1 and 2.
Then, it is impossible to travel from Town 1 to Town 3.
When the Teleporters with an undetermined end are all determined to be connected to Town 2,
the 1-st Teleporter connects Town 2 and itself, and the 2-nd one connects Towns 1 and 2.
Again, it is impossible to travel from Town 1 to Town 3.
When the Teleporters with an undetermined end are all determined to be connected to Town 3,
the 1-st Teleporter connects Town 3 and Town 2, and the 2-nd one connects Towns 1 and 2.
In this case, we can travel from Town 1 to Town 3 in two minutes.
- Use the 2-nd Teleporter to travel from Town 1 to Town 2.
- Use the 1-st Teleporter to travel from Town 2 to Town 3.
Therefore, -1,-1, and 2 should be printed in this order.
Note that, depending on which town the Teleporters with an undetermined end are connected to, there may be a Teleporter that connects a town and itself, or multiple Teleporters that connect the same pair of towns.
Sample Input 2
5 5 1 2 1 3 3 4 4 5 0 2
Sample Output 2
3 3 3 3 2