Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Croc Champ 2012 Round 2 A問題 - Trading Business (この記事を編集する[管理者用])

Source

Croc Champ 2012 Round 2 A問題 (500pt)
Problem description

問題概要

n個 (10以下) の惑星がある.
m個 (100以下) のアイテムがある.
それぞれの惑星で,それぞれのアイテムが,
 幾らで売られているか
 幾らで売れるか
 そのアイテム買うことのできる上限数(在庫数)
が与えられる.
宇宙船の容量kも与えられ,合計でk個のアイテムしか運べない.
初期資金は大量にあるとして,惑星をちょうど2個(1回ずつ)訪れるとき,儲けれる額の最大値を求める問題.

解法

訪れる惑星とその順番は全探索する.
どのアイテムを買うかは,売値と買値の差が大きい方からgreedyに買えば良い.
損をするものは買わない.

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)

void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}

int main(){
  int i,j,k,l,m,n,lim,go;
  int a[10][100], b[10][100], c[10][100];
  int gain[100], num[100];
  int res = 0, tmp;

  scanf("%d%d%d",&n,&m,&lim);
  rep(i,n){
    scanf("%*s");
    rep(j,m) scanf("%d%d%d",a[i]+j, b[i]+j, c[i]+j);
  }
  rep(i,n) rep(j,n) if(i!=j){
    rep(k,m){
      gain[k] = b[j][k] - a[i][k];
      num[k] = c[i][k];
    }
    intIntSort(gain, num, m);
    l = lim;
    tmp = 0;
    for(k=m-1;k>=0;k--){
      if(gain[k] < 0) break;
      go = l;
      if(go > num[k]) go = num[k];
      l -= go;
      tmp += gain[k] * go;
    }
    if(res < tmp) res = tmp;
  }

  printf("%d\n",res);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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