Oct 23 2014

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 +

Oct 21 2014

解題區►出題解題

[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 +

Oct 17 2014

學校課程►計算幾何

計算幾何 - 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?

$z = 0 \cup z = 1$
$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 +

Oct 17 2014

解題區►出題解題

[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 +

Oct 17 2014

解題區►解題區 - 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 +

Oct 17 2014

解題區►解題區 - 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 +

Oct 17 2014

解題區►解題區 - 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 +

Oct 17 2014

學校課程►通識課程

[通識] 文明的進程 Week 4

每次小考禮貌與羞恥相關的考題，看來這門通識相當難過呢。

文明相對性

文明化是具有相對性的，根據不同時間，原本認為好的文明舉止也有可能被汰換掉，而不好的舉止也有可能再下一個世代中被重用。

舉一個最簡單的例子，以我們亞洲社會來講，一個溫文儒雅、拘謹的人才算文明，而在過去可能認為瀟灑自在、豪放不羈才算是一個文明俠士。在這一個過程中，文明舉止居然變得不文明，是個相當有趣的現象。

看看那電影中的英雄，有多少文明人呢？個個不守規矩，個個都有反抗意識。還做英雄？還是做文明人？

文明阻隔

文明舉止阻隔了什麼？身為一個生物的 自然功能 (Elias 書中特地不寫 屎尿屁 )，現代人眼中講出 屎尿屁 三字的羞恥程度居然沒有比過去還要高，Elias 的年代講出這幾個字想必都羞愧不如。

進食可以忍耐、延後，但是屎尿屁三者卻是相當難抑制。人都不人，這正常功能卻要被約束，抑制反而會傷了身體，為了禮儀而傷了自己，在現代則盡可能以 健康為由 ，走向與禮儀相反的舉止，盡可能轉換這一過程。

論廁所

廁所越來越不像廁所，越來越隱密，越隱密就越受歡迎，相反的卻也越來越不環保，為了在空氣流通不好的地方保持流通，消耗更多電力來維護。

當人們越常在外活動，公廁的存在就很重要，因此用公廁的普遍性呈現一個國家的文明程度，

在鄉下的農業社會中，鄉民們還會替你準備公廁呢，「 你的屎尿就是黃金肥料 」化學肥料沒有普及到那邊時，屎尿可能比黃金更珍貴，因此處處可見這種由農民建起的公廁，而有誤解成中國為 “禮儀之邦”，人的屎尿不會隨處可見，反觀歐洲在下水道還沒有技術支持前，人的屎尿在街道上到處都是，相較中國反而文明了！

規範手法

外顯禮貌
內在羞恥

其中羞恥心為最重要的手法，尤其是當沒有別人眼光時，仍然要遵守禮儀就是相當需要羞恥心的。

「小天使會在一旁看著，如果不想讓天使討厭你，請隨時注意禮節。」而在現在監視器取代了小天使，想要在沒人的地方裸體，看來還是得注意點呢！

已經從顧及他人觀感到愛護自己健康，愛護自己更具有說服力，潔身自愛成為新的主流，人際之間的階層關係沒有說服力，誰能抵擋健康這一個理由呢！

什麼時候會拋棄自己的文化舉動呢？向低等人示友好厚愛時，做出一樣羞恥的事情，反而會更加地容易親近，但是相反地會更鞏固之間的階層關係 (因為認同彼此階級的差別)。

論餐桌夾菜

階層社會：以示照顧、關愛
平等社會：侵犯主權

被傷害的孩子

禮儀演進消耗百年，而孩子卻要在數年之內完成禮儀和羞恥的學習，這麼巨量的訊息藉由不同管道了解，每當我們認為小孩相當不禮貌時，同時也表示我們對於禮儀的要求又更高。

結語

如果在沒人的地方，做出平常人不會做的事情，就真的羞恥了嗎？為什麼沒有傷害別人，卻也必須冠上妨害風化、風俗的罪名。為了防止無知的效仿效應，難道這一點趣味都要遏止？

禮儀教給我們到底是什麼？更加鞏固自己的地位嗎？區分彼此身分的第一印象嗎？我們遵守禮儀失去了真正生物的本能，就如捷運殺人案，反抗本能消散，我們是怎麼失去暴力的。

作業

請觀看影片 2 cellos “Thunderstruck”，並從文明化的觀點分析（100字）

大人們固定成形的價值觀，相較於小孩更難以改變，只要一更動部分可能就會替換掉一大部分觀念，年輕人講出來的點子的基準不同，彼此之間的溝通性好、衝突少。才會造就影片中受到小孩喜歡、大人們卻難以接受的情況。

Read More +

Oct 12 2014

解題區►出題解題

[ACM 題目] 少女與戰車

Problem

蘋果樹和梨樹花朵綻放，茫茫霧靄在河面飄揚。出門走到河岸邊，喀秋莎，到那又高又陡的河岸。

一面走著，一面唱著歌兒。唱道草原上空的蒼鷹，唱道她衷心喜愛的男孩。他的來信封封都珍藏。

啊！歌兒，女孩悠揚的歌聲，請跟隨著光明的太陽，飛翔到遙遠前方的戰士，為喀秋莎來向他致意。

願他還記得純情的女孩，願她的歌聲能被聽聞。願他保衛著祖國的大地，而喀秋莎守護著愛情。

蘋果樹和梨樹花朵綻放，茫茫霧靄在河面飄揚。出門走到河岸邊，喀秋莎，到那又高又陡的河岸。

正當梨花開遍了天涯，河上飄著柔曼的輕紗，喀秋莎站在峻峭的岸上，歌聲好像明媚的春光。

姑娘唱著美妙的歌曲，她在歌唱草原的雄鷹，她在歌唱心愛的人兒，她還藏著愛人的書信。

啊，這歌聲姑娘的歌聲，跟著光明的太陽去飛吧，去向遠方邊疆的戰士，把喀秋莎的問候傳達。

駐守邊疆年輕的戰士，心中懷念遙遠的姑娘，勇敢戰鬥保衛祖國，喀秋莎愛情永遠屬於他。

正當梨花開遍了天涯，河上飄著柔曼的輕紗，喀秋莎站在峻峭的岸上，歌聲好像明媚的春光。

現在有 N 台戰車平行奔馳在雪地上，在時間 $t = 0$ 時，分別位於 $x_{i}$，並且每戰車都維持等速度 $v_{i}$，請問有哪幾台曾經在奔馳的過程中當過領先者。

Input

輸入有多組測資，每組第一行會有一個整數 N (N < 32767)。

接著會有 N 行戰車資訊，每一行上會有兩個實數 $(x_{i}, v_{i})$，其中 $-100,000\le x_{i} \le 100,000$、$-100\le v_{i} \le 100$。

Output

對於每組輸出一行，按照輸入順序輸出是否曾經當過領先者，參閱範例輸出。

Sample Input

Sample Output

1 1 0
1 1 1 1 0 0
1 0 1
1 1 1 0

hint

Javascript Animation Click It !

example 1
example 2
example 3
example 4

Solution

Read More +

Oct 12 2014

解題區►解題區 - UVa

UVa 12806 - Grand Tichu

Problem

增加 4 張牌到撲克牌中，每名玩家將會獲得 14 張牌，而在有 8 張的時候，可以預估是否會湊到 4 種類型的手牌，如果可以組合出其中一種的機率大於 0.25，則喊出 Grand Tichu!。

Sample Input

D23468AA
D2P4688K
D23468KA
D2233889
PdM2345T
PdM234AA
0

Sample Output

Grand Tichu!
Grand Tichu!
Grand Tichu!
...
...
...

Solution

搜索順序的重要性，由於 4 種組合牌中，只與 ADPMd 有關，剩下的類型可以直接利用組合去計算，只要窮舉 ADPMd 出現在手牌的組合情況即可。

如果按照一般的 23456789TJQKADPMd 效率不彰，耗費時間太久，再多剪枝都不夠。

一開始誤以為是 4 種機率加總大於 0.25 就輸出，不管怎麼樣連範測都會錯，後來發現是湊出其中一種的機率必須大於 0.25。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long C[50][50];
const char kind[20] = "ADPMd23456789TJQK";
int ihand[20], ohand[20], mhand[20];
int suffix[20];
long long va[10], vb;
void dfs(int idx, int card, long long ways) {
	if (idx > 4) {
		ways = ways * C[suffix[idx]][14 - card];
		int hh = 0;
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[0] > 0)
			hh = 1, va[hh] += ways;// D P A
		if (ohand[1] > 0 && ohand[0] >= 2)
			hh = 2, va[hh] += ways;// D A A
		if (ohand[2] > 0 && ohand[0] >= 3)
			hh = 3, va[hh] += ways; // P A A A
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[3] > 0 && ohand[4] > 0)
			hh = 4, va[hh] += ways; // D P M d
		vb += ways;
		return ;
	}
	if (card == 14) {
		int hh = 0;
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[0] > 0)
			hh = 1, va[hh] += ways;// D P A
		if (ohand[1] > 0 && ohand[0] >= 2)
			hh = 2, va[hh] += ways;// D A A
		if (ohand[2] > 0 && ohand[0] >= 3)
			hh = 3, va[hh] += ways; // P A A A
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[3] > 0 && ohand[4] > 0)
			hh = 4, va[hh] += ways; // D P M d
		vb += ways;
		return ;
	}
	if (idx == 17 || card + suffix[idx] < 14)	return ;
	for (int i = 0; i <= ihand[idx] && card + i <= 14; i++) {
		ohand[idx] += i;
		dfs(idx+1, card + i, ways * C[ihand[idx]][i]);
		ohand[idx] -= i;
	}
}
int main() {
	for (int i = 0; i < 50; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++)
			C[i][j] = C[i-1][j-1] + C[i-1][j];
	}
	char hand[64];
	while (scanf("%s", &hand) == 1 && hand[0] != '0') {
		memset(ihand, 0, sizeof(ihand));
		memset(ohand, 0, sizeof(ohand));
		for (int i = 4; i < 17; i++)
			ihand[i] = 4, mhand[i] = 4;
		ihand[0] = 4, mhand[0] = 4;
		for (int i = 1; i <= 4; i++)
			ihand[i] = 1, mhand[i] = 1;
		for (int i = 0; i < 8; i++) {
			int p = find(kind, kind + 17, hand[i]) - kind;
			ihand[p]--, ohand[p]++;
		}
		memset(suffix, 0, sizeof(suffix));
		for (int i = 17; i >= 0; i--)
			suffix[i] = suffix[i+1] + ihand[i];
		memset(va, 0, sizeof(va));
		vb = 0;
		dfs(0, 8, 1);
		int ok = 0;
		for (int i = 0; i < 4; i++) {
			double p = (double)va[i] / vb;
			if (p > 0.25)	ok = 1;
		}
		if (ok)
			puts("Grand Tichu!");
		else
			puts("...");
	}
	return 0;
}
/*
D23468AA
D2P4688K
D23468KA
D2233889
PdM2345T
PdM234AA
0
D23468AA
0.000000
0.125000
1.000000
0.025439
Grand Tichu
D2P4688K
0.000000
0.424761
0.070768
0.004394
Grand Tichu
D23468KA
0.000000
0.125000
0.336263
0.003315
Grand Tichu
D2233889
0.000000
0.046558
0.070768
0.000298
...
PdM2345T
0.000000
0.046558
0.006332
0.004394
...
PdM234AA
0.000000
0.125000
0.125000
0.236702
...
*/

Read More +

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

文明相對性

文明阻隔

論廁所

規範手法

論餐桌夾菜

被傷害的孩子

結語

作業

Problem

Input

Output

Sample Input

Sample Output

hint

Solution

Problem

Sample Input

Sample Output

Solution

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：