Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

October 2012 Cook-Off 2問目 - Equalization (この記事を編集する[管理者用])

Source

codechef October 2012 Cook-Off 2問目
Problem Statement

問題概要

N要素の整数列が与えられる.Nは30以下,各要素は1以上1000以下.
以下の操作を繰り返して,全部の要素を一致させる方法を1つ求める問題.
ただし,操作回数は1000回を超えてはいけない.(最小回数である必要はない)
 素数個の要素を取ってきて,それらをすべて,取ってきた要素の平均値(整数とは限らない)に置き換える

解法

要素は何であろうとできる方法がある.
Nが素数なら全部の平均を取って終わり.
そうでなければ,Nを割り切る素数pを1つ取ってきて,配列をp個に分割して,各部分は再帰的に同じ要素になるようにしておく.
後は各要素から1個ずつ取ってきて,平均化する操作を,N/p回だけ繰り返せば良い.

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 res[2000][100], op, rs[2000];

void solve(int N, int st){
  int i, j, k, p, m;

  if(N==1) return;
  for(p=2;;p++) if(N%p==0) break;

  if(p==N){
    rs[op] = N;
    rep(i,N) res[op][i] = st+i;
    op++;
    return;
  }

  m = N/p;
  rep(i,p) solve(m, st+m*i);

  rep(i,m){
    rs[op] = p;
    rep(j,p) res[op][j] = st+i+j*m;
    op++;
  }
}

int main(){
  int T, N, A[100];

  int i, j, k;

  scanf("%d",&T);
  while(T--){
    scanf("%d",&N);
    rep(i,N) scanf("%d",A+i);

    op = 0;
    solve(N, 0);

    printf("%d\n",op);
    rep(i,op){
      printf("%d",rs[i]);
      rep(j,rs[i]) printf(" %d",res[i][j]+1);
      puts("");
    }
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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