Sticks(1) - カメヲラボ
同じ長さの棒を出来るだけたくさん作るには、 ①まず入力値(input)の合計(sum)を求める。 ②sumの約数で、かつinputの最大値(max)以上のもの(=length)を、小さい順から順番に調べていく。 ③すべてのinputを使用して長さlengthの棒ができれば、lengthを出力して終了。これだけでできることはすぐに分かる。 たとえば、前回の入力例 4 3 2 1なら、合計値が10になる。約数は、1,2,5,10このうち入力の最大値4よりも大きいのは5,10だから、最初はたして5になるような組み合わせを見つければよい。 もし入力が5 3 2 1なら合計値が11(素数)なので11がそのまま答えになる。 実際にコードを書いてみると、 001 int input[64]; 002 int length,n; 003 004 main() 005 { 006 int a,b,sum;
2005-12-13
グラフ理論がらみで何かネタになりそうな問題はないかと探していたら、1011番の問題を見つけた。本当はもっと単純な問題がいいのだけど問題量が多すぎてなかなか見つからない。良さげな問題があったら誰か教えてください。 http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1011 長さがバラバラの棒の切れ端をつなぎ合わせて、同じ長さの棒を作る問題。つなぎ合わせた棒の長さは考えられる答えの中で最小でなければならない。なるべく短くするということは、同じ長さの棒をできるだけたくさん作れば良いということだ。 たとえば、 このように長さの違う4本の棒なら、 という風に同じ長さの棒を2本作ることが出来る。 入力は 1行目：棒の切れ端の数(最大64) 2行目：切れ端の長さ(スペース区切り) 3行目以降は上記2行の繰り返しになっていて、最後の行が0(切
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
1011 Tree Summing
http://www.4dm.org/PKU/
