2014-10-23

UVa 11731 - Ex-circles

Problem

給三個圓，它們彼此之間的內公切線會構成一個三角形，現在給定三角形的三邊長，請問灰色扇形面積為何。

Sample Input

1
2
3

3 4 5
10 11 12
0 0 0

Sample Output

1 2	Case 1: 30.00 21.62 Case 2: 211.37 144.73

Solution

模擬三角形三個點座標，三個圓座標分別坐落於兩兩外角的角平分線上，算出圓心之後就能找到扇形面積。

#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
const double pi = acos(-1); 
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator*(const double &a) const {
        return Pt(x * a, y * a);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
    a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
double getGrayArea(Pt A, Pt B, Pt C) {
    double r = fabs(cross2(B - A, C - A)) / dist(B, C);
    double radBAC = angle(B - A, C - A);
    return r * r * radBAC /2;
}
int main() {
    int cases = 0;
    double a, b, c;
    while(scanf("%lf %lf %lf", &a, &b, &c) == 3 && a+b+c) {
        Pt A, B, C, D, E, F;
        double radBAC = acos((b*b + c*c - a*a)/(2*b*c));
        double radABC = acos((a*a + c*c - b*b)/(2*a*c));
        double radACB = acos((a*a + b*b - c*c)/(2*a*b));
        A = Pt(0, 0);
        B = Pt(c, 0);
        C = A + rotateRadian(Pt(1, 0), radBAC) * b;
        double t1, t2, t3;
        t1 = (pi - radBAC)/2;
        t2 = (pi - radABC)/2;
        t3 = (pi - radACB)/2;
        Pt divA, divB, divC;
        divA = rotateRadian(C - A, t1); 
        divB = rotateRadian(B - A, t2);
        divC = rotateRadian(C - B, t3);
        D = getIntersection(A, divA, C, divC);
        E = getIntersection(B, divB, C, divC);
        F = getIntersection(A, divA, B, divB);
//		printf("%lf %lf, %lf %lf, %lf %lf\n", A.x, A.y, B.x, B.y, C.x, C.y);
//		printf("%lf %lf, %lf %lf, %lf %lf\n", D.x, D.y, E.x, E.y, F.x, F.y);
        double area = fabs(cross2(E - D, F - D))/2;
        double gray = getGrayArea(D, A, C) + getGrayArea(E, B, C) + getGrayArea(F, A, B);
        printf("Case %d: %.2lf %.2lf\n", ++cases, area, gray);
    }
    return 0;
}
/*
3 4 5
10 11 12
*/

Read More +

2014-10-23

解題區/解題區 - UVa

UVa 10794 - The Deadly Olympic Returns

Problem

給你兩個三維空間的射線，請問它們的最近距離為何。

Sample Input

2
1
0 0 0 1 0 0
0 -1 0 0 -2 0
4
0 0 0 1 0 0
-1 0 0 -2 0 0

Sample Output

1 2	Case 1: 1.0000 Case 2: 1.0000

Solution

三分時間，因為射線的速度不一致，目前還沒有想到好的數學解。

#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
struct Point3D {
    double x, y, z;
    Point3D(double a = 0, double b = 0, double c = 0):
        x(a), y(b), z(c) {}
    void read() {
        scanf("%lf %lf %lf", &x, &y, &z);
    }
    Point3D operator+(const Point3D &a) const {
        return Point3D(x + a.x, y + a.y, z + a.z);
    }
    Point3D operator-(const Point3D &a) const {
        return Point3D(x - a.x, y - a.y, z - a.z);
    }
    Point3D operator/(const double &a) const {
        return Point3D(x/a, y/a, z/a);
    }
    Point3D operator*(const double &a) const {
        return Point3D(x*a, y*a, z*a);
    }
    double dist(Point3D a) const {
        return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y) + (z - a.z) * (z - a.z));
    }
    double dist2(Point3D a) const {
        return (x - a.x) * (x - a.x) + (y - a.y) * (y - a.y) + (z - a.z) * (z - a.z);
    }
};
int main() {
    int testcase, cases = 0;
    double time;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf", &time);
        Point3D A, B, C, D, V1, V2;
        A.read(), B.read();
        C.read(), D.read();
        V1 = (B - A) / time;
        V2 = (D - C) / time;
        double l = 0, r = 1e+8;
        double mid, midmid, md, mmd;
        double mndist = A.dist2(C);
        while (fabs(l - r) > 1e-8) {
            mid = (l + r)/2;
            midmid = (mid + r)/2;
            md = ((V1 * mid) + A).dist2((V2 * mid) + C);
            mmd = ((V1 * midmid) + A).dist2((V2 * midmid) + C);
            mndist = min(mndist, md);
            mndist = min(mndist, mmd);
            if (md < mmd)
                r = midmid;
            else
                l = mid;
        }
        printf("Case %d: %.4lf\n", ++cases, sqrt(mndist));
    }
    return 0;
}

Read More +

2014-10-23

解題區/解題區 - UVa

UVa 1627 - Team them up

Problem

現在有 2 個 team，每個 team 至少一個成員，同一個 team 成員之間必然會互相認識，不同 team 的成員之間則不一定。

給定他們互相認識的關係圖，請問他們可以分屬的 team 的情況，並且輸出 team 人數差距最少的那一組。

Sample Input

Sample Output

No solution
3 1 3 5
2 2 4

Solution

對於不認識的兩個人，保證他們在不同的 team。

取補圖，建造相互不認識的兩個人的關係圖，對於每一個 component 做二分圖判定，找到每個二分圖的兩個集合大小。

對於每一個二分圖結果，使用背包問題的解法，將兩個 team 的總數劃分均勻。

#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 128
int g[MAXN][MAXN], visited[MAXN];
int color[MAXN], n;
int dfs(int u, int c, vector<int> &s0, vector<int> &s1) {
    visited[u] = 1, color[u] = c;
    if (c == 0)	s0.push_back(u);
    else		s1.push_back(u);
    for (int i = 1; i <= n; i++) {
        if ((!(g[u][i] == 1 && g[i][u] == 1)) && i != u) {
            if (visited[i] == 0) {
                if (!dfs(i, !color[u], s0, s1))
                    return 0;
            } else {
                if (color[u] == color[i])
                    return 0;
            }
        }
    }
    return 1;
}
int main() {
    int testcase, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        while (getchar() != '\n');
        memset(g, 0, sizeof(g));
        memset(visited, 0, sizeof(visited));
        memset(color, 0, sizeof(color));
        for (int i = 1; i <= n; i++) {
            while (scanf("%d", &x) == 1 && x)
                g[i][x] = 1;
        }
        int ok = 1, m = 0;
        vector<int> s0[MAXN], s1[MAXN];
        for (int i = 1; i <= n; i++) {
            if (visited[i] == 0) {
                m++;
                ok &= dfs(i, 0, s0[m], s1[m]);
            }
        }
        if (!ok) {
            puts("No solution");
        } else {
            int dp[MAXN][MAXN] = {}, from[MAXN][MAXN] = {};
            dp[0][0] = 1;
            for (int i = 1; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    if (dp[i - 1][j]) {
                        dp[i][j + s0[i].size()] = 1;
                        dp[i][j + s1[i].size()] = 1;
                        from[i][j + s0[i].size()] = 0;
                        from[i][j + s1[i].size()] = 1;
                    }
                }
            }
            int ch = -1;
            for (int i = n/2; i >= 1; i--) {
                if (dp[m][i])	ch = i, i = -1;
            }
            assert(ch > 0);
            vector<int> team1, team2;
            for (int i = m; i >= 1; i--) {
                if (from[i][ch] == 0) {
                    ch -= s0[i].size();
                    team1.insert(team1.end(), s0[i].begin(), s0[i].end());
                    team2.insert(team2.end(), s1[i].begin(), s1[i].end());
                } else {
                    ch -= s1[i].size();
                    team1.insert(team1.end(), s1[i].begin(), s1[i].end());
                    team2.insert(team2.end(), s0[i].begin(), s0[i].end());
                }
            }
            printf("%d", team1.size());
            for (int i = 0; i < team1.size(); i++)
                printf(" %d", team1[i]);
            puts("");
            printf("%d", team2.size());
            for (int i = 0; i < team2.size(); i++)
                printf(" %d", team2[i]);
            puts("");
        }
        if (testcase)	puts("");
    }
    return 0;
}
/*
2
5
3 4 5 0
1 3 5 0
2 1 4 5 0
2 3 5 0
1 2 3 4 0
5
2 3 5 0
1 4 5 3 0
1 2 5 0
1 2 3 0
4 3 2 1 0
*/

Read More +

2014-10-23

解題區/解題區 - UVa

UVa 1390 - Interconnect

Problem

N 個城鎮之間一開始有一些邊相連，接著每次任挑兩個城鎮拉一條邊相連，請問期望值需要幾次才能將 N 個城鎮彼此相連成為一個連通元件。

原本彼此連通的城鎮，也有可能重複拉邊。

Sample Input

Sample Output

1
2

0.0 
1.5

Solution

事實上，將狀態壓縮成每一個連通元件的節點個數，對於連通元件之間做拉邊即可。

對於狀態 u, v，期望值 E[u] = 1 + E[v] * p + E[u] * q，

E[v] * p 表示：將兩個不同連通元件之間拉邊，則會將兩個連通元件融合，機率 p。
E[u] * q 表示：在各自的連通元件內布拉邊，不影響狀態結果。

左移一下得到 E[u] = (1 + E[v] * p) / (1 - q);

#include <stdio.h> 
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int parent[32], weight[32];
int findp(int x) {
    return parent[x] == x ? x : findp(parent[x]);
}
void joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	return;
    if (weight[x] > weight[y])
        parent[y] = x, weight[x] += weight[y];
    else
        parent[x] = y, weight[y] += weight[x];
}
#define hash_mod 1000003
struct state {
    vector<int> c;
    unsigned int hash() {
        unsigned int a = 63689, b = 378551;
        unsigned int value = 0;
        for (int i = 0; i < c.size(); i++) {
            value = value * a + c[i];
            a *= b;
        }
        return value % hash_mod;
    }
    bool operator<(const state &a) const {
        if (c.size() != a.c.size())
            return c.size() < a.c.size();
        for (int i = 0; i < c.size(); i++)
            if (c[i] != a.c[i])
                return c[i] < a.c[i];
        return false;
    }
};
map<state, double> hash[hash_mod];
double dfs(state &u) {
    sort(u.c.begin(), u.c.end());
    if (u.c.size() == 1)	return 0;
    
    int h = u.hash();
    if (hash[h].find(u) != hash[h].end())
        return hash[h][u];
    double &ret = hash[h][u];
    double self = 0, total = 0;
    ret = 0;
    for (int i = 0; i < u.c.size(); i++) {
        self += u.c[i] * (u.c[i] - 1) / 2.0;
        total += u.c[i];
    }
    total = total * (total - 1) / 2.0;
    for (int i = 0; i < u.c.size(); i++) {
        for (int j = i+1; j < u.c.size(); j++) {
            state v = u;
            v.c[i] += v.c[j];
            v.c.erase(v.c.begin() + j);
            ret += u.c[i] * u.c[j] * dfs(v);
        }
    }
    // E[u] = 1 + E[v] * p + E[u] * q
    ret = (ret / total) + 1;
    ret = ret / (1 - self / total);
    return ret;
}
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 1; i <= n; i++)
            parent[i] = i, weight[i] = 1;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            joint(x, y);
        }
        
        state st;
        for (int i = 1; i <= n; i++) {
            if (parent[i] == i) // root
                st.c.push_back(weight[i]);
        }
        printf("%lf\n", dfs(st));
    }
    return 0;
}

Read More +

2014-10-23

解題區/解題區 - UVa

UVa 1383 - Harmony Forever

Problem

加入一個數字 X 於陣列尾端
找到序列中 mod Y 的最小值的數字 X 位置，如果有相同的，取最後加入的數字位置。

Sample Input

Sample Output

Case 1: 
1 
2 
1 
Case 2: 
1

Solution

怎麼想都沒有好的思路，最後還是用多次區間查找來完成這個最小值詢問。

每一次查詢區間 [0, Y - 1]、[Y, 2Y - 1]、[2Y, 3Y - 1] … 的最小值。

因此每一次會需要詢問 O(500000 / Y * log (500000))，當 Y 夠大的時候，效率會比直接搜索來得快，如果 Y 太小則直接搜索的效果會比較好，因為增加的數字 X 最多 40000 個。

閥值 5000。

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 524288
struct E {
    int value, index;
    E(int a = 0, int b = 0):
        value(a), index(b) {}
    bool operator<(const E &a) const {
        return value < a.value;
    }
};
E tree[(MAXN<<1) + 10];
int M;
void setTree(int s, int t) {
    int i;
    for(i = 2 * M - 1; i >= 0; i--) {
    	tree[i] = E(0x3f3f3f3f, 0);
    }
}
E query(int s, int t) {
    E ret(0x3f3f3f3f, 0);
    for(s = s + M - 1, t = t + M + 1; (s^t) != 1;) {
        if(~s&1)
            ret = min(ret, tree[s^1]);
        if(t&1)
            ret = min(ret, tree[t^1]);
        s >>= 1, t >>= 1;
    }
    return ret;
}
void update(int s, E v) {
    tree[s + M] = v;
    for (s = s + M; s > 0; s >>= 1)
        tree[s] = min(tree[s], v);
}
int main() {
    int n, x, cases = 0;
    char cmd[5];
    while (scanf("%d", &n) == 1 && n) {
        for (M = 1; M < 500000+2; M <<= 1);
        setTree(0, M);
        int B = 0;
        vector<int> BX;
        if (cases++)
            puts("");
        printf("Case %d:\n", cases);
        for (int i = 0; i < n; i++) {
            scanf("%s %d", cmd, &x);
            if (cmd[0] == 'B') {
                update(x + 1, E(x + 1, ++B));
                BX.push_back(x);
            } else {
                if (BX.size() == 0)
                    puts("-1");
                else if (x < 5000) {
                    int mn1 = 0x3f3f3f3f, mn2 = -1, u;
                    for (int i = BX.size() - 1; i >= 0; i--) {
                        u = BX[i]%x;
                        if (u == 0) {
                            mn1 = 0, mn2 = i + 1;
                            break;
                        }
                        if (u < mn1)
                            mn1 = u, mn2 = i + 1;
                    }
                    printf("%d\n", mn2);
                } else {
                    int mn1 = 0x3f3f3f3f, mn2 = -1;
                    for (int y = 0; y <= 500000; y += x) {
                        E t = query(y + 1, min(y + 1 + x - 1, 500000));
                        if (t.value - y < mn1 || (t.value - y == mn1 && t.index > mn2))
                            mn1 = t.value - y, mn2 = t.index;
                    }
                    printf("%d\n", mn2);
                }
            }
        }
    }
    return 0;
}

Read More +

2014-10-23

解題區/解題區 - UVa

UVa 1182 - Sequence Alignment

Problem

基因對齊的最大匹配問題，或者是說 minimum edit distance，最小編輯距離。

花費方案

連續個 - 獲益 -1，也就是 ----- = -1、a--b--c = -2
對齊 a - a 獲益 2。
不對 a - b 獲益 0。 (這一個對法，題目沒有講，因此很容易掛 WA。)

Sample Input

2
AADDEFGGHC 
ADCDEGH 
ERTTHCBYNQC 
BEARTBCHQYN

Sample Output

1
2

9 
8

Solution

狀態 dp[i][j][a_str or b_str][prev gap/ no prev gap]

先將 a, b 反轉，靠右對齊不是重點！

考慮 a 字串 i 位置匹配到 b 字串 j 位置，然後考慮尾端的狀態，要不兩個都是字符，要不其中一個是 - 產生的 gap，而這個 gap 可能在 a 字串或者是 b 字串，如果已經存在 gap，放置時則不需要花費，反之額外增加花費。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
void inv(char s[], int n) {
    for (int i = 0, j = n-1; i < j; i++, j--)
        swap(s[i], s[j]);
}
int dp[64][64][2][2];
int main() {
    int testcase;
    char s1[64], s2[64];
    scanf("%d", &testcase);
    while (getchar() != '\n');
    while (testcase--) {
        gets(s1);
        gets(s2);
        int n1 = strlen(s1), n2 = strlen(s2);
        inv(s1, n1), inv(s2, n2);
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                dp[i][j][0][0] = dp[i][j][0][1] = -0x3f3f3f3f;
                dp[i][j][1][0] = dp[i][j][1][1] = -0x3f3f3f3f;
            }
        }
        dp[0][0][0][1] = 0;
        dp[0][0][1][1] = 0;
        int ret = -0x3f3f3f3f;
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                int v = max(dp[i][j][0][0], dp[i][j][0][1]);
                v = max(v, max(dp[i][j][1][0], dp[i][j][1][1]));
                dp[i+1][j+1][0][1] = max(dp[i+1][j+1][0][1], v);
                dp[i+1][j+1][1][1] = max(dp[i+1][j+1][1][1], v);
                if (s1[i] == s2[j]) {
                    dp[i+1][j+1][0][1] = max(dp[i+1][j+1][0][1], v + 2);
                    dp[i+1][j+1][1][1] = max(dp[i+1][j+1][1][1], v + 2);
                }
                dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][0][0]);
                dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][1][0] - 1);
                dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][0][1] - 1);
                dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][1][1] - 1);
                
                dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][1][0]);
                dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][0][0] - 1);
                dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][0][1] - 1);
                dp[i][j+1][1][0] = max(dp[i][j+1][1][0], dp[i][j][1][1] - 1);
                if (j == n2 || i == n1) {
                    ret = max(ret, max(dp[i][j][0][0], dp[i][j][0][1]));
                    ret = max(ret, max(dp[i][j][1][0], dp[i][j][1][1]));
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
2
AADDEFGGHC
ADCDEGH
ERTTHCBYNQC
BEARTBCHQYN
3
ABC
ABC
ABC
AC
BAC
AC
*/

Read More +

2014-10-23

解題區/解題區 - UVa

UVa 1108 - Mining Your Own Business

Problem

给定一个连通图，设置一个些安全点，使得其他任意一些节点崩塌后，其他点都能到一个安全点，问安全点最小数量和情况数

Sample Input

Sample Output

1 2	Case 1: 2 4 Case 2: 4 1

Solution

先找到所有割點，而一個連通元件上可能連接好幾個割點，對於這個連通元件而言，不論割點是否崩塌，它們仍然可以通到其他連通元件上的逃生口。

如果這個連通元件只有一個割點，則萬一割點崩塌，則連通元件中至少要有一個逃生口，而方法數就是 component.size()，因此會發現，只需要將只有一個割點的連通元件的方法數相乘即可。

對於沒有割點的連通元件而言，至少要設置兩個逃生口，只有一個逃生口會造成萬一逃生口崩塌而死掉的情況，特別考慮方法數 component.size() * (component.size() - 1) / 2。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define MAXN 65536
vector<int> g[MAXN];
int visited[MAXN], vIdx, back[MAXN], depth[MAXN];
int cutPoint[MAXN];
void tarjan(int u, int p, int root) {
    back[u] = depth[u] = ++vIdx;
    visited[u] = 1;
    int son = 0;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!visited[v]) {
            tarjan(v, u, root);
            back[u] = min(back[u], back[v]);
            son++;
            if ((u == root && son > 1) || (u != root && back[v] >= depth[u]))
                cutPoint[u]++;
        } else if (v != p) {
            back[u] = min(back[u], depth[v]);
        }
    }
}
//
set<int> adjCutPt;
int comSize = 0;
void dfs(int u) {
    visited[u] = 1, comSize++;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (cutPoint[v])	adjCutPt.insert(v);
        if (cutPoint[v] || visited[v])
            continue;
        dfs(v);
    }
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int n, m, x, y;
    int cases = 0;
    while(scanf("%d", &m) == 1 && m) {
        int used[MAXN] = {}, usedn = 0;
        for (int i = 0; i < MAXN; i++)
            g[i].clear();
        n = 0;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            n = max(n, max(x, y));
            x--, y--;
            used[x] = used[y] = 1;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for (int i = 0; i < n; i++)
            usedn += used[i];
        // find all cut point
        vIdx = 0;
        for (int i = 0; i < n; i++)
            visited[i] = cutPoint[i] = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && used[i])
                tarjan(i, -1, i);
        }
//		for (int i = 0; i < n; i++)
//			printf("%d ", cutPoint[i]);
//		puts("");
        // find each component adjacent one cut point, without any cut point.
        vector<int> D; 
        for (int i = 0; i < n; i++)
            visited[i] = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && !cutPoint[i]) {
                comSize = 0, adjCutPt.clear();
                dfs(i);
                if (adjCutPt.size() == 1)
                    D.push_back(comSize);
            }
        }
        long long ways = 1, mn = D.size();
        for (int i = 0; i < D.size(); i++)
            ways *= D[i];
        if (D.size() == 0)	ways = (long long) usedn * (usedn-1) / 2, mn = 2;
        printf("Case %d: %lld %lld\n", ++cases, mn, ways);
    }
    return 0;
}
/*
3
1 2
2 3
3 1
32
15 15
8 4
17 7
6 1
12 6
3 17
5 9
20 8
20 4
7 15
4 18
7 17
14 1
14 3
5 3
5 18
13 18
5 15
1 13
18 3
2 4
20 4
20 16
5 20
2 3
10 4
6 6
13 16
2 7
6 17
14 14
1 15
33
10 12
17 14
19 3
2 3
19 9
17 16
9 2
8 9
6 8
14 10
3 13
14 4
9 3
1 18
10 7
15 14
13 1
15 1
16 6
14 20
12 7
6 17
19 5
19 1
10 13
5 3
18 6
12 17
4 5
9 18
9 17
9 20
15 15
*/

Read More +

2014-10-23

解題區/解題區 - UVa

UVa 1011 - Crossing the Desert

Problem

在一個沙漠中，有 N 個綠洲，每一個綠洲只有水源可以獲取使用，食物可以從起點城鎮帶過來存放，但是綠洲本身不帶有食物獲取，每走一步將會損耗單位水和食物，身上負重最多 W，你可以攜帶一部分食物放置在綠洲，然後走回起點再帶食物過來存放，要推進到終點，至少要從城鎮中購買多少食物。

Sample Input

Sample Output

1
2
3

Trial 1: 136 units of food
Trial 2: Impossible

Solution

很簡單想的，我們只能從終點逆推回來，我們考慮綠洲 u 到終點 end 的最少食物花費 cost_u，現在考慮從 v 點到 u 再到 end，如果 cost_u 加上 e(v, u) 的花費不超過負重，則可以得知直接從 v 攜帶 cost_u 的食物量。

如果 cost_u 太大，則表示必須來來往往於 u, v 之間，而每一趟 v->u->v，攜帶路徑花費 1 倍水、 2 倍食物 (在 u 那邊打水即可)，剩下的空間為一次運送的食物量 (放置在 u 儲存)。最後一趟，則不考慮回程，額外可以增加攜帶食物量。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
#define eps 1e-8
int main() {
    int n, m;
    int cases = 0;
    while (scanf("%d %d", &n, &m) == 2 && n+m) {
        double x[50], y[50];
        double g[50][50];
        double dp[50];
        int used[50] = {};
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x[i], &y[i]);
            dp[i] = 1e+6;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                double d = hypot(x[i] - x[j], y[i] - y[j]);
                g[i][j] = d;
            }
        }
        dp[n-1] = 0;
        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (used[j] == 0 && (u == -1 || dp[u] > dp[j]))
                    u = j;
            }
            used[u] = 1;
            for (int j = 0; j < n; j++) {
                if (used[j])	continue;
                double w = g[u][j];
                if (m >= dp[u] + 2 * w)
                    dp[j] = min(dp[j], dp[u] + w);
                else if (m >= 3 * w) {
                    int times = ceil((dp[u] - (m - 2 * w))/ (m - 3 * w));
                    dp[j] = min(dp[j], dp[u] + times * (2 * w) + w);
                }
            }
        }
        printf("Trial %d: ", ++cases);
        if (dp[0] != 1e+6)
            printf("%.0lf units of food\n", ceil(dp[0]));
        else
            puts("Impossible");
        puts("");
    }
    return 0;
}
/*
4 100
10 -20
-10 5
30 15
15 35
2 100
0 0
100 100
0 0
*/

Read More +

2014-10-23

解題區/解題區 - UVa

UVa 938 - Gilix

Problem

給一個環狀的蜂巢式地圖，上下沒有包裹，只有左右是相連的。現在在某一個蜂巢中放置特殊藥水，走到那個放置處喝下，之後所需要的花費都會砍半。求某點到某點的最少花費。

Sample Input

4 8
4 2 2 2 4 4 6 10
2 6 8 4 4 4 4 2
8 2 6 8 4 4 4 6
6 4 4 6 8 4 4 4
0 0
3 4
1 1

Sample Output

Solution

類似最短路徑，不過狀態為 dist[N][2] 是否已經經過放置藥水的地點，隨著 spfa 更新即可。關於蜂巢地圖，直接根據奇偶數 row 分開討論即可。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int g[512][512];
int dist[512][512][2], inq[512][512][2];
const int dx1[] = {-1, -1, 0, 1, 1, 0};
const int dy1[] = {0, 1, 1, 1, 0, -1};
const int dx2[] = {-1, -1, 0, 1, 1, 0};
const int dy2[] = {-1, 0, 1, 0, -1, -1};
void spfa(int L, int C, int sx, int sy, int ex, int ey, int px, int py) {
    memset(dist, 63, sizeof(dist));
    queue<int> X, Y, S;
    int tx, ty, ts, ss;
    dist[sx][sy][0] = 0;
    X.push(sx), Y.push(sy), S.push(0);
    while (!X.empty()) {
        sx = X.front(), X.pop();
        sy = Y.front(), Y.pop();
        ss = S.front(), S.pop();
        inq[sx][sy][ss] = 0;
        for (int i = 0; i < 6; i++) {
            if (sx&1)
                tx = sx + dx1[i], ty = sy + dy1[i];
            else
                tx = sx + dx2[i], ty = sy + dy2[i];
            if (tx < 0 || tx >= L)	continue;
            ty = (ty + C)%C;
            ts = ss;
            int cost = ts ? g[tx][ty]/2 : g[tx][ty];
            if (tx == px && ty == py)
                ts = ss | 1;
            if (dist[tx][ty][ts] > dist[sx][sy][ss] + cost) {
                dist[tx][ty][ts] = dist[sx][sy][ss] + cost;
                if (!inq[tx][ty][ts]) {
                    inq[tx][ty][ts] = 1;
                    X.push(tx), Y.push(ty), S.push(ts);
                }
            }
        }
    }
    printf("%d\n", min(dist[ex][ey][0], dist[ex][ey][1]));
}
int main() {
    int L, C;
    int sx, sy, ex, ey, px, py;
    while (scanf("%d %d", &L, &C) == 2) {
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < C; j++)
                scanf("%d", &g[i][j]);
        }
        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        scanf("%d %d", &px, &py);
        spfa(L, C, sx, sy, ex, ey, px, py);
    }
    return 0;
}
/*
4 8
4 2 2 2 4 4 6 10
2 6 8 4 4 4 4 2
8 2 6 8 4 4 4 6
6 4 4 6 8 4 4 4
0 0
3 4
1 1
*/

Read More +

2014-10-23

解題區/解題區 - UVa

UVa 233 - Package Pricing

Problem

總共有 a, b, c, d 四種類型的燈泡，現在給予一些組合包的價格和各自內有四種類型的燈泡數量，現在要求購買指定個數以上的方案，求最少花費。

Sample Input

5
10 25.00 b 2
502 17.95 a 1
3 13.00 c 1
55 27.50 b 1 d 2 c 1
6 52.87 a 2 b 1 d 1 c 3
6
d 1
b 3
b 3 c 2
b 1 a 1 c 1 d 1 a 1
b 1 b 2 c 3 c 1 a 1 d 1
b 3 c 2 d 1 c 1 d 2 a 1

Sample Output

1:   27.50 55
2:   50.00 10(2)
3:   65.50 3 10 55
4:   52.87 6
5:   90.87 3 6 10
6:  100.45 55(3) 502

Solution

這一題不外乎就是整數線性規劃，很明顯地是一個 NPC 問題，所以就兩種策略強力剪枝、背包問題。

關於強力剪枝，大概是當年解決問題的方法，因為題目沒有特別說明數據範圍，用背包問題是相當不方便的，我也搜索不到當年 WF 的 code，所以測試一下數據範圍，發現將四種類型燈泡需求相乘結果不大於 100 萬。

藉由這個條件，將狀態訂為 dp[a_size][b_size][c_size][d_size] 的最小花費為何，但是可能忽大忽小，所以自己定義 row major 來完成。嘗試將每一種組合去迭代找最小值，中間過程要記得取 min bound，以免越界。

#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <assert.h>
#include <map>
#include <queue>
using namespace std;
struct COMB {
    int label, supply[4];
    double price;
    void init() {
        memset(supply, 0, sizeof(supply));
    }
    void print() {
        printf("%d %lf %d %d %d %d\n", label, price, supply[0], supply[1], supply[2], supply[3]);
    }
    bool operator<(const COMB &p) const {
        return label < p.label;
    }
} products[64];
int n, q, need[16];
int mnCnt[64], path[64];
double mnCost;
double dp[1048576];
int dpChoose[1048576][2];
int row[4];
int getIndex(int A[]) {
    int v = 0;
    for (int j = 0; j < 4; j++)
        v += A[j] * row[j];
    return v;
}
void bfs() {
    row[0] = (need[3]+1)*(need[2]+1)*(need[1]+1);
    row[1] = (need[3]+1)*(need[2]+1);
    row[2] = need[3]+1;
    row[3] = 1;
    int A[4], B[4], u, v, mxState = getIndex(need);
    for (int i = 0; i <= mxState; i++)
        dp[i] = 1e+50, dpChoose[i][0] = dpChoose[i][1] = -1;
    dpChoose[0][1] = -1, dp[0] = 0;
    for (int p = 0; p <= mxState; p++) {
        u = p;
        for (int i = 0; i < 4; i++)
            A[i] = u / row[i], u %= row[i];
        u = p;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 4; j++)
                B[j] = min(A[j] + products[i].supply[j], need[j]);
            v = getIndex(B);
            if (dp[v] > dp[u] + products[i].price)
                dp[v] = dp[u] + products[i].price, dpChoose[v][0] = i, dpChoose[v][1] = u;
        }
    }
    memset(mnCnt, 0, sizeof(mnCnt));
    for (int p = mxState; p != -1; p = dpChoose[p][1])
        mnCnt[dpChoose[p][0]]++;		
    mnCost = dp[mxState];
}
int main() {
    char line[1024];
    string token;
    int cnt = 0;
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n');
        
        for (int i = 0; i < n; i++) {
            products[i].init();
            gets(line);
            stringstream sin(line);
            sin >> products[i].label >> products[i].price;
            while (sin >> token >> cnt)
                products[i].supply[token[0] - 'a'] += cnt;
        }
        sort(products, products + n);
        gets(line);
        sscanf(line, "%d", &q);
        for (int i = 0; i < q; i++) {
            memset(need, 0, sizeof(need));
            gets(line);
            stringstream sin(line);
            while (sin >> token >> cnt)
                need[token[0] - 'a'] += cnt;
            bfs();
            printf("%d:%8.2lf", i + 1, mnCost);
            for (int j = 0; j < n; j++) {
                if (mnCnt[j]) {
                    printf(" %d", products[j].label);
                    if (mnCnt[j] > 1)
                        printf("(%d)", mnCnt[j]);
                }
            }
            puts("");
        }
        puts("");
    }
    return 0;
}

Read More +