I was solving spoj problem LISA. This is my code.
http://www.spoj.pl/problems/LISA/
First, my doubt is how to store such a big number in array? My array is
unsigned long, and even its maximum is less than 2^64. now if I use *long
long*, i get a runtime error on my system?!!
Second, consider the test case
1+2*3+4*5+6*7+8*9+9*8+7*6+5*4
It gives the same ouput as for
1+2*3+4*5+6*7+8*9+9*8+7*6+5*4+3
why is this happening?? Am I doing anything wrong? The code is straight
forward, a simple dp. please ask anything u didnt get about my code... Any
help will be greatly appreciated..
#include<iostream>
#include<conio.h>
#include<string.h>
using namespace std;
int main()
{
int t;
unsigned long max_table[100];
unsigned long min_table[100];
char *str;
scanf("%d",&t);
while(t--)
{
cin>>str;
int len=strlen(str)/2;
max_table[0]=atoi(&str[0]);
min_table[0]=atoi(&str[0]);
if(str[1]=='*')
{
max_table[1]=atoi(&str[0])*atoi(&str[2]);
min_table[1]=atoi(&str[0])*atoi(&str[2]);
}
else
{
max_table[1]=atoi(&str[0])+atoi(&str[2]);
min_table[1]=atoi(&str[0])+atoi(&str[2]);
}
cout<<max_table[0]<<"\t"<<min_table[0]<<"\n"<<max_table[1]<<"\t"<<min_table[1];
cout<<"\n";
for(int i=2;i<len+1;i++)
{
if(str[2*i-1]=='*' && str[2*i-3]=='+')
{
max_table[i]=max(atoi(&str[2*i])*max_table[i-1],(atoi(&str[2*i])*atoi(&str[2*i-2]))+max_table[i-2]);
min_table[i]=min(atoi(&str[2*i])*min_table[i-1],(atoi(&str[2*i])*atoi(&str[2*i-2]))+min_table[i-2]);
cout<<max_table[i]<<"\t"<<min_table[i]<<"\n";
}
else
if(str[2*i-1]=='+' && str[2*i-3]=='*')
{
max_table[i]=max(atoi(&str[2*i])+max_table[i-1],(atoi(&str[2*i])+atoi(&str[2*i-2]))*max_table[i-2]);
min_table[i]=min(atoi(&str[2*i])+min_table[i-1],(atoi(&str[2*i])+atoi(&str[2*i-2]))*min_table[i-2]);
cout<<max_table[i]<<"\t"<<min_table[i]<<"\n";
}
else
if(str[2*i-1]=='+' && str[2*i-3]=='+')
{
max_table[i]=atoi(&str[2*i])+max_table[i-1];
min_table[i]=atoi(&str[2*i])+min_table[i-1];
cout<<max_table[i]<<"\t"<<min_table[i]<<"\n";
}
else
if(str[2*i-1]=='*' && str[2*i-3]=='*')
{
max_table[i]=atoi(&str[2*i])*max_table[i-1];
min_table[i]=atoi(&str[2*i])+min_table[i-1];
cout<<max_table[i]<<"\t"<<min_table[i]<<"\n";
}
}
cout<<max_table[len]<<" "<<min_table[len]<<"\n";
}
getch();
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
