Codeforces Round #251 (Div. 2)
はい。
http://codeforces.com/contest/439
A. Devu, the Singer and Churu, the Joker
ざっくりと大意
・歌手のDevuはn曲歌うのにそれぞれ\(t_i\)分かかる。
・コメディアンのDevuは1ジョークに5分ぴったり使う。
・Devuは歌った後に10分の休憩が必要。
・Devuは1曲毎に10分の休憩をとりつつd分以内に予定の全ての曲を歌いきりたい。
・ジョークショーは最大で何回実行されるか???
方針のようなもの
・休憩をはさみつつ歌いきれるか??を判定させて歌う以外のジョークに使える時間を求める。
n,d=map(int,raw_input().split()) l=[int(x) for x in raw_input().split()] chk=sum(l)+(n-1)*10 print (d-sum(l))/5 if chk<=d else -1
#include<iostream> #include<cmath> #include<string> #include<cctype> #include<vector> #include<numeric> #include<algorithm> using namespace std; /** vector<int>ar(3); for(auto&e:ar){ scanf("%d",&e); } sort(ar.begin(),ar.end()) int sum=accumulate(ar.begin(),ar.end(),0); **/ int main(){ double pai=3.141592653589; int n,d,t; long long chk=0; scanf("%d %d",&n,&d); for(int i=0;i<n;i++){ scanf("%d",&t); chk+=t; } if(chk+(n-1)*10>d){ printf("-1\n"); }else{ //printf("%I64d\n",(d-chk)/5); printf("%lld\n",(d-chk)/5); } return 0; }
歌のみの合計時間と休憩を挟むので(n-1)*10の和が歌い切るのに最低必要な時間。歌いきれるならばdから歌のみの時間を引くとジョークに使える時間が残るので5で割って余りは切り捨てでジョークの回数が求まる。
B. Devu, the Dumb Guy
ざっくりと大意
・Devuはn教科でそれぞれ\(c_i\)個の章を1章ごとにx時間使って学習する。
・1教科終わると必要な学習時間x時間が1時間減り続ける、但し1時間よりは減らない。
方針のようなもの
・ソートして計算する。
n,x=map(int,raw_input().split()) l=[int(i) for i in raw_input().split()] ans=chk=0 l.sort() for i in l: ans+=i*x if x>1: x-=1 print ans
おそらく貪欲法で。時間の掛る科目はxが小さくなっている方が学習に必要な時間が少なくなるので元々の時間の少ない科目から消化してxを小さく学習効率を上げてから進める。
C. Devu and Partitioning of the Array
ざっくりと大意
・n個の数が与えられるので空である組がないようにk組に分割する。
・その内のp組は和が偶数に、k-p組は和が奇数になるようにする。
・各組ごとに1行でその組内の数の個数と内容を出力する。
方針のようなもの
・おそらく奇数の分け方に気をつける。
後で