Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #74 DIV1 A問題/DIV2 C問題 - Robbery (この記事を編集する[管理者用])

Source

Codeforces Beta Round #74 DIV1 A問題 (500pt)
Codeforces Beta Round #74 DIV2 C問題 (1500pt)
Problem description

問題概要

一列に並んだn個 (10^4以下) のショーケースに,それぞれa[i]個の宝石が入っている.(a[i]は10^5以下)
防犯システムは,毎秒,隣り合うショーケースの宝石の数の和 (n-1個) を調べ,1つでも変化があったらアラームが作動する.
1秒間にm回 (10^9以下) 行動でき,持ち時間はk秒 (10^9以下) である.
アラームを作動させずに,盗める宝石の数の最大値を求める問題.
1回の行動では以下のどれかができる.
 あるショーケースの宝石を1つ,別のショーケースに移動させる
 あるショーケースの宝石を1つ,自分のポケットに移動させる (盗む)
 自分のポケットの宝石を1つ,あるショーケースに移動させる
最初,ポケットには宝石は1つも入っていないとする.

解法

端からつじつまが合うように考えると,nが偶数の時は何も得になる操作できない.
nが奇数の時は,偶数番目(0番目から数えて)をa減らし,奇数番目をaだけ増やすという操作が可能.(1個ポケットに入れる)
1秒間に操作可能なaの最大値を求めて,それを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)

#define ll long long

int main(){
  int i,j,k,l,m,n;
  int in[10000];
  int mx, per;
  ll res;

  while(scanf("%d%d%d",&n,&m,&k)==3){
    rep(i,n) scanf("%d",in+i);
    if(n%2==0){puts("0"); continue;}

    mx = in[0];
    for(i=2;i<n;i+=2) if(mx > in[i]) mx = in[i];

    per = m / ((n+1) / 2);
    res = per * (ll)k;

    if(res > mx) res = mx;
    printf("%d\n",(int)res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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