スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Google Code Jam 2011 Round1A

2011/05/21 10:00 ~ 12:30 (JST)
Google Code Jam 2011 Round1A の参加記録

上位 1000 人が通過。

Tags : プログラミング GCJ 未解決

結果

A. small: AC, large: AC
B. small: AC, large: --
C. small: --, large: --

コンテスト中

失敗しても、まだ 1B, 1C があるので、気楽な気持ちで参加。

A. FreeCell Statistics
読んだ。

わからん。
しばらく考える。
:
:
ようするに、P_D/100 = D'/D となる D', D (≦ N) があればいいということか。
じゃあ、P_D/100 を約分して、分母をできるだけ小さくしたときに、分母 ≦ N かどうかを見ればいい。

G は、めちゃくちゃ大きく取れば、いくらでも調整できそう。
でも、P_G = 0, 100 のときだけは例外。これは、D = ∞ に相当するから。

書いた。
submit.

B. The Killer Word
読んだ。

ややこしそう。
普通にシミュレーションすればいいのでは?

書く。
small incorrect.
直す。
small incorrect.
直す。
small incorrect.
直す。
small incorrect.
直す。
small incorrect.

合わない。
問題文の例をちゃんと読もう。

間違えて開けた文字の情報も以降の戦略に組み込むのか。
さらにややこしくなった。

直す。
small correct.

今のコードじゃ large は全然間に合わない。
オーダーを落とす方法が思いつかないので、bit とかを使って小手先の最適化をする。
そろそろ競技終了なので、ダメもとで large のテストケースをダウンロード。
run
やっぱり遅すぎる。
30 分くらい走らせたら終わりそうな速度。
time expired.

解答

言語は C++。テンプレはここを参照。

A.
int gcd(int a,int b){ return b?gcd(b,a%b):a; }

int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
ll n;
int pd,pg; scanf("%lld%d%d",&n,&pd,&pg);

bool res;
if (pg== 0) res=(pd== 0);
else if(pg==100) res=(pd==100);
else{
if(n>=100) res=true;
else{
int g=gcd(pd,100);
res=(100/g<=n);
}
}

printf("Case #%d: %s\n",T,res?"Possible":"Broken");
}

return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。