My Weblog

Blog about programming and math

SPOJ 4273. Train TimeTable

SPOJ 4273. Train TimeTable is from google code jam 2008 and i remember participating in this code jam from my internship to Arcelor Mittal Research Center , Spain . Just downloaded my source code from code jam and submitted . You can read the analysis of this problem here . I will try to code this problem in Haskell .

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
     struct tt
       {
                int time;
                bool avail;
       };
bool cmp(struct tt a,struct tt b)
     {
                return a.time<b.time;
     }
                   
int main()
 {
          
          int N,T,NA,NB;
          scanf("%d",&N);
          int Case=1;
          while(N--)
           {
                    
                    vector<struct tt> Va1,Va2,Vb1,Vb2;
                    scanf("%d",&T);
                    scanf("%d%d",&NA,&NB);
                    int t1,t2,s1,s2;
                    struct tt t;
                    for(int i=0;i<NA;i++)
                      {
                            scanf("%d:%d %d:%d",&t1,&s1,&t2,&s2);
                            t.time=60*t1+s1;
                            t.avail=1;
                            Va1.push_back(t);
                            t.time=60*t2+s2+T;
                            t.avail=1;
                            Va2.push_back(t);
                      }
                     
                    for(int i=0;i<NB;i++)
                       {
                            scanf("%d:%d %d:%d",&t1,&s1,&t2,&s2);
                            t.time=60*t1+s1;
                            t.avail=1;
                            Vb2.push_back(t);
                            t.time=60*t2+s2+T;
                            t.avail=1;
                            Vb1.push_back(t);
                       }
                    sort(Va1.begin(),Va1.end(),cmp);
                    sort(Vb1.begin(),Vb1.end(),cmp);
                    sort(Va2.begin(),Va2.end(),cmp);
                    sort(Vb2.begin(),Vb2.end(),cmp);
                    
                    /*for(int i=0;i<NA;i++)
                     cout<<Va1[i].time<<" "<<Va1[i].avail<<endl;
                    for(int i=0;i<NB;i++)
                     cout<<Vb1[i].time<<" "<<Vb1[i].avail<<endl;*/
                   
                   int counta=0,countb=0;
                   int f;
                   for(int i=0;i<NA;i++)
                     {
                           f=1;
                           for(int j=0;j<NB;j++)
                            {
                                   if(Va1[i].time<Vb1[j].time)
                                    {
                                       counta++;
                                       f=0; 
                                       break;
                                    }
                                   else
                                   {
                                       if(Vb1[j].avail==true)
                                          {
                                              Vb1[j].avail=0;
                                              f=0;
                                              break;
                                          }
                                   }
                                 
                            }
                            if(f)
                            counta++;
                   }        
                      
                      
                  for(int i=0;i<NB;i++)
                     {
                           f=1;
                           for(int j=0;j<NA;j++)
                            {
                                   if(Vb2[i].time<Va2[j].time)
                                    {
                                       countb++;
                                       f=0; 
                                       break;
                                    }
                                   else
                                   {
                                       if(Va2[j].avail==true)
                                          {
                                              Va2[j].avail=0;
                                              f=0;
                                              break;
                                          }
                                   }
                                 
                            }
                            if(f)
                            countb++;
                   }                             
                  printf("Case #%d: %d %d\n",Case++,counta,countb);
           }
           
    }    
                                                 

Advertisements

June 1, 2011 - Posted by | Programming |

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: