Breaking Bricks Codechef Solution

Hello coders, today we are going to solve Breaking Bricks Codechef Solution.

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 Chase2learn.This tutorial is only for Educational and Learning purpose.