medium
1 views

Six Blocks Two Towers

Given six block heights and two target tower heights, arrange three blocks each to form two towers of specified heights, outputting blocks in descending order

Understand the Problem

Problem Statement

Given six blocks with specific heights and two target tower heights, determine how to arrange exactly three blocks for each tower such that the sum of block heights equals the target tower height. The blocks used for each tower must be output in descending order of their heights.

Each block can only be used once. The problem guarantees a valid solution exists.

Constraints

  • Height of each block: 1 ≤ height ≤ 1000
  • Height of each tower: 3 ≤ height ≤ 3000
  • Exactly 6 blocks will be provided as input
  • Exactly 2 tower heights will be provided as input
  • Each tower must use exactly 3 blocks
  • All blocks must be used (no blocks left unused)
  • A valid solution is guaranteed to exist

Examples

Example 1
Input
10 15 90 65 30 25
135 100
Output
90 30 15 & 65 25 10
Explanation

For tower 1 (height 135): 90 + 30 + 15 = 135. For tower 2 (height 100): 65 + 25 + 10 = 100. The blocks are sorted in descending order for each tower.

Example 2
Input
45 30 12 18 10 40
40 115
Output
18 12 10 & 45 40 30
Explanation

For tower 1 (height 40): 18 + 12 + 10 = 40. For tower 2 (height 115): 45 + 40 + 30 = 115. The blocks are sorted in descending order for each tower.

Solution

#include <stdio.h>
#include <stdbool.h>

void sortDescending(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] < arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int blocks[6];
    int tower1, tower2;
    
    // Read block heights
    for (int i = 0; i < 6; i++) {
        scanf("%d", &blocks[i]);
    }
    
    // Read tower heights
    scanf("%d %d", &tower1, &tower2);
    
    int used[6] = {0};  // Track which blocks are used
    int tower1Blocks[3];
    int tower2Blocks[3];
    bool found = false;
    
    // Try all combinations of 3 blocks
    for (int i = 0; i < 6 && !found; i++) {
        for (int j = i + 1; j < 6 && !found; j++) {
            for (int k = j + 1; k < 6 && !found; k++) {
                if (blocks[i] + blocks[j] + blocks[k] == tower1) {
                    // Found valid combination for tower 1
                    tower1Blocks[0] = blocks[i];
                    tower1Blocks[1] = blocks[j];
                    tower1Blocks[2] = blocks[k];
                    used[i] = used[j] = used[k] = 1;
                    found = true;
                }
            }
        }
    }
    
    // Collect remaining blocks for tower 2
    int idx = 0;
    for (int i = 0; i < 6; i++) {
        if (used[i] == 0) {
            tower2Blocks[idx++] = blocks[i];
        }
    }
    
    // Sort both towers in descending order
    sortDescending(tower1Blocks, 3);
    sortDescending(tower2Blocks, 3);
    
    // Output result
    for (int i = 0; i < 3; i++) {
        printf("%d ", tower1Blocks[i]);
    }
    printf("& ");
    for (int i = 0; i < 3; i++) {
        printf("%d", tower2Blocks[i]);
        if (i < 2) printf(" ");
    }
    
    return 0;
}
Time:O(1)
Space:O(1)
Approach:

The C solution uses nested loops to generate all possible combinations of 3 blocks from the 6 available blocks. For each combination, it checks if the sum equals the first target tower height.

Key steps:

  1. Read input using scanf
  2. Use three nested loops (i, j, k) to iterate through all combinations of 3 blocks
  3. When a valid combination for tower 1 is found, mark those blocks as used
  4. Collect the remaining 3 blocks for tower 2
  5. Sort both sets of blocks in descending order using bubble sort
  6. Output the result with proper formatting

The algorithm has O(1) time complexity since the number of blocks is fixed at 6, making the nested loops constant time.

Visual Explanation

Loading diagram...
All Problems