C - Count Distinct Integers

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

配点 : 200 点

問題文

長さ N の正整数列 a = (a_1, a_2, \dots, a_N) には何種類の整数が現れますか？

制約

  • 1 \leq N \leq 1000
  • 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
  • 入力は全て整数

入力

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

N
a_1 \ldots a_N

出力

答えを出力せよ。

入力例 1

6
1 4 1 2 2 1

出力例 1

3

1, 2, 4 の 3 種類の整数が現れます。

入力例 2

1
1

出力例 2

1

入力例 3

11
3 1 4 1 5 9 2 6 5 3 5

出力例 3

7

Score : 200 points

Problem Statement

In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?

Constraints

  • 1 \leq N \leq 1000
  • 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 \ldots a_N

Output

Print the answer.

Sample Input 1

6
1 4 1 2 2 1

Sample Output 1

3

There are three different integers: 1, 2, 4.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

11
3 1 4 1 5 9 2 6 5 3 5

Sample Output 3

7
D - Multi Test Cases

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

配点 : 200 点

問題文

この問題は 1 つの入力ファイルに複数のテストケースが含まれる問題です。
はじめに整数 T が与えられます。T 個のテストケースについて次の問題を解いてください。

  • N 個の正整数 A_1, A_2, ..., A_N があります。このうち奇数は何個ありますか？

制約

  • 1 \leq T \leq 100
  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 10^9
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで \text{test}_i は i 番目のテストケースを意味する。

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

各テストケースは以下の形式で与えられる。

N
A_1 A_2 \dots A_N

出力

T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。

入力例 1

4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000

出力例 1

2
1
5
0

この入力は 4 個のテストケースが含まれています。

入力の 2 行目と 3 行目が 1 番目のテストケースに対応する入力で、N = 3, A_1 = 1, A_2 = 2, A_3 = 3 になります。
A_1, A_2, A_3 のうち奇数は全部で 2 個なので 1 行目に 2 を出力します。

Score : 200 points

Problem Statement

In this problem, an input file contains multiple test cases.
You are first given an integer T. Solve the following problem for T test cases.

  • We have N positive integers A_1, A_2, ..., A_N. How many of them are odd?

Constraints

  • 1 \leq T \leq 100
  • 1 \leq N \leq 100
  • 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, where \text{test}_i represents the i-th test case:

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

Each test case is in the following format:

N
A_1 A_2 \dots A_N

Output

Print T lines. The i-th line should contain the answer for the i-th test case.

Sample Input 1

4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000

Sample Output 1

2
1
5
0

This input contains four test cases.

The second and third lines correspond to the first test case, where N = 3, A_1 = 1, A_2 = 2, A_3 = 3.
We have two odd numbers in A_1, A_2, and A_3, so the first line should contain 2.
E - Four Variables

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

配点 : 300 点

問題文

正整数 N が与えられます。
正整数の組 (A,B,C,D) であって、AB + CD = N を満たすものの個数を求めてください。

なお、本問の制約の下、答えが 9 \times 10^{18} 以下であることが証明できます。

制約

  • 2 \leq N \leq 2 \times 10^5
  • N は整数

入力

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

N

出力

答えを出力せよ。

入力例 1

4

出力例 1

8

(A,B,C,D) として以下の 8 個が考えられます。

  • (A,B,C,D)=(1,1,1,3)
  • (A,B,C,D)=(1,1,3,1)
  • (A,B,C,D)=(1,2,1,2)
  • (A,B,C,D)=(1,2,2,1)
  • (A,B,C,D)=(1,3,1,1)
  • (A,B,C,D)=(2,1,1,2)
  • (A,B,C,D)=(2,1,2,1)
  • (A,B,C,D)=(3,1,1,1)

入力例 2

292

出力例 2

10886

入力例 3

19876

出力例 3

2219958

Score : 300 points

Problem Statement

You are given a positive integer N.
Find the number of quadruples of positive integers (A,B,C,D) such that AB + CD = N.

Under the constraints of this problem, it can be proved that the answer is at most 9 \times 10^{18}.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • N is an integer.

Input

The input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

4

Sample Output 1

8

Here are the eight desired quadruples.

  • (A,B,C,D)=(1,1,1,3)
  • (A,B,C,D)=(1,1,3,1)
  • (A,B,C,D)=(1,2,1,2)
  • (A,B,C,D)=(1,2,2,1)
  • (A,B,C,D)=(1,3,1,1)
  • (A,B,C,D)=(2,1,1,2)
  • (A,B,C,D)=(2,1,2,1)
  • (A,B,C,D)=(3,1,1,1)

Sample Input 2

292

Sample Output 2

10886

Sample Input 3

19876

Sample Output 3

2219958
F - Centers

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

配点 : 250 点

問題文

1,2,\dots,N がちょうど 3 回ずつ現れる長さ 3N の数列 A=(A_1,A_2,\dots,A_{3N}) が与えられます。

i=1,2,\dots,N について、A の中にある i のうち真ん中にあるものの添字を f(i) と定めます。 1,2,\dots,N を f(i) の昇順に並べ替えてください。

f(i) の定義は厳密には以下の通りです。

  • A_j = i を満たす j が j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma) であるとする。このとき、f(i) = \beta である。

制約

  • 1\leq N \leq 10^5
  • 1 \leq A_j \leq N
  • i=1,2,\dots,N それぞれについて、A の中に i はちょうど 3 回現れる
  • 入力は全て整数

入力

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

N
A_1 A_2 \dots A_{3N}

出力

1,2,\dots,N を f(i) の昇順に並べ替えてできる長さ N の数列を空白区切りで出力せよ。

入力例 1

3
1 1 3 2 3 2 2 3 1

出力例 1

1 3 2
  • A の中にある 1 は A_1,A_2,A_9 なので、f(1) = 2 です。
  • A の中にある 2 は A_4,A_6,A_7 なので、f(2) = 6 です。
  • A の中にある 3 は A_3,A_5,A_8 なので、f(3) = 5 です。

よって、f(1) < f(3) < f(2) であるため 1,3,2 の順に出力します。

入力例 2

1
1 1 1

出力例 2

1

入力例 3

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

出力例 3

3 4 1 2

Score : 250 points

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

  • Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

  • 1\leq N \leq 10^5
  • 1 \leq A_j \leq N
  • i occurs in A exactly three times, for each i=1,2,\dots,N.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_{3N}

Output

Print the sequence of length N obtained by sorting 1,2,\dots,N in ascending order of f(i), separated by spaces.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2
  • 1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
  • 2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
  • 3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3 4 1 2
G - "redocta".swap(i,i+1)

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

配点 : 400 点

問題文

atcoder の並べ替えである文字列 S が与えられます。
この文字列 S に対して以下の操作を 0 回以上行います。

  • S 中の隣接する 2 文字を選び、入れ替える。

S を atcoder にするために必要な最小の操作回数を求めてください。

制約

  • S は atcoder の並べ替えである文字列

入力

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

S

出力

答えを整数として出力せよ。

入力例 1

catredo

出力例 1

8

catredo \rightarrow [ac]tredo \rightarrow actre[od] \rightarrow actr[oe]d \rightarrow actro[de] \rightarrow act[or]de \rightarrow acto[dr]e \rightarrow a[tc]odre \rightarrow atcod[er]
という流れで操作を行うと、 8 回で S を atcoder にすることができ、これが達成可能な最小の操作回数です。

入力例 2

atcoder

出力例 2

0

この場合、文字列 S は元から atcoder です。

入力例 3

redocta

出力例 3

21

Score : 400 points

Problem Statement

You are given a string S that is a permutation of atcoder.
On this string S, you will perform the following operation 0 or more times:

  • Choose two adjacent characters of S and swap them.

Find the minimum number of operations required to make S equal atcoder.

Constraints

  • S is a string that is a permutation of atcoder

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer as an integer.

Sample Input 1

catredo

Sample Output 1

8

You can make S equal atcoder in 8 operations as follows:
catredo \rightarrow [ac]tredo \rightarrow actre[od] \rightarrow actr[oe]d \rightarrow actro[de] \rightarrow act[or]de \rightarrow acto[dr]e \rightarrow a[tc]odre \rightarrow atcod[er]
This is the minimum number of operations achievable.

Sample Input 2

atcoder

Sample Output 2

0

In this case, the string S is already atcoder.

Sample Input 3

redocta

Sample Output 3

21