22. Two pictures on paper - solution
Introduction
In this task we need to examine how many correct arrangements there are for two pictures on a sheet of paper of known dimensions, with certain restrictions:
- The pictures must be shown completely on the paper, without overlapping.
- The pictures are placed parallel to the edges of the paper (the pictures are not rotated).
- The paper can be rotated (horizontal "landscape" and vertical "portrait" orientation).
- The pictures can be placed in two basic arrangements:
- One below the other.
- One next to the other.
The pictures can be placed in at most four arrangements, but some of them may be incorrect because of the size of the paper compared to the pictures.
Instructions for solving
1. Input data
We read the dimensions of the paper, the first picture and the second picture:
- Width and height of the paper.
- Width and height of the first picture.
- Width and height of the second picture.
2. Rotating the paper
We consider two cases for the paper:
- Horizontal orientation (width × height).
- Vertical orientation (height × width).
3. Checking the arrangement of the pictures
For every placement case we check:
- Whether the pictures can fit one below the other:
- Total height of the pictures ≤ height of the paper and the width of each picture ≤ width of the paper.
- Whether the pictures can fit one next to the other:
- Total width of the pictures ≤ width of the paper and the height of each picture ≤ height of the paper.
4. Result
The number of correct arrangements can be from 0 (no correct arrangements) to 4 (all combinations are correct). We print the number of correct arrangements.
Note
- Think about all combinations of the dimensions of the paper and the pictures, especially taking into account that the paper can be rotated.
- If no arrangement is valid, the result is 0.
Solution 1
#include <iostream> // Enables working with input and output using namespace std; // Uses the standard namespace int main() { int w, h, pw1, ph1, pw2, ph2; // Declares the dimensions of the paper (w, h) and the dimensions of the pictures (pw1, ph1, pw2, ph2) cin >> w >> h >> pw1 >> ph1 >> pw2 >> ph2; // Reading the dimensions of the paper and the pictures int b = 0; // Counter of valid arrangements of the pictures // 1. Checking the first arrangement: pictures next to each other int pwu = pw1 + pw2; // Total width of the pictures next to each other int phu = (ph1 > ph2) ? ph1 : ph2; // Maximum height of the pictures if(w >= pwu && h >= phu) { b++; // If the width and height of the paper are enough, increase the counter } // 2. Checking the second arrangement: pictures one below the other pwu = ph1 + ph2; // Total height of the pictures one below the other phu = (pw1 > pw2) ? pw1 : pw2; // Maximum width of the pictures if(w >= pwu && h >= phu) { b++; // If the width and height of the paper are enough, increase the counter } // 3. Checking the third arrangement: pictures next to each other (rotated) pwu = pw1 + pw2; // Total width of the pictures next to each other phu = (ph1 > ph2) ? ph1 : ph2; // Maximum height of the pictures if(h >= pwu && w >= phu) { b++; // If the height and width of the paper are enough for the rotated pictures, increase the counter } // 4. Checking the fourth arrangement: pictures one below the other (rotated) pwu = ph1 + ph2; // Total height of the pictures one below the other phu = (pw1 > pw2) ? pw1 : pw2; // Maximum width of the pictures if(h >= pwu && w >= phu) { b++; // If the height and width of the paper are enough for the rotated pictures, increase the counter } cout << b << endl; // Prints the number of valid arrangements of the pictures return 0; // Ends the program }
This program takes the dimensions of the paper and two pictures and checks whether the pictures can fit on the paper in different arrangements. The program checks four possibilities: pictures next to each other, pictures one below the other, pictures next to each other with rotation and pictures one below the other with rotation. For each arrangement it checks whether the width and height of the paper can hold the pictures, and counts how many arrangements are valid.
Detailed description:
- Reading the dimensions: The program takes the dimensions of the paper (width and height) as well as the dimensions of the two pictures (width and height of the first and second picture) using the
cincommand. - Checking the arrangements: The program checks four arrangements of the pictures:
- First arrangement (pictures next to each other): If the total width of the pictures (the sum of the widths of both pictures) does not exceed the width of the paper, and the height of the paper is enough for the largest height of the pictures, the counter of valid arrangements is increased.
- Second arrangement (pictures one below the other): If the total height of the pictures (the sum of the heights of both pictures) does not exceed the height of the paper, and the width of the paper is enough for the largest width of the pictures, the counter of valid arrangements is increased.
- Third arrangement (pictures next to each other, rotated): If the height of the paper can hold the total width of the pictures, and the width of the paper can hold the largest height of the pictures, the counter of valid arrangements is increased.
- Fourth arrangement (pictures one below the other, rotated): If the height of the paper can hold the total width of the pictures, and the width of the paper can hold the largest height of the pictures, the counter of valid arrangements is increased.
- Printing the result: Finally, the program prints the number of valid arrangements of the pictures on the paper.
At the end, the program returns 0, which means that the execution finished successfully.
Solution 2
#include <iostream> // Enables working with input and output #include <cmath> // Enables using mathematical functions such as abs using namespace std; // Uses the standard namespace int main() { int paper_width, paper_height, picture1_width, picture1_height, picture2_width, picture2_height; // The dimensions of the paper and the pictures are declared cin >> paper_width >> paper_height >> picture1_width >> picture1_height >> picture2_width >> picture2_height; // Reading the dimensions of the paper and the pictures int valid_arrangements = 0; // Counter of correct arrangements of the pictures if ((picture1_width + picture2_width <= paper_width && max(picture1_height, picture2_height) <= paper_height) // Checking the arrangement of the pictures next to each other || (picture1_height + picture2_height <= paper_height && max(picture1_width, picture2_width) <= paper_width)) { valid_arrangements++; // The arrangement next to each other is correct } if ((picture1_width + picture2_width <= paper_height && max(picture1_height, picture2_height) <= paper_width) // Checking the arrangement of the pictures one below the other || (picture1_height + picture2_height <= paper_width && max(picture1_width, picture2_width) <= paper_height)) { valid_arrangements++; // The arrangement one below the other is correct } cout << valid_arrangements << endl; // Prints the number of correct arrangements of the pictures return 0; // Ends the program }
This program checks whether two pictures can fit on the paper in different arrangements. The program checks two basic arrangements: pictures next to each other (horizontally) and pictures one below the other (vertically). It also checks the rotated versions of these arrangements. Finally, the program counts how many arrangements fit on the paper and prints that number.
Detailed description:
- Reading the dimensions:
The program takes the dimensions of the paper and the two pictures (width and height) using the
cincommand. - Checking the arrangements:
The program checks two arrangements of the pictures:
- Pictures next to each other:
The program checks whether the sum of the widths of both pictures is less than or equal to the width of the paper and whether the largest height of the pictures is less than or equal to the height of the paper. It also checks the opposite arrangement with the pictures rotated.
- Pictures one below the other:
The program checks whether the sum of the heights of the pictures is less than or equal to the height of the paper and whether the largest width of the pictures is less than or equal to the width of the paper, as well as the rotated version.
- Pictures next to each other:
- Arrangement with rotation:
If the pictures do not fit in their original form, the rotated versions of these arrangements are also checked. The program uses the function
maxto find which dimension of the pictures is larger, so that it can compare it correctly with the dimensions of the paper. - Counter of correct arrangements:
For every valid arrangement that fits on the paper, the counter
valid_arrangementsis increased. Finally, the program prints the total number of correct arrangements.
At the end, the program returns 0, which means that the execution finished successfully.
Comparison of the solutions
1. Correctness
Both solutions have the same goal: to check whether two pictures can fit on the paper in different arrangements. However, the two solutions do not cover all possible rotations and arrangements in the same way.
- The first solution: checks all possible arrangements with rotations for both arrangements (horizontal and vertical), which means that all basic cases are covered.
- The second solution: uses
max()to find the larger dimension and checks only the basic arrangements, without explicit rotation. Since the functionmax()makes sure that the larger dimension is taken, it also covers most cases, but without listing the rotations directly.
2. Efficiency
Both solutions run in constant time, because all necessary computations are done in a few basic conditions.
- The first solution: consists of four simple conditions, each with basic computations and comparisons.
- The second solution: is somewhat shorter and uses the function
max()for shorter and clearer code, but achieves the same result in the same time.
3. Simplicity and readability
- The first solution: has more detailed comments for every part of the code, but using more variables to compute the width and height can make the code a little less clear.
- The second solution: is simpler, because it uses direct functions and shorter code, which makes the code easier to understand and maintain.
4. Extensibility
- The first solution: would be easier to extend if we want to add more arrangements or rotations, because all arrangements are defined separately.
- The second solution: is already optimized for the basic cases, but if more arrangements or rotations were needed, it would require bigger changes.
5. Using standard libraries
- The first solution: uses only basic conditions and mathematical operations, without the need for additional libraries.
- The second solution: uses the library
cmathand the functionmax(), which is simple and efficient for finding the larger dimensions, but includes an additional library.
Conclusion:
- The first solution: is more detailed in terms of correctness, because it explicitly checks all rotations and arrangements. This means the code is more precise, but perhaps a little longer.
- The second solution: is simpler and shorter, uses
max()for shorter code and can be better for simpler cases, but it is less precise when rotations and additional arrangements are important.
Both solutions are efficient and correct for the basic cases, but the first solution is better for a more detailed check of arrangements and rotations.
