10324 - Zeros and Ones

[SARKAR]

lolzzz

i got ac with same code........but believe i got wrong ans so many times.........



dunno y??????

[kintu]

Hi,,,i solve this problem and it shows correct output for all input. I also test all input from forum. But when,i submit it to online judge, i give me WA.
Please give me some Sample Input,/output. Or test my code.
Hope reply.
Thanks in avance!

Here my code:

Code: Select all

/*** Remove after getting AC.

Thanks to Jaan Vaiya for his sample input ***/

[Jan]

Try the set.

Input:

Code: Select all

10000
4
0 1
0 2
0 3
0 4

Output:

Code: Select all

Case 1:
No
No
No
No

Hope it helps.

[ligregni]

Hi!, I used dinamyc memory in this problem,

I read each char (0 or 1) until I found a '\n',

I save this in a kind of stack (I say kind because it is not really a stack, I know the first element adress and the last element adress, the first element adress (from here "*first") is used in the solving part (I pass this adress, use it in the solve function, this is my index=0, I change *first until I get the lowest index of the i,j, then I review until i<j and when I found a 1 after a 0 (or a 0 after a 1), I end with the function, returning a value for use it and print "No", the last element adress (*last) is for adding new nodes to the pile)

I used this technique in other problem and It worked OK.

Here, I got TIME LIMIT EXCEEDED

Here's my code:

Code: Select all

/* Zeros and Ones */

#include <stdio.h>

struct DIGIT
{
	char d;
	struct DIGIT *next;
};

int add (struct DIGIT **, char);
int solve (struct DIGIT *, struct DIGIT *, int, int);

int main ()
{
/*FILE *in = freopen ("c.in", "r", stdin);/**/

	struct DIGIT *zed = NULL, *fis = NULL;

	char c='\0';

	int cases=0;

	while (c!=EOF&&(c=getchar())!=EOF)
	{
		struct DIGIT *zed = NULL, *fis = NULL;

		cases++;

		struct DIGIT *node;

		node = (struct DIGIT *) malloc (sizeof(struct DIGIT));

		node->d = c;

		node->next = zed;

		zed = node;

		fis = node;

		while ((c=getchar())!='\n')
			add (&zed, c);

		int query=0, query_r=0;

		scanf("%d", &query);

		printf("Case %d:\n", cases);

		while (query_r++<query)
		{
			int a, b;

			scanf("%d %d", &a, &b);

			printf("%s\n", (solve(fis, zed, a,b))?"Yes":"No");

		}

		c = getchar();
	}

	return 0;
}

int add (struct DIGIT **p, char c)
{
	struct DIGIT *node;

	node = (struct DIGIT *) malloc (sizeof(struct DIGIT));

	node->d = c;

	(**p).next = node;

	node->next = *p;

	*p = node;

	return 0;
}

int solve (struct DIGIT *p, struct DIGIT *q, int a, int b)
{
	if (a==b)
		return 1;

	if (a>b)
	{
		int c=a;
		a=b;
		b=c;
	}

	int x=0;

	while (x++<a)
	{
		p = p->next;
	}

	short va=0, flag=0;

	while (a<b)
	{
		va = p->d - '0';

		p = p->next;

		if ((p->d-'0')!=va)
			return 0;

		a++;
	}

	return 1;
}

Thanks!

[yjwoo14]

I don`t understand why i got WA

this is my code

Code: Select all

#include <iostream>

#define MAXL 1000002

using namespace std;

char M[MAXL];
int L[MAXL];

int main(){
        int casen = 1;
        int n;
        int last_fill, len;
        int x, y;
        char value;

        while(cin >> M){
                len = strlen(M);

                cin >> n;
                value = M[0];
                last_fill = 0;
                for (int i = 1 ; i < len ; i++){
                        if (value != M[i]){
                                for (int j = last_fill ; j < i ; j++){
                                        L[j] = i - 1;
                                }
                                value = M[i];
                                last_fill = i;
                        }
                }
                if (last_fill < len - 1){
                        for (int i = last_fill ; i < len ; i++){
                                L[i] = len - 1;
                        }
                }

                cout << "Case " << casen++ << ":" << endl;
                for (int i = 0 ; i < n ; i++){
                        cin >> x >> y;

                        if (L[x] >= y){
                                cout << "Yes" << endl;
                        }else
                                cout << "No" << endl;
                }
        }
}

I used another integer Array.

The array was used to indicate last Index that same character

[turcse143]

i think there is an error in here. check it.

Code: Select all

for (int i = 1 ; i < len ; i++){
                        if (value != M[i]){
                                for (int j = last_fill ; j < i ; j++){
                                        L[j] = i - 1;
                                }
                                value = M[i];
                                last_fill = i;
                        }
                } 

[vahid sanei]

i get TLE but my algo work with O(n)
i dont know i get time limit error

Code: Select all

  Removed

thanks in advance

[vahid sanei]

I got Acc ,
it "int a[1000000]" gives me stack overflow
but i can use "vector <int> a (1000000)" or a dynamic array

[noor_aub]

Hi

Can Any One Tell Me what to do in this problem. What Dose it Men by Min(i,j) and Max(i,j)

Thank You

[sohel]

The problem statement is pretty straight forward!
min(i,j) = minimum of i and j
max(i,j) = maximum of i and j

example:
min(5, 9) = 5
max(5, 9) = 9

[saiful_islam]

10324 - Zeros and Ones WA PLz HELP

Code: Select all

#include<stdio.h>
#include<string.h>
char a[1000010];
int  main()
{
	freopen("G:\\in.txt","r",stdin);
	
	freopen("G:\\out.txt","w",stdout);
	int i,e,r=1,t,y,u,v;
	
	while(gets(a))
	{
		printf("Case %d:\n",r);
		r++;
		v=1;
		int z,q,w;
		scanf("%d",&y);
		while(v<=y)
		{
		scanf("%d%d",&i,&e);
		if(i>e)
		{
			z=i;
			i=e;
			e=z;
		}
		
		if(a[i]==a[e])
		{
			u=1;
			while(i<=e&&u==1)
			{
				if(a[i]==a[e])
				{
					i++;
				}
				else
					u=0;

			}
		}
		else
			u=0;
		if(u==1)
			printf("Yes\n");
		else
			printf("No\n");
		v++;
		}
		gets(a);
		gets(a);

	}
	return 0;
}

[aaa111]

Why WA:

Code: Select all

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

#define SIZE 1000002
#define MAX(i,j) (i>j)?i:j
#define MIN(i,j) (i<j)?i:j

int Find_Result(char [],long,long);

int main(void)
{
char str[SIZE];
long i,j;
int k,n,l;

l=0;

while(gets(str)){
				if(strlen(str)==0)
					break;

				scanf("%d",&n);
		
				l++;

				for(k=0;k<n;k++)
						{
						scanf("%ld %ld",&i,&j);
			
						i=MIN(i,j);
						j=MAX(i,j);
					
						if(k==0)
							printf("Case %d:\n",l);										
							
						if(Find_Result(str,i,j))
							printf("Yes\n");
						else
							printf("No\n");
						}
				gets(str);
				}

return 0;
}

int Find_Result(char str[],long i,long j)
{
long k;
char ch;

ch=str[i];

for(k=i+1;k<=j;k++)
	{
	if(str[k]!=ch)
		return 0;			
	}

return 1;
}

[miisakib]

What's The Problem in My Code.. Why UVA shows it Wrong Answer??


#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;

int main()
{
long long int sumArray[1000002], caseNo=1, noOfQuery, temp1, i, j, sumOfNumbersBetweenTheRange, max, min;
string inputString;
sumArray[0]=0;
while(getline(cin,inputString))
{
if(inputString.length()==0)
{
break;
}
for(temp1=0; temp1<inputString.length(); temp1++)
{
if(inputString[temp1]=='1')
sumArray[temp1+1]=sumArray[temp1]+1;
else
sumArray[temp1+1]=sumArray[temp1];
}
cout<<"Case "<<caseNo<<":"<<endl;
caseNo++;
cin>>noOfQuery;
for(temp1=1; temp1<=noOfQuery; temp1++)
{
cin>>i>>j;
if(i>j)
{
max=i;
min=j;
}
else
{
max=j;
min=i;
}
sumOfNumbersBetweenTheRange=sumArray[max+1]-sumArray[min];
if(sumOfNumbersBetweenTheRange==0)
cout<<"Yes"<<endl;
else if(sumOfNumbersBetweenTheRange==(max-min+1))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
fflush(stdin);
}
}

[Baset]

Maybe your compiler does not have an 8 bits size char, or maybe it is another compiler related issue.

I compiled your program with gcc (which is the compiler the online judge uses) and it failed with that input Phone Card Calling Cards

[sijan]

Where is the problem of my code??? I have got 9 WA...Plzz help...

Code: Select all

#include <stdio.h>
#include <string.h>
#define indx 1000050

char a[indx],tmp,c;
int i,j,com,s,in[indx],cas=1,l;
int main()
{
	while(gets(a))
	{
		l=strlen(a);
		if(l==0)
			break;
		in[0]=0;
		s=1;
		while(s<l)
		{
			in[s]=in[s-1];
			if(a[s]!=a[s-1])
				in[s]++;
			s++;
		}
		scanf("%d",&com);
		printf("Case %d:\n",cas);
		cas++;
		while(com--)
		{
			scanf("%d %d",&i,&j);
			if(i>j)
			{
				tmp=i;
				i=j;
				j=tmp;
			}
			if(j>l)
				printf("No\n");
			else if(in[j] == in[i])
				printf("Yes\n");
			else
				printf("No\n");
		}
		getchar();
	}
	return 0;
}