A - Alternately

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 人が一列に並んでいます。列の状態は長さ N の文字列 S で与えられ、前から i 番目の人は S の i 文字目が M のとき男性、F のとき女性です。

男女が交互に並んでいるかどうか判定してください。

男性同士が隣り合う箇所も女性同士が隣り合う箇所も存在しないとき、かつ、そのときに限り、男女が交互に並んでいるといいます。

制約

  • 1 \leq N \leq 100
  • N は整数である
  • S は M および F のみからなる長さ N の文字列である

入力

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

N
S

出力

男女が交互に並んでいるとき Yes、そうでないとき No と出力せよ。

入力例 1

6
MFMFMF

出力例 1

Yes

男性同士が隣り合う箇所も女性同士が隣り合う箇所も存在せず、男女が交互に並んでいます。

入力例 2

9
FMFMMFMFM

出力例 2

No

入力例 3

1
F

出力例 3

Yes

Score : 100 points

Problem Statement

There is a row of N people. They are described by a string S of length N. The i-th person from the front is male if the i-th character of S is M, and female if it is F.

Determine whether the men and women are alternating.

It is said that the men and women are alternating if and only if there is no position where two men or two women are adjacent.

Constraints

  • 1 \leq N \leq 100
  • N is an integer.
  • S is a string of length N consisting of M and F.

Input

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

N
S

Output

Print Yes if the men and women are alternating, and No otherwise.

Sample Input 1

6
MFMFMF

Sample Output 1

Yes

There is no position where two men or two women are adjacent, so the men and women are alternating.

Sample Input 2

9
FMFMMFMFM

Sample Output 2

No

Sample Input 3

1
F

Sample Output 3

Yes
B - Move Right

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

横一列に 4 つのマスが並んでいます。

各文字が 0 または 1 である長さ 4 の文字列 S が与えられます。
S の i 文字目が 1 であるとき、左から i 番目のマスには 1 人の人がおり、
S の i 文字目が 0 であるとき、左から i 番目のマスには人がいません。

全ての人が一斉に、1 つ右隣のマスへ移動します。この移動により、もともと右端のマスにいた人は消えます。

移動後の各マスに人がいるかどうかを、S と同様のルールで文字列として出力してください。

制約

  • S は 0, 1 のみからなる長さ 4 の文字列

入力

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

S

出力

長さ 4 の文字列であって、移動後、左から i 番目のマスに人がいるならば i 文字目が 1、いないならば 0 であるようなものを出力せよ。

入力例 1

1011

出力例 1

0101

移動により、左から 1 番目のマスにいた人は左から 2 番目のマスに、
左から 3 番目のマスにいた人は左から 4 番目のマスに移動し、
左から 4 番目のマス(右端のマス)にいた人は消えます。

入力例 2

0000

出力例 2

0000

入力例 3

1111

出力例 3

0111

Score : 100 points

Problem Statement

There are 4 squares lined up horizontally.

You are given a string S of length 4 consisting of 0 and 1.
If the i-th character of S is 1, there is a person in the i-th square from the left;
if the i-th character of S is 0, there is no person in the i-th square from the left.

Now, everyone will move to the next square to the right simultaneously. By this move, the person who was originally in the rightmost square will disappear.

Determine if there will be a person in each square after the move. Print the result as a string in the same format as S. (See also Sample Input / Output for clarity.)

Constraints

  • S is a string of length 4 consisting of 0 and 1.

Input

Input is given from Standard Input in the following format:

S

Output

Print a string of length 4 such that the i-th character is 1 if there will be a person in the i-th square from the left after the move, and 0 otherwise.

Sample Input 1

1011

Sample Output 1

0101

After the move, the person who was originally in the 1-st square will move to the 2-nd square,
the person in the 3-rd square to the 4-th square,
and the person in the 4-th square will disappear.

Sample Input 2

0000

Sample Output 2

0000

Sample Input 3

1111

Sample Output 3

0111
C - 3^A

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 M が与えられます。 以下の条件を全て満たす正整数 N と非負整数列 A=(A_1,A_2,\ldots,A_N) を一つ求めてください。

  • 1\le N\le 20
  • 0\le A_i\le 10 (1\le i\le N)
  • \displaystyle \sum_{i=1}^N 3^{A_i}=M

ただし、制約下では条件を満たす N と A の組が必ず存在することが証明できます。

制約

  • 1\le M\le 10^5

入力

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

M

出力

以下の形式で条件を満たす N と A を出力せよ。

N
A_1 A_2 \ldots A_N

なお、条件を満たす N と A の組が複数存在する場合は、どれを出力しても正答となる。

入力例 1

6

出力例 1

2
1 1

N=2 、A=(1,1) とすると \displaystyle \sum_{i=1}^N 3^{A_i}=3+3=6 より全ての条件を満たします。

他に N=4 、 A=(0,0,1,0) なども条件を満たします。

入力例 2

100

出力例 2

4
2 0 2 4

入力例 3

59048

出力例 3

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

1\le N\le 20 という制約に注意してください。

Score : 200 points

Problem Statement

You are given a positive integer M. Find a positive integer N and a sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) that satisfy all of the following conditions:

  • 1 \le N \le 20
  • 0 \le A_i \le 10 (1 \le i \le N)
  • \displaystyle \sum_{i=1}^N 3^{A_i} = M

It can be proved that under the constraints, there always exists at least one such pair of N and A satisfying the conditions.

Constraints

  • 1 \le M \le 10^5

Input

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

M

Output

Print N and A satisfying the conditions in the following format:

N
A_1 A_2 \ldots A_N

If there are multiple valid pairs of N and A, any of them is acceptable.

Sample Input 1

6

Sample Output 1

2
1 1

For example, with N=2 and A=(1,1), we have \displaystyle \sum_{i=1}^N 3^{A_i} = 3+3=6, satisfying all conditions.

Another example is N=4 and A=(0,0,1,0), which also satisfies the conditions.

Sample Input 2

100

Sample Output 2

4
2 0 2 4

Sample Input 3

59048

Sample Output 3

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

Note the condition 1 \le N \le 20.
D - Typing

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は英小文字からなる文字列 S をキーボードで入力しようとしました。

高橋君は画面を見ずにキーボードだけを見てタイピングをしていました。

誤って別の英小文字を入力してしまったときにはその直後にバックスペースキーを押しましたが、バックスペースキーが壊れていたため誤って入力された文字は消去されず、実際に入力された文字列は文字列 T となりました。

また、英小文字以外のキーを誤って押してしまうことはありませんでした。

T のうち高橋君が誤って入力した文字でないものを正しく入力された文字であると定めます。

正しく入力された文字が T の何文字目であるか答えてください。

制約

  • S, T は長さ 1 以上 2 \times 10^5 以下の英小文字からなる文字列
  • T は問題文中の手続きにより得られる文字列

入力

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

S
T

出力

S の長さを |S| として、正しく入力された文字が A_1, A_2, \ldots, A_{|S|} 文字目であるとき A_1, A_2, \ldots, A_{|S|} の値をこの順に空白区切りで出力せよ。

ただし、出力は昇順になるようにせよ。すなわち、各 1 \leq i \leq |S| - 1 に対して A_i < A_{i + 1} を満たすようにせよ。

入力例 1

abc
axbxyc

出力例 1

1 3 6

高橋君のタイピングの一連の流れは以下のようになります。

  • a を入力する。
  • b を入力しようとするが、誤って x を入力してしまう。
  • バックスペースキーを押すが、文字の削除は行われない。
  • b を入力する。
  • c を入力しようとするが、誤って x を入力してしまう。
  • バックスペースキーを押すが、文字の削除は行われない。
  • c を入力しようとするが、誤って y を入力してしまう。
  • バックスペースキーを押すが、文字の削除は行われない。
  • c を入力する。

正しく入力された文字は 1, 3, 6 文字目です。

入力例 2

aaaa
bbbbaaaa

出力例 2

5 6 7 8

入力例 3

atcoder
atcoder

出力例 3

1 2 3 4 5 6 7

高橋君が誤った文字を入力することはありませんでした。

Score: 200 points

Problem Statement

Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.

He was typing while looking only at the keyboard, not the screen.

Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.

He did not mistakenly press any keys other than those for lowercase English letters.

The characters in T that were not mistakenly typed are called correctly typed characters.

Determine the positions in T of the correctly typed characters.

Constraints

  • S and T are strings of lowercase English letters with lengths between 1 and 2 \times 10^5, inclusive.
  • T is a string obtained by the procedure described in the problem statement.

Input

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

S
T

Output

Let |S| be the length of S. If the correctly typed characters are the A_1-th, A_2-th, \ldots, A_{|S|}-th characters of T, print the values of A_1, A_2, \ldots, A_{|S|} in this order, separated by spaces.

Ensure that the output is in ascending order. That is, A_i < A_{i + 1} should hold for each 1 \leq i \leq |S| - 1.

Sample Input 1

abc
axbxyc

Sample Output 1

1 3 6

The sequence of Takahashi's typing is as follows:

  • Type a.
  • Try to type b but mistakenly type x.
  • Press the backspace key, but the character is not deleted.
  • Type b.
  • Try to type c but mistakenly type x.
  • Press the backspace key, but the character is not deleted.
  • Try to type c but mistakenly type y.
  • Press the backspace key, but the character is not deleted.
  • Type c.

The correctly typed characters are the first, third, and sixth characters.

Sample Input 2

aaaa
bbbbaaaa

Sample Output 2

5 6 7 8

Sample Input 3

atcoder
atcoder

Sample Output 3

1 2 3 4 5 6 7

Takahashi did not mistakenly type any characters.
E - digitnum

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

整数 N が与えられるので、以下の問題を解いてください。

f(x)= ( x 以下の正整数で、 x と桁数が同じものの数) とします。
f(1)+f(2)+\dots+f(N) を 998244353 で割った余りを求めてください。

制約

  • N は整数
  • 1 \le N < 10^{18}

入力

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

N

出力

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

入力例 1

16

出力例 1

73
  • 1 以上 9 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 1,2,\dots,x です。
    • これより、 f(1)=1,f(2)=2,...,f(9)=9 となります。
  • 10 以上 16 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 10,11,\dots,x です。
    • これより、 f(10)=1,f(11)=2,...,f(16)=7 となります。

結局、求める答えは 73 です。

入力例 2

238

出力例 2

13870

入力例 3

999999999999999999

出力例 3

762062362

998244353 で割った余りを求めることに注意してください。

Score : 300 points

Problem Statement

Given an integer N, solve the following problem.

Let f(x)= (The number of positive integers at most x with the same number of digits as x).
Find f(1)+f(2)+\dots+f(N) modulo 998244353.

Constraints

  • N is an integer.
  • 1 \le N < 10^{18}

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer as an integer.

Sample Input 1

16

Sample Output 1

73
  • For a positive integer x between 1 and 9, the positive integers at most x with the same number of digits as x are 1,2,\dots,x.
    • Thus, we have f(1)=1,f(2)=2,...,f(9)=9.
  • For a positive integer x between 10 and 16, the positive integers at most x with the same number of digits as x are 10,11,\dots,x.
    • Thus, we have f(10)=1,f(11)=2,...,f(16)=7.

The final answer is 73.

Sample Input 2

238

Sample Output 2

13870

Sample Input 3

999999999999999999

Sample Output 3

762062362

Be sure to find the sum modulo 998244353.