2014-07-06

UVa 11215 - How Many Numbers

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

Problem

You might have heard the game of 24: given 4 integers, you’re to make an expression to get the number 24. For example, given 4, 4, 10, 10, you can write (1010-4)/4=24, given 1, 5, 5, 5, you can write (5-1/5)5=24.

In this problem, your task is a little bit harder: count the number of numbers that can be made. Don’t forget to count negative numbers and non-integers. You can use binary additions, subtractions, multiplications and divisions with parenthesis (unary operations are not allowed). Numbers cannot be concatenated to form a larger number (e.g. you cannot concatenate 1 and 2 to get 12).

For example, given two 1’s, exactly 3 numbers can be made: 1+1=2, 1-1=0, 1*1=1. You cannot get 11 or -1.

Input

The input consists of at most 30 test cases. Each case begins with a line containing a single integer n (1 < n < 7), the number of integers given. The next line contains n non-negative integers not greater than 10. The last case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and the number of numbers that can be made.

Sample Input

Output for the Sample Input

1
2
3

Case 1: 3
Case 2: 47
Case 3: 255

Solution

題目描述：

對於給定的數字，考慮所有加減乘除括號的所有計算方案，計算出有多少不同種的運算結果。

題目解法：

類似矩陣鏈乘積，考量每一種排列方式。

對於其中一種排列方式，紀錄狀態 [l, r] 之間所有可能的運算結果，當要合併兩個區間時，枚舉兩個區間的所有可能，並且將其兩兩合併。

[l, r] = [l, k](+-*/)[k+1, r]

使用 double 以為小數點誤差影響不太，但怎麼做都 WA，最後直接用分數的方式進行計算，最後拿了很慢的 AC。

#include <stdio.h> 
#include <algorithm>
#include <set>
#include <math.h>
using namespace std;
#define eps 1e-3
struct Fraction {
    long long a, b;
    Fraction(long long x=0, long long y=1) {
        long long g = __gcd(x, y);
        a = x / g;
        b = y / g;
        if(b < 0)	a = -a, b = -b;
    }
    Fraction operator+(const Fraction &x) const {
        return Fraction(a * x.b + x.a * b, b * x.b);
    }
    Fraction operator-(const Fraction &x) const {
        return Fraction(a * x.b - x.a * b, b * x.b);
    }
    Fraction operator*(const Fraction &x) const {
        return Fraction(a * x.a, b * x.b);
    }
    Fraction operator/(const Fraction &x) const {
        return Fraction(a * x.b, b * x.a);
    }
    bool operator<(const Fraction &x) const {
        return a * x.b < b * x.a;
    }
};
int main() {
    int n, cases = 0, A[10];
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        set<Fraction> ret;
        sort(A, A+n);
        do {
            set<Fraction> dp[10][10];
            for(int i = 0; i < n; i++)
                dp[i][i].insert(Fraction(A[i]));
            for(int i = 1; i < n; i++) {
                for(int j = 0; i + j < n; j++) {
                    for(int k = j; k < j+i; k++) {
                        for(set<Fraction>::iterator it = dp[j][k].begin();
                            it != dp[j][k].end(); it++)
                        for(set<Fraction>::iterator jt = dp[k+1][j+i].begin();
                            jt != dp[k+1][j+i].end(); jt++) {
                            Fraction a = *it, b = *jt;
                            dp[j][j+i].insert(a+b);
                            dp[j][j+i].insert(a-b);
                            dp[j][j+i].insert(a*b);
                            if(b.a)
                                dp[j][j+i].insert(a/b);
                        }
                    }
                }
            }
            for(set<Fraction>::iterator it = dp[0][n-1].begin();
                it != dp[0][n-1].end(); it++)
                ret.insert(*it);
        } while(next_permutation(A, A+n));
        printf("Case %d: %d\n", ++cases, ret.size());
    }
    return 0;
}

Morris' Blog