Hello Programmers In this post, you will know how to solve the Breaking Bricks Codechef Solution.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.
Problem
For her next karate demonstration, Ada will break some bricks.
Ada stacked three bricks on top of each other. Initially, their widths (from top to bottom) are W1,W2,W3W1,W2,W3.
Ada’s strength is SS. Whenever she hits a stack of bricks, consider the largest k≥0k≥0 such that the sum of widths of the topmost kk bricks does not exceed SS; the topmost kk bricks break and are removed from the stack. Before each hit, Ada may also decide to reverse the current stack of bricks, with no cost.
Find the minimum number of hits Ada needs in order to break all bricks if she performs the reversals optimally. You are not required to minimise the number of reversals.
Input
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first and only line of each test case contains four space-separated integers SS, W1W1, W2W2 and W3W3.
Output
For each test case, print a single line containing one integer ― the minimum required number of hits.
Constraints
- 1≤T≤641≤T≤64
- 1≤S≤81≤S≤8
- 1≤Wi≤21≤Wi≤2 for each valid ii
- it is guaranteed that Ada can break all bricks
Subtasks
Subtask #1 (50 points): W1=W2=W3W1=W2=W3
Subtask #2 (50 points): original constraints
Sample Input 1
3 3 1 2 2 2 1 1 1 3 2 2 1
Sample Output 1
2 2 2
Explanation
Example case 1: Ada can reverse the stack and then hit it two times. Before the first hit, the widths of bricks in the stack (from top to bottom) are (2,2,1)(2,2,1). After the first hit, the topmost brick breaks and the stack becomes (2,1)(2,1). The second hit breaks both remaining bricks.
In this particular case, it is also possible to hit the stack two times without reversing. Before the first hit, it is (1,2,2)(1,2,2). The first hit breaks the two bricks at the top (so the stack becomes (2)(2)) and the second hit breaks the last brick.
Breaking Bricks CodeChef Solution in JAVA
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef {
public static void main(String[] args) throws java.lang.Exception {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t != 0) {
int s = sc.nextInt();
int w1 = sc.nextInt();
int w2 = sc.nextInt();
int w3 = sc.nextInt();
if (w1 + w2 + w3 <= s)
System.out.println(1);
else if (w1 + w2 <= s || w2 + w3 <= s)
System.out.println(2);
else
System.out.println(3);
t--;
}
}
}Breaking Bricks CodeChef Solution in CPP
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int s;
cin>>s;
int a,b,c;
cin>>a>>b>>c;
int sum=a+b+c;
if(sum<=s)
cout<<1<<endl;
else
{
if(a+b<=s or b+c<=s)
cout<<2<<endl;
else
cout<<3<<endl;
}
}
}
Breaking Bricks CodeChef Solution in Python
try:
t=int(input())
for _ in range(t):
s,*w = map(int,input().split())
if sum(w)<=s:
print("1")
elif ((w[0]+w[1])<=s and w[2]<=s) or ((w[2]+w[1])<=s and w[0]<=s):
print("2")
else:
print("3")
except Exception :
pass
Disclaimer: The above Problem (Breaking Bricks) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.
Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.