A - AC or WA

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

問題文

高橋君は、プログラミングコンテスト AXC001 に参加しており、問題 A にコードを提出しました。
この問題には N 個のテストケースがあり、すべてのテストケースに正解した場合のみ提出は AC となります。
高橋君の提出は、N 個のテストケースのうち M 個のテストケースに正解しました。
高橋君の提出が AC となるか判定してください。

制約

  • 1 \leq N \leq 100
  • 0 \leq M \leq N
  • 入力はすべて整数である。

入力

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

N M

出力

高橋君の提出が AC となる場合は Yes, そうでない場合は No と出力せよ。

入力例 1

3 3

出力例 1

Yes

3 つのテストケースすべてに正解したので、AC となります。

入力例 2

3 2

出力例 2

No

3 つのテストケース中 2 つしか正解できなかったので、AC となりません。

入力例 3

1 1

出力例 3

Yes

Score : 100 points

Problem Statement

Takahashi is participating in a programming contest, AXC001. He has just submitted his code to Problem A.
The problem has N test cases, all of which must be passed to get an AC verdict.
Takahashi's submission has passed M cases out of the N test cases.
Determine whether Takahashi's submission gets an AC.

Constraints

  • 1 \leq N \leq 100
  • 0 \leq M \leq N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

If Takahashi's submission gets an AC, print Yes; otherwise, print No.

Sample Input 1

3 3

Sample Output 1

Yes

All three test cases have been passed, so his submission gets an AC.

Sample Input 2

3 2

Sample Output 2

No

Only two out of the three test cases have been passed, so his submission does not get an AC.

Sample Input 3

1 1

Sample Output 3

Yes
B - Comparing Strings

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200 点

問題文

1 桁の正整数 a ,b が与えられます。整数 a を b 回繰り返してできる文字列と 整数 b を a 回繰り返してできる文字列のうち、辞書順で小さい方を答えてください。

制約

  • 1 ≤ a ≤ 9
  • 1 ≤ b ≤ 9
  • a,b は整数

入力

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

a b

出力

2 つの文字列のうち辞書順で小さい方を出力せよ。(2 つの文字列が等しいときは、そのうちどちらかを出力せよ。)

入力例 1

4 3

出力例 1

3333

できる 2 つの文字列は、444 と 3333 です。このうち辞書順で小さい文字列は 3333 です。

入力例 2

7 7

出力例 2

7777777

Score : 200 points

Problem Statement

Given are 1-digit positive integers a and b. Consider these two strings: the concatenation of b copies of the digit a, and the concatenation of a copies of the digit b. Which of these is lexicographically smaller?

Constraints

  • 1 \leq a \leq 9
  • 1 \leq b \leq 9
  • a and b are integers.

Input

Input is given from Standard Input in the following format:

a b

Output

Print the lexicographically smaller of the two strings. (If the two strings are equal, print one of them.)

Sample Input 1

4 3

Sample Output 1

3333

We have two strings 444 and 3333. Between them, 3333 is the lexicographically smaller.

Sample Input 2

7 7

Sample Output 2

7777777
C - Low Elements

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

1, \ldots, N の順列 P_1, \ldots, P_N が与えられます。
次の条件を満たす整数 i(1 \leq i \leq N) の個数を数えてください。

  • 任意の整数 j(1 \leq j \leq i) に対して、 P_i \leq P_j

制約

  • 1 \leq N \leq 2 \times 10^5
  • P_1, \ldots, P_N は 1, \ldots, N の順列である。
  • 入力はすべて整数である。

入力

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

N
P_1 ... P_N

出力

条件を満たす整数 i の個数を出力せよ。

入力例 1

5
4 2 5 1 3

出力例 1

3

i=1,2,4 が条件を満たします。
i=3 は条件を満たしません。
例えば、 j=1 とすると、 P_i > P_j となります。
同様に、 i=5 も条件を満たしません。
したがって、条件を満たす整数 i の個数は 3 となります。

入力例 2

4
4 3 2 1

出力例 2

4

すべての整数 i(1 \leq i \leq N) が条件を満たします。

入力例 3

6
1 2 3 4 5 6

出力例 3

1

i=1 のみが条件を満たします。

入力例 4

8
5 7 4 2 6 8 1 3

出力例 4

4

入力例 5

1
1

出力例 5

1

Score : 300 points

Problem Statement

Given is a permutation P_1, \ldots, P_N of 1, \ldots, N. Find the number of integers i (1 \leq i \leq N) that satisfy the following condition:

  • For any integer j (1 \leq j \leq i), P_i \leq P_j.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • P_1, \ldots, P_N is a permutation of 1, \ldots, N.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 ... P_N

Output

Print the number of integers i that satisfy the condition.

Sample Input 1

5
4 2 5 1 3

Sample Output 1

3

i=1, 2, and 4 satisfy the condition, but i=3 does not - for example, P_i > P_j holds for j = 1.
Similarly, i=5 does not satisfy the condition, either. Thus, there are three integers that satisfy the condition.

Sample Input 2

4
4 3 2 1

Sample Output 2

4

All integers i (1 \leq i \leq N) satisfy the condition.

Sample Input 3

6
1 2 3 4 5 6

Sample Output 3

1

Only i=1 satisfies the condition.

Sample Input 4

8
5 7 4 2 6 8 1 3

Sample Output 4

4

Sample Input 5

1
1

Sample Output 5

1
D - Handstand 2

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

正の整数 N が与えられます。
N 以下の正の整数の組 (A,B) であって、次の条件を満たすものの個数を求めてください。

  • A,B を先頭に 0 のつかない 10 進数表記で表したときに、 A の末尾の桁が B の先頭の桁に等しく、 A の先頭の桁が B の末尾の桁に等しい

制約

  • 1 \leq N \leq 2 \times 10^5
  • 入力はすべて整数である。

入力

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

N

出力

答えを出力せよ。

入力例 1

25

出力例 1

17

条件を満たす正の整数の組 (A,B) は、
(1,1), (1,11), (2,2), (2,22), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9), (11,1), (11,11), (12,21), (21,12), (22,2), (22,22)
の 17 個あります。

入力例 2

1

出力例 2

1

入力例 3

100

出力例 3

108

入力例 4

2020

出力例 4

40812

入力例 5

200000

出力例 5

400000008

Score : 400 points

Problem Statement

Given is a positive integer N.
Find the number of pairs (A, B) of positive integers not greater than N that satisfy the following condition:

  • When A and B are written in base ten without leading zeros, the last digit of A is equal to the first digit of B, and the first digit of A is equal to the last digit of B.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

25

Sample Output 1

17

The following 17 pairs satisfy the condition: (1,1), (1,11), (2,2), (2,22), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9), (11,1), (11,11), (12,21), (21,12), (22,2), and (22,22).

Sample Input 2

1

Sample Output 2

1

Sample Input 3

100

Sample Output 3

108

Sample Input 4

2020

Sample Output 4

40812

Sample Input 5

200000

Sample Output 5

400000008
E - Flatten

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

N 個の正整数 A_1,...,A_N が与えられます。

次の条件を満たすような正整数 B_1,...,B_N を考えます。

条件：1 \leq i < j \leq N を満たすどのような i,j についても A_i B_i = A_j B_j が成り立つ。

このような B_1,...,B_N における B_1 + ... + B_N の最小値を求めてください。

ただし、答えは非常に大きくなる可能性があるため、(10^9 +7) で割ったあまりを出力してください。

制約

  • 1 \leq N \leq 10^4
  • 1 \leq A_i \leq 10^6
  • 入力中のすべての値は整数である。

入力

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

N
A_1 ... A_N

出力

条件を満たすような B_1,...,B_N における B_1 + ... + B_N の最小値を (10^9 +7) で割ったあまりを出力せよ。

入力例 1

3
2 3 4

出力例 1

13

B_1=6, B_2=4, B_3=3 とすると条件を満たします。

入力例 2

5
12 12 12 12 12

出力例 2

5

全ての B_i を 1 とすればよいです。

入力例 3

3
1000000 999999 999998

出力例 3

996989508

和を (10^9+7) で割った余りを出力してください。

Score : 500 points

Problem Statement

Given are N positive integers A_1,...,A_N.

Consider positive integers B_1, ..., B_N that satisfy the following condition.

Condition: For any i, j such that 1 \leq i < j \leq N, A_i B_i = A_j B_j holds.

Find the minimum possible value of B_1 + ... + B_N for such B_1,...,B_N.

Since the answer can be enormous, print the sum modulo (10^9 +7).

Constraints

  • 1 \leq N \leq 10^4
  • 1 \leq A_i \leq 10^6
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the minimum possible value of B_1 + ... + B_N for B_1,...,B_N that satisfy the condition, modulo (10^9 +7).

Sample Input 1

3
2 3 4

Sample Output 1

13

Let B_1=6, B_2=4, and B_3=3, and the condition will be satisfied.

Sample Input 2

5
12 12 12 12 12

Sample Output 2

5

We can let all B_i be 1.

Sample Input 3

3
1000000 999999 999998

Sample Output 3

996989508

Print the sum modulo (10^9+7).
F - Tree and Constraints

実行時間制限: 4 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

1 から N までの番号がつけられた N 個の頂点を持つ木があります。 この木の i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。
この木の各辺に、それぞれ白か黒の色を塗ることを考えます。このような塗り方は 2^{N-1} 通り考えられますが、そのうち以下の M 個の制約をすべて満たすものの個数を求めてください。

  • i(1 \leq i \leq M) 番目の制約は、 2 つの整数 u_i と v_i によって表される。これは、頂点 u_i と頂点 v_i を結ぶパスに含まれる辺のうち、黒く塗られているものが 1 つ以上存在しなければならないことを意味する。

制約

  • 2 \leq N \leq 50
  • 1 \leq a_i,b_i \leq N
  • 入力で与えられるグラフは木である。
  • 1 \leq M \leq \min(20,\frac{N(N-1)}{2})
  • 1 \leq u_i < v_i \leq N
  • i \not= j なら u_i \not=u_j または v_i\not=v_j
  • 入力はすべて整数である。

入力

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

N
a_1 b_1
:
a_{N-1} b_{N-1}
M
u_1 v_1
:
u_M v_M

出力

M 個の制約をすべて満たす塗り方の個数を出力せよ。

入力例 1

3
1 2
2 3
1
1 3

出力例 1

3

この入力中の木は以下のようなものです。

図

辺 1 と辺 2 をそれぞれ (白,黒), (黒,白), (黒,黒) で塗った場合に、M 個の制約をすべて満たすことができます。
したがって答えは 3 です。

入力例 2

2
1 2
1
1 2

出力例 2

1

この入力中の木は以下のようなものです。

図

辺 1 を黒く塗った場合のみ、 M 個の制約をすべて満たすことができます。
したがって答えは 1 です。

入力例 3

5
1 2
3 2
3 4
5 3
3
1 3
2 4
2 5

出力例 3

9

この入力中の木は以下のようなものです。

図

入力例 4

8
1 2
2 3
4 3
2 5
6 3
6 7
8 6
5
2 7
3 5
1 6
2 8
7 8

出力例 4

62

この入力中の木は以下のようなものです。

図

Score : 600 points

Problem Statement

We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and Vertex b_i.
Consider painting each of these edges white or black. There are 2^{N-1} such ways to paint the edges. Among them, how many satisfy all of the following M restrictions?

  • The i-th (1 \leq i \leq M) restriction is represented by two integers u_i and v_i, which mean that the path connecting Vertex u_i and Vertex v_i must contain at least one edge painted black.

Constraints

  • 2 \leq N \leq 50
  • 1 \leq a_i,b_i \leq N
  • The graph given in input is a tree.
  • 1 \leq M \leq \min(20,\frac{N(N-1)}{2})
  • 1 \leq u_i < v_i \leq N
  • If i \not= j, either u_i \not=u_j or v_i\not=v_j
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}
M
u_1 v_1
:
u_M v_M

Output

Print the number of ways to paint the edges that satisfy all of the M conditions.

Sample Input 1

3
1 2
2 3
1
1 3

Sample Output 1

3

The tree in this input is shown below:

Figure

All of the M restrictions will be satisfied if Edge 1 and 2 are respectively painted (white, black), (black, white), or (black, black), so the answer is 3.

Sample Input 2

2
1 2
1
1 2

Sample Output 2

1

The tree in this input is shown below:

Figure

All of the M restrictions will be satisfied only if Edge 1 is painted black, so the answer is 1.

Sample Input 3

5
1 2
3 2
3 4
5 3
3
1 3
2 4
2 5

Sample Output 3

9

The tree in this input is shown below:

Figure

Sample Input 4

8
1 2
2 3
4 3
2 5
6 3
6 7
8 6
5
2 7
3 5
1 6
2 8
7 8

Sample Output 4

62

The tree in this input is shown below:

Figure