426 - Fifth Bank of Swamp County

[Whinii F.]

Hi, it looks like a simple problem. I use qsort() to sort all the transactions..
Getting many WAs..

anybody who received an AC please give some hints or tricky cases.

My code:
[cpp]
cut: spolier
[/cpp]

[nealzane]

here is the trick:

All checks for $1 million or more require special processing and are not handled through the bank's normal check clearing process; such checks will not appear on these statements.

[UFP2161]

Are checks that are $1 million or more considered when determining whether or not a certain check is in sequential order?

[little joey]

No, there are no such cases. All amounts are <$1000000.

I ran Whinii's program against a very large testset and compared it with my AC output. No differences. Strange.

The only difference I see is in the way we handle dirty input.

Code: Select all

2

93/10/15 1001 116.81
93/10/27 1000 840.85
93/10/26 1002 555.55

93/10/15 1001
93/10/27 1000 840.85
93/10/26 1002 555.555

My program:

Code: Select all

1000     840.85 93/10/27   1001     116.81 93/10/15   1002     555.55 93/10/26

1000     840.85 93/10/27   1001       0.00 93/10/15   1002     555.55 93/10/26

Whinii's program:

Code: Select all

1000     840.85 93/10/27   1001     116.81 93/10/15   1002     555.55 93/10/26

1000     840.85 93/10/27   1001     840.00 93/10/15   1002     555.555 93/10/26

But I can't tell if there are realy such cases in the judge's input.

[Whinii F.]

Wow thanks very very much, little joey!!
There EXISTS that kind of input. Three digits of a cent. How strange.

Anyway after modifying that I got an AC.
Thanks again for your sincere reply(even after 6 months the question is posted! ).

Best regards,

[little joey]

No prob! That's what we're here for!

Had WA on this one for ages, looked at it again yesterday, and suddenly saw the light (I didn't handle the one cheque case correctly). I was so excited about finaly solving it, that I couldn't resist trying my luck on your program. That's the way it works.

Happy hunting,

-little joey

[boatfish]

I have tried many times, it always gave me:
Your program has died with signal 11 (SIGSEGV). Meaning:
Invalid memory reference
Why??
[cpp]#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

struct src{
string date;
int check;
double money;
bool star;
};

src table[10000];

bool new_less(src a,src b){
return a.check<b.check;
}

void print(int n,int no){
if(n>=no)
return;

cout.width(4);
cout<<(table[n]).check;
if((table[n]).star){
cout<<'*';
cout.width(8);
}
else
cout.width(9);
cout.precision(2);
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout<<(table[n]).money<<' '<<(table[n]).date;
}

int main(){
int case_no,no,i,dx,t_int;
double t_double;
string t_string;
char bu;
cin>>case_no;
cin.get(bu);
cin.get(bu);
while(case_no--){
no=0;
while(cin.peek()!='\n'){
cin>>t_string>>t_int;
cin.get(bu);
if(cin.peek()!='\n')
cin>>t_double;
else
t_double=0.0;
if(t_double<1000000){
(table[no]).date=t_string;
(table[no]).check=t_int;
(table[no]).money=t_double;
no++;
}
cin.get(bu);
}

sort(table,table+no,new_less);
(table[0]).star=false;
for(i=1;i<no;i++)
if((table).check-(table[i-1]).check!=1)
(table).star=true;
else
(table).star=false;

if(no%3==0)
dx=no/3;
else
dx=no/3+1;

for(i=1;i<=ceil(double(no)/3.0);i++){
print(i-1,no);
cout<<" ";
print(i-1+dx,no);
cout<<" ";
print(i-1+dx*2,no);
cout<<endl;
}

if(case_no)
cout<<endl;
cin.get(bu);
}
return 0;
}
[/cpp]

[Salman]

Donot understand why gettting runtime Error?

Code: Select all

/*
Name: Fifth Bank of Swamp County 
Number: 426
Type :  adhoc\sorting
Process : ON
Author :Salman Zaman
Email : zamansalman@gmail.com
Date : 21/08/05 23:27




*/



#include<stdio.h>
#include<string.h>
#include<math.h>


//#include<conio.h>


struct bank{
     char date[100];
     int check;
     double money;  
     char c;
    
};    


bank mbank[2000]; 

void interchange(int x,int y)
{
	  
      bank temp;
	  temp=mbank[x];
	  mbank[x]=mbank[y];
	  mbank[y]=temp;


}


int partition(int p,int r){

	int i,j,x;

	x=mbank[r].check;
	i=p-1;
	for(j=p;j<=r-1;j++){
	   if(mbank[j].check<=x){
	      i=i+1;
	      interchange(i,j);

	   }

	}
	interchange(i+1,r);
	return i+1;



}



void quicksort(int l,int h){

	 int j;

	 if(l<h){

	      j=partition(l,h);
	      quicksort(l,j-1);
	      quicksort(j+1,h);
	 }


}


int main(){

       char input[1000];;
        int n,i,j,count,col,temp,tempo,t;
   //    freopen("426.txt","r",stdin);
        
       gets(input);
       
       sscanf(input,"%d",&n);        
       gets(input);
         for(i=0;i<n;i++){
            j=1;
            while(gets(input)){
               if(strcmp(input,"")!=0){ 
                sscanf(input,"%s %d %lf",&mbank[j].date,&mbank[j].check,&mbank[j].money);
                mbank[j].c=' ';
//                printf("%s %d %lf\n" ,mbank[j].date,mbank[j].check,mbank[j].money);   
                j++;
               } 
               else {
                    break;
                }       
                
            }    
            quicksort(1,j-1);  
            for(count=1;count<=j-1;count++){
//               printf("%s %d %lf\n" ,mbank[count].date,mbank[count].check,mbank[count].money);   
//                
                
            }    
//            printf("%d\n",j-1);
  
            col=j-1;
//          col=(int)ceil((j-1)/3);
  //         printf("%d\n",col);
             temp=(int)floor(((j-1)+2)/3);
         // printf("%d\n",temp);
             /*
             for(count=1;count<=temp;count++,printf("\n")){
                        tempo=(temp*0)+count;
                        if(tempo<=col){
                               printf("%4d   %6.2lf %s",mbank[tempo].check,mbank[tempo].money,mbank[tempo].date);    
                         }      
                         printf("   ");
                        tempo=(1*temp)+count;
                        if(tempo<=col){
                               printf("%4d   %6.2lf %s",mbank[tempo].check,mbank[tempo].money,mbank[tempo].date);    
                         }
                         printf("   ");
                        tempo=(temp*2)+count;

                      if(tempo<=col){
                               printf("%4d   %6.2lf %s",mbank[tempo].check,mbank[tempo].money,mbank[tempo].date);    
                         }      
                         printf("   ");
                                 
           
               }    
  */
  
             for(count=1;count<=col;count++){
                 if(mbank[count+1].check!=mbank[count].check && mbank[count+1].check!=mbank[count].check+1){
                     mbank[count+1].c='*';
                 }    
              }     
  
           for(count=1;count<=temp;count++,printf("\n")){
                     for(t=0;t<3;t++){ 
                          tempo=(temp*t)+count;
                        if(tempo<=col){

                               printf("%4d%c %8.2lf %s",mbank[tempo].check,mbank[tempo].c,mbank[tempo].money,mbank[tempo].date);    
 //                        printf("   ");
                               
                         }      
                         printf("   ");
    
                     }    
            }        
            printf("\n");
         }    

     
  // getch();
   return 0;
}

[stcheung]

Another potential trap to look for is what your program would output for an amount of 999999.99

My program initially used float and would output 1000000.00

I eventually have to use long double to make it output the correct 999999.99

[daveon]

Hi,

Try increasing your table size. There is more than 10000 tuples.

[boshkash1986]

Please can anyone give me the correct ouput for this :

Code: Select all

5

93/10/15 1001 116.81 
93/10/27 1000 840.85 
93/10/26 1002 555.55 
93/10/26 1003 555.55 

93/10/15 1001 
93/10/27 1000 9999999.99 
93/10/26 1002 555.555      

93/10/01 998  .65
93/10/01 999 0123.89
93/10/05 996 29.99
93/10/06 993 116.52
93/10/12 995 418.00
93/10/15 1001 15045.00
93/10/27 1000 840.85
93/10/15 1003 15045.00

93/10/01 998  .65
93/10/01 999 0123.89
93/10/05 996 29.99
93/10/06 993 116.52
93/10/12 995 418.00
93/10/15 1001 15045.00
93/10/27 1000 840.85
93/10/15 1003 15045.00
93/10/15 1006 

93/10/01 998  .65
93/10/01 999 0123.89
93/10/05 996 29.99
93/10/06 993 116.52
93/10/12 995 418.00 

[boshkash1986]

Please can anyone help me ???

[shakil]

Salman,
you can change the following and get PE.

Code: Select all

struct bank{
     char date[10];
     int check;
     double money; 
     char c;
   
};   


bank mbank[100000];

[DD]

I have tried many times, it always gave me:

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Why??

[cpp]#include<iostream>

#include<string>

#include<algorithm>

#include<math.h>

using namespace std;



struct src{

string date;

int check;

double money;

bool star;

};



src table[10000];



bool new_less(src a,src b){

return a.check<b.check;

}



void print(int n,int no){

if(n>=no)

return;



cout.width(4);

cout<<(table[n]).check;

if((table[n]).star){

cout<<'*';

cout.width(8);

}

else

cout.width(9);

cout.precision(2);

cout.setf(ios::fixed);

cout.setf(ios::showpoint);

cout<<(table[n]).money<<' '<<(table[n]).date;

}



int main(){

int case_no,no,i,dx,t_int;

double t_double;

string t_string;

char bu;

cin>>case_no;

cin.get(bu);

cin.get(bu);

while(case_no--){

no=0;

while(cin.peek()!='\n'){

cin>>t_string>>t_int;

cin.get(bu);

if(cin.peek()!='\n')

cin>>t_double;

else

t_double=0.0;

if(t_double<1000000){

(table[no]).date=t_string;

(table[no]).check=t_int;

(table[no]).money=t_double;

no++;

}

cin.get(bu);

}



sort(table,table+no,new_less);

(table[0]).star=false;

for(i=1;i<no;i++)

if((table).check-(table[i-1]).check!=1)

(table).star=true;

else

(table).star=false;



if(no%3==0)

dx=no/3;

else

dx=no/3+1;



for(i=1;i<=ceil(double(no)/3.0);i++){

print(i-1,no);

cout<<" ";

print(i-1+dx,no);

cout<<" ";

print(i-1+dx*2,no);

cout<<endl;

}



if(case_no)

cout<<endl;

cin.get(bu);

}

return 0;

}

[/cpp]

You should try to use vector to handle this.

[DD]

Please can anyone give me the correct ouput for this :

Code: Select all

5

93/10/15 1001 116.81 
93/10/27 1000 840.85 
93/10/26 1002 555.55 
93/10/26 1003 555.55 

93/10/15 1001 
93/10/27 1000 9999999.99 
93/10/26 1002 555.555      

93/10/01 998  .65
93/10/01 999 0123.89
93/10/05 996 29.99
93/10/06 993 116.52
93/10/12 995 418.00
93/10/15 1001 15045.00
93/10/27 1000 840.85
93/10/15 1003 15045.00

93/10/01 998  .65
93/10/01 999 0123.89
93/10/05 996 29.99
93/10/06 993 116.52
93/10/12 995 418.00
93/10/15 1001 15045.00
93/10/27 1000 840.85
93/10/15 1003 15045.00
93/10/15 1006 

93/10/01 998  .65
93/10/01 999 0123.89
93/10/05 996 29.99
93/10/06 993 116.52
93/10/12 995 418.00 

Following is the output generated by my A.C. program:

Code: Select all

1000     840.85 93/10/27   1002     555.55 93/10/26
1001     116.81 93/10/15   1003     555.55 93/10/26

1000  9999999.99 93/10/27   1001       0.00 93/10/15   1002     555.55 93/10/26

 993     116.52 93/10/06    998*      0.65 93/10/01   1001   15045.00 93/10/15
 995*    418.00 93/10/12    999     123.89 93/10/01   1003*  15045.00 93/10/15
 996      29.99 93/10/05   1000     840.85 93/10/27

 993     116.52 93/10/06    998*      0.65 93/10/01   1001   15045.00 93/10/15
 995*    418.00 93/10/12    999     123.89 93/10/01   1003*  15045.00 93/10/15
 996      29.99 93/10/05   1000     840.85 93/10/27   1006*  15045.00 93/10/15

 993     116.52 93/10/06    996      29.99 93/10/05    999     123.89 93/10/01
 995*    418.00 93/10/12    998*      0.65 93/10/01