EMTY2 - Can You Make It Empty 2

You are given a string S with only 0 and 1. You can delete the string 100 from any position of S an infinite number of times and obtain a new S after concatenation. Is it possible to make the string empty?

As for example, if S=101000 then 101000->100->empty

If S=1010001 then 1010001->1001->1->not empty


Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains a string S. The size of string is at most 120000.


For each test case, print the case number and “yes” if it is possible to make the string S empty, print “no” otherwise.

Sample Input

Output for Sample Input


Case 1: yes
Case 2: no

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology

hide comments
sanjeev30798: 2020-01-12 18:42:09

counting zeroes and ones would not help. For numbers like 100001, counting would give yes but the answer is no.

prachij: 2019-12-17 09:27:56

Solved it just by counting :)

iamwaste: 2019-02-08 19:53:28

interesting question - think about automata theory while doing - AC on second attempt

payal2621: 2018-01-29 15:41:52

guys getting tle use this "ios_base::sync_with_stdio(false);"

sedulous_001: 2017-09-25 16:21:18

Yes, there is white space between " Case x: " & "yes/no". Got wrong answer twice :(

vinuvarsidh: 2017-09-17 16:49:01

iam getting wrong answer.. though i print it as Case 1: yes can anyone tell me why

mahilewets: 2017-08-30 11:17:03

Sample output looks like there is no whitespace between "Case X:" and "yes/no"

But there is

And if you do not output whitespace after ":" you are WA

nikhil2504: 2017-07-07 02:10:24

Stack kills it!

vengatesh15: 2017-01-21 17:59:10

AC in 1 go:-)

madhavgaba: 2016-12-16 09:11:01

Did without stacks in O(n)........just count number of zeros and ones :D

Added by:Md Abdul Alim
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem