A - Code Formula 2015

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

Code Formulaは、非常に大きなコンテストです。 来年の予選では、 A 回の予選で、上位 B 人を本選に招待する予定です。 毎回の予選では参加者の重複がないものとして、合計何人を本選に招待することになるかを出力しなさい。

入力

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

A B
  • 1 行目には、予選の回数を表す整数 A (1≦A≦1000) 、1 回の予選での予選通過人数を表す整数 B(1≦B≦1000) が、スペース区切りで与えられる。

出力

本選の招待人数を 1 行で出力せよ。出力の末尾には改行をいれること。

入力例1

1000 1000

出力例1

1000000

来年のCode Formulaは大盛況です。 1,000,000 人で本選を行います。

入力例2

1 1

出力例2

1

本選参加者が 1 人しかいない場合でも、本選を行います。

Source Name

Code Formula 2014 本戦
B - 3歩進んで2歩下がる

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君は、奇数日目に 3 歩前に進み、偶数日目に 2 歩後ろに下がります。

1 歩の距離は、前に進むときも、後ろに下がるときも、同じ距離です。

1 日目から n 日目の間に、高橋君が何歩分前に進んだかを出力してください。

入力

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

n
  • 1 行目には、日数を表す整数 n (1 ≦ n ≦ 10^{15}) が与えられる。

出力

高橋君が何歩分前に進んだかを 1 行で出力せよ。出力の末尾には改行をいれること。

入力例1

6

出力例1

3

高橋君は、1, 3, 5 日目に 3 歩進み、2, 4, 6 日目に 2 歩戻ります。 よって、3-2+3-2+3-2=3 歩分、前に進みます。

入力例2

999999999999999

出力例2

500000000000002

高橋君は、どれだけ長い期間でも、 3 歩進んで 2 歩戻り続けます。

Source Name

Code Formula 2014 本戦
C - 次世代SNS

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

あなたは、とあるSNSを作ろうとしています。

このSNSでは、@usernameという形式で、特定のユーザーにメッセージを送ることが可能であり、1 つの発言に複数のユーザーを指定することで、複数のユーザーに同時にメッセージを送ることが可能になります。

このSNSは、以下のようなルールに従っています。

  • 書き込まれるメッセージは、半角小文字アルファベット、半角スペース、@のみを含む。
  • 書き込まれたメッセージに@が含まれていた場合、@直後の、アルファベットのみで構成される文字列のうち、最も長い文字列をユーザー名として扱い、そのユーザーにメッセージを届ける。
  • @の直後がアルファベットでなかった場合は無視する。
  • 複数回同じユーザーが指定されても、メッセージは 1 回届ければ良い。

あなたは、このシステムを実装するために、書き込まれたメッセージに対し、メッセージを届けるべきユーザーを列挙するプログラムを作りたいです。

メッセージを送るべきユーザーを全て出力しなさい。なお、ユーザーが複数いる場合は、辞書順で出力しなさい。

入力

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

S
  • 1 行目には、書き込まれるメッセージを表す文字列 S(1≦|S|≦140) が与えられる。
  • 文字列 S には、小文字アルファベット、 、@以外の文字は含まれない。

出力

メッセージを送るべきユーザーを、 1 行ずつ全て出力しなさい。なお、ユーザーが複数いる場合は、辞書順で出力しなさい。

入力例1

@codeformula why is this contest so easy

出力例1

codeformula

codeformulaさんへのメッセージです。半角スペースが挟まれているので、why以降をユーザー名として認識することはありません。

また、@を出力する必要はありません。

入力例2

myon @@c @a @aba@a @@bb bbb @@@@@ @a test  @ space  aaa test @a@a  test@takoyaki

出力例2

a
aba
bb
c
takoyaki

aが何度も指定されていますが、一度だけ出力する必要があります。

また、ユーザ名は辞書順で出力する必要があります。

入力例3

no atmark

出力例3



            
メッセージを送るべきユーザーがいない場合、何も出力しないで構いません。


        

    




			


			
				

				
Source Name

				Code Formula 2014 本戦
			
		

	
		

		

			D - 映画の連続視聴
			

			
Time Limit: 2 sec / Memory Limit: 64 MB


			

				







問題文



高橋君は、同じ種類の映画を何度も見るのが大好きです。同じ種類の映画を連続で見る事で、より多くの幸福度を得ることが出来ます。



ですが、高橋君は忘れっぽいので、一度違う種類の映画を見ると、それ以前に見た映画のことを、綺麗さっぱり忘れてしまいます。以前見た種類の映画を見ても、直前に見た種類の映画以外は、初めてその種類の映画を見た時と同じだけの幸福度を得ます。



高橋君は、 k 回連続で同じ種類の映画を見た時、その回に H_k の幸福度を得ます。つまり、同じ種類の映画を連続して k回 見た場合、最後には 1 回目から合わせて H_1 + H_2 + … + H_kの幸福度を得ることになります。



高橋君が、 k 回連続で同じ種類の映画を見た時にその回に得られる幸福度 H_k と、本日の映画のスケジュールが与えられるので、高橋君が本日映画を見ることで得られる幸福度の和の最大値を求めてください。



なお、映画の途中から見たり、映画の途中で見るのをやめたりすることはできません。



また、 2 つの映画の放送時間に重複する部分がなければ、間に全く空き時間がなくても、どちらの映画も見ることが可能であることとします。

















入力



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



N
H_1 H_2 … H_N
M_1 S_1 E_1
M_2 S_2 E_2
:
M_N S_N E_N




    

	
  • 1 行目には、本日上映される予定の映画の本数を表す整数 N (1≦N≦3000) が与えられる。
    • 

	
  • 2 行目には、N 個の数字が与えられる。このうち i (1≦i≦N) 番目の整数 H_i(1≦H_i≦10000) は、i 回連続で映画を見た時に、その回に得られる幸福度を表す。
    • 

	
  • i＜j の時、H_i≦H_j が保障されている。
    • 

	
  • 3 行目から、N 行は、本日上映される予定の映画の情報を表す。このうち i (1≦i≦N) 行目には、i 番目の映画の種類を表す整数 M_i(1≦M_i≦N) 、上映開始時間と終了時間を表す整数 S_i, E_i(0≦S_i＜E_i≦100000) が、スペース区切りで与えられる。
    • 














出力



高橋君が本日映画によって得られる幸福度の和の最大値を 1 行で出力せよ。出力の末尾には改行をいれること。
















入力例1



4
100 200 300 400
1 0 120
1 15 135
2 10 40
1 240 330













出力例1



300




1番目の映画と4番目の映画を見れば2連続で種類1の映画を見ることになり、100 + 200 = 300の幸福度を得ることになります。














入力例2



10
100 200 250 250 300 400 540 600 650 680
1 10 130
2 0 900
1 20 110
1 200 230
3 200 210
2 201 220
2 240 300
3 0 90
1 250 320
2 330 400













出力例2



650










			


			
				

				
Source Name

				Code Formula 2014 本戦
			
		

	
		

		

			E - ab文字列
			

			
Time Limit: 2 sec / Memory Limit: 64 MB


			

				







問題文



以下のような漸化式を考えます。



    

	
  • F_{1,0} =  b
    • 

	
  • F_{2,0} =  a
    • 

	
  • n≧3 かつ 0≦k<2^{n-2} かつ k が偶数のとき、F_{n,k} = F_{n-1,floor(k/2)} + F_{n-2,floor(k/4)}
    • 

	
  • n≧3 かつ 0≦k<2^{n-2} かつ k が奇数のとき、F_{n,k} = F_{n-2,floor(k/4)} + F_{n-1,floor(k/2)}
    • 





以上の漸化式で定義されない F_{n,k} に関しては、考慮しないものとします。



文字列 S が与えられます。この文字列は、F_{p,q} の形で表せることが解っています。



S = F_{p,q} となる p,q のうち、1 つを出力してください。



ただし、floor(n) は、n の床関数とします。
















入力



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



S




    

	
  • 1 行目には、文字列 S (1 ≦ |S| ≦ 20000) が与えられる。
    • 














出力



S = F_{p,q} となる p,q のうち、1 つを、スペース区切りで出力せよ。出力の末尾には改行をいれること。
















入力例1



babaa













出力例1



5 5




    

	
  • F_{1,0} =  b
    • 

	
  • F_{2,0} =  a
    • 

	
  • F_{3,1} = F_{1,0} + F_{2,0} =  ba
    • 

	
  • F_{4,2} = F_{3,1} + F_{2,0} =  baa
    • 

	
  • F_{5,5} = F_{3,1} + F_{4,2} =  babaa
    • 





となるため、p=5, q=5 が、求める答えの 1 つとなります。














入力例2



aababaabaababaabaababaababaabaabab













出力例2



9 44




解は複数ある場合もあることに注意してください。









			


			
				

				
Source Name

				Code Formula 2014 本戦
			
		

	
		

		

			F - 100個の円
			

			
Time Limit: 2 sec / Memory Limit: 64 MB


			

				







問題文



100 個の円があります。 このうち k 番目の円の半径は k であることがわかっています。



これを、1500 × 1500 の正方形の中に敷き詰めることにしました。



敷き詰め方の一例を出力してください。



なお、円の中心の座標は、x 座標、 y 座標ともに、整数でないといけないことに注意してください。
















入力



入力は与えられない。












出力



出力形式は、以下のようなものである。



X_1 Y_1
X_2 Y_2
:
X_{100} Y_{100}




円の情報を 100 行で出力せよ。



k 行目には、k 番目の円の中心の x 座標と y 座標を表す X_k, Y_k を、スペース区切りで 1 行で出力せよ。



なお、出力は整数しか認められず、全ての円が、座標 (0,0) と (1500,1500) を結ぶ線分を対角線とする正方形の内部に収まっている必要がある。



円や正方形が接していても良いが、重なることは許されない。














出力例1



1 1
5 10
500 30
:




以上の例では、半径 1 の円を座標 (1,1) に、半径 2 の円を座標 (5,10) に、半径 3 の円を座標 (500,30) に置いています。



上記のような形で、 100 行出力するのが、今回の課題です。









			


			
				

				
Source Name

				Code Formula 2014 本戦
			
		

	
		

		

			G - ノイハの塔
			

			
Time Limit: 2 sec / Memory Limit: 64 MB


			

				







問題文



「ハノイの塔」という有名なパズルがあります。
ハノイの塔は 3 つの杭と、中央に穴の空いたサイズが相異なる N 個の円盤からなるパズルです。
3 つの杭には 1 から 3 の番号が付けられています。また、 i 番目に小さい円盤の半径は i センチメートルです。



初め、全ての円盤は杭 1 に、サイズが大きい順に下から積み重ねられて、「塔」を形成しています。杭 2, 3 には何も置いていません。
プレイヤーは 1 回の操作で、ある杭の塔の一番上にある円盤を、他の杭に移動させて、移動先の杭の塔の一番上に積み重ねるという事ができます。
このとき、小さい円盤の上に大きい円盤を置くことはできません。
ハノイの塔のゴールはできるだけ少ない回数の操作で、高さNの塔を杭 2 もしくは杭 3 に移すことです。



高橋君は久しぶりにこのパズルを遊ぼうと思い、押し入れの奥からハノイの塔のおもちゃを探しだしました。
しかし、だれかがいたずらをしたようで、N 個全ての円盤がバラバラの順番で杭 1 に積まれていました。
そこで高橋君はそのバラバラの状態から開始して、「小さい円盤の上に大きい円盤を置いてはならない」というルールを無視して操作し、いずれかの杭に全ての円盤がサイズが大きい順に下から積み重なるように移動させる、という別のパズルを遊ぶことにしました。



あらかじめ、杭 1 に積み重ねられている円盤のサイズの情報が与えられるので、いずれかの杭(杭 1 でもよい)に全ての円盤がサイズ順に積み重なるように移動させる操作をひとつ挙げてください。
ただし操作が多すぎるとパズルとして美しくないので 225,000 回以内の操作で移動させてください。
















入力



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



N
r_1
r_2
:
r_N




    

	
  • 1 行目には円盤の個数 N (1 ≦ N ≦ 10,000) が与えられる。
    • 

	
  • 2 行目からの N 行のうち i 行目には、初め杭 1 に下から i 番目に置かれている円盤の半径 r_i (1 ≦ r_i ≦ N)が与えられる。
    • 

	
  • x ≠ y ならば r_x ≠ r_y が成り立つ。
    • 














部分点



この問題には部分点が設定されている。



    

	
  • 1 ≦ N ≦ 400 を満たすデータセットに正解した場合は 30 点が与えられる。
    • 

	
  • 1 ≦ N ≦ 10,000を満たすデータセットに正解した場合はさらに 70 点が与えられる。合計で100点となる。
    • 














出力



出力形式は以下のようなものである。



M
from_1 to_1
from_2 to_2
:
from_M to_M




    

	
  • 1 行目には操作の回数 M を出力せよ。
    • 

	
  • 2 行目からの M 行のうち i 行目にはi番目の操作で動かす円盤の元あった杭の番号 from_i と動かす先の杭の番号 to_i を空白区切りで出力せよ。
    • 

	
  • i 番目の操作の時に、杭 from_i に円盤が一つも存在しない場合、その操作は妥当でないとする。それ以外の操作は妥当であるとする。
    • 

	
  • 本来のハノイの塔と異なり小さい円盤の上に大きい円盤を置くことが許されていることに注意せよ。
    • 

	
  • M ≦ 225,000 かつすべての操作が妥当であり、最後にいずれかの杭に全ての円盤がサイズの大きい順に下から積み重ねられていたときのみ、解答は正解とされる。
    • 


















入力例1



5
1
2
3
4
5













出力例1



5
1 2
1 2
1 2
1 2
1 2




初め、全ての円盤が逆順に杭 1 に積み重ねられています。上から順番に杭 2 に移動させれば、下から大きい順に並び替えられます。














入力例2



5
5
3
2
4
1













出力例2



8
1 2
1 2
1 3
1 3
2 1
3 1
3 1
2 1




最後に全ての円盤が積み重ねられる杭は 1 でもかまいません。









			


			
				

				
Source Name

				Code Formula 2014 本戦
			
		

	
		

		

			H - 平和協定
			

			
Time Limit: 4 sec / Memory Limit: 64 MB


			

				







問題文



高橋ワールドにはN個の国が存在します。現在はどの国も互いにいがみ合っており、殺伐としています。
そこで各国の首脳が話し合って、いくつかの国の間で平和協定を結ぶことにしました。



各国には面積と人口の2つのパラメーターが有り、 i 番目の国の面積は A_i、 人口は B_i です。
ある2つの国 x, y に対して、面積の差と人口の差の積、つまり (A_x - A_y) ×(B_x - B_y) の値を「規模の違い」と定義します。これが負になることがあることに注意してください。



平和協定は2国間で結ばれますが、規模が違いすぎたり、似すぎたりすると関係がうまくいかないので、ほどよく規模が違う国同士でのみ協定を結びます。
すなわち「規模の違い」がS1以上、S2以下であるような場合のみ、その2国は協定を結ぶことができます。
もし仮に、協定を結ぶことが出来る2国が全て協定を結んだ場合、何個の協定が結ばれるか求めてください。



なお、面積も人口も全く同じであるような2国は存在しません。
















入力



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



N S1 S2
A_1 B_1
A_2 B_2
:
A_N B_N




    

	
  • 1 行目には高橋ワールドにある国の数N(1 ≦ N ≦ 50,000)、協定を結ぶための「規模の違い」の下限と上限S1, S2(1 ≦ S1 ≦ S2 ≦ 50,000)が空白区切りで与えられる。
    • 

	
  • 2 行目からの N 行のうち i 行目には i 番目の国の面積 A_i(1 ≦ A_i ≦ 50,000) と人口 B_i(1 ≦ B_i ≦ 50,000) が空白区切りで与えられる。
    • 

	
  • i ≠ j ならば A_i ≠ A_j と B_i ≠ B_j の少なくとも一方が成立する。
    • 














部分点



この問題には部分点が設定されている。



    

	
  • 1 ≦ N ≦ 3,000 ,1 ≦ S1 ≦ S2 ≦ 3,000 , 1 ≦ A_i, B_i ≦ 3,000 を満たすデータセットに正解した場合は 10 点が与えられる。
    • 

	
  • 1 ≦ N ≦ 50,000 ,1 ≦ S1 ≦ S2 ≦ 50,000 , 1 ≦ A_i, B_i ≦ 50,000 を満たすデータセットに正解した場合はさらに 90 点が与えられる。合計で 100 点となる。
    • 














出力



協定を結べる国が全て協定を結んだ場合に、結ばれる協定の個数を1行で出力せよ。出力の末尾には改行をいれること。
















入力例1



3 1 5
1 1
2 2
4 4













出力例1



2




1, 2番目の国や2, 3番目の国は協定を結べますが、1, 3番目の国は規模の違いが9となり上限を超えるので、協定が結べません。














入力例2



4 1 100
1 1
1 2
2 1
2 2













出力例2



1




1, 4番目の国のみが協定を結べます。
2, 3番目の国の規模の違いは負になることに注意してください。














入力例3



16 3 14
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3
8 4
6 2
6 4
3 3
8 3
2 7
9 5













出力例3



34










			


			
				

				
Source Name

				Code Formula 2014 本戦