Google Code Jam(GCJ) 2010 Qualification Round

Programming Algorithm

概要

ぐーぐる先生のプログラミングコンテスト。18歳以上だと選ばれてダブリンとか行けるらしい。裏山。

入力を得て出力を提出する形式が特徴。つまり、お好みのマニアックな環境(期限なし無料で入手可能なものに限る)でよいらしい。だが俺はC++でいいや…

A

電源入力と電源出力と音センサーを持つ機械がある。機械は内部スイッチがあり、電源入力に入力があってかつスイッチがオンのとき電源出力に電力が出力される。

音センサーは電源入力に入力があるときに働き、音を出すとオンオフが切り替わる。(オフになってから電源出力が停止するまでにディレイがあるとしてよい)。

n個の機械が直列に繋がれ、最初の入力はコンセントに、最後の出力は電球に繋がれている。

最初は全ての機械がオフである。k回手を叩いたとき、電球がついているか判定せよ。

k+1 mod 2^nが0のときオン。
適当に書いて提出。

B

n個の大きな(10^50以下の)整数t_iがある。gcd(t_i+y for all i)の最大値を与える最小の非負整数yを求めよ。

多倍長ゲー。自前で実装してしまったけど、GCJは外部ライブラリも使えるので次からはgmpxxでも使おうと思ったらちゃんとインストールされてた自分ぱない

C

人数をあらわすキューがある。1回の操作で、先頭から合計がkに満たない限り多く取りだす。取りだしたものは順番を保持したまま再キューされる。
r回操作したときに、処理した人数の合計値を答えよ。

ループ検出したりごにょごにょして最適化。

largeがでたときにlong long周りであせったが無事提出。

結果

全部通った。