Time Limit: 1 sec / Memory Limit: 256 MB
問題文
kagamizは, 紅茶を飲みながら, 次のような問題を解いていた.
"2 つの正の整数の組を次のように並べるとき, (m, n)は何番目にあるか.
(1, 1), (2, 1), (1, 2), (3, 1), (2, 2), (1, 3), (4, 1), (3, 2), (2, 3), (1, 4), (5, 1), ..."
この問題は彼には簡単すぎたので, 彼はこの問題を基に次のような問題を考えた.
"上の様な整数の組で, i 番目の組の成分と j 番目の組の成分をそれぞれ足した組は何番目にあるか.
すなわち, 上記の整数の組のi 番目を(a_i, b_i), j番目を(a_j, b_j)と表すとき, (a_i+a_j, b_i+b_j) は何番目にあるか."
あなたの仕事は, kagamizから出題されたこの問題を解くことである.
入力
i j
- 1行目には正の整数 i, j が空白を区切りとして書かれている.
出力
i 番目の組の成分と j 番目の組の成分をそれぞれ足した組が何番目にあるかを, 1行に出力せよ.
改行を忘れないように注意せよ.
制約
- 1 ≦ i, j ≦ 10^8 整数の組の番号
- i=j となることがある.
入力例 1
1 1
出力例 1
5
1番目の組(1, 1) の成分と1 番目の組(1, 1)の成分をそれぞれ足すと(2, 2) となる.
(2, 2) はこの並びの5 番目の組なので, 5 を出力する.
入力例 2
3 2
出力例 2
13
入力例 3
114 514
出力例 3
1155
(Problem) kagamiz
(Tester) fura2
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
※20:22現在, セット採点がうまく動作していないようです。修正後リジャッジを行います。(恐らくテストケース毎に表示されている結果は正しいです)
※20:35セット採点データを修正し、リジャッジを行いました。正解しているように見えた解答も不正解扱いになっている可能性があります。ご確認ください。ご迷惑をおかけしました。
kyuridenamidaは, お菓子を食べ過ぎて1本の歯を虫歯にしてしまった.
その歯がとても痛むので歯医者さんに治療してもらったところ, 歯の神経のうち N 箇所を治療してもらえた.
kyuridenamidaの歯の神経は, 図1に示すように, 深さがKの完全二分木になっている.
(二分木については, Wikipediaのページなどを参照せよ.)
彼の神経を表す二分木で, 深さが i で左から j 番目の神経を (i,j)と表す(図 2 ).
このとき, 根に当たる神経 (0,1) に, 先祖を遡ってたどり着ける神経を, 虫歯神経と呼ぶこととする.
ただし, 虫歯神経の先祖が既に治療されている場合, その虫歯神経は根の神経 (0, 1) に辿りつけない.
また, (0, 1)自身が治療されていなければ, (0, 1) が自身にたどり着けるものとする.
根に辿り着ける虫歯神経の個数の総和を歯の痛みとする.
あなたの仕事は, kyuridenamidaの虫歯の情報が与えらるので, その歯の痛みをkyuridenamidaに教えて上げることである.
入力
K N p_1 q_1 p_2 q_2 . . . p_N q_N
- 1 行目には, 神経の深さを表す整数Kが書かれている.
- 2 行目には, 治療された神経の数を表す整数Nが書かれている.
- 続く N 行には, 治療済みの神経の情報をあらわす, 整数 p_iと q_i (1 ≦ i ≦ N) が空白区切りで書かれている.
これは, 場所 (p_i,q_i) の神経が治療されていることを表す.
出力
(答えが 32 bit整数型に収まらない可能性があることに注意せよ.)
制約
- 1 ≦ K ≦ 50 歯の神経の深さ
- 0 ≦ N ≦ 10^5 治療済みの神経の個数
- 0 ≦ p_i ≦ K 治療済み神経 i の深さ
- 1 ≦ q_i ≦ 2^{p_i} 治療済み神経 i の, 深さ p_iでの位置
- p_i = p_j であれば, q_i ≠ q_jが保証されている.
部分点
配点の 40% 分については, N ≦ 1000 を満たす.
入力例 1
1 1 1 1
出力例 1
2
入力例 2
9 0
出力例 2
1023
入力例 3
3 2 1 2 3 7
出力例 3
8
ヒント
ここで, 図の青丸は治療された神経を表し, 赤の×印は根に辿り着ける虫歯神経を表す.
(Problem) kagamiz
(Tester) fura2
Time Limit: 1 sec / Memory Limit: 256 MB
問題文
※20:31現在, この問題もセット採点がうまく動作していないようです。修正後リジャッジを行います。(恐らくテストケース毎に表示されている結果は正しいです)。ご迷惑をおかけします。
※20:35セット採点データを修正し、リジャッジを行いました。正解しているように見えた解答も不正解扱いになっている可能性があります。ご確認ください。ご迷惑をおかけしました。
2 以上 n 以下の正整数 x に対して, 以下の操作が許されている.
- x+1 がn 以下のとき, x + 1 を新たな x とする.
- \sqrt{x} が整数のとき, \sqrt{x} を新たな x とする.
例えば, x = 2 のとき, 3を新しい x とすることができる.
x = 4 のとき, (2,5) のいずれかを新しい x とすることができる.
そこで, kagamizは x=2 として開始し, この操作で許される全ての遷移の仕方を,
少なくともそれぞれ 1 回ずつ以上行って 再び x=2 に戻ってくるような方法のうち, 操作回数が最小になる場合にかかる操作回数を知りたい.
あなたの仕事は, そのような方法が存在するかどうかと, 存在するならばその最小操作回数をkagamizに教えてあげることである.
入力
n入力では, 整数 n が 1 つだけ与えられる.
出力
もし, そのような方法が存在しない場合は
-1
を出力せよ.もしどのような操作も許されていない場合, 一切操作を行わなくても "この操作で許される全ての遷移の仕方を, 少なくともそれぞれ 1 回ずつ以上行った", とみなしてよい.
制約
- 2 ≦n ≦ 10^{12} たどり着ける数の上限値
入力例 1
9
出力例 1
10
- 2→3
- 3→4
- 4→5
- 5→6
- 6→7
- 7→8
- 8→9
- 4→2
- 9→3
入力例 2
5
出力例 2
-1
入力例 3
4
出力例 3
3
(Problem) kyuridenamida
(Tester) fura2
Time Limit: 1 sec / Memory Limit: 256 MB
問題文
kagamizは, ペットのミズゴロウと毎日家から K m 離れた公園まで散歩をしている.
このとき, kagamizは往路と復路で, ミズゴロウと次のようなゲームをする:
- 1 m 先か 2 m 先にマシュマロを投げ, ミズゴロウがそのマシュマロをキャッチする.
- 投げた先にkagamizも移動し, 同じ操作を繰り返す.
ただし, このときに, 公園より後の地点や, 家より前の地点にマシュマロを投げることは許されない.
また, 往路でのスタート地点は 家から 0 mの地点, 復路でのスタート地点は 家から K mの地点であり, ここには必ず訪れることとなる.
しかし, 往路のうち P 個の地点, 復路のうち Q 個の地点, 合計 R 個の地点には水たまりがあり,
せっかくのマシュマロが濡れてしまい, ミズゴロウが水たまりで遊ぶためそこから動かなくなってしまう.
したがって, 水たまりがある地点にマシュマロを投げることはしない.
このとき, kagamizとミズゴロウが, 全ての地点にマシュマロを投げ散歩をする方法は何通りあるだろうか.
あなたの仕事は, K , R , および水たまりができる地点の情報が与えられるとき, K m ある地点すべてにマシュマロを投げて, 散歩をする方法の数を 100000 で割ったあまりを kagamizに教えてあげることである.
入力
K R t_1 a_1 t_2 a_2 . . . t_R a_R
- 1 行目には, 整数 K , R が空白を区切りとして書かれている.
- 続く R 行には, 水たまりの情報が書かれている.
i + 1 行目 (1 ≦ i ≦ R) には, 1, 2 のいずれかの整数の後に, 整数 a_i が空白区切りで書かれている.
i + 1 行目の最初の数が 1 (t_i = 1) であるとき, 往路の家から a_i m離れた場所に水たまりがあることを示し,
i + 1 行目の最初の数が 2 (t_i = 2) であるとき, 復路の家から a_i m離れた場所に水たまりがあることを示す.
出力
制約
- 1 ≦ K ≦ 3000000 家から公園までの距離
- 0 ≦ R ≦ 100000 往路または復路にある水たまりの個数の総数
- 1 ≦ a_i ≦ K 家から水たまりがある地点までの距離
- 往路か復路を表す整数 t_i は, 必ず 1,2 のいずれかである.
部分点
配点の 30% 分については, R = 0 を満たす.
配点の 20% 分については, K ≦ 15 を満たす.
配点の 10% 分については, これら 2 つの条件を両方満たす.
配点の 40% 分については, これら 2 つの条件の少なくとも一方を満たす.
※30%+20%+10%+40%=100%という意味ではないことに注意せよ.
入力例 1
3 0
出力例 1
7
入力例 2
14 2 1 9 2 3
出力例 2
7105
入力例 3
1 1 2 1
出力例 3
0復路の出発点は必ず K mの地点であることに注意せよ.
入力例 4
3 2 1 1 2 1
出力例 4
0この入出力例では, 家から 1 m 離れている地点に, 往路・復路ともに水たまりがある.
したがって, すべての地点に訪れる事ができないので, 0 を出力する.
(Problem) kagamiz
(Tester) fura2
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
kagamizは, ハッシュについて勉強をしている.
kagamizはローリングハッシュについて蟻本で学び, ハッシングが文字列探索に有効な手法だということを知った.
そこで, kagamizは, 任意の多重集合についてハッシングすることが出来ないかということを考え, 以下のようなハッシュ関数を考案した.
「
Pを素数とする. ハッシュ化する列を {x_1,x_2,x_3,...,x_n} とし, 全ての x_iについて, j≦iかつ x_j=x_iが成り立つような jの個数をC_iとすると,
(ハッシュ値) = Σx_i^{C_i} mod P
」
このハッシュ関数は容易に衝突ケースが作れてしまうが, ともかくこの関数を用いた以下の問題をあなたに解かせることにした.
問題: 長さNの数列{a_1,a_2,a_3,...,a_N} がある. この数列の Q 個の部分列について, それぞれ前述のハッシュ値を求めなさい.
入力
N Q P a_1 a_2 ... a_N s_1 t_1 s_2 t_2 . . . s_Q t_Q最初に数列の長さ N , ハッシュ値を求めたい連続した部分列の個数 Q , 素数 P が与えられる.
次に, 長さ N の数列 {a_1,a_2,..,a_N} が与えられる.
最後に, Q個の部分列の端点[s_i, t_i]が与えられる.
出力
制約
- 1 ≦ N ≦ 10^5 数列の長さ
- 1 ≦ Q ≦ 10^5 ハッシュ値を求めたい連続した部分列の個数
- 1 ≦ P ≦ 10^9 ハッシュ関数で用いる素数
- 1 ≦ a_i ≦ 10^6 数列の各項の値
- 1 ≦ s_i ≦ t_i ≦ N 各部分列の端点
部分点
配点の 20% 分については, i≠jのときa_i≠a_j を満たす.
入力例 1
10 10 8999 2 1 1 2 1 2 1 2 1 2 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10
出力例 1
2 3 4 8 9 17 18 34 35 67
入力例 2
6 6 2 1 2 3 4 5 6 1 2 2 3 3 4 4 4 5 5 6 6
出力例 2
1 1 1 0 1 0
(Problem) kyuridenamida
(Tester) fura2
kyuridenamida「ところでこの問題文, 全然暗号化じゃないですよね.」