Codeforces 93 B. End of Exams

問題

n個のボトルにそれぞれwリットルの牛乳が入っていて、それをm個のカップに同じ量ずつ分けたい。
一つのボトルから注げるカップは2つまでという制限があるとき、牛乳を同じ量ずつ分けることは可能か。
可能ならそのような分け方をどれか一通り出力し、そうでないならNOを出力せよ。

制約条件

n,m≦50
w≦1000

方針

ボトルからカップへ、注げるだけ注ぐ。
二つのカップに注げるだけ注いだとき、ボトルに牛乳が余っていたらダメ。
これを繰り返せば解ける。

何故これで良いのかよくわかっていない。

ソースコード

int n,w,m;

void run(){
  cin>>n>>w>>m;
  vector<vector<pair<int,double> > > v(m);
  
  double b,c,t,cup=n*1.0*w/m;
  int i=0,j=0;
  c=0;
  for(;i<n&&j<m;i++){
    b=w;
    rep(k,2){
      t=min(b,cup-c);
      b-=t;
      c+=t;
      v[j].pb(mp(i+1,t));
      if(abs(c-cup)<EPS){
        if(++j>=m)break;
        c=0;
      }
      if(b<EPS)break;
    }
    if(b>EPS){
      cout<<"NO"<<endl;
      return;
    }
  }
  if(i==n&&j==m){
    cout<<"YES"<<endl;
    rep(i,m){
      rep(j,v[i].size())printf("%d %.9f ",v[i][j].first,v[i][j].second);
      cout<<endl;
    }
  }
  else cout<<"NO"<<endl;
}