10324 - Zeros and Ones

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

SARKAR
New poster
Posts: 21
Joined: Tue May 22, 2007 4:18 pm

hmmm...got ac

Post by SARKAR » Sun Jun 10, 2007 12:45 pm


lolzzz :lol:

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



dunno y??????

kintu
New poster
Posts: 6
Joined: Sun Mar 18, 2007 11:31 am
Location: In home

Post by kintu » Fri Jun 29, 2007 8:42 am

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 ***/
Last edited by kintu on Fri Jun 29, 2007 8:12 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Jun 29, 2007 11:37 am

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.
Ami ekhono shopno dekhi...
HomePage

ligregni
New poster
Posts: 11
Joined: Thu Nov 29, 2007 12:41 am
Location: Queretaro, M
Contact:

Help!, I am OK but TLE!!!

Post by ligregni » Thu Dec 27, 2007 2:13 am

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!
C: multum in parvo

"a lot since quite few"

http://acmicpc-live-archive.uva.es/nuev ... user=12539

yjwoo14
New poster
Posts: 7
Joined: Wed Jan 09, 2008 5:58 am

Plz Help me

Post by yjwoo14 » Sun Mar 16, 2008 3:14 pm

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
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Wed Mar 19, 2008 9:20 pm

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;
                        }
                } 
''I want to be most laziest person in the world''

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10324 - Zeros and Ones

Post by vahid sanei » Fri Jan 09, 2009 6:50 pm

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
Impossible says I`m possible

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10324 - Zeros and Ones

Post by vahid sanei » Thu Feb 26, 2009 7:40 am

I got Acc ,
it "int a[1000000]" gives me stack overflow
but i can use "vector <int> a (1000000)" or a dynamic array :lol:
Impossible says I`m possible

noor_aub
New poster
Posts: 26
Joined: Sat Aug 22, 2009 12:16 pm

Re: 10324 - Zeros and Ones

Post by noor_aub » Tue Jul 13, 2010 2:54 pm

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10324 - Zeros and Ones

Post by sohel » Wed Jul 14, 2010 5:14 pm

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
New poster
Posts: 6
Joined: Tue Feb 08, 2011 7:41 pm

Re: 10324 - Zeros and Ones

Post by saiful_islam » Fri Mar 11, 2011 10:39 am

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
New poster
Posts: 14
Joined: Sat Nov 21, 2009 2:55 pm

Re: 10324 - Zeros and Ones

Post by aaa111 » Wed Mar 16, 2011 10:14 pm

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
New poster
Posts: 1
Joined: Sat May 21, 2011 12:35 am

Re: 10324 - Zeros and Ones

Post by miisakib » Sat May 21, 2011 12:37 am

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
New poster
Posts: 1
Joined: Mon Sep 12, 2011 1:37 pm

Re: 10324 - Zeros and Ones

Post by Baset » Mon Sep 12, 2011 1:46 pm

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
Last edited by Baset on Wed Jun 05, 2013 7:05 pm, edited 1 time in total.

sijan
New poster
Posts: 5
Joined: Fri Sep 09, 2011 6:44 pm

10324 - Zeros and Ones..

Post by sijan » Sat Nov 19, 2011 5:22 pm

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


Post Reply

Return to “Volume 103 (10300-10399)”