Page 8 of 12
Posted: Mon Mar 06, 2006 6:16 pm
by mf
Just consider the string as a sequence of numbers {a_1, a_2, ..., a_n}, and compute its partial sums: S_k=a_1+a_2+...+a_k. (trivial DP: S_0=0, S_k=S_{k-1}+a_k.)
Then all elements in range i..j are 0's if S_{i-1}=S_j.
And elements in range i..j are 1's if S_j-S_{i-1} = j-i+1.
thanks
Posted: Tue Mar 07, 2006 11:04 am
by sv90
but it still have problem
its output is bellow
Case 1:
No
Yes
Yes
Case 2:
Yes
Yes
Yes
Yes
Yes
Case 3:
Yes
so what should i do now
Posted: Tue Mar 07, 2006 1:50 pm
by beloni
well, your code ... try to broken it down in some functions...
It is so dificult to read
Posted: Tue Mar 07, 2006 2:18 pm
by beloni
thanks, but anyway I'll must to cover the array in range i..j, as well my TLE algorithm.. or no ???
int same(int start, int end, const char *str)
{
int w;
for(w = start+1; w <= end; w++)
if( str[w] != str[start] )
return 0;
return 1;
}
Posted: Tue Mar 07, 2006 4:01 pm
by mf
No, my algorithm finds the answer by examining just two elements of array S, it doesn't need to scan the sequence.
Maybe my previous post wasn't very clear to you, so here's a pseudocode:
Code: Select all
Let a[0], a[1], ..., a[n-1] be the input sequence of 0's and 1's.
Let S be an array of size n+1, indexed from 0 to n.
S[0] = 0
for i = 1 to n do:
S[i] = S[i-1] + a[i-1]
/* Now every S[k] is equal to the sum: S[k] = a[0] + a[1] + ... + a[k-1]. */
for each query i, j do:
if i > j then swap(i, j)
x = S[j+1] - S[i]
/* Now x is equal to the sum a[i] + a[i+1] + ... + a[j]. */
if x == 0 or x == (j-i+1) then
print "Yes"
else
print "No"
Re: 10324 Help me ! or i will DIE
Posted: Sat Jul 01, 2006 12:55 pm
by Stummer
Why I got TLE??
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
char c[1000005];
int m[1000005];
int main()
{
int n,a,b,i,ii=0;
while(scanf("%s",c)!=EOF)
{
ii++;
cout<<"Case "<<ii<<':'<<endl;
m[0]=0;
for(i=1;i<strlen(c);i++)
{
if(c
!=c[i-1]) m=m[i-1]+1;
else m=m[i-1];
}
cin>>n;
for(i=0;i<n;i++)
{
cin>>a>>b;
if(m[a]==m) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}
Re: 10324 Help me ! or i will DIE
Posted: Sat Jul 01, 2006 12:59 pm
by Stummer
At least I got Accepted!
Here is my code:
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
char c[1000005];
int m[1000005];
int main()
{
int n,a,b,i,ii=0,k;
while(scanf("%s",c)!=EOF)
{
ii++;
cout<<"Case "<<ii<<':'<<endl;
m[0]=0;
k=strlen(c);
for(i=1;i<k;i++)
{
if(c
!=c[i-1]) m=m[i-1]+1;
else m=m[i-1];
}
cin>>n;
for(i=0;i<n;i++)
{
cin>>a>>b;
if(m[a]==m) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}
Posted: Sun Jul 02, 2006 9:08 pm
by emotional blind
no one should post his ACCEPTED code here.
its very much spoiling.
10324
Posted: Sun Jul 09, 2006 8:44 am
by S.M.Abdullah
I have submitted prime cut. But the machine give me wrong answer.
What's the problem?
Code: Select all
#include<stdio.h>
int main()
{
char a[100000];
long long i,p,q,c,d,x,j,z=1,flage,temp;
while(scanf("%s",a)!=EOF)
{
if(a=="\0")
break;
scanf("%lld",&x);
printf("Case %lld:\n",z++);
for(j=1;j<=x;j++)
{
XY:
flage=1;
scanf("%lld %lld",&p,&q);
if(q<p)
{
temp=p;
p=q;
q=temp;
}
for(i=p;i<q;i++)
{
if(a[i]!=a[i+1])
{
flage=0;
printf("No\n");
j=j+1;
if(j<=x)
goto XY;
}
}
if(flage==1)
printf("Yes\n");
}
}
return 0;
}
Posted: Sun Jul 09, 2006 10:04 am
by Joseph Kurniawan
What problem are you working at?
Is it 10324 - Zeros and Ones?
Besides this is the forum for Volume I --> for prob 100 until 199.
Suggestion.
Posted: Sun Jul 09, 2006 11:54 am
by linux
Hi, Abdullah I'll just suggest you that you should avoid using goto functions. It can cause unexpected errors along with extra raising extra complexity in code. So it's a good practice to avoid using goto.
Keep posting!
10324
Posted: Thu Sep 07, 2006 6:16 am
by newton
i cant find what is the problem with my innocent code?
why wrong answer?
can anybody help me finding the problem?
Code: Select all
#include<stdio.h>
#include<string.h>
main()
{
char str1[1000001];
char str2[1000001];
int Case,m,n,i,c;
Case=0;
while(scanf("%s",str1)==1)
{
str2[0]=1;
for(i=0;str1[i];i++)
if(str1[i]!=str1[i+1])
str2[i+1]=str2[i]+1;
else
str2[i+1]=str2[i];
printf("Case: %d\n",++Case);
scanf("%d",&c);
for(i=1;i<=c;i++)
{
scanf("%d %d",&m,&n);
if(str2[m]==str2[n])
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}
10324
Posted: Fri Sep 08, 2006 7:09 pm
by nnicool
I don't know why WA..
I can't find any mistakes in my code..
-----------------------
#include <iostream>
#define swap(a,b){a^=b;b^=a;a^=b;}
using namespace std;
int main()
{
long cnt,pos,tmp,T,min,max,CASES,TOTAL,size;
char G[1000001];
char buf,ch;
CASES = 0;
while(!cin.eof())
{
if(cin.eof())
break;
cnt = pos = 0;
CASES++;
cin.getline(G,1000000);
size = strlen(G);
buf = G[0];
G[0] = (char)0;
for(tmp = 0; tmp < size-1;tmp++)
{
cnt++;
ch = G[cnt];
if(ch == buf)
G[cnt] = pos;
else
{
G[cnt] = ++pos;
buf = ch;
}
}
cin >> T;
cout << "Case " << CASES << ":" << endl;
for(cnt = 0; cnt < T;cnt++)
{
cin >> min >> max;
if ( min > max )
swap(min,max);
if(size-1 < max || min < 0)
cout << "No" << endl;
else
{
if(G[min] == G[max])
{
cout << "Yes" << endl;
}
else
cout << "No" << endl;
}
}
cin.get();
}
return 0;
}
----------------
if ther are complex test cases , plz ...
Posted: Thu Sep 21, 2006 5:06 pm
by rio
"The input ends with an empty string that is a line containing only the new line character, this string should not be processed. The input may also with end of file. So keep check for both."
try this code.
CASES++;
cin.getline(G,1000000);
size = strlen(G);
if (size == 0) break; // i think you need this!
buf = G[0];
Posted: Sun Oct 01, 2006 4:58 pm
by daveon
Hi,
The strings can be up to 1000000 characters long. So you need at least 1000001 sized array because you need 1 more for the null character. So just increase your array size.