2008年10月30日 星期四

ACM102 - Ecological Bin Packing 


#include 
#include 
#include 
#include 
using namespace std;
class Q102
{
      private:   
          map > bin;
          map movecount;
      unsigned int MoveCount(string bin1,string bin2,string bin3)
      {
               unsigned int movecount=0;
               movecount+=bin[1][bin1]+bin[2][bin1];
               movecount+=bin[0][bin2]+bin[2][bin2];
               movecount+=bin[0][bin3]+bin[1][bin3];
               return movecount;
      }
      void GetAllMoveCount()
      {
           movecount["BCG"]=MoveCount("B","C","G");
           movecount["BGC"]=MoveCount("B","G","C");
           movecount["CBG"]=MoveCount("C","B","G");
           movecount["CGB"]=MoveCount("C","G","B");
           movecount["GBC"]=MoveCount("G","B","C");
           movecount["GCB"]=MoveCount("G","C","B");
      }
      public:
      Q102()
      {
            for(int i=0;i<3;++i)
            {
                bin[i]["G"]=0;
                bin[i]["B"]=0;
                bin[i]["C"]=0;
            }
      }
      void SetGlass(unsigned int b1,unsigned int g1,unsigned int c1,unsigned int b2,unsigned int g2,unsigned int c2,unsigned int b3,unsigned int g3,unsigned int c3)
      {
                bin[0]["B"]=b1;
                bin[0]["G"]=g1;
                bin[0]["C"]=c1;
                bin[1]["B"]=b2;
                bin[1]["G"]=g2;
                bin[1]["C"]=c2;
                bin[2]["B"]=b3;
                bin[2]["G"]=g3;
                bin[2]["C"]=c3;        
      }
      void ShowMin()
      {
           GetAllMoveCount();
           unsigned int min=movecount["BCG"];
           string minlable="BCG";
           for(map::iterator iter=movecount.begin();iter!=movecount.end();++iter)
           {
               if(iter->second < min)
               {
                   min=iter->second;
                   minlable=iter->first;
               }
           }
           cout << minlable << " " << min << endl;
      }
      
};
int main(int argc, char *argv[])
{
    Q102 q102;
    unsigned int b1, g1,c1, b2,g2, c2, b3, g3, c3;
    while(true)
    {
       cin >> b1 >> g1 >> c1 >> b2 >> g2 >> c2 >> b3 >> g3 >> c3;
       if(cin.eof())
       {
           break;
       }
       q102.SetGlass(b1,g1,c1,b2,g2,c2,b3,g3,c3);
       q102.ShowMin();
    }
}
張貼者： yup 於 晚上11:55 0 意見
標籤：

ACM101 The Blocks Problem 


#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
class Q101
{
      public:
              map > thelist;
              int _size;
              void SetSize(int size)
              {
                   _size=size;
                   for(int i=0;i<_size;++i)
                   {
                       thelist[i].clear();
                       thelist[i].push_back(i);
                   }
               }
              
              void Show()
              {
                   for(int i=0;i<_size;++i)
                   {
                           cout << i << ":";
                          
                           for(list::iterator iter=thelist[i].begin();iter!=thelist[i].end();++iter)
                           {
                               cout << " " << *iter;
                           }
                           cout << endl;
                   }
               }
               
               int Search(int n)
               {
                    for(map>::iterator iter=thelist.begin();iter!=thelist.end();++iter)
                    {
                        for(list::iterator iter2=iter->second.begin();iter2!=iter->second.end();++iter2)
                        {
                            if(*iter2==n)
                            {
                                return iter->first;
                            }
                        }
                    }
                    return -1;
                    
                }
                
               void ResetAfter(int n)
               {
                    int index=Search(n);
                    while(thelist[index].back()!=n)
                    {
                       int temp=thelist[index].back();
                       thelist[index].pop_back();
                       thelist[temp].push_back(temp);
                    }
                }
                
                stack GetStack(int n)
                {
                    stack s;
                    int index =Search(n);
                    while(thelist[index].back()!=n)
                    {
                        s.push(thelist[index].back());
                        thelist[index].pop_back();
                    }
                    s.push(thelist[index].back());
                    thelist[index].pop_back();
                    return s;
                }
               void moveonto(int a,int b)
               {
                   if(a==b)
                   {
                           return;
                   }
                   int aat= Search(a);
                   int bat=Search(b);
                   if(aat==bat)
                   {
                      return;
                   }
                   ResetAfter(a);
                   ResetAfter(b);
                  
                   thelist[aat].pop_back();
                   thelist[bat].push_back(a);
                }
               void moveover(int a,int b)
               {
                   if(a==b)
                   {
                           return;
                   }
                   int aat= Search(a);
                   int bat=Search(b);
                   if(aat==bat)
                   {
                      return;
                   }
                   ResetAfter(a);            
                   thelist[aat].remove(a);
                   thelist[bat].push_back(a);
                }
                void pileonto(int a,int b)
                {
                   if(a==b)
                   {
                           return;
                   }
                   int aat= Search(a);
                   int bat=Search(b);
                   if(aat==bat)
                   {
                      return;
                   }
                   ResetAfter(b);
                   stack s=GetStack(a);
                   while(!s.empty())
                   {
                       thelist[bat].push_back(s.top());
                       s.pop();
                   }
                }
                 void pileover(int a,int b)
                {
                   if(a==b)
                   {
                           return;
                   }
                   int aat= Search(a);
                   int bat=Search(b);
                   if(aat==bat)
                   {
                      return;
                   }
                
                   stack s=GetStack(a);
                   while(!s.empty())
                   {
                       thelist[bat].push_back(s.top());
                       s.pop();
                   }
                }
};
int main(int argc, char *argv[])
{
    Q101 q101;
    while(true)
    {
       int size;
       cin >> size;
       if(cin.eof())
       {
           break;
       }
       q101.SetSize(size);
       
       while(true)
       {
        string cmd1,cmd2;
        int a,b;
        string input;
        getline(cin,input);
        istringstream ss;
        ss.str(input);
        ss >> cmd1;
       
         if(cmd1=="quit")
        {
            q101.Show();            
            break;
        }
        ss >> a;
        ss >> cmd2;
        ss >> b;
        if(cmd1=="move")
        {
           if(cmd2=="onto")
           {
               q101.moveonto(a,b);
           }
           else if(cmd2=="over")
           {
                q101.moveover(a,b);
           }
        }
        else if(cmd1=="pile")
        {
        if(cmd2=="onto")
           {
               q101.pileonto(a,b);
           }
           else if(cmd2=="over")
           {
                q101.pileover(a,b);
           }
        }   
       }       
    }
}
張貼者： yup 於 晚上11:50 0 意見
標籤：

ACM100: The 3n + 1 problem 


#include 
using namespace std;
class n3plus1
{
     
      public:
       int GetMaxCycle(int i,int j)
       {
           int max=0;
           int temp;
           for(;i<=j;++i)
           {
               temp=GetCycle(i,0);
               max=temp>max?temp:max;
           }
           return max;
       }
       int GetCycle(int n,int temp)
       {
           ++temp;
           if(n==1)
           {
               return temp;
           }
           else if(n%2==0)
           {
              return GetCycle(n/2,temp);         
           }
           else
           {
               return GetCycle(n*3+1,temp);
           }
       }
};
int main(int argc, char *argv[])
{
   
    int m,n,max,min;
    n3plus1 obj;
    while(true)
    {
    cin >> m >> n;
    if(cin.eof())
    {
        break;
    }
    max=m>n?m:n;
    min=m    cout << m << " " << n << " " << obj.GetMaxCycle(min,max) << endl;
    }
}
張貼者： yup 於 晚上11:30 0 意見
標籤：

ACM476: Points in Figures: Rectangles 


#include   
#include 
#include 
using namespace std; 
class Point
{
      public:
             Point(float xx,float yy):x(xx) , y(yy){};
             float x,y;
             
}; 
class Rectangle
{
      public:
             Point point1,point2;
             Rectangle(float x1,float y1,float x2,float y2):point1(x1,y1),point2(x2,y2){};
      bool IsIn(Point point)
      {
           return point.x > point1.x && point.x < point2.x && point.y < point1.y && point.y > point2.y;
      }
};
class ACM476
{
      public:
             vector rectangles;
             vector points;
};
int main(int argc, char *argv[])  
{  
   ACM476 acm476;
    while(true)  
    {       
        string input;
        getline(cin,input);
        istringstream ss;
        ss.str(input);
        string cmd;
        float x1,y1,x2,y2;
        ss >> cmd;         
        if(cmd=="*")
        {                     
            break;
        }
        switch(cmd[0])
        {
            case 'r':
                 ss >> x1;ss >> y1;ss >> x2;ss >> y2;
                 acm476.rectangles.push_back(Rectangle(x1,y1,x2,y2));
                 break;
        }
    }  
     while(true)  
    {  
        string input;
        getline(cin,input);
        istringstream ss;
        ss.str(input);
        float x,y;
        ss >> x;
        ss >> y;
        if(x==9999.9f && y==9999.9f)
        {   
            break;
        }
        acm476.points.push_back(Point(x,y));
    }  
    for(vector::size_type ip =0;ip != acm476.points.size();++ip)
    {
         bool flag=false;
         for(vector::size_type ir =0; ir != acm476.rectangles.size();++ir)
         {
             if(acm476.rectangles[ir].IsIn(acm476.points[ip]))
             {
                  cout << "Point " << ip+1 << " is contained in figure " << ir+1 << endl;
                  flag=true;
             }
         }
         if(!flag)
         {
                 cout << "Point " << ip+1 <<" is not contained in any figure" << endl;                                                  
         }
         
    }
}
張貼者： yup 於 晚上11:15 0 意見
標籤：

ACM458 - The Decoder

http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&page=show_problem&problem=399



    #include 
    using namespace std;
    int main(int argc, char *argv[])
    {
        string input;
        int cmt;
        int i;
        while(true)
        {
            cin >> input;
            if(cin.eof())
            {
                break;
            }
            cmt=input.size();
            for(i=0;i < cmt;++i)
            {
                    input[i]-=7;
            }
            cout << input << endl;
        }
    }
張貼者： yup 於 凌晨1:36 0 意見
標籤：
訂閱： 文章 (Atom)