Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #10 B問題 - Cinema Cashier (この記事を編集する[管理者用])

Source

Codeforces Beta Round #10 B問題
Problem description
Beta Round #10の自分の参加記録

問題概要

映画館でk*kの席がある.
N人の人が到着したら,できるだけ真ん中で,一並びの席を用意する.
真ん中の基準は
 各席と真ん中の席までのマンハッタン距離の和
が最も小さい.
一並びの席が存在しないなら追い返す.
何人の人が到着したかのログが与えられるので,どの席に座るのかシミュレーションする問題.
kは100以下で奇数.

解法

書くだけ.愚直に書いても計算時間的には問題ない.

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)

#define INF 1000000000
int mp[111][111];

int ab(int a){if(a<0) return -a; return a;}

int main(){
  int i,j,k,l,m,n,q;
  int r1,r2,r3;
  int x,y1,y2,opt,tmp;

  scanf("%d%d",&q,&n);
  rep(i,n) rep(j,n) mp[i][j]=0;

  while(q--){
    scanf("%d",&m); opt=INF;
    rep(x,n) rep(y1,n-m+1){
      y2 = y1+m;
      REP(i,y1,y2) if(mp[x][i]) break;
      if(i<y2) continue;

      tmp=0;
      REP(i,y1,y2) tmp += ab((n+1)/2 - x-1) + ab((n+1)/2 - i-1);
      if(tmp < opt) opt=tmp, r1=x, r2=y1, r3=y2;
    }
    if(opt==INF){puts("-1"); continue;}
    printf("%d %d %d\n",r1+1,r2+1,r3);
    REP(i,r2,r3) mp[r1][i]=1;
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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