Description

You are given a rectangular board with width w and height h. The board may be cut repeatedly along horizontal or vertical directions. Each resulting rectangle can also be further cut in the same way.

However, rectangles can only be sold if they match one of exactly three allowed sizes, specified as:

• w1 × h1

• w2 × h2

• w3 × h3

Because the board has grain texture, rectangles cannot be rotated. (有方向性)
The selling price of a rectangle is:

• price = width × height

Your task is to compute the maximum total selling price obtainable by cutting the original w×h board into zero or more allowed rectangles. Cutting may produce leftover rectangles that cannot be sold; such pieces contribute zero profit.

 

Sample Input / Output

A 5×7 board can be cut into two 5×2 pieces and two 2×3 pieces.
The total value obtained is:

• 5×2 + 5×2 + 2×3 + 2×3 = 32

Hint

Instead of directly computing the maximum sellable area, we can compute the minimum wasted area during cutting. Here is some pseudocode that you can refer to.

constant N_PIECE = 3      # we have 3 sellable sizes

# sellable sizes are stored as:
# size[i].w = width of piece i
# size[i].h = height of piece i

function min_piece(w, h, size[0..N_PIECE-1]) -> int

    # 1. invalid size: no waste
    if w <= 0 OR h <= 0 then
        return 0
    end if

    # 2. if this rectangle exactly matches a sellable size,
    #    we can sell it completely → no waste
    for i from 0 to N_PIECE-1 do
        if w == size[i].w AND h == size[i].h then
            return 0
        end if
    end for

    # 3. check whether we can at least cut out one sellable piece inside
    canCut := false
    for i from 0 to N_PIECE-1 do
        if w >= size[i].w AND h >= size[i].h then
            canCut := true
        end if
    end for

    # if we cannot cut out any of the 3 sellable sizes,
    # then the whole w×h area is wasted
    if canCut == false then
        return w * h
    end if

    # 4. try cutting using each sellable size as a "reference" piece
    minWaste := w * h     # initialize with worst case

    for i from 0 to N_PIECE-1 do

        wi := size[i].w
        hi := size[i].h

        # only consider this size if it fits inside w×h
        if w >= wi AND h >= hi then

            # --- Cut style 1: cut horizontally first ---
            #   top:    w × (h - hi)
            #   bottom: (w - wi) × hi
            waste1 := min_piece(w,      h - hi, size)
                      + min_piece(w - wi, hi,    size)

            if waste1 < minWaste then
                minWaste := waste1
            end if

            # --- Cut style 2: cut vertically first ---
            #   left:   (w - wi) × h
            #   right:  wi × (h - hi)
            waste2 := min_piece(w - wi, h,      size)
                      + min_piece(wi,    h - hi, size)

            if waste2 < minWaste then
                minWaste := waste2
            end if

        end if
    end for

    return minWaste
end function

Input

First line: two integers w, h — width and height of the original board.

Next three lines: each line contains two integers describing one allowed rectangle size:

• w1, h1
• w2, h2
• w3, h3

Constraints:

• 0 < w, h ≤ 32

• 0 < w1, w2, w3 ≤ w

• 0 < h1, h2, h3 ≤ h

Output

A single integer: the maximum total profit achievable by cutting and selling rectangles according to the rules.

The output must exactly match the required format.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given 13 Mahjong tiles, each represented by an integer between 1 and 9.
Each integer represents the number printed on the tile.

In Mahjong, a winning hand requires one pair (雀頭, e.g., 3 3) and four sets.
Each set consists of exactly three tiles, and can be either of the following:

1. Triplet (刻子) — three tiles with the same number, e.g., 4 4 4.

2. Sequence (順子) — three tiles with consecutive numbers, e.g., 4 5 6.

A complete Mahjong winning hand therefore contains
1 pair (2 tiles) + 4 sets (4×3 = 12 tiles) = 14 tiles.

Since we are given only 13 tiles, we are looking for which tile(s) could complete the hand —
in other words, we want to determine which tiles are winning tiles (聽牌).

 

Sample Explanation

Given the following 13 tiles: 1 1 1 2 2 2 3 3 3 4 4 4 4

We want to check which tile, if added, can form a valid 14-tile winning hand.

If we add 1, grouping: 11, 123, 123, 234, 444 → 1 is a winning tile

If we add 2, grouping: 111, 222, 33, 234, 444 → 2 is a winning tile

If we add 3, grouping: 111, 22, 333, 234, 444 → 3 is a winning tile

If we add 5, grouping: 111, 222, 33, 444, 345 → 5 is a winning tile

Why 4 is NOT a winning tile?

Although adding 4 would theoretically allow groupings like:
111, 222, 333, 44, 444
this would require five 4’s, which is impossible — each tile appears at most 4 times.
Therefore 4 cannot be considered a winning tile.

Hint

Try each tile 1~9 as the possible winning tile.
For each tile:
    - Check that adding it does not exceed 4 copies.
    - Pick every possible number as the pair.
    - After removing the pair, check if the rest can form four sets
      (each set is either AAA or ABC).
Output all tiles that make the hand winnable.

 

Input

Thirteen integers between 1 and 9 (order does not matter).
Each integer appears at most 4 times.

Output

All winning tiles (1 to 9), one per line, sorted in increasing order.
If no tile can complete a winning hand, output 0.

Ensure that the output formatting exactly matches the samples.

Sample Input  Download

Sample Output  Download

Tags

Discuss