Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
文字列 S が与えられます。S の Prefix Array を求めなさい。
ただし、Prefix Arrayとは、Suffix Array (リンク先は Wikipedia「接尾辞配列」) の定義における「接尾辞」を「接頭辞」に変更したものです。
(具体例は下記の入出力例 1 で確認できます。)
制約
- 1 ≦ |S| ≦ 100,000
- S は小文字アルファベットのみからなる。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の Prefix Array を |S| 行に出力せよ。
入力例 1
chokudai
出力例 1
1 2 3 4 5 6 7 8
chokudai
のすべての接尾辞を辞書順にソートすると、以下のようになります。
c
ch
cho
chok
choku
chokud
chokuda
chokudai
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
正整数 N が与えられます。A^2 が N を超えないような最大の整数 A を出力してください。
制約
- 1 ≦ N ≦ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N
出力
A^2 が N を超えないような最大の整数 A を出力せよ。
入力例 1
10
出力例 1
3
入力例 2
100
出力例 2
10
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
整数 M を 11 で割った余りは、M の下から奇数桁目の数の和
から M の下から偶数桁目の数の和
を引いた値を 11 で割った余りと一致します。
整数 N が与えられます。N を 11 で割った余りを出力してください。
制約
- 1 ≦ N ≦ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N を 11 で割った余りを出力せよ。
入力例 1
123456
出力例 1
3
(2 + 4 + 6) - (1 + 3 + 5) = 3 となります。
入力例 2
90909
出力例 2
5
(9 + 9 + 9) - (0 + 0) = 27 となり、これを 11 で割った余りは 5 です。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
10^{10^{10}} 以下のすべての正整数を、文字列として見たときに辞書順で小さい順に並べた列を考えます。この列の先頭から N 番目の整数を求めてください。
制約
- 1 ≦ N ≦ 100,000
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
2
出力例 1
10
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 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
入力
入力は以下の形式で標準入力から与えられる。
N
出力
解答を N 行に出力せよ。
入力例 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
と出力します。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 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
入力
入力は以下の形式で標準入力から与えられる。
P
出力
題意を満たす整数 N を出力せよ。そのような整数が複数存在するときは、そのうちのいずれを出力してもよい。なお、この問題の制約下でそのような整数が必ず存在することが示せる。
入力例 1
5
出力例 1
5
入力例 2
1000
出力例 2
1789997546303
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
文字列 S が与えられます。S に含まれる文字をそれぞれ一度ずつ使い、何個かの回文を作ることを考えます。例えば S = aaab
のとき、二つの回文 aba
と a
を作ることができます。このように、文字は自由な順序で使用することができ、S に複数回現れる文字は合計でその回数だけ使用します。
長さ L の回文を 1 個作るごとに、L^2 のスコアが得られます。最大で合計いくつのスコアを得ることができるでしょうか?
制約
- 1 ≦ |S| ≦ 100,000
- S は小文字アルファベットのみからなる。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
得られる最大の合計スコアを出力せよ。
入力例 1
aaba
出力例 1
10
aaba
からは二つの回文 aba
と a
を作ることができます。このときに得られる合計スコアは 9+1=10 であり、これが得られる最大の値です。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 枚のコインがあります。高橋君と青木君は、以下の操作を高橋君から始めて交互に繰り返します。
- 整数 k (k≧0) を選び、コインを 8^k 枚取り除く。ただし、取り除く枚数が残っているコインの枚数を超えるような k を選ぶことはできない。
先に操作を行えなくなった者の負けです。両者が最適に行動するとき、どちらが勝つでしょうか?
制約
- 1 ≦ N ≦ 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
高橋君が勝つ場合は Win
、青木君が勝つ場合は Lose
と出力せよ。
入力例 1
15
出力例 1
Lose
入力例 2
10000
出力例 2
Win