## 10324 - Zeros and Ones

Moderator: Board moderators

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

### hmmm...got ac

lolzzz 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
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.
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
Contact:
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!!!

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')

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

I dont 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;
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
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''
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 10324 - Zeros and Ones

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

Code: Select all

  Removed

Impossible says Im possible
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 10324 - Zeros and Ones

I got Acc ,
it "int a" gives me stack overflow
but i can use "vector <int> a (1000000)" or a dynamic array Impossible says Im possible
noor_aub
New poster
Posts: 26
Joined: Sat Aug 22, 2009 12:16 pm

### Re: 10324 - Zeros and Ones

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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 10324 - Zeros and Ones

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

10324 - Zeros and Ones WA PLz HELP

Code: Select all

#include<stdio.h>
#include<string.h>
char a;
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

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

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, caseNo=1, noOfQuery, temp1, i, j, sumOfNumbersBetweenTheRange, max, min;
string inputString;
sumArray=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

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

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

`