問題文

文字列 S が与えられます。S の Prefix Array を求めなさい。

ただし、Prefix Arrayとは、Suffix Array (リンク先は Wikipedia「接尾辞配列」) の定義における「接尾辞」を「接頭辞」に変更したものです。

(具体例は下記の入出力例 1 で確認できます。)

制約

• 1 ≦ |S| ≦ 100,000
• S は小文字アルファベットのみからなる。

入力例 1

chokudai

出力例 1

1
2
3
4
5
6
7
8

chokudai のすべての接尾辞を辞書順にソートすると、以下のようになります。

• c
• ch
• cho
• chok
• choku
• chokud
• chokuda
• chokudai

問題文

正整数 N が与えられます。A^2 が N を超えないような最大の整数 A を出力してください。

制約

• 1 ≦ N ≦ 10^9

入力例 1

10

出力例 1

3

入力例 2

100

出力例 2

10

問題文

整数 M を 11 で割った余りは、M の下から奇数桁目の数の和 から M の下から偶数桁目の数の和 を引いた値を 11 で割った余りと一致します。

整数 N が与えられます。N を 11 で割った余りを出力してください。

制約

• 1 ≦ N ≦ 10^9

入力例 1

123456

出力例 1

3

(2 + 4 + 6) - (1 + 3 + 5) = 3 となります。

入力例 2

90909

出力例 2

5

(9 + 9 + 9) - (0 + 0) = 27 となり、これを 11 で割った余りは 5 です。

問題文

10^{10^{10}} 以下のすべての正整数を、文字列として見たときに辞書順で小さい順に並べた列を考えます。この列の先頭から N 番目の整数を求めてください。

制約

• 1 ≦ N ≦ 100,000

入力例 1

2

出力例 1

10

問題文

整数 N が与えられます。FizzBuzz問題 (リンク先は Wikipedia「Fizz Buzz」) を解いてください。 ただし、通常のFizzBuzz問題においては

• 3 の倍数に対し Fizz
• 5 の倍数に対し Buzz

と出力しますが、今回は、

• 2 の倍数に対し a
• 3 の倍数に対し b
• 4 の倍数に対し c
• 5 の倍数に対し d
• 6 の倍数に対し e

と出力してください。 (より詳しくは、出力例 1 をご覧ください。)

制約

• 1 ≦ N ≦ 1,000

入力例 1

20

出力例 1

1
a
b
ac
d
abe
7
ac
b
ad
11
abce
13
a
bd
ac
17
abe
19
acd

7 行目と 10 行目の出力について述べます。

• 7 行目: 7 は 2,3,4,5,6 のいずれの倍数でもないため、7 と出力します。
• 10 行目: 10 は 2 と 5 の倍数であるため、ad と出力します。

問題文

整数 X に対し、値 f(X) を以下のように定義します。

• X ≧ 10^{16} のとき、f(X) = 0
• 上記以外で X ≦ 1 のとき、f(X) = 0
• 上記以外で X が偶数のとき、 f(X) = f(X/2) + 1
• 上記以外のとき、f(X) = f(3X + 1) + 1

整数 P が与えられます。f(N) = P となるような 10^{16} 以下の正整数 N をいずれか 1 つ出力してください。

制約

• 0 ≦ P ≦ 1,000

入力例 1

5

出力例 1

5

入力例 2

1000

出力例 2

1789997546303

問題文

文字列 S が与えられます。S に含まれる文字をそれぞれ一度ずつ使い、何個かの回文を作ることを考えます。例えば S = aaab のとき、二つの回文 aba と a を作ることができます。このように、文字は自由な順序で使用することができ、S に複数回現れる文字は合計でその回数だけ使用します。

長さ L の回文を 1 個作るごとに、L^2 のスコアが得られます。最大で合計いくつのスコアを得ることができるでしょうか？

制約

• 1 ≦ |S| ≦ 100,000
• S は小文字アルファベットのみからなる。

入力例 1

aaba

出力例 1

10

aaba からは二つの回文 aba と a を作ることができます。このときに得られる合計スコアは 9+1=10 であり、これが得られる最大の値です。

問題文

N 枚のコインがあります。高橋君と青木君は、以下の操作を高橋君から始めて交互に繰り返します。

• 整数 k (k≧0) を選び、コインを 8^k 枚取り除く。ただし、取り除く枚数が残っているコインの枚数を超えるような k を選ぶことはできない。

先に操作を行えなくなった者の負けです。両者が最適に行動するとき、どちらが勝つでしょうか？

制約

• 1 ≦ N ≦ 10^{18}

入力例 1

15

出力例 1

Lose

入力例 2

10000

出力例 2

Win