10324 - Zeros and Ones

[ibrahim]

Do u get any idea ?

Thanks for your answere.

I use this process. But it takes 0.141
Any body, want to say some thing???

Ibrahim

[Rocky]

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

#define max 1000000

int main(void)
{
char input[max],c;
int i,j,i_j,caseno,t_c,t1,t2,not=0,test,temp;
caseno=0;

while(scanf("%s",input)!=EOF)
{
temp = strlen(input);
if(temp==0)
break;
caseno++;
scanf("%d",&test);
printf("Case %d:\n",caseno);
for(t_c=1;t_c<=test;t_c++)
{
scanf("%d%d%c",&i,&j,&c);
not=0;

t1= (i>j)?i:j;
t2= (i<j)?i:j;

if(t2>temp)
{
printf("No\n");
continue;
}

for(i_j=t1;i_j<t2;i_j++)
{
if(input[i_j]!=input[i_j+1])
{
not=1;
break;
}
}

if(not) printf("No\n");
else printf("Yes\n");
}
}
return 0;
}

Can Any Body Help Me?

Thank's IN Advance
Rocky

[shamim]

int i,j,i_j,caseno,t_c,t1,t2,not=0,test,temp;

you are using a variable name not, change it to a different name. not is actually an operator. e.g if (not i), meaning if ( !i)

[Rocky]

I Change It And Got TLE Why???
What Is The Efeicient Way To Solve It.
Need Help.

Thank's in Advance
Rocky

[Rocky]

Yehaa.

Got It.I Got Acc At Last.Thank's To Shamim
Shamim Can i Get Your Email Adress.

Thank's
Rocky

[J&Jewel]

Please do not new post the same number problem....

[59557RC]

ll i not b able 2 solve 10324.my code below :


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

int main(void)
{

char str[1000000],ch;
long int i,j,c,f,flag,temp,count=0,p,q;
gets(str);
while(str[0]!='\0'){
count++;
scanf("%ld",&c);



for(i=0;i<c;i++){
flag=0;
scanf("%ld %ld",&p,&q);
if(f==0){printf("Case %ld:\n",count);f=1;}
if(p>q) {temp=p;p=q;q=temp;}
ch=str[p];

for(j=p;j<=q;j++){


if(ch!=str[j]) {flag=1; printf("No\n");break;} }




if(flag==0) printf("Yes\n");

}

gets(gets(str));
f=0;

}






return 0;
}

[59557RC]

can anyone pls explain me some things:

1. what does it mean by "input may be with end of file"?
2. what does gets(gets(str)) means?
3.what's wrong with my code :

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

int main(void)
{

char str[1000000],ch;
long int i,j,c,flag,temp,count=0,p,q;
gets(str);
while(str[0]!=0){
count++;
printf("Case %ld:\n",count);
scanf("%ld",&c);



for(i=0;i<c;i++){
flag=0;
scanf("%ld %ld",&p,&q);

if(p>q) {temp=p;p=q;q=temp;}

ch=str[p];

for(j=p;j<=q;j++){


if(ch!=str[j]) {flag=1; printf("No\n");break;} }




if(flag==0) printf("Yes\n");

}

gets(gets(str));


}






return 0;
}

[59557RC]

can anyone pls explain me some things:

1. what does it mean by "input may be with end of file"?
2. what does gets(gets(str)) means?
3.what's wrong with my code :

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

int main(void)
{

char str[1000000],ch;
long int i,j,c,flag,temp,count=0,p,q;
gets(str);
while(str[0]!=0){
count++;
printf("Case %ld:\n",count);
scanf("%ld",&c);



for(i=0;i<c;i++){
flag=0;
scanf("%ld %ld",&p,&q);

if(p>q) {temp=p;p=q;q=temp;}

ch=str[p];

for(j=p;j<=q;j++){


if(ch!=str[j]) {flag=1; printf("No\n");break;} }




if(flag==0) printf("Yes\n");

}

gets(gets(str));


}






return 0;
}

[dumb dan]

1. Input may be terminated by either EOF or a blank line. So you need to use something like while(cin>>str&&str!=""){/*...*/}; rather than just while(str!=""){/*...*/};
2. Basically the same thing as gets(str);gets(str);, meaning you do two gets-calls where the second overwrites the first. This is because gets(str) returns str if the call was executed successfully (otherwise a null-pointer is returned).

3. (I'll leave this one for you or someone else to figure out).

[sohel]

1] Already answered.
2] Already answered.

3] First of all don't declare huge arrays within the main function.. try to declare it gloablly or make it static.
.. second thing is that a bruteforce solution for this problem won't pass the time limit. This problem can be solved in O(n) time where n is the length of the original string and for each query O(1) should be used.

Some hints and spoilers:
suppose the string is "00011101100111000111",
try to maintain another array that will map a sequence of a particular character to one integer... and then for each query, simply check whether the lower and upper range map to the same integer..

ie. the above string would be transformed to A[11122234455666777888]
.. so if the query is (3 7) then the anwer is no because A[3] != A[7] .

Hope it helps.

[mohsincsedu]

I do not uderstand Why i got TLE
Plz tell me about this!!!

Here is my code:

Code: Select all

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

#define MAX 1000001
#define M 1000001

char num[MAX];


int main()
{
   int counter[M];
   long n, a, b, i, j,len,test = 1;
   char pre, post;
   //freopen("10324.in","r",stdin);
   //freopen("10324.out","w",stdout);
   while(scanf("%s",num)!=EOF)
   {
      if(num[0]=='\0')
         break;
      len = strlen(num);
      for(i = 0; i<= len;i++)
         counter[i] = 0;
      pre = num[0];
      for(i = 1;i<len;i++)
      {
         post = num[i];
         if(pre!=post)
         {
            for(j = i;j<len;j++)
               counter[j]++;
            pre = post;
         }
      }
      scanf("%ld",&n);
      printf("Case %ld:\n",test++);
      for(i = 1;i<=n;i++)
      {
         scanf("%ld %ld",&a,&b);

         if(counter[a]==counter[b])
            printf("Yes\n");
         else
            printf("No\n");
      }

   }
   return 0;
}

[Solaris]

Code: Select all

for(i = 1;i<len;i++)
      {
         post = num[i];
         if(pre!=post)
         {
            for(j = i;j<len;j++)
               counter[j]++;
            pre = post;
         }
      }


Dear Mohsin,

u r running a O(n^2) loop here. As n can be as big as 10,00,000 u should get TLE.

You have to think of a better algo

[mohsincsedu]

Thanks Solaris...
I got ACC........

[sv90]

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

i with draw my code