Hey guys,
I've tried out the test cases here (and they work fine for me), but I just can't seem to get AC. I've used forward DP. Any help?
#include<stdio.h>
#include<string.h>
int valid;
long long int dp[10000];
int count(char str[],int len)
{
memset(dp,0,sizeof(dp));
int i;dp[0]=1;
for(i=1;i<len;i++) {
//if(str[i]=='0')
dp[i]=dp[i-1];
//else
{ if(str[i-1]=='1')
{ if(dp[i-1]==1 && str[i]!='0')
dp[i]=2;
else if(str[i]!='0')
dp[i]=dp[i-1]+dp[i-2];
}
if(str[i-1]=='2' && (str[i]>='0' && str[i]<='6')) {
if(dp[i-1]==1 && str[i]!='0')
dp[i]=2;
else if(str[i]!='0')
dp[i]=dp[i-1]+dp[i-2];
}
}
}
/* for(i=0;i<len;i++)
printf("%d ",dp[i]);
printf("\n");
*/ return dp[len-1];
}
int main()
{
while(1) {
char str[5010];
scanf("%s",str);//cout<<str<<endl;
if(strcmp("0",str)==0)
return 0;
printf("%d\n",count(str,strlen(str)));
valid=0;
}
return 0;
}
works for all above mentioned test cases but is giving WA
a is similar to dptable[i-2]
b is similar to dptable[i-1]
#include<stdio.h>
int main(void)
{
char str[5001];
unsigned long long int a,b,cnt=0,i=1,n;
scanf("%s",str);
while(str[0]!='0')
{
a=1;
b=1;
cnt=0;
i=1;
while(str[i]!='\0')
{
if(((str[i-1]=='2' && str[i]<'7') || (str[i-1]=='1')) && str[i]!='0')
cnt=a+b;
else if(str[i]=='0')
{
if(str[i-1]=='2' || str[i-1]=='1')
cnt=a;
else
{cnt=0; break;}
}
else
cnt=b;
a=b;
b=cnt;
i++;
}
printf("%llu\n",cnt);
scanf("%s",str);
}
return 0;
}
Problem url - http://www.spoj.pl/problems/ACODE/4
My code is working for test case but i am getting WA ... Could anyone suggest more test cases or point out the mistake in the program ?
include
include
using namespace std;
int main()
{
char s[10000];
long long int sc[10000],sz=0,i,j,k,c=0,ans=1,m,n,x;
while(1)
{
cin>>s;
sz=strlen(s);
if(sz==1 &&s [0]=='0')
break;
for(i=0;i<sz;i++)
{
if (s[i]=='0')
sc[c-1] = ((int)s[i-1]-48)*10;
else
{
sc[c] = (int)s[i]-48;
c++;
}
}
m=1;n=0;
if(sc[0]<27)
{
for(i=1;i<c;i++)
{
if(sc[i]>26)
{ans=0;break;}
if( (10*sc[i-1]+sc[i])<27 )
{
ans = 2*m+n;
x = m;
m = m+n;
n = x;
}
else{
ans = m+n;
m = m+n;
n = 0;
}
}
}
else
ans=0;
cout<<ans<<endl;
c=0;ans=1;
}
return 0;
}
can anybody give me sometest cases......... plzzzzzzzzzz.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string a;
while(1)
{
cin>>a;
if(a[0]=='0')
break;
int n=a.size();
long long int f[3];
f[0]=1;
int x=(a[1]-48)+(a[0]-48)*10;
int i=2;
if(x<=26 && x>10 && x!=20 && (a[1]!='0'))
{
if(x==21 || x==22 || x==11 ||x==12)
{
if(a[2]=='0')
{
f[1]=1;
i++;
}
else
{
f[1]=2;
}
}
else
f[1]=2;
}else
f[1]=1;
for(int i=2;i<n;i++)
{
x=(a[i]-48)+(a[i-1]-48)*10;
if(x<=26 && x>10 && x!=20)
{
if(x==21 || x==22 || x==11 || x==12)
{
if(a[i+1]=='0')
{
f[2]=f[1];
i++;
}
else
{
f[2]=f[0]+f[1];
}
}
else
f[2]=f[0]+f[1];
}
else
f[2]=f[1];
f[0]=f[1];
f[1]=f[2];
}
cout<<f[2]<<"\n";
}
}
}
@rbaid thanx......... bt it is again giving WA. its working for 110
#include <iostream>
#include <string>
using namespace std;
int main()
{
string a;
while(1)
{
cin>>a;
if(a[0]=='0')
break;
int n=a.size();
long long int f[3];
f[0]=1;
int x=(a[1]-48)+(a[0]-48)*10;
int i=2;
if(x<=26 && x>10 && x!=20 && (a[1]!='0'))
{
if(x==21 || x==22 || x==11 ||x==12)
{
if(a[2]=='0')
{
f[1]=1;
i++;
}
else
{
f[1]=2;
}
}
else
f[1]=2;
}else
f[1]=1;
for(int i=2;i<n;i++)
{
x=(a[i]-48)+(a[i-1]-48)*10;
if(x<=26 && x>10 && x!=20)
{
if(x==21 || x==22 || x==11 || x==12)
{
if(a[i+1]=='0')
{
f[2]=f[1];
i++;
}
else
{
f[2]=f[0]+f[1];
}
}
else
f[2]=f[0]+f[1];
}
else
f[2]=f[1];
f[0]=f[1];
f[1]=f[2];
}
cout<<f[2]<<"\n";
}
}
[quote="abhishekiiit"]@rbaid thanx......... bt it is again giving WA. its working for 110
#include <iostream>
#include <string>
using namespace std;
int main()
{
string a;
while(1)
{
cin>>a;
if(a[0]=='0')
break;
int n=a.size();
long long int f[3];
f[0]=1;
int x=(a[1]-48)+(a[0]-48)*10;
int i=2;
if(x<=26 && x>10 && x!=20 && (a[1]!='0'))
{
if(x==21 || x==22 || x==11 ||x==12)
{
if(a[2]=='0')
{
f[1]=1;
i++;
}
else
{
f[1]=2;
}
}
else
f[1]=2;
}else
f[1]=1;
for(int i=2;i<n;i++)
{
x=(a[i]-48)+(a[i-1]-48)*10;
if(x<=26 && x>10 && x!=20)
{
if(x==21 || x==22 || x==11 || x==12)
{
if(a[i+1]=='0')
{
f[2]=f[1];
i++;
}
else
{
f[2]=f[0]+f[1];
}
}
else
f[2]=f[0]+f[1];
}
else
f[2]=f[1];
f[0]=f[1];
f[1]=f[2];
}
cout<<f[2]<<"\n";
}
}
[/quote]
on testcase:
10
0
your code is giving some garbage value - 577741808038355000
Forum konkursu High School Programming League (hs.spoj.pl4)
My solution produces valid op for all the test cases mentioned here. However, it fails when i submit it. Any idea which test cases it could fail to?
#!/usr/bin/env python
def solution(a):
a = str(a)
poss = [0] * len(a)
for i in xrange(len(a)):
if i == 0:
poss[i] = 1
elif i > 0:
poss[i] = poss[i-1]
if int(a[i-1] + a[i]) < 27 and a[i] != '0':
if i >= 2:
poss[i] = poss[i-2] + poss[i-1]
else:
poss[i] = 2
return poss[-1]
while True:
a = int(raw_input())
if a == 0:
exit()
else:
print solution(a)
Please check my IO
Input
181292321118743131219236834956616923925
61247812412412123124579127212412435689
1798235697156912783569836129273561725378612378635613059612634513257896128935618263
91253942735679263798126356239175735123123621561235621891231231289329845123895893912943129491253945129543951293459125912534912359145912123591256
9125394273567124124121241266251212047128436215612356218912312312893298451238958939129431294912539451295439512934591259125349123591459121235912561451111111111
101010
502
0
Output
10240
19440
0
58773123072
125539390881792
1
0
Please check where my code is getting WA ? For what tests Case ?
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
using namespace std;
typedef long long int ll;
int main()
{
// ifstream cin("/Users/Rajdeep/Downloads/Google Code Jam Practice/Google Code Jam Practice/input.txt");
string s;
cin>>s;
while(s!="0")
{
ll n;
n = (ll)s.size();
long long int dp[n+1];
dp[n] = 1;
ll f;
f = s[n-1]-'0';
if(f==0)
{
dp[n-1]=0;
}
else
{
dp[n-1]=1;
}
for(ll i=n-2;i>=0;i--)
{
ll a;
a = s[i] - '0';
ll b;
b = s[i+1] - '0';
ll w;
w = (10*a)+b;
if(a==0&&b==0)
{
dp[0] = 0;
break;
}
else if(a!=0)
{
if(b!=0)
{
dp[i] = dp[i+1];
// cout<<w<<endl;
if(w<=26)
{
dp[i] = dp[i] + dp[i+2];
}
// cout<<dp[i]<<endl;
}
else
{
if(w<=26)
{
dp[i] = dp[i+2];
}
else
{
dp[0] = 0;
break;
}
}
}
else
{
dp[i] = dp[i+1];
}
}
cout<<dp[0]<<endl;
cin>>s;
}
return 0;
}
Suggested Topics
Topic | Category | Replies | Views | Activity |
---|---|---|---|---|
ADV04F - Four Chips(hard) HELP! | ProblemSet Archive | 1 | 54 | 18d |
Help me please! | ProblemSet Archive | 4 | 24 | 9d |
ABCPATH - ABC Path | ProblemSet Archive | 1 | 91 | May 11 |
Getting TLE in AKBAR - Akbar , The great. Why? | ProblemSet Archive | 3 | 190 | Mar 11 |
COT - Count on a tree - TLE | ProblemSet Archive | 1 | 132 | Mar 18 |