10324 - Zeros and Ones

[mamun]

BY THIS CODE ICAN'T GET SEVERAL INPUT
SO WHAT CAN I DO NOW

You can write your code so that it can read inputs until EOF. There are many posts regarding this like the sticky post of 100. Anyway here it can be

Code: Select all

while(scanf(" %s",str)!=EOF)             //str is char array
{
     // this is the beginning of each input block
     // do all the initializaion and processing here and then print output.
}

Search the forum. You'll get more help.

[sv90]

thanks

[sv90]

This is my code but i got WA
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main()
{
unsigned long int i,m=0,a[100001],t=0,counter=0,l;
unsigned long int j,cases,z=0;
unsigned long int min,max;
char ch[100001],ctemp[1];

while((scanf("%s",&ch))!=EOF)
{
z++;
counter=0;
l=strlen(ch);
for(t=0;t<=l;t++)
{
ctemp[0]=ch[t];
i=atoi(ctemp);
if(i==m)
{
a[t]=counter;
}
else if(i!=m)
{
m=i;
counter++;
a[t]=counter;
}
}
scanf("%lu",&cases);
for(j=1;j<=cases;j++)
{
if(j==1)
{
printf("Case %lu:\n",z);
}
scanf("%lu%lu",&min,&max);
if(a[min]==a[max])
{
printf("Yes\n");
}
if(a[min]!=a[max])
{
printf("No\n");
}
}
}
return 0;
}

[beloni]

This is wrong:

while((scanf("%s",&ch))!=EOF)

the name of an array is the same address of the array, so if you put &ch is an error

[beloni]

can you show me that algorithm did you used to got AC???
cause I'm with same problem...
and I have no idea...

[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.

[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

[beloni]

well, your code ... try to broken it down in some functions...

It is so dificult to read

[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;
}

[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"


[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[i]!=c[i-1]) m[i]=m[i-1]+1;
else m[i]=m[i-1];
}
cin>>n;
for(i=0;i<n;i++)
{
cin>>a>>b;
if(m[a]==m[b]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}

[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[i]!=c[i-1]) m[i]=m[i-1]+1;
else m[i]=m[i-1];
}
cin>>n;
for(i=0;i<n;i++)
{
cin>>a>>b;
if(m[a]==m[b]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}

[emotional blind]

no one should post his ACCEPTED code here.
its very much spoiling.

[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;
}


[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 ...