E - Almost Equal

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

配点 : 250 点

問題文

英小文字からなる長さ M の文字列 N 個 S_1,S_2,\dots,S_N が与えられます。ここで、S_i は互いに異なります。

これらを並び替えた文字列の列 T_1,T_2,\dots,T_N であって、以下の条件を満たすものが存在するか判定してください。

  • 1 \le i \le N-1 を満たす全ての整数 i に対して、T_i を 1 文字だけ別の英小文字に変えて T_{i+1} にすることが出来る。

制約

  • 2 \le N \le 8
  • 1 \le M \le 5
  • S_i は英小文字からなる長さ M の文字列である。(1 \le i \le N)
  • S_i は互いに異なる。

入力

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

N M
S_1
S_2
\vdots
S_N

出力

問題文の条件を満たす列が存在するならば Yes を、そうでないならば No を出力せよ。


入力例 1

4 4
bbed
abcd
abed
fbed

出力例 1

Yes

abcd , abed , bbed , fbed の順に並び替えると条件を満たします。


入力例 2

2 5
abcde
abced

出力例 2

No

どのように並び替えても条件を満たすことは出来ません。


入力例 3

8 4
fast
face
cast
race
fact
rice
nice
case

出力例 3

Yes

Score : 250 points

Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

  • for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

  • 2 \le N \le 8
  • 1 \le M \le 5
  • S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
  • S_i are pairwise distinct.

Input

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

N M
S_1
S_2
\vdots
S_N

Output

Print Yes if one can obtain a conforming sequence; print No otherwise.


Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.


Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.


Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes
F - Submask

実行時間制限: 2 sec / メモリ制限: 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.

G - Keep Distance

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

配点 : 425 点

問題文

整数 N と M が与えられます。

以下の条件をすべて満たす長さ N の整数列 (A_1, A_2, \ldots, A_N) を辞書順にすべて出力してください。

  • 1 \leq A_i
  • 2 以上 N 以下の各整数 i に対して A_{i - 1} + 10 \leq A_i
  • A_N \leq M
数列の辞書順とは

長さ N の数列 S = (S_1, S_2, \ldots, S_N) が長さ N の数列 T = (T_1, T_2, \ldots, T_N) より辞書順で小さいとは、ある整数 1 \leq i \leq N が存在して下記の 2 つがともに成り立つことをいいます。

  • (S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})
  • S_i が T_i より(数として)小さい。

制約

  • 2 \leq N \leq 12
  • 10N - 9 \leq M \leq 10N
  • 入力される値はすべて整数

入力

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

N M

出力

条件を満たす長さ N の整数列の個数を X として X + 1 行出力せよ。

1 行目には X の値を出力せよ。

i + 1 (1 \leq i \leq X) 行目には条件を満たす整数列のうち辞書順で i 番目に小さいものを空白区切りで出力せよ。


入力例 1

3 23

出力例 1

10
1 11 21
1 11 22
1 11 23
1 12 22
1 12 23
1 13 23
2 12 22
2 12 23
2 13 23
3 13 23

(1, 11, 21), (1, 11, 22), (1, 11, 23), (1, 12, 22), (1, 12, 23), (1, 13, 23), (2, 12, 22), (2, 12, 23), (2, 13, 23), (3, 13, 23) の 10 個の数列が条件を満たします。

Score: 425 points

Problem Statement

You are given integers N and M.

Print all integer sequences (A_1, A_2, \ldots, A_N) of length N that satisfy all of the following conditions, in lexicographical order.

  • 1 \leq A_i
  • A_{i - 1} + 10 \leq A_i for each integer i from 2 through N
  • A_N \leq M
What is lexicographical order?

A sequence S = (S_1, S_2, \ldots, S_N) of length N is smaller in lexicographical order than a sequence T = (T_1, T_2, \ldots, T_N) of length N if and only if there exists an integer 1 \leq i \leq N such that both of the following hold:

  • (S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})
  • S_i is less than T_i (as a number).

Constraints

  • 2 \leq N \leq 12
  • 10N - 9 \leq M \leq 10N
  • All input values are integers.

Input

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

N M

Output

Let X be the number of integer sequences that satisfy the conditions, and print X + 1 lines.

The first line should contain the value of X.

The (i + 1)-th line (1 \leq i \leq X) should contain the i-th smallest integer sequence in lexicographical order, with elements separated by spaces.


Sample Input 1

3 23

Sample Output 1

10
1 11 21
1 11 22
1 11 23
1 12 22
1 12 23
1 13 23
2 12 22
2 12 23
2 13 23
3 13 23

(1, 11, 21), (1, 11, 22), (1, 11, 23), (1, 12, 22), (1, 12, 23), (1, 13, 23), (2, 12, 22), (2, 12, 23), (2, 13, 23), (3, 13, 23) are the 10 sequences that satisfy the conditions.

H - Sum of All Substrings

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

配点 : 475 点

問題文

1 から 9 までの数字からなる長さ N の文字列 S が与えられます。

整数の組 (i,j) \ (1\leq i\leq j\leq N) に対して、 f(i,j) を「 S の i 文字目から j 文字目までの連続部分文字列を 10 進法の整数としてみなしたときの値」とします。\displaystyle \sum_{i=1}^N \sum_{j=i}^N f(i,j) を求めてください。

制約

  • 1\leq N\leq 2\times 10^5
  • N は整数
  • S は 1 から 9 までの数字からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。


入力例 1

3
379

出力例 1

514

答えは f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=3+37+379+7+79+9=514 です。


入力例 2

30
314159265358979323846264338327

出力例 2

369673254065355789035427227741

Score : 475 points

Problem Statement

You are given a string S of length N consisting of digits from 1 through 9.

For each pair of integers (i,j) \ (1\leq i\leq j\leq N), define f(i, j) as the value obtained by interpreting the substring of S from the i-th through the j-th character as a decimal integer. Find \displaystyle \sum_{i=1}^N \sum_{j=i}^N f(i, j).

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • N is an integer.
  • S is a string of length N consisting of digits from 1 through 9.

Input

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

N
S

Output

Print the answer.


Sample Input 1

3
379

Sample Output 1

514

The answer is f(1,1) + f(1,2) + f(1,3) + f(2,2) + f(2,3) + f(3,3) = 3 + 37 + 379 + 7 + 79 + 9 = 514.


Sample Input 2

30
314159265358979323846264338327

Sample Output 2

369673254065355789035427227741
I - Second Largest Query

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

配点 : 525 点

問題文

長さ N の数列 A = (A_1, A_2, \ldots, A_N) が与えられます。

Q 個のクエリが与えられるので、与えられた順に処理してください。各クエリは以下の 2 種類のいずれかです。

  • タイプ 1 : 1 p x の形式で与えられる。 A_p の値を x に変更する。
  • タイプ 2 : 2 l r の形式で与えられる。 (A_l, A_{l+1}, \ldots, A_r) において 2 番目に大きい値の個数を出力する。より厳密には、l \leq i \leq r を満たす整数 i であって、A_l, A_{l+1}, \ldots, A_r のうち A_i より大きい値がちょうど 1 種類であるものの個数を出力する。

制約

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • タイプ 1 のクエリにおいて、1 \leq p \leq N
  • タイプ 1 のクエリにおいて、1 \leq x \leq 10^9
  • タイプ 2 のクエリにおいて、1 \leq l \leq r \leq N
  • タイプ 2 のクエリが 1 つ以上存在する
  • 入力される値はすべて整数

入力

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

N Q
A_1 A_2 \ldots A_N
\text{query}_{1}
\vdots
\text{query}_{Q}

ただし、\text{query}_{i} は i 個目のクエリであり、以下のいずれかの形式で与えられる。

1 p x
2 l r

出力

タイプ 2 のクエリの個数を q として、q 行出力せよ。 i 行目には i 個目のタイプ 2 のクエリに対する答えを出力せよ。


入力例 1

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

出力例 1

1
0
2

はじめ、A = (3, 3, 1, 4, 5) です。

1 個目のクエリでは、(3, 3, 1) において 2 番目に大きい値は 1 であり、3, 3, 1 の中に 1 は 1 個あるので 1 を出力します。

2 個目のクエリでは、(5) において 2 番目に大きい値は存在しないので 0 を出力します。

3 個目のクエリでは、A = (3, 3, 3, 4, 5) となります。

4 個目のクエリでは、(3, 3, 4) において 2 番目に大きい値は 3 であり、3, 3, 4 の中に 3 は 2 個あるので 2 を出力します。


入力例 2

1 1
1000000000
2 1 1

出力例 2

0

入力例 3

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

出力例 3

0
1
0
2
4

Score: 525 points

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N.

Process Q queries in the order they are given. Each query is of one of the following two types:

  • Type 1: Given in the form 1 p x. Change the value of A_p to x.
  • Type 2: Given in the form 2 l r. print the number of occurrences of the second largest value in (A_l, A_{l+1}, \ldots, A_r). More precisely, print the number of integers i satisfying l \leq i \leq r such that there is exactly one distinct value greater than A_i among A_l, A_{l+1}, \ldots, A_r.

Constraints

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • For type-1 queries, 1 \leq p \leq N.
  • For type-1 queries, 1 \leq x \leq 10^9.
  • For type-2 queries, 1 \leq l \leq r \leq N.
  • There is at least one type-2 query.
  • All input values are integers.

Input

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

N Q
A_1 A_2 \ldots A_N
\text{query}_{1}
\vdots
\text{query}_{Q}

Here, \text{query}_{i} is the i-th query and given in one of the following formats:

1 p x
2 l r

Output

Let q be the number of type-2 queries. Print q lines. The i-th line should contain the response to the i-th type-2 query.


Sample Input 1

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

Sample Output 1

1
0
2

Initially, A = (3, 3, 1, 4, 5).

For the first query, the second largest value in (3, 3, 1) is 1, which appears once in 3, 3, 1, so print 1.

For the second query, there is no second largest value in (5), so print 0.

The third query makes A = (3, 3, 3, 4, 5).

For the fourth query, the second largest value in (3, 3, 4), is 3, which appears twice in 3, 3, 4, so print 2.


Sample Input 2

1 1
1000000000
2 1 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

0
1
0
2
4