2014-07-21

UVa 10769 - Pillars

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

The world-famous architect Mr. Fruí from Reus plans to build a colossal pillar H units high. Mr. Fruí has n black pieces with heights b1,…, bn and m white pieces with heights w1,…, wm. According to his design the pillar must have four pieces: a black piece on its bottom, a white piece above it, another black piece above, and finally a white piece on the top of the pillar.

Mr. Fruí wishes to know which of the combinations of four pieces with total height H is the most stable. Given two combinations A = [a1, a2, a3, a4] and B = [b1, b2, b3, b4] (where a1 denotes the height of the bottom (black) piece of the pillar A, a2 denotes the height of the second (white) piece of A, and so on), A is more stable than B if a1 > b1, or if a1 = b1 but a2 > b2, etc. (In other words, A is more stable than B if and only if the sequence of heights of the pieces of A is lexicographically larger than the sequence of heights of the pieces of B.)

Write a program such that, given the desired height H of the pillar, the heights of the black pieces and the heights of the white pieces, computes which pillar (if any) of height exactly H would be the most stable.

Input

Input consists of zero ore more test cases. Each test case has on the first line H, an integer between 1 and 4*108. The second and third lines of each test consist respectively of the sequence b1,…, bn and of the sequence w1,…, wm. A blank line separates two consecutive test cases. You can assume 2$\le$n$\le$100 and 2$\le$m$\le$100, and that no piece has a height larger than 108.

Output

For every test case, print one line with the sequence of heights of the pieces of the most stable pillar. If no solution exists, print “no solution”.

Sample Input

100
20 20
30 10 30 50
 
100
20 10 4
50 30 45

Sample Output

1 2	20 50 20 10 no solution

Solution

題目描述：

這位世界著名的建築師，設計一個黑白相間的柱子，而這個柱子高度必須為 H，並且由四塊石塊來完成，分別是黑 (底部)、白、黑、白 (底部)。

每一種顏色的石塊都有自己的高度，請輸出恰好能組成高度 H 且字典順序最小的組合。

題目解法：

依序窮舉組合。

當初想要偷吃步加快操作，反而吃了一些字典順序的閉門羹。

#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <sstream>
#include <functional>
using namespace std;
vector<int> getLineNumber(char s[]) {
    stringstream sin(s);
    vector<int> ret;
    int x;
    while(sin >> x)
        ret.push_back(x);
    return ret;
}
int main() {
    char s[1024];
    int H;
    while(gets(s)) {
        sscanf(s, "%d", &H);
        vector<int> B, W;
        gets(s), B = getLineNumber(s);
        gets(s), W = getLineNumber(s);
        gets(s);
        sort(B.begin(), B.end(), greater<int>());
        sort(W.begin(), W.end(), greater<int>());
        
        int f = 0;
        for(int i = 0; i < B.size(); i++)
        for(int j = 0; j < W.size(); j++)
        for(int a = i+1; a < B.size(); a++)
        for(int b = j+1; b < W.size(); b++) {
            if(B[i]+W[j]+B[a]+W[b] == H) {
                printf("%d %d %d %d\n", B[i], W[j], B[a], W[b]);
                i = a = B.size();
                j = b = W.size();
                f = 1;
            }
        }
        if(!f)
            puts("no solution");
    }
    return 0;
}

Morris' Blog