Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

2010 Round 1B B問題 - Picking Up Chicks (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1B B問題
Problem Statement
SPOJ 6691 [GCJ101BB]

問題概要

N匹のひよこが1次元上を移動できる.
各ひよこの初期位置,最大スピードが与えられる.
最初,各ひよこは目的地の左にいる.
K匹以上が目的地に辿り着くために,最小のひよこの追い越し回数を求める問題.
不可能ならそれを指摘する.
small: Nは10以下.Kは3以下
large: N, Kは50以下

解法

目的地に辿り着けるひよこを追い抜かす必要はない,後ろからついていけば良い.
なので,目的地に辿りつけるひよこは,自分より前にいる,目的地に辿り着けないひよこの数だけ追い抜けば目的地にたどり着ける.
つまり,初期位置で前からK匹の目的地に辿り着けるひよこが,目的地に辿り着くまでに追い抜くひよこの数の和を求める.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.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,res,dame;

  int N, K, B, T;
  int x[60], v[60];

  int size,count=0;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d%d%d",&N,&K,&B,&T);
    rep(i,N) scanf("%d",x+i);
    rep(i,N) scanf("%d",v+i);

    res=0; dame=0;
    for(i=N-1;i>=0;i--){
      if(K==0) break;
      if(x[i]+v[i]*T >= B){
        K--; res += dame;
      } else {
        dame ++;
      }
    }

    printf("Case #%d: ",++count);
    if(K) puts("IMPOSSIBLE"); else printf("%d\n",res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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