Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #26 E問題 - Multithreading (この記事を編集する[管理者用])

Source

Codeforces Beta Round #26 E問題
Problem description
Beta Round #26の自分の参加記録

問題概要

N個のプロセスがあって,プロセスiがn[i]回
 y[i] := y
 y := y[i]+1
という操作を行う.メモリは共通.
最初yの値が0で最終的にWになる方法を1つ求める問題.
方法とは,全部のプロセスは1行ずつ実行する(その間は他のプロセスは邪魔しない)として,実行順番のこと.
Nは100以下,n[i]は1000以下.

解法

adhoc.
n=1のときは,n[1]しか作れない.
n[k]=1なるkが存在したら1を作れる.そうでなければ作れる範囲は2~∑n[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 get_mini(int in[],int n){
  int i,k,mx=100000;
  rep(i,n) if(in[i] && mx>in[i]) mx=in[i], k=i;
  return k;
}

int get_mx(int in[],int n){
  int i,k,mx=-1;
  rep(i,n) if(mx<in[i]) mx=in[i], k=i;
  return k;
}

int main(){
  int i,j,k,l,m,n,W;
  int in[120], sum, now;

  scanf("%d%d",&n,&W);
  rep(i,n) scanf("%d",in+i);
  if(W<=0){ puts("No"); return 0; }

  sum=0;
  rep(i,n) sum+=in[i];
  now=get_mini(in,n);
  
  if(W>sum){ puts("No"); return 0; }
  if(n==1 && W!=sum){ puts("No"); return 0; }
  if(in[now]>1 && W==1){ puts("No"); return 0; }

  puts("Yes");

  if(W >= in[now]){
    k = sum-W;
    printf("%d",now+1);
    rep(i,n) if(i!=now){
      while(in[i] > 0 && k > 0){
        printf(" %d %d",i+1,i+1);
        in[i]--; k--;
      }
    }
    printf(" %d",now+1); in[now]--;
    rep(i,n) while(in[i] > 0){ printf(" %d %d",i+1,i+1); in[i]--; }
  } else {
    rep(k,n) if(k!=now) break;
    printf("%d",k+1);
    while(in[now]>1) printf(" %d %d",now+1,now+1), in[now]--;
    printf(" %d %d",k+1,now+1); in[k]--;

    sum=0;
    rep(i,n) sum += in[i];
    k = sum - W + 1;

    rep(i,n) if(i!=now){
      while(in[i] > 0 && k > 0){
        printf(" %d %d",i+1,i+1);
        in[i]--; k--;
      }
    }
    printf(" %d",now+1); in[now]--;
    rep(i,n) while(in[i] > 0){ printf(" %d %d",i+1,i+1); in[i]--; }
  }
  
  puts("");

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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