Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2342-71652187
この記事にトラックバックする(FC2ブログユーザー)

Bayan 2012-2013 Elimination Round G問題 - Challenging Balloons (この記事を編集する[管理者用])

Source

Bayan 2012-2013 Elimination Round G問題 (ACM/ICPC形式)
Problem description

問題概要

以下の問題に対する解答プログラムが問題文に与えられている.
そのプログラムが間違った答えを返すケースを1つ出力する問題.

一直線上に,n個の風船を配置する.nは500以下.
各風船は地面に接するようにおき,各風船の中心のx座標は与えられている.
各風船の最大サイズも与えられる.
風船は接することはできても,重なることはできない.
各風船の半径の和の最大値を求める問題.

解法

jを300までしかチェックしてないのが問題.
 でかい風船,接しないように右に行くにつれて小さくなるように小さい風船たち,でかい風船
で,でかい風船が重なるようにすれば良い.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n,x;
  n = 500;
  x = 0;

  printf("%d\n",n);
  rep(i,n){
    k = 600-i;
    if(i==0 || i==n-1) k = 1000000;
    if(!(i==0 || i==n-1)) x += 2*k;
    if(i==n-1) x += 10000;
    printf("%d %d\n",x,k);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2342-71652187
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。