Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #28 A問題 - Bender Problem (この記事を編集する[管理者用])

Source

Codeforces Beta Round #28 A問題
Problem description
Beta Round #28の自分の参加記録

問題概要

各辺がx軸かy軸に平行なn角形の頂点に釘が打ってある.nは偶数で100以下.
m個の針金があって,それぞれちょうど1回だけ90度曲げて配置する.
曲げた部分と,両端は多角形の頂点に位置しないといけない.
針金で多角形を作るとき,各頂点に対して
 そこで曲げた針金が置かれているなら,その針金の番号
 そうでないなら-1
を出力する問題.
使わない針金があっても良い.同じ辺は2回以上針金が通ってない.答えが複数あるならどれを出力しても良い.
針金の長さは200000以下の正整数.

解法

2つ置きに,両隣の頂点までの距離の和の長さの針金を使っていく.

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 ab(int x){ if(x<0)return -x; return x; }

int main(){
  int i,j,k,l,m,n,st;
  int x[666], y[666];
  int in[666], used[666];
  int res[666];

  scanf("%d%d",&n,&m);
  rep(i,n) scanf("%d%d",x+i,y+i);
  rep(i,m) scanf("%d",in+i);

  rep(st,2){
    rep(i,n) res[i]=-1;
    rep(i,m) used[i]=0;

    for(i=st;i<n;i+=2){
      k  = 0;
      k += ab(x[i]-x[(i+n-1)%n]) + ab(y[i]-y[(i+n-1)%n]);
      k += ab(x[i]-x[(i+n+1)%n]) + ab(y[i]-y[(i+n+1)%n]);
      rep(j,m) if(in[j]==k && used[j]==0) break;
      if(j==m) break;
      res[i] = j+1; used[j]=1;
    }
    if(i>=n){
      puts("YES");
      rep(i,n){
        if(i) putchar(' ');
        printf("%d",res[i]);
      }
      puts("");
      return 0;
    }
  }
  puts("NO");
  
  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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