×

Cake walk

None

# PROBLEM:

You're given an array of houses some of which have a bomb and others don't. These bombs will explode simultaneously and when bomb in ith house explodes, it destroys adjacent houses. Your task is to find out the number of houses which aren't destroyed.

# QUICK EXPLANATION:

For every house check if it is destroyed or not.

# DETAILED EXPLANATION:

There are two almost similar ways of solving this problem. Key idea is to find out for each house if it is destroyed or not. How do we check if ith house will be destroyed or not? It will be destroyed iff at least one of i-1, i and i+1th houses have a bomb. Just beware of the boundaries as first and last houses have only one adjacent house. So final solution is :

saved_count = 0
for i from 1 to N
destroyed = false
if( S[i] == '1') destroyed = true
if( i > 1 and S[i-1] == '1') destroyed = true
if( i < N and S[i+1] == '1') destroyed = true
if( not destroyed)
saved_count += 1
print saved_count


An alternative solution would be to move over houses with bombs and mark those houses that will explode.

bool will_be_destroyed [N]
fill( will_be_destroyed, false)

for i from 1 to N
if S[i] == '1'
will_be_destroyed[i] = true
if(i > 1) will_be_destroyed[i-1] = true
if(i < N) will_be_destroyed[i+1] = true

saved_count = 0
for i from 1 to N
if(not will_be_destroyed[i])
saved_count += 1

print saved_count


Both of these are O(N) solutions and very comfortably fit in time limit.

# TESTER'S SOLUTION:

Can be found here.

This question is marked "community wiki".

1243837
accept rate: 0%

 0 Tell the case where it fails? solution answered 28 Jul '14, 10:21 3★tech_boy 1.2k●4●19●31 accept rate: 7%
 0 Whats wrong in my code??? Why is it showing NZEC everytime. Some one please help. enter code here  import java.io.; import java.util.; class acm { public static void main(String[] args) { FasterScanner sc=new FasterScanner(System.in); int t=sc.nextInt(); while(t>0){ int n=sc.nextInt(); String s=sc.nextString(); int count=0; for(int i=0;i= numChars) { curChar = 0; try { numChars = mIs.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public String nextLine() { int c = read(); while (isSpaceChar(c)) c = read(); StringBuilder res = new StringBuilder(); do { res.appendCodePoint(c); c = read(); } while (!isEndOfLine(c)); return res.toString(); } public String nextString() { 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 long nextLong() { int c = read(); while (isSpaceChar(c)) c = read(); int sgn = 1; if (c == '-') { sgn = -1; c = read(); } long 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 int nextInt() { 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 boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; }  } enter code here  answered 09 Nov '16, 02:09 1★kanha95 1 accept rate: 0% I got it...i missed the case when n=1.... (09 Nov '16, 02:42) kanha951★
 0  #include using namespace std; main() { int t = 0 ; cin>>t; while(t--) { string inp; int b = 0 ; int u = 0 ; int s = 0 ; cin>>s; cin>>inp; for(int i = 0 ; i < s;i++) { if(inp.at(i) == '1' ) { b -= 2 ; if(i == 0 || i == s-1) { b += 1 ; } } else if (inp.at(i) == '0') { u++; } } cout<
 0 I'm getting WA. I don't understand on which test case its failing. Someone please help? link to solution: https://www.codechef.com/viewsolution/16605991 answered 19 Dec '17, 20:16 2★mohmum 2 accept rate: 0% @mohmum your code fails for 1 1 1 answer should be zero but your code prints 1 (19 Dec '17, 20:38)
 0 Somebody, please tell me where does my program fail? https://www.codechef.com/viewsolution/16606169 answered 19 Dec '17, 20:42 14●4 accept rate: 0%
 0 whats wrong in my C code for the problem LEBOMBS LEBOMBS https://www.codechef.com/viewsolution/17048802 can anyone tell me on which values my code fails .. Thanks answered 11 Jan, 01:36 1●1 accept rate: 0%

# include<bits stdc++.h="">

using namespace std; int main(){ int t;cin>>t; while(t--){ int n;cin>>n;int count=0; string s;cin>>s; if(s[0]=='1'){count+=1;if(s[1]=='0'){s[1]='2';count+=1;}} for(int i=1;i<n-1;i++){ if(s[i]="='0'||s[i]=='2'){continue;}" else{++count;="" if(s[i-1]="='0'){count+=1;}" if(s[i+1]="='0'){++count;s[i+1]='2';}" }}if(s[n-1]="='1'){count+=1;" if(n="">2){if(s[n-2]=='0'&&s[n-3]=='0')count+=1;} else if(s[0]=='0')count+=1;} cout<<(n-count)<<endl;} return 0;}

What is wrong with the code?

2★shubhsy
1
accept rate: 0%

 0 https://www.codechef.com/viewsolution/17555048 Can anyone help me with this code, please? answered 27 Feb, 15:00 2★shubhsy 1 accept rate: 0%

whats wrong in my solution?? \

# include<iostream>

using namespace std; int main(){ int i,n,t,count; cin>>t; while(t--){ count=0; cin>>n; char c[n]; for(i=0;i<n;i++) cin="">>c[i]; if(c[0]=='0'&&c[1]=='0'){ count++; } if(c[n-1]=='0'&&c[n-2]=='0'){ count++; } for(i=1;i<(n-1);i++){ if(c[i]=='0'){ if(c[i-1]=='0'&&c[i+1]=='0') count++; } } cout<<count<<endl; } return 0; }

1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,429
×1,429
×865
×15

question asked: 11 Aug '12, 15:32

question was seen: 4,965 times

last updated: 02 Jul, 02:07