Tuesday, February 21, 2012

My UVA 394 MapMaker Solution


http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=330


#include <iostream>
#include <fstream>
#include <vector>


using namespace std;


int main(int argc, char** arg)
{
    int N,R;
    cin>>N>>R;


    vector<string> name(N);
    long B[N];
    int size[N];
    long D[N];
    vector<long> upper[N];
    vector<long> lower[N];


    for(int i=0;i<N;i++)
    {
      cin>>name[i];
      cin>>B[i];
      cin>>size[i];
      cin>>D[i];
      upper[i].assign(D[i]+1,0l);
      lower[i].assign(D[i]+1,0l);
      for(int j=1;j<=D[i];j++)
      {
        cin>>lower[i][j]>>upper[i][j];
      }
    }
/*
    for(int i=0;i<N;i++)
    {
      cout<<name[i]<<endl;
      cout<<B[i]<<endl;
      cout<<size[i]<<endl;
      cout<<D[i]<<endl;
      for(int j=1;j<=D[i];j++)
      {
        cout<<lower[i][j]<<","<<upper[i][j]<<endl;
      }
    }
*/
    vector<long> cD[R];
    vector<string> cname(R);
    int cidx[R];


    for(int i=0;i<R;i++)
    {
      cin>>cname[i];
      cidx[i]=-1;
      for(int i2=0;i2<N;i2++)
        if(cname[i].compare(name[i2])==0)
          {cidx[i]=i2;break;}
      if(cidx[i]>=0)
      {
            cD[i].assign(D[cidx[i]]+1,0l);
            for(int i2=1;i2<=D[cidx[i]];i2++)
            {
                cin>>cD[i][i2];
            }
      }
    }


/*
    for(int i=0;i<R;i++)
    {
      cout<<cname[i]<<endl;
      cout<<cidx[i]<<endl;
      for(int i2=1;i2<=D[cidx[i]];i2++)
            cout<<cD[i][i2]<<",";
      cout<<endl;
    }
*/
    vector<long> cC[R];


    // main part
    for(int i=0;i<R;i++)
    {
      if(cidx[i]>=0&&cidx[i]<N)
      {
          cC[i].assign(D[cidx[i]]+1,0l);
          cC[i][D[cidx[i]]]=size[cidx[i]];
          for(int d=D[cidx[i]]-1;d>=1;d--)
          {
            cC[i][d]=cC[i][d+1]*(upper[cidx[i]][d+1]-lower[cidx[i]][d+1]+1);
          }


          cC[i][0]=B[cidx[i]];
          for(int d=D[cidx[i]];d>=1;d--)
            cC[i][0]-=lower[cidx[i]][d]*cC[i][d];
          long res=cC[i][0];
          for(int i2=1l;i2<=D[cidx[i]];i2++)
            res+=(cC[i][i2]*cD[i][i2]);


          cout<<cname[i]<<"[";
          for(int i2=1;i2<=D[cidx[i]];i2++)
          {
            if(i2!=1)
              cout<<", ";
            cout<<cD[i][i2];
          }
          cout<<"] = "<<res<<endl;
      }
    }


    return 0;
}

No comments:

Post a Comment