A - ab

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。
S の中で a と b が隣接する箇所があれば Yes を、なければ No を出力してください。(a と b の順序は問いません。)

制約

  • 2 \leq N \leq 100
  • S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

S の中で a と b が隣接する箇所があれば Yes を、なければ No を出力せよ。


入力例 1

3
abc

出力例 1

Yes

文字列 abc は 1 文字目にある a と 2 文字目にある b が隣接しています。よって Yes を出力してください。


入力例 2

2
ba

出力例 2

Yes

文字列 ba は 2 文字目にある a と 1 文字目にある b が隣接しています。(a と b の順番は逆でも良い点に注意してください。)


入力例 3

7
atcoder

出力例 3

No

Score : 100 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.
If there are any adjacent occurrences of a and b in S, print Yes; otherwise, print No. (The order of a and b does not matter.)

Constraints

  • 2 \leq N \leq 100
  • S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

If there are any adjacent occurrences of a and b in S, print Yes; otherwise, print No.


Sample Input 1

3
abc

Sample Output 1

Yes

The string abc has a as the first character and b as the second character, which are adjacent. Thus, print Yes.


Sample Input 2

2
ba

Sample Output 2

Yes

The string ba has a as the second character and b as the first character, which are adjacent. (Note that the order of a and b does not matter.)


Sample Input 3

7
atcoder

Sample Output 3

No
B - 1-2-4 Test

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

3 問の問題からなる試験があり、それぞれの問題の配点は 1 点、2 点、4 点でした。

高橋君、青木君、すぬけ君の 3 人がこの試験を受け、 高橋君は A 点、青木君は B 点を取りました。

すぬけ君は、高橋君と青木君のうち少なくとも一方が解けた問題は解け、 2 人とも解けなかった問題は解けませんでした。

すぬけ君の点数を求めてください。

ただし、この問題の制約下で、すぬけ君の点数は一意に定まる事が証明できます。

制約

  • 0\leq A,B \leq 7
  • A,B は整数

入力

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

A B

出力

すぬけ君の点数を整数で出力せよ。


入力例 1

1 2

出力例 1

3

高橋君は 1 点を取った事から、 1 点の問題のみを正解し、それ以外の 2 問は解けなかったことがわかります。
同様に、青木君は 2 点を取った事から、 2 点の問題のみを正解し、それ以外の 2 問は解けなかったことがわかります。

よって、すぬけ君は 1 点の問題と 2 点の問題を正解し、高橋君と青木君がともに解けなかった 4 点の問題はすぬけ君も解けなかったことになるので、3 点を取ったことがわかります。よって、3 を出力します。


入力例 2

5 3

出力例 2

7

高橋君は 5 点を取った事から、 1 点の問題と 4 点の問題を正解し、 2 点の問題は解けなかったことがわかります。
同様に、青木君は 3 点を取った事から、 1 点の問題と 2 点の問題を正解し、 4 点の問題は解けなかったことがわかります。

よって、3 問すべてについて、高橋君と青木君の少なくとも一方が正解しているため、すぬけ君はすベての問題に正解し、7 点を取ったことがわかります。 よって、7 を出力します。


入力例 3

0 0

出力例 3

0

高橋君と青木君は 2 人ともいずれの問題も解けていません。 よって、すぬけ君もいずれの問題も解けておらず、 0 を出力します。

Score : 100 points

Problem Statement

There was an exam consisting of three problems worth 1, 2, and 4 points.

Takahashi, Aoki, and Snuke took this exam. Takahashi scored A points, and Aoki scored B points.

Snuke solved all of the problems solved by at least one of Takahashi and Aoki, and failed to solve any of the problems solved by neither of them.

Find Snuke's score.

It can be proved that Snuke's score is uniquely determined under the Constraints of this problem.

Constraints

  • 0\leq A,B \leq 7
  • A and B are integers.

Input

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

A B

Output

Print Snuke's score as an integer.


Sample Input 1

1 2

Sample Output 1

3

Since Takahashi scored 1 point, we see that he solved only the 1-point problem and failed to solve the other two.
Similarly, since Aoki scored 2 points, we see that he solved only the 2-point problem and failed to solve the other two.

Therefore, Snuke must have solved the 1- and 2-point problems, but not the 4-point one, which Takahashi and Aoki both failed to solve, for a score of 3 points. Thus, 3 should be printed.


Sample Input 2

5 3

Sample Output 2

7

Since Takahashi scored 5 points, we see that he solved the 1- and 4-point problems but not the 2-point one.
Similarly, since Aoki scored 3 points, we see that he solved the 1- and 2-point problems but not the 4-point one.

Therefore, each of the three problems is solved by at least one of Takahashi and Aoki, so we see that Snuke solved all of the problems, for a score of 7 points. Thus, 7 should be printed.


Sample Input 3

0 0

Sample Output 3

0

Both Takahashi and Aoki solved none of the problems. Therefore, so did Snuke. Thus, 0 should be printed.

C - Magic Square

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

3 以上の奇数 N が与えられます。

N 行 N 列のマス目があり、はじめどのマスも空白です。 今から、以下の手順に従ってこのマス目の各マスに整数を書き込みます。 なお、上から i+1 行目、左から j+1 列目 (0\leq i<N, 0\leq j<N) のマスを (i,j) と表記することとします。

  1. マス (0,\frac{N-1}{2}) に 1 を書き込む。
  2. 次の操作を N^2-1 回繰り返す。
    • 前回整数を書き込んだマスを (r,c)、書き込んだ整数を k としたとき、マス ((r-1) \bmod N, (c+1) \bmod N) が空白ならばそのマスに、そうでなければマス ((r+1) \bmod N,c) に k+1 を書き込む。 ここで、x \bmod N は x を N で割ったあまりを表す。

この手順においてそれぞれのマスに書き込まれる整数を求めてください。 なお、どのマスもちょうど 1 回だけ整数を書き込まれることが証明できます。

制約

  • 3\leq N \leq 99
  • N は奇数

入力

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

N

出力

マス (i,j) に書き込まれる整数を a_{i,j} として、以下の形式で出力せよ。

a_{0,0} a_{0,1} \dots a_{0,N-1}
\vdots
a_{N-1,0} a_{N-1,1} \dots a_{N-1,N-1}

入力例 1

3

出力例 1

8 1 6
3 5 7
4 9 2

以下のように各マスに整数が書き込まれていきます。

  1. マス (0,\frac{3-1}{2})=(0,1) に 1 を書き込む。
  2. マス ((0-1) \bmod 3, (1+1) \bmod 3)=(2,2) は空白なので、そこに 2 を書き込む。
  3. マス ((2-1) \bmod 3, (2+1) \bmod 3)=(1,0) は空白なので、そこに 3 を書き込む。
  4. マス ((1-1) \bmod 3, (0+1) \bmod 3)=(0,1) は空白ではないので、マス ((1+1) \bmod 3,0)=(2,0) に 4 を書き込む。
  5. \vdots

入力例 2

5

出力例 2

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9

Score : 200 points

Problem Statement

You are given an odd number N that is at least 3.

There is a grid with N rows and N columns, where all cells are initially empty. Now, you will write integers in each cell of this grid according to the following procedure. Let (i,j) denote the cell at the (i+1)-th row from the top and (j+1)-th column from the left (0\leq i<N, 0\leq j<N).

  1. Write 1 in cell (0,\frac{N-1}{2}).
  2. Repeat the following operation N^2-1 times:
    • Let (r,c) be the cell where an integer was written last time, and k be the integer written. If cell ((r-1) \bmod N, (c+1) \bmod N) is empty, write k+1 in that cell; otherwise, write k+1 in cell ((r+1) \bmod N,c). Here, x \bmod N denotes the remainder when x is divided by N.

Find the integer that will be written in each cell in this procedure. It can be proved that each cell will have an integer written in it exactly once.

Constraints

  • 3\leq N \leq 99
  • N is an odd number.

Input

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

N

Output

Let a_{i,j} be the integer written in cell (i,j), and print it in the following format:

a_{0,0} a_{0,1} \dots a_{0,N-1}
\vdots
a_{N-1,0} a_{N-1,1} \dots a_{N-1,N-1}

Sample Input 1

3

Sample Output 1

8 1 6
3 5 7
4 9 2

Integers are written in each cell as follows:

  1. Write 1 in cell (0,\frac{3-1}{2})=(0,1).
  2. Cell ((0-1) \bmod 3, (1+1) \bmod 3)=(2,2) is empty, so write 2 there.
  3. Cell ((2-1) \bmod 3, (2+1) \bmod 3)=(1,0) is empty, so write 3 there.
  4. Cell ((1-1) \bmod 3, (0+1) \bmod 3)=(0,1) is not empty, so write 4 in cell ((1+1) \bmod 3,0)=(2,0).
  5. \vdots

Sample Input 2

5

Sample Output 2

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
D - Longest Uncommon Prefix

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。 S の x 文字目 (1 \le x \le N) は S_x です。

i=1,2,\dots,N-1 それぞれについて、以下の条件を全て満たす最大の非負整数 l を求めてください。

  • l+i \le N である。
  • 全ての 1 \le k \le l を満たす整数 k について、 S_{k} \neq S_{k+i} を満たす。

なお、 l=0 は常に条件を満たすことに注意してください。

制約

  • N は 2 \le N \le 5000 を満たす整数
  • S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

N-1 行にわたって出力せよ。そのうち x 行目 (1 \le x < N) には i=x とした場合の答えを整数として出力せよ。


入力例 1

6
abcbac

出力例 1

5
1
2
0
1

この入力では、 S= abcbac です。

  • i=1 のとき、 S_1 \neq S_2, S_2 \neq S_3, \dots ,S_5 \neq S_6 であるため、 最大値は l=5 です。
  • i=2 のとき、 S_1 \neq S_3 ですが S_2 = S_4 であるため、 最大値は l=1 です。
  • i=3 のとき、 S_1 \neq S_4, S_2 \neq S_5 ですが S_3 = S_6 であるため、 最大値は l=2 です。
  • i=4 のとき、 S_1 = S_5 であるため、 最大値は l=0 です。
  • i=5 のとき、 S_1 \neq S_6 であるため、 最大値は l=1 です。

Score : 200 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.

For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:

  • l+i \le N, and
  • for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.

Note that l=0 always satisfies the conditions.

Constraints

  • N is an integer such that 2 \le N \le 5000.
  • S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print (N-1) lines. The x-th (1 \le x < N) line should contain the answer as an integer when i=x.


Sample Input 1

6
abcbac

Sample Output 1

5
1
2
0
1

In this input, S= abcbac.

  • When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
  • When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
  • When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
  • When i=4, we have S_1 = S_5, so the maximum value is l=0.
  • When i=5, we have S_1 \neq S_6, so the maximum value is l=1.
E - Happy New Year!

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

10 進法で表記したときに 0,2 のみからなる正整数のうち、 K 番目に小さいものを求めてください。

制約

  • K は 1 以上 10^{18} 以下の整数

入力

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

K

出力

答えを整数として出力せよ。
ただし、たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要がある。たとえば、 2.34e+22 のような指数表記や、 0523 のような先頭に不要な 0 を付けたような表記は許されない。


入力例 1

3

出力例 1

22

10 進法で表記した時に 0,2 のみからなる正整数を小さい方から並べると、 2,20,22,\dots となります。
このうち K=3 番目である 22 を出力してください。


入力例 2

11

出力例 2

2022

入力例 3

923423423420220108

出力例 3

220022020000202020002022022000002020002222002200002022002200

たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要があることに注意してください。

Score : 300 points

Problem Statement

Among the positive integers that consist of 0's and 2's when written in base 10, find the K-th smallest integer.

Constraints

  • K is an integer between 1 and 10^{18} (inclusive).

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer as an integer.
Here, the exact value must be printed as an integer, even if it is big. Exponential notations such as 2.34e+22, for example, or unnecessary leading zeros such as 0523 are not allowed.


Sample Input 1

3

Sample Output 1

22

The positive integers that consist of 0's and 2's when written in base 10 are 2,20,22,\dots in ascending order.
The (K=) 3-rd of them, which is 22, should be printed.


Sample Input 2

11

Sample Output 2

2022

Sample Input 3

923423423420220108

Sample Output 3

220022020000202020002022022000002020002222002200002022002200

Note that the exact value of the answer must be printed as an integer, even if it is big.