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

pecijackson
New poster
Posts: 3
Joined: Tue Jan 31, 2012 7:05 am

Re: How long can a Pascal string be?

yes you might use unsistring because of it's dinamic size, though it will make it slower.

nazmus_20000
New poster
Posts: 7
Joined: Fri Dec 14, 2012 9:01 pm

10324 - Zeros and Ones

pls can anyone tell why it is not accepting plzz....

#include<stdio.h>
#include<string.h>
int main()
{
char a[1000001];
int n,i,j,k,l,b=1,c,t;
while(scanf("%s",&a)!=EOF)
{
if(strlen(a)==0)break;
scanf("%d",&n);
for(k=1;k<=n;k++)
{
scanf("%d %d",&i,&j);
if((i>strlen(a)-1)||(j>strlen(a)-1))t=0;
if(i>j)
{
c=i;i=j;j=c;
}
if(k==1)printf("Case %d:\n",b++);
for(l=i;l<j;)
{
if(t==0)
{
printf("No\n");
l=j-1;
break;
}
if(i==j)
{
printf("Yes\n");
l=j-1;
break;
}
if(a[l]==a[l+1])
{
l++;
}
else
{
printf("No\n");
break;
}
}
if(l==j)printf("Yes\n");
}
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10324 - Zeros and Ones

doesn't match the sample i/o
Check input and AC output for thousands of problems on uDebug!

sindrella
New poster
Posts: 1
Joined: Thu Mar 07, 2013 8:43 am

Re: How long can a Pascal string be?

I have no idea but get lots of help from your page.. knowledgeable sharing you have done....

arjun22
New poster
Posts: 1
Joined: Thu Jul 25, 2013 5:20 pm

10324 - Zeros and Ones

can anyone pl tell me why i'm getting WA with this code
#include<stdio.h>
int main()
{
int n,i,j,p,q,temp,k=0;
char a[1000002];

while(fgets(a,1000001,stdin))
{
fflush(stdin);
if(a[0]=='\n')
break;
scanf("%d",&n);
k++;
printf("Case %d:\n",k);
for(i=0;i<n;i++)
{
scanf("%d %d",&p,&q);
fflush(stdin);
if(p>q)
{
temp=p;
p=q;
q=temp;
}
for(j=p+1;j<=q;j++)
{
if(a[j]!=a[p])
{
printf("No\n");
break;
}
}
if(j==q+1)
{
printf("Yes\n");
}
}

}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10324 - Zeros and Ones

Don't use fflush(stdin);
Check input and AC output for thousands of problems on uDebug!

SamuelTangz
New poster
Posts: 4
Joined: Wed Jul 31, 2013 11:09 am

Re: 10324 - Zeros and Ones

I have received TLE verdict with this code...
Could anyone help?

Code: Select all

``Removed after AC``
Last edited by SamuelTangz on Thu Aug 15, 2013 10:30 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10324 - Zeros and Ones

Execute lines 14-22 of your code once per test case instead of every query.
Check input and AC output for thousands of problems on uDebug!

SamuelTangz
New poster
Posts: 4
Joined: Wed Jul 31, 2013 11:09 am

Re: 10324 - Zeros and Ones

brianfry713 wrote:Execute lines 14-22 of your code once per test case instead of every query.
ACed... I have rewritten this code twice and didn't observe this mistake...
Thank you!!

Salam!
New poster
Posts: 7
Joined: Tue Sep 10, 2013 7:14 pm

Re: 10324 - Zeros and Ones

Hi Guys
I Don't know why I get TLE On My code (10324 Zero and Ones)
Plz Help me
I Think My Algorithm is good

Code: Select all

``````#include<iostream>
#include<string>
using namespace std;
int main()
{
string s;
int p=0;
while(getline(cin,s))
{
if(s.empty())break;
p++;
int n;
cin>>n;
cout<<"Case "<<p<<":"<<endl;
for (int i = 0; i < n; i++)
{
int a,b;
cin>>a>>b;
int y=0,u=0;
if(a>b)swap(a,b);
for (int j = a; j <= b; j++)
{
if(s[j]=='0')y++;
else if(s[j]=='1')u++;
}

if(u!=0&&y!=0) cout<<"No\n";
else cout<<"Yes\n";
}
getline(cin,s);
}
return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10324 - Zeros and Ones

Read this thread. Your algorithm is too slow.
Check input and AC output for thousands of problems on uDebug!

siriustrung
New poster
Posts: 1
Joined: Mon Sep 23, 2013 9:53 pm

Re: 10324 - Zeros and Ones

Hi there, I tried many times but keep receiving LTE. I even tried to have a faster input and output. Many thanks if someone can look through and give me advices

Code: Select all

``````import java.io.*;

import java.util.*;

public class Main {

public static void main (String args[]){
// TODO Auto-generated method stub
InputReader in 		= new InputReader(System.in);
OutputWriter out	=	new OutputWriter(System.out);
int count = 0;
String text = in.readString();
while ((text != null) && (text != ""))
{
count++;
char arrayString [] = text.toCharArray();
int tests = in.readInt();

System.out.println("Case "+(count)+":");
for (int i = 0; i< tests; i++){
int tem = 0;
int value1 = in.readInt();
int value2 = in.readInt();
if (value1>value2) {
tem = value1;
value1 = value2;
value2 = tem;
}
String isSame = "Yes";
for (int j = value1; j<value2; j++){
if(j+1 < value2){
if (arrayString[j] != arrayString[j+1]){
isSame = "No";
break;
}
}}
out.printLine(isSame);
out.flush();

}
text = in.readString();
out.printLine(text);}
out.close();
}

}
class InputReader {

private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;

public InputReader(InputStream stream) {
this.stream = stream;
}

public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}

public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}

public String readString() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}

public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public String next() {
return readString();
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}

class OutputWriter {
private final PrintWriter writer;

public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}

public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}

public void print(Object...objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}

public void printLine(Object...objects) {
print(objects);
writer.println();
}

public void close() {
writer.close();
}

public void flush() {
writer.flush();
}

}

class IOUtils {

public static int[] readIntArray(InputReader in, int size) {
int[] array = new int[size];
for (int i = 0; i < size; i++)
array[i] = in.readInt();
return array;
}

}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10324 - Zeros and Ones

brianfry713 wrote:Read this thread. Your algorithm is too slow.
Check input and AC output for thousands of problems on uDebug!

Al'
New poster
Posts: 1
Joined: Fri Apr 18, 2014 11:22 pm

Re: 10324 - Zeros and Ones

Code: Select all

``````#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
char in, last;
int  totalQuestions;
int  a, b;
int  counter = 0;
int  number = 1;
int  *changes = (int*) malloc(sizeof(int) * 1000020);

while(1)  {
counter = 1;
last    = getchar();
if(!(last == '0' || last == '1')) break;
changes[0] = 0;
while((in = getchar()) && in != '\n') {
if(last == in) changes[counter++] = changes[counter-1];
else {
changes[counter++] = changes[counter-1] + 1;
}
last = in;
}
scanf("%d", &totalQuestions);
printf("Case %d:\n", number++);
while(totalQuestions--) {
scanf("%d %d", &a, &b);
if((a < counter && b < counter) && changes[a] == changes[b]) printf("Yes\n");
else {
printf("No\n");
}
}
getchar();
}
return 0;
}
``````
Can someone spot my mistake or give test case which fails?

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10324 - Zeros and Ones

Al' wrote:Can someone spot my mistake or give test case which fails?
Couple points:

(1) Couldn't get your code to produce any output unless I commented out the following lines

Code: Select all

``````#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif``````
Why don't you consider redirecting from stdin instead of opening a file?

(2) Don't expect the judge's input to always be perfectly formatted. So, it's probably not a good idea to use getchar()s to deal with newlines.

(3) Your code doesn't generate the correct output for the following input. Specifically, Cases 5 through 7 are not output.

Input:

Code: Select all

``````0000011111
3
0 5
4 2
5 9
01010101010101010101010101111111111111111111111111111111111110000000000000000
5
4 4
25 60
1 3
62 76
24 62
1
1
0 0
01
1
0 1
000011111
5
0 3
0 4
4 5
2 4
9 11
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1
500 501
10000
4
0 1
0 2
0 3
0 4
``````
AC Output:

Code: Select all

``````Case 1:
No
Yes
Yes
Case 2:
Yes
Yes
No
Yes
No
Case 3:
Yes
Case 4:
No
Case 5:
Yes
No
Yes
No
No
Case 6:
Yes
Case 7:
No
No
No
No
``````
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.