2014-10-23

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 +

2014-10-21

解題區/出題解題

[ACM 題目] 等高線

Problem

給一個等高線二維地圖，每一個等高線由一個平行兩軸的矩形構成，有 N 個矩形、 M 個地點，輸出每一個地點的所在位置高度，以及當前的所在矩形編號。

保證矩形之間的邊不相交。

exmple 1

Input

有多組測資，

每一組第一行會有一個整數 N，表示接下來有多少個等高線。
接下來會有 N 行，每行上會有四個整數 (lx, ly, rx, ry)。

接著一行一個整數 M，表示接下來有 M 個點詢問，接下來會有 M 行 (x, y)。

N < 32767, 0 < lx < rx < 1,000,000, 0 < ly < ry < 1,000,000

-10,000,000 < x, y < 10,000,000

Output

每組第一行，按照輸入順序輸出每條等高線高度，接著輸出 M 行詢問所在的等高線編號。

Sample Input

Sample Output

1 2 2 3 3 3 2
3
2
2
1
3
-1

Solution

#include <stdio.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct Rectangle {
    int lx, ly, rx, ry;
    void read() {
        scanf("%d %d %d %d", &lx, &ly, &rx, &ry);
    }
    int contain(Rectangle &a) {
        return lx <= a.lx && ly <= a.ly && rx >= a.rx && ry >= a.ry;
    }
    int contain(int x, int y) {
        return lx <= x && ly <= y && rx >= x && ry >= y;
    }
} rect[32767];
struct QPt {
    int x, y, label;
    QPt(int a = 0, int b = 0, int c = 0):
        x(a), y(b), label(c) {}
    bool operator<(const QPt &a) const {
        return make_pair(x, y) < make_pair(a.x, a.y);
    }
};
vector<int> g[32767];
int parent[32767], visited[32767], depth[32767];
void dfs(int u) {
    visited[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (visited[v] == 0) {
            if (rect[u].contain(rect[v]))
                parent[v] = u, depth[v] = depth[u] + 1;
            else
                parent[v] = parent[u], depth[v] = depth[parent[u]] + 1;
            dfs(v);
        }
    }
}
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, m, x, y;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            rect[i].read(), g[i].clear(), visited[i] = 0;
        scanf("%d", &m);
        vector<QPt> XY;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            XY.push_back(QPt(x, y, i));
        }
        map<int, vector< pair<int, int> > > R;
        for (int i = 0; i < n; i++) {
            vector< pair<int, int> > &l = R[rect[i].lx], &r = R[rect[i].rx];
            l.push_back(make_pair(i, 1));
            l.push_back(make_pair(i, 2));
            r.push_back(make_pair(i, -1));
            r.push_back(make_pair(i, -2));
        }
        set< pair<int, int> > S;
        set< pair<int, int> >::iterator Sit, Sjt;
        for (map<int, vector< pair<int, int> > >::iterator it = R.begin();
            it != R.end(); it++) {
            vector< pair<int, int> > &D = it->second;
            for (int i = 0; i < D.size(); i++) {
                int k = D[i].first;
                if (D[i].second > 0) {
                    if (D[i].second == 1) {
                        Sit = S.lower_bound(make_pair(rect[k].ly, -1)), Sjt = Sit;
                        if (Sit != S.begin()) {
                            Sjt--;
                            g[Sjt->second].push_back(k);
                        }
                        S.insert(make_pair(rect[k].ly, k));
                    } else {
                        Sit = S.lower_bound(make_pair(rect[k].ry, -1)), Sjt = Sit;
                        if (Sit != S.end()) {
                            g[Sit->second].push_back(k);
                        }
                        S.insert(make_pair(rect[k].ry, k));
                    }
                } else {
                    if (D[i].second == -1)	S.erase(make_pair(rect[k].ly, k));
                    else					S.erase(make_pair(rect[k].ry, k));
                }
            }
        }
        int indeg[32767] = {};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < g[i].size(); j++)
                indeg[g[i][j]]++;
        }
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                parent[i] = -1, depth[i] = 1;
                dfs(i);
            }
        }
        for (int i = 0; i < n; i++)
            printf("%d%c", depth[i], i == n - 1 ? '\n' : ' ');
            
        sort(XY.begin(), XY.end());		
        int run_m = 0, OUT[32767] = {};
        S.clear();
        for (map<int, vector< pair<int, int> > >::iterator it = R.begin();
            it != R.end(); it++) {					
            vector< pair<int, int> > &D = it->second;
            for (int i = 0; i < D.size(); i++) {
                int k = D[i].first;
                if (D[i].second > 0) {
                    if (D[i].second == 1) {
                        Sit = S.lower_bound(make_pair(rect[k].ly, -1)), Sjt = Sit;
                        S.insert(make_pair(rect[k].ly, k));
                    } else {
                        Sit = S.lower_bound(make_pair(rect[k].ry, -1)), Sjt = Sit;
                        S.insert(make_pair(rect[k].ry, k));
                    }
                }
            }			
            while (run_m < m && XY[run_m].x <= it->first) {
                Sit = S.lower_bound(make_pair(XY[run_m].y, -1));
                if (rect[Sit->second].contain(XY[run_m].x, XY[run_m].y))
                    OUT[XY[run_m].label] = Sit->second;
                else
                    OUT[XY[run_m].label] = parent[Sit->second];
                run_m++;
            }
            for (int i = 0; i < D.size(); i++) {
                int k = D[i].first;
                if (D[i].second < 0) {
                    if (D[i].second == -1)	S.erase(make_pair(rect[k].ly, k));
                    else					S.erase(make_pair(rect[k].ry, k));
                }
            }
        }
        for (int i = 0; i < m; i++)
            printf("%d\n", OUT[i]);
    }
    return 0;
}
/*
7
0 0 10 10
1 1 9 2
1 3 9 7
2 4 4 6
5 4 6 5
7 5 8 6
1 8 9 9 
6 
3 5
6 6
7 4
9 1 
2 4 
-1 -1 
*/

Read More +

2014-10-17

學校課程/計算幾何

計算幾何 - HW02

Chapter 3

3.2

A rectilinear polygon is a simple polygon of which all edges are horizontal or vertical. Let P be a rectilinear polygon with n vertices. Give an example to show that$\left \lfloor n/4 \right \rfloor$ cameras are sometimes necessary to guard it.

正交多邊形是其中一種多邊形，邊與邊之間不是平行就是垂直。至少需要 n/4 個攝影機才能監視每一個角落。

The rectilnear polygon would contain$\left \lfloor n/4 \right \rfloor$ parallel “alleys”. At least$\left \lfloor n/4 \right \rfloor$ cameras are needed because no cameras can see more than one alleys.

正交多邊形，可以產生$\left \lfloor n/4 \right \rfloor$ 個平行的走廊，每一個攝影機只能顧及一個走廊，因此得到一個最簡單的例子需要$\left \lfloor n/4 \right \rfloor$ 個攝影機。

3.7

Let P be a simple polygon with n vertices, which has been partitioned into monotone pieces. Prove that the sum of the number of vertices of the pieces is O(n).

證明一個 n 個節點的簡單多邊形，拆成多個 monotone pieces，節點總數仍然是 O(n)。

一個簡單多邊形可以三角化成 n - 2 個三角形，每個三角形都是一個 monotone piece，因此節點個數總和$3 * (n - 2) = O(n)$

證明一個簡單多邊形有 n 個頂點，可以切成 n - 2 個三角形。

n = 3 時，T(3) = 1, 符合 T(n) = n - 2 成立
當 n = k 時，k >= 3, 且符合 T(n) = n - 2
n = k + 1 時，T(n + 1) = T(n) + 1 = (n - 2) + 1 = n - 1，

切割的證明為，找到多邊形的最左側點，然後他一定是凸的，將相鄰兩點拉一條線，如果構成的三角形內部沒有其他點，則直接變成 n - 1 個節點的多邊形，如果裡面有點，則挑一個最靠近最左側點的那個點，將最左側那個點與其相連，這時劃分成兩個多邊形，保證算法一樣。

3.11

Give an efficient algorithm to determine whether a polygon P with n
vertices is monotone with respect to some line, not necessarily a horizontal
or vertical one.

請參考 [ACM 題目] 單調測試的解法。

主要解法複雜度為 O(n log n)，採用角度掃描。

Chapter 4

4.2

Consider the casting problem in the plane: we are given polygon P and a 2-dimensional mold for it. Describe a linear time algorithm that decides whether P can be removed from the mold by a single translation.

對於 P 的任一面$f_{i}$ 的法向量$\vec{n_{i}}$，找到一個移動向量$\vec{d}$，使其$\vec{n_{i}}$ 和$\vec{d}$ 張角全大於 90 度。也就是內積小於 0。
給 {(n1x, n1y), (n2x, n2y), …}
nix * dx + niyy * dy <= 0
如果不單純派 dy = 1，調用 2DRANDOMIZEDBOUNDLP 判斷是否有解即可，不必最佳化其結果。

4.8

The plane z = 1 can be used to represent all directions of vectors in 3-dimensional space that have a positive z-value. How can we represent all directions of vectors in 3-dimensional space that have a non-negative z-value? And how can we represent the directions of all vectors in 3-dimensional space?

1.$z = 0 \cup z = 1$
2.$z = -1 \cup z = 1 \cup x = -1 \cup x = 1 \cup y = -1 \cup y = 1$，有人問說單純$z = -1 \cup z = 1$ 不就包含了所有方向嗎？但是我思考了一下收斂問題，這之間到底有沒有連續？極限上是相同，但是包不包含呢？這一點我比較擔憂，總之找一個方法將原點包起，保證原點拉到任一個面都能產生出所有方向，我附的答案是六面體，最簡單的四面體都然也可以，但是不太好寫。

4.16

On n parallel railway tracks n trains are going with constant speeds v1, v2, . . . , vn. At time t = 0 the trains are at positions k1, k2, . . . , kn. Give an O(nlogn) algorithm that detects all trains that at some moment in time are leading. To this end, use the algorithm for computing the intersection of half-planes.

公式$X_{i}(t) = K_{i} + V_{i} * t$
對於所有 polyhedral set$H = {(t, x) : \forall i; X \geq X_{i}(t)}$

之後將這些半平面做交集，看交集結果的邊屬於哪一個半平面的邊界，哪一個火車就曾經領先過。套用半平面求交集只需要 O(n log n)

請參考 [ACM 題目] 少女與戰車

Read More +

2014-10-17

解題區/出題解題

[ACM 題目] 單調測試

Problem

單調－這性質相當巧妙，可以在算法上好好地敲上一筆，處理速度跟你輸入的速度一樣快呢。

Background

這是計算幾何作業中的一環，但是找到一個 O(n) 算法果然不容易。

3.11 Give an efficient algorithm to determine whether a polygon P with n vertices is monotone with respect to some line, not necessarily a horizontal or vertical one.

到底有沒有可能用單調性質測試單調呢？ O(n log n) 就是極限？讓我們來挑戰挑戰。

Problem

假想一個二維平面，x 軸左右兩側將會射入雷射，現在要將一個簡單多邊形由上往下放入，雷射將會打在第一個碰觸的點上，請問有沒有一種放置方式，使得每一個邊都被雷射覆蓋到。

如上圖，假使這樣放置，位置 (0, 0), (2, 0) 將無法被雷射覆蓋，如果將此圖旋轉 90 度放入，就能覆蓋到所有邊了！因此，決定是否有一個角度放入，能覆蓋到所有邊。

Input

有多組測資，每一組測資第一行將會有一個整數 N，

接下來會有 N 行，每一行上會有一個座標 (x, y)，採用順時針或者逆時針順序。

Output

對於每組測資輸出一行，每一行輸出 yes/no。

Sample Input

Sample Output

1
2

yes
no

Solution

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
#include <map>
using namespace std;
#define eps 1e-10
#define MAXN 32767
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    x(a), y(b) {}
    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);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
Pt getIntersect(Pt l1, Pt p1, Pt l2, Pt p2) {
    double a1, b1, c1, a2, b2, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x;
    c1 = a1 * p1.x + b1 * p1.y;
    a2 = l2.y, b2 = -l2.x;
    c2 = a2 * p2.x + b2 * p2.y;
    dx = c1 * b2 - c2 * b1, dy = a1 * c2 - a2 * c1;
    d = a1 * b2 - a2 * b1;
    return Pt(dx/d, dy/d);
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
};
struct CMP2 {
    bool operator()(const double &i, const double &j) const {
        if (fabs(i-j) > eps)
            return i < j;
        return false;
    }
};
Seg segs[MAXN];
Pt D[MAXN];
int testMonotone(int n, Pt D[]) {
    int m = 0, origin_n = n;
    D[n] = D[0], D[n+1] = D[1];
    for (int i = 1; i <= n; i++) {
        Pt v1 = D[i + 1] - D[i];
        Pt v2 = D[i - 1] - D[i];
        segs[m++] = Seg(v1, v2, i);
        segs[m++] = Seg(v1 * -1, v2 * -1, i);
    }
    n = m;
    Pt pos = Pt(0, 0);
    set<int> S;
    map<double, vector< pair<int, int> >, CMP2> angle;
    for (int i = 0; i < n; i++) {
        double v1 = atan2(segs[i].s.y - pos.y, segs[i].s.x - pos.x);
        double v2 = atan2(segs[i].e.y - pos.y, segs[i].e.x - pos.x);
        angle[v1].push_back(make_pair(i, 0));
        angle[v2].push_back(make_pair(i, 1));
    }
    double c;
    pair<int, int> u = angle.begin()->second[0];
    Pt fpt;
    if (u.second == 0)  fpt = segs[u.first].s;
    else                fpt = segs[u.first].e;
    for (int i = 0; i < n; i++) {
        if (cross(pos, fpt, segs[i].s) * cross(pos, fpt, segs[i].e) < 0) {
            Pt q = getIntersect(segs[i].s - segs[i].e, segs[i].s, fpt - pos, pos);
            if (dot(q - pos, fpt - pos) > 0)
                S.insert(segs[i].label);
        } 
    }
    for (map<double, vector< pair<int, int> >, CMP2>::iterator it = angle.begin();
         it != angle.end(); it++) {
        for (int i = 0; i < it->second.size(); i++) {
            pair<int, int> u = it->second[i];
            if (u.second == 0)
                c = cross(pos, segs[u.first].s, segs[u.first].e);
            else
                c = cross(pos, segs[u.first].e, segs[u.first].s);
            if (fabs(c) > eps) {
                if (c > 0)
                    S.insert(segs[u.first].label);
                else
                    S.erase(segs[u.first].label);
            }
        }
        if (S.size() >= origin_n - 2)
            return 1;
    }
    return 0;
}
int main() {
    int n;
    double x, y;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            D[i] = Pt(x, y);
        }
        int flag = testMonotone(n, D);
        puts(flag ? "yes" : "no");
    }
    return 0;
}

Read More +

2014-10-17

解題區/解題區 - Zerojudge

b327. 學姊日談

內容：

Background

某 M 正與學姊討論蘿莉控追小海女的故事。

某 M 喃喃自語 …
『用了暴力法來完成的話，就能在調整 O(1) - O(E[x]) 完成。』
『如果用一個最常見的樹鏈剖分來完成也不過是 O(log n) - O(log^2 n)』
『在一般情況下，詢問次數肯定比調整次數來得高，想一想常數還得加上去，完全贏不了啊。』

學姊在一旁說到
『那如果是單純的二元樹，有比較好做嗎？說不定有更簡化的算法來完成？』
『說不定那個 … bitvertor 還是 bitset 能完成呢。』
『這個想法難不成是找到 lowbit 嗎？我沒有暫時想法。』某 M 這麼回答道。
『也許吧 … 我也不確定』學姊簇著眉。

某 M 發了瘋似的想了一個算法
『如果我們將其轉換成 k-ary search tree，也就是說需要將節點編號重新編成有大小關係，然後維護一個 BST 來查找 lower_bound 的結果，這麼一來就是 O(k log n) - O(log n) 了！』
『啊啊啊，這個方法不可行，』
學姊將鄙視般的眼神投向某 M。看來這場病還要持續很久。

『將題目弄成找樹前綴和好了，既然暴力法有期望值的剪枝，讓它剪不了不就好了！』
『你覺得不會被其他解法坑殺嗎 …』學姊如此擔憂地表示到。
『沒關係，吾等 M 可不是說假的』
Problem

給定一棵樹，樹根 root 編號 0，每個點一開始的權重為 0。

操作 x k: 將節點 x 的權重增加 k，請輸出從 x 到 root 的權重和。

輸入說明：

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

輸出說明：

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行，保證總和可以在 signed 32 bits 內。

範例輸入：

範例輸出：

Solution 1

先將一棵樹壓平，壓平的方式為採用前序走訪。壓樹的另一個思考方式就是換成括弧表示法。(A (B) (C(D)(E))) 類似的情況。壓樹之後，每個節點對應一個左右括弧位置，當我們增加節點 v 權重時，相當於將所有區間的內數字加上 k (子樹的所有節點到根的花費)。

因此我們的問題變成

操作 [l, r]：將區間內的所有數字加上 k
詢問 x：詢問位置 x 元素的值。

下面使用 Binary indexed tree 示範區間調整，單點詢問。

對於 ADD [l, r] k 時，相當於 BIT[l] += k, BIT[r+1] -= k，單點詢問相當於找前綴和 [1, x] 的結果。

每個操作時間複雜度 O(log n)。

#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
struct Tree {
    vector<int> g[MAXN];
    int root;	
    void init(int n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        root = 0;
    }
    void addEdge(int x, int y) {
        g[x].push_back(y);
        g[y].push_back(x);
    }
} tree;
int bPos[MAXN], ePos[MAXN], inOrder[MAXN<<1], inIdx = 0;
void prepare(int u, int p) {
    bPos[u] = ePos[u] = ++inIdx, inOrder[inIdx] = u;
    for (int i = 0; i < tree.g[u].size(); i++) {
        int v = tree.g[u][i];
        if (v == p)	continue;
        prepare(v, u);
    }
    ePos[u] = ++inIdx, inOrder[inIdx] = u;
}
int bitTree[MAXN<<1];
void modify(int x, int N, int val) {
    while (x <= N) {
        bitTree[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += bitTree[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int n, q, x, y;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        tree.init(n);
        
        int on[MAXN] = {};
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree.addEdge(x, y);
        }
        
        inIdx = 0;
        prepare(tree.root = 0, -1);
        memset(bitTree, 0, sizeof(bitTree));
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            scanf("%d %d", &x, &y);
            modify(bPos[x], inIdx, y);
            modify(ePos[x] + 1, inIdx, -y);
            printf("%d\n", query(bPos[x]));
        }
        puts("");
    }
    return 0;
}

Solution 2

這個解法直接使用樹鏈剖分，樹鏈剖分將子樹節點數量最大的當作重邊，其餘皆為輕邊。將以重邊相連的所有節點，看似一個鏈狀，當作一個 1D Array 看待。

保證每個點爬到 root，只會經過 log n 的輕邊，而中間鏈狀處理，可以使用 segment tree 等之類的樹來壓縮處理時間。

下面為樹鏈剖分的解法，詢問效率 O(log^2 n)，調整 O(log n)。

#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
int hNext[MAXN], iNode[MAXN], aPos[MAXN];
int used[MAXN], nodesize = 0;
struct Node {
    int p, pPos;
    vector<int> A;
    vector<int> BIT;
    void init() {
        A.clear(), BIT.clear();
        p = -1;
    }
} nodes[262144];
struct Tree {
    vector<int> g[MAXN];
    int root;	
    void init(int n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        root = 0;
    }
    void addEdge(int x, int y) {
        g[x].push_back(y);
        g[y].push_back(x);
    }
} tree;
int prepare(int u, int p) {
    int sz = 1, mx = 0, hedge = -1;
    int v, t;
    for (int i = 0; i < tree.g[u].size(); i++) {
        v = tree.g[u][i], t;
        if (v == p)	continue;
        sz += (t = prepare(v, u));
        if (mx < t)
            mx = t, hedge = v;
    }
    hNext[u] = hedge;
    return sz;
}
void build(int u, int p) {	
    if (used[u] == 0) {
        Node &nd = nodes[++nodesize];
        nd.init();
        for (int i = u; i != -1; i = hNext[i]) {
            used[i] = 1;
            iNode[i] = nodesize, aPos[i] = nd.A.size();
            nd.A.push_back(i);
        }
        nd.BIT.clear(), nd.BIT.resize(nd.A.size() + 10, 0);
        if (p != -1)	nd.p = iNode[p], nd.pPos = aPos[p];
    }
    int v;
    for (int i = 0; i < tree.g[u].size(); i++) {
        v = tree.g[u][i];
        if (v == p)	continue;
        build(v, u);
    }
}
int queryBIT(vector<int> &BIT, int x) {
    int ret = 0;
    while (x)
        ret += BIT[x], x -= x&(-x);
    return ret;
}
void modifyBIT(vector<int> &BIT, int x, int val, int L) {
    while (x <= L)
        BIT[x] += val, x += x&(-x);
}
void search(int u) {
    int sum = 0;
    set< pair<int, int> >::iterator it, jt;
    for (int i = iNode[u], in = aPos[u]; i != -1; in = nodes[i].pPos, i = nodes[i].p)
        sum += queryBIT(nodes[i].BIT, in + 1);
    printf("%d", sum);
    puts("");
}
void modify(int u, int val) {
    Node &nd = nodes[iNode[u]];
    int pos = aPos[u];
    modifyBIT(nd.BIT, pos + 1, val, nd.A.size());
}
int main() {
    int n, q, x, y;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        tree.init(n);
        
        int on[MAXN] = {};
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree.addEdge(x, y);
        }
        
        prepare(tree.root = 0, -1);
        memset(used, 0, sizeof(used));
        nodesize = 0;
        build(tree.root = 0, -1);
        
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            scanf("%d %d", &x, &y);
            modify(x, y);
            search(x);
        }
        puts("");
    }
    return 0;
}

Read More +

2014-10-17

解題區/解題區 - Zerojudge

b322. 樹形鎖頭

內容：

Background

正值大四的 Morris，面臨無法畢業的窘境，每天不是玩 PoE 遊戲就是在解題目，為了逃避現實解題目也越來越多，但對於未來目標仍然沒有任何進展，一個人在房間裡孤拎拎地打著 PoE，萬萬沒想到遊戲帳號被盜取，「密碼鎖什麼的果然太天真的，ACM 鎖才是未來的目標」打密碼登入有什麼了不起的，寫程式 AC 登入才有意思。

Problem

一張無向圖，給 N 個點、N - 1 條邊，任兩點之間只會有一條路徑。

操作 (u, v, k)：將 u, v 之間經過的節點權重加上 k。

請問經過 M 次操作後，每個節點的權重值為何？

輸入說明：

輸入有多組測資。

每一組測資第一行會有兩個正整數 N, M (0 < N, M < 32767)，接下來會有 N - 1 行，每行上會有兩個整數 u, v (0 <= u, v < N) 表示 u 和 v 之間有一條邊。接著會有 M 行操作 (u, v, k) (0 < k < 32767)。

輸出說明：

每組測資輸出一行，分別將節點權重輸出。

範例輸入：

範例輸出：

1	5 3 5 3 2 4 8

Solution

解說圖

A[] : 子樹總和
B[] : 節點權重

增加路徑 u 到 v 的權重為 k 時，路徑相當於 u 到某點 x 再到 LCA(u, v) 接著 y 最後 v。

那我們增加節點 u, v 的權重 B[u] += k, B[v] += k，減少其 LCA 的權重 B[LCA(u, v)] -= 2k，然後你會觀察 A[] 的部分，權重增加 k 的只會有 u-v 之間的所有節點。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
int visited[32767];
vector<int> tree[32767];
int parent[32767], weight[32767];
int findp(int x) {
    return parent[x] == x ? x : (parent[x] = findp(parent[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
// LCA
vector< pair<int, int> > Q[32767];// query pair, input index - node
int LCA[131072]; // [query time] input query answer buffer.
void tarjan(int u, int p) {// rooted-tree.
    parent[u] = u;
    for(int i = 0; i < tree[u].size(); i++) {//son node.
        int v = tree[u][i];
    	if(v == p)	continue;
        tarjan(v, u);
        parent[findp(v)] = u;
    }
    visited[u] = 1;
    for(int i = 0; i < Q[u].size(); i++) {
        if(visited[Q[u][i].second]) {
            LCA[Q[u][i].first] = findp(Q[u][i].second);
        }
    }
}
int dfs(int u, int p, int weight[]) {
    int sum = weight[u];
    for(int i = 0; i < tree[u].size(); i++) {//son node.
        int v = tree[u][i];
    	if(v == p)	continue;
        sum += dfs(v, u, weight);
    }
    return weight[u] = sum;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int n, m, x, y, u, v, k;
    int X[32767], Y[32767], K[32767];
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            tree[i].clear();
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree[x].push_back(y);
            tree[y].push_back(x);
        }
        
        int weight[32767] = {}, extra[32767] = {};
        for (int i = 0; i < n; i++)
            visited[i] = 0, Q[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &X[i], &Y[i], &K[i]);
            Q[X[i]].push_back(make_pair(i, Y[i]));
        	Q[Y[i]].push_back(make_pair(i, X[i]));
        }
        tarjan(0, -1);
        for (int i = 0; i < m; i++) {
            extra[LCA[i]] += K[i];
            weight[X[i]] += K[i];
            weight[Y[i]] += K[i];
            weight[LCA[i]] -= 2 * K[i];
        }
        dfs(0, -1, weight);
        for (int i = 0; i < n; i++)
            printf("%d%s", weight[i] + extra[i], i == n-1 ? "" : " ");
        puts("");
    }
    return 0;
}

Read More +

2014-10-17

解題區/解題區 - Zerojudge

b321. 河道分界

內容：

M 國開始藉由河道進行分裂，M 國土只會介於 y = 0 和 y = 1 之間，在 x 軸兩側無限延伸，保證河道彼此不會相交任何一點。

操作 A u v : 增加河道 (u, 1) 到 (v, 0)，該河道編號為當前操作 A 的數量。

操作 Q x y : 詢問位置 (x, y) 在哪兩個河道之間。

輸入說明：

第一行將會有一個整數 N (N < 100, 000)，表示接下來會有幾筆操作。

操作 A u v : u, v [-50000, 50000] 之間的實數。

操作 Q x y : x 屬於 [-50000, 50000], y 屬於 [0, 1]。

輸出說明：

對於每個詢問，輸出在哪兩個河道之間，邊界為 [S, M]，如果恰好在河道上輸出 [?, ?]，詳細請參考範例輸出。

範例輸入：

8
A 0 0
Q -1 0
Q 1 0
Q 0 0
A 1 2
Q 1 0.5
Q 3 0.5
Q 1.5 0.5

範例輸出：

[S, 1]
[1, M]
[?, ?]
[1, 2]
[2, M]
[?, ?]

Solution

建造一個 BST，這裡使用內建 std::set 的紅黑樹，查找 lower_bound 即可。如果是靜態的河道，一開始對其排序即可，然後二分查找 lower_bound。

如果測資有錯，歡迎打我。

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct seg {
    Pt s, e;
    int label;
    seg(Pt a, Pt b):s(a), e(b) {}
};
struct CMP {
    static double y;
    
    double interpolate(const Pt& p1, const Pt& p2, double& y) {
        if (p1.y == p2.y) return p1.x;
        return p1.x + (double)(p2.x - p1.x) / (p2.y - p1.y) * (y - p1.y);
    }
    
    bool operator()(const seg &i, const seg &j) {
        double v1 = interpolate(i.s, i.e, y), v2 = interpolate(j.s, j.e, y);
        if (fabs(v1 - v2) > eps)
            return v1 < v2;
        return false;
    }
};
double CMP::y = 0;
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    int n;
    double x, y, up, down;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        set<seg, CMP> S;
        for (int i = 0, k = 1; i < n; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'A') {
                scanf("%lf %lf", &up, &down);
                seg tmp = seg(Pt(up, 1), Pt(down, 0));
                tmp.label = k;
                S.insert(tmp), k++;
            } else {
                scanf("%lf %lf", &x, &y);
                CMP::y = y;
                set<seg>::iterator it = S.lower_bound(seg(Pt(x, 1), Pt(x, 1))), jt;
                if (it != S.end()) {
                    if (onSeg(it->s, it->e, Pt(x, y))) {
                        puts("[?, ?]");
                        continue;
                    }
                }
                int l = -1, r = -1;
                if (it != S.begin()) {
                    jt = it, jt--;
                    l = jt->label;
                    if (onSeg(jt->s, jt->e, Pt(x, y))) {
                        puts("[?, ?]");
                        continue;
                    }
                }
                if (it != S.end())
                    r = it->label;
                if (l == -1)
                    printf("[S, ");
                else
                    printf("[%d, ", l);
                if (r == -1)
                    printf("M]");
                else
                    printf("%d]", r);
                puts("");
            }
        }
    }
    return 0;
}

Read More +

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Input

Output

Sample Input

Sample Output

Solution

Chapter 3

3.2

3.7

3.11

Chapter 4

4.2

4.8

4.16

Problem

Input

Output

Sample Input

Sample Output

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution 1

Solution 2

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：