解題區/解題區 - UVa

UVa 10713 - Map

Problem

A pirate’s treasure map typically contains a series of instructions which, if followed, lead you from the landing place on a desert isle to the spot marked X where the treasure is buried. You are to construct such a series of instructions for a particular desert isle.

The island is a circle with radius r paces whose centre is at (0,0). Relative to the centre, the point (0,1) is north, (0,-1) is south, (1,0) is east, and (-1,0) is west. Also, (1,1) is northeast, (1,-1) is southeast, (-1,1) is northwest, and (-1,-1) is southwest.

The landing place, on the circumference, is specified by its coordinates. The spot marked X, on the surface of the island is also specified by its coordinates.

Each instruction in the sequence should have the form

direction distance

where direction is one of { north, south, east, west, northeast, northwest, southeast, southwest } and distance is a non-negative real number indicating the number of paces to be travelled in the given direction. When executed as a sequence the instructions should lead from the landing place to the spot marked X without leaving the island. The total distance (that is, the sum of the distances in your sequence) should be minimized. From the possible sequences that minimize total distance, choose one with the minimum number of instructions.

Input will consist of a number of test cases, followed by a line containing -1. Each test case consists of a single line containing five real numbers: r, x, y, X, Y. r is the radius of the island; x,y are the coordinates of the landing place; X,Y are the coordinates of the spot marked X. The landing place and the spot marked X are distinct.

For each test case, output the sequence, one instruction per line. Distances should be accurate to ten places after the decimal, as shown. Output an empty line between test cases.

Sample Input

1
2
100.0 0.0 100.0 25.0 50.0
-1

Possible Output for Sample Input

1
2
south 25.0000000000
southeast 35.3553390593

Solution

題目描述：

在一個圓心島嶼上，給定登陸的座標以及寶藏的位置，只能由 8 個方向的指令，在不跑出陸地的情況下，用最少指令抵達目的地。

題目解法：

很明顯地，保證不超過兩步，但是問題在於要如何不跑出陸地上。

首先，畫一個三角形，保證能用 45 度 + 90 度的情況走到另外一個角，但是對於圓上兩點拉出來平行兩軸的矩形中，能拆分成兩個三角形，對於其中一個做就可以了。

考慮先走 45 度和 90 度其中一個，只會有兩種情況，模擬先走 45 度的情況，查閱是否超出邊界，否則倒序輸出步驟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <math.h> 
#define eps 1e-8 
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    double r, x1, x2, y1, y2;
    const double sq2 = sqrt(2);
    int cases = 0;
    while(scanf("%lf %lf %lf %lf %lf", &r, &x1, &y1, &x2, &y2) == 5) {
        if(cases++)	puts("");
        double dx = x2 - x1, dy = y2 - y1;
        if(fabs(dx) < fabs(dy)) {
            double diff = fabs(dy) - fabs(dx);
            if(dy < 0) {
                double x = x1 + dx, y = y1 - fabs(dx);
//				printf("%lf %lf\n", x, y);
                if(x*x + y*y > r*r) {
                    if(fabs(diff) > eps)
                        printf("south %.10lf\n", diff);
                    if(dx > 0)
                        printf("southeast %.10lf\n", fabs(dx) * sq2);
                    if(dx < 0)
                        printf("southwest %.10lf\n", fabs(dx) * sq2);
                } else {
                    if(dx > 0)
                        printf("southeast %.10lf\n", fabs(dx) * sq2);
                    if(dx < 0)
                        printf("southwest %.10lf\n", fabs(dx) * sq2);
                    if(fabs(diff) > eps)
                        printf("south %.10lf\n", diff);
                }
            } else {
                double x = x1 + dx, y = y1 + fabs(dx);
                if(x*x + y*y > r*r + eps) {
                    if(fabs(diff) > eps)
                        printf("north %.10lf\n", diff);
                    if(dx > 0)
                        printf("northeast %.10lf\n", fabs(dx) * sq2);
                    if(dx < 0)
                        printf("northwest %.10lf\n", fabs(dx) * sq2);
                } else {
                    if(dx > 0)
                        printf("northeast %.10lf\n", fabs(dx) * sq2);
                    if(dx < 0)
                        printf("northwest %.10lf\n", fabs(dx) * sq2);
                    if(fabs(diff) > eps)
                        printf("north %.10lf\n", diff);
                }
            }
        } else {
            double diff = fabs(dx) - fabs(dy);
            if(dx < 0) {
                double x = x1 - fabs(dy), y = y1 + dy;
                if(x*x + y*y > r*r + eps) {
                    if(fabs(diff) > eps)
                        printf("west %.10lf\n", diff);
                    if(dy > 0)
                        printf("northwest %.10lf\n", fabs(dy) * sq2);
                    if(dy < 0)
                        printf("southwest %.10lf\n", fabs(dy) * sq2);
                } else {
                    if(dy > 0)
                        printf("northwest %.10lf\n", fabs(dy) * sq2);
                    if(dy < 0)
                        printf("southwest %.10lf\n", fabs(dy) * sq2);					
                    if(fabs(diff) > eps)
                        printf("west %.10lf\n", diff);
                }
            } else {
                double x = x1 + fabs(dy), y = y1 + dy;
                if(x*x + y*y > r*r + eps) {
                    if(fabs(diff) > eps)
                        printf("east %.10lf\n", diff);
                    if(dy > 0)
                        printf("northeast %.10lf\n", fabs(dy) * sq2);
                    if(dy < 0)
                        printf("southeast %.10lf\n", fabs(dy) * sq2);
                } else {
                    if(dy > 0)
                        printf("northeast %.10lf\n", fabs(dy) * sq2);
                    if(dy < 0)
                        printf("southeast %.10lf\n", fabs(dy) * sq2);					
                    if(fabs(diff) > eps)
                        printf("east %.10lf\n", diff);
                }
            }
        }
    }
    return 0;
}
/*
    74.584 49.541 55.754 -43.557 -37.453
    74.584 49.541 55.754 23.560 -69.849
    74.584 -40.498 -62.632 0.540 6.183
    74.584 -40.498 -62.632 -14.154 0.389
*/
Read More +
解題區/解題區 - UVa

UVa 149 - Forests

Problem

The saying You can't see the wood for the trees is not only a cliche, but is also incorrect. The real problem is that you can’t see the trees for the wood. If you stand in the middle of a wood (in NZ terms, a patch of bush), the trees tend to obscure each other and the number of distinct trees you can actually see is quite small. This is especially true if the trees are planted in rows and columns (as in a pine plantation), because they tend to line up. The purpose of this problem is to find how many distinct trees you can see from an arbitrary point in a pine plantation (assumed to stretch for ever).

picture23

You can only see a distinct tree if no part of its trunk is obscured by a nearer tree–that is if both sides of the trunk can be seen, with a discernible gap between them and the trunks of all trees closer to you. Also, you can’t see a tree if it is apparently too small. For definiteness, not too small and discernible gap will mean that the angle subtended at your eye is greater than 0.01 degrees (you are assumed to use one eye for observing). Thus the two trees marked picture169 obscure at least the trees marked picture175 from the given view point.

Write a program that will determine the number of trees visible under these assumptions, given the diameter of the trees, and the coordinates of a viewing position. Because the grid is infinite, the origin is unimportant, and the coordinates will be numbers between 0 and 1.

Input

Input will consist of a series of lines, each line containing three real numbers of the form 0.nn. The first number will be the trunk diameter–all trees will be assumed to be cylinders of exactly this diameter, with their centres placed exactly on the points of a rectangular grid with a spacing of one unit. The next two numbers will be the x and y coordinates of the observer. To avoid potential problems, say by being too close to a tree, we will guarantee that tex2html_wrap_inline260 . To avoid problems with trees being too small you may assume that tex2html_wrap_inline262 . The file will be terminated by a line consisting of three zeroes.

Output

Output will consist of a series of lines, one for each line of the input. Each line will consist of the number of trees of the given size, visible from the given position.

Sample input

1
2
0.10 0.46 0.38
0 0 0

Sample output

1
128

Solution

題目描述：

所有樹木的圓心都在整數座標上，給定每棵樹的直徑和當前所在位置，問能看見多少棵樹木。

能看見的定義為：看到樹兩側邊緣的張角必須大於 0.01 度，同時要跟之前的前方遮蔽的樹木之間保留 0.01 度之間的間隔。

(也就是說樹不能太細瘦，同時看過去的時候不考慮遠方樹木時，要與前方的樹木之間有小縫隙。)

題目解法：

由於有限制張角在 0.01 以上，因此太遠的樹木不用考慮，因此窮舉一部分的樹木即可。

對於窮舉位置的樹木，由距離當前位置的數字由小排到大，開始考慮前方是否有樹木遮蔽，因此把每個樹木的張角 [l, r] 先算出來，接著對於一個樹木，查找是否有距離更近的樹木遮蔽。

對於計算張角的部分 (圓外一點)，有兩種做法

  • 算出兩切線的交點，來得到兩交點的所形成的角度，保證不超過 180 度。
  • 從起點拉到圓心，算出角度之後，根據切線所形成的三角形，算出 asin 把角度疊加即可。

後者比較簡單，前者雖為本次的計算方式，略為不滿意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define eps 1e-6
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 dist2(Pt a, Pt b) {
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(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 getLineIntersection(double a1, double b1, double c1, double a2, double b2, double c2) {
    // a1 x + b1 y + c1 = 0, a2 x + b2 y + c2 = 0
    c1 = -c1, c2 = -c2;
    double d, dx, dy;
    d = a1 * b2 - a2 * b1;
    dx = c1 * b2 - c2 * b1;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx/d, dy/d);
}
void getTangentIntersection(Pt co, double r, Pt p, Pt &pa, Pt &pb) {
    double a, b, c;
    double m1a, m1b, m1c, m2a, m2b, m2c, m1, m2;
    a = r*r - (co.x - p.x) * (co.x - p.x);
    b = 2 * (co.x - p.x) * (co.y - p.y);
    c = r*r - (co.y - p.y) * (co.y - p.y); // am^2 + bm + c = 0
    if(fabs(a) < eps) {
        m2 = (-c)/b;
        m1a = 1, m1b = 0, m1c = - (m1a * p.x + m1b * p.y);
        m2a = m2, m2b = -1, m2c = - (m2a * p.x + m2b * p.y);
    } else {
        m1 = (-b + sqrt(b*b - 4*a*c))/ (2*a);
        m2 = (-b - sqrt(b*b - 4*a*c))/ (2*a);
        m1a = m1, m1b = -1, m1c = - (m1a * p.x + m1b * p.y);
        m2a = m2, m2b = -1, m2c = - (m2a * p.x + m2b * p.y);
    }
    pa = getLineIntersection(m1a, m1b, m1c, m1b, -m1a, -(m1b * co.x + (-m1a) * co.y));
    pb = getLineIntersection(m2a, m2b, m2c, m2b, -m2a, -(m2b * co.x + (-m2a) * co.y));
}
struct Interval {
    Pt p;
    double dist, l, r;
    Interval(double a = 0, double b = 0, double c = 0, Pt d = Pt()):
        dist(a), l(b), r(c), p(d) {
    }
    bool operator<(const Interval &x) const {
        return dist < x.dist;
    }
};
int main() {
    Pt pa, pb, co(1, 1), p(0, 0);
    const double pi = acos(-1);
    double diameter, radius;
    while(scanf("%lf %lf %lf", &diameter, &p.x, &p.y) == 3) {
        if(fabs(diameter) < eps)
            break;
        vector<Interval> interval;
        radius = diameter/2;
        for(int i = -20; i < 20; i++) {
            for(int j = -20; j < 20; j++) {
                getTangentIntersection(Pt(i, j), radius, p, pa, pb);
                double t1, t2;
                t1 = atan2(pa.y - p.y, pa.x - p.x);
                t2 = atan2(pb.y - p.y, pb.x - p.x);
                if(t1 > t2)	swap(t1, t2);
                if(fabs(t1 - t2)*180/pi < 0.01f)
                    continue;
                interval.push_back(Interval(pow(pa.x-p.x, 2)+pow(pb.y-p.y, 2), t1, t2, Pt(i, j)));
            }
        }
        sort(interval.begin(), interval.end());
        int ret = 0;
        for(int i = 0; i < interval.size(); i++) {
            double t1 = interval[i].l, t2 = interval[i].r;
            if(t2 - t1 < pi) {
                int f = 1;
                for(int j = 0; j < i; j++) {
                    double l = max(t1, interval[j].l), r = min(t2, interval[j].r);
                    if(l <= r + 0.01f * pi/180)
                        f = 0, j = i;
                }
                ret += f;
            } else {				
                double t3, t4;
                t3 = t2, t4 = pi;
                t2 = t1, t1 = -pi;
                int f = 1;
                for(int j = 0; j < i; j++) {
                    double l = max(t1, interval[j].l), r = min(t2, interval[j].r);
                    if(l <= r + 0.01f * pi/180)
                        f = 0, j = i;
                }
                if(!f)
                    continue;
                t1 = t3, t2 = t4;
                for(int j = 0; j < i; j++) {
                    double l = max(t1, interval[j].l), r = min(t2, interval[j].r);
                    if(l <= r + 0.01f * pi/180)
                        f = 0, j = i;
                }
                if(!f)
                    continue;
                ret += f;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
0.10 0.46 0.38
*/
Read More +
學校課程/大學專題

[筆記] 虛擬化技術

前提概要

本課程為暑期開課，產學合作的課程。暑期上課各種虐待，反人類行為。

Day 1 虛擬機技術簡介

虛擬化不外乎就是在同一個硬體執行環境下，同時模擬出多個的執行環境，當然不外乎模擬的行為都是間接對機器硬體執行，因此許多指令需要被轉譯，或者是多好幾個步驟來做轉換，因此效率上一定會慢許多。

虛擬化的好處在於，根據硬體的汰換率在維護的費用，每隔固定一段時間就必須增加硬體來服務新的需求，如此一來必須要有更大的空間和電費來部屬伺服器。而且每一台伺服器的功率沒有一直維持高效佔有 (即使 CPU 使用率不高，用電量也不會下降多少，貌似 10% 不到，可以說是少得可憐)。倒不如來整合硬體，根據需求進行分配，同時可以讓需要的空間縮小、電費下降，做到整合到同一台機器上運行，就需要虛擬化的技術。

虛擬化技術分很多層面，最常見的就是在 Host OS 上開始虛擬化的軟體，如 VMware workstation, xen 之類的，在上面可以掛載很多不同的作業系統 Guest OS 執行。在全虛擬化的情況 (如上述)，與一般使用個人電腦沒有什麼差別，所以非常容易入手。半虛擬化效率上又比全虛擬化來得高，在硬體需求上部分不使透過軟體進行，可以在高效率的情況下接軌。

在虛擬化的另一個最常見的就是 JVM，這是在 Application 面向的虛擬化，Java visual machine，提供跨平台等服務，這麼看起來虛擬化無所不在。

虛擬化有幾個困難之處，從經濟面向來看，一開始的轉移到虛擬階段和虛擬化的授權費用太高，畢竟不是所有虛擬化的技術都是 open source。從技術層面來看，虛擬化必須針對硬體做銜接，因此有時候必須靠有限的資源進行組合，才能完成虛擬化的單一功能，因此在初步階段，還必須看 Intel 等硬體架構，是否有考慮虛擬化的設計。在現今，已經有根據虛擬化進行設計，虛擬化也更為普及。

在周邊設備上，虛擬化的架構設計也相當重要，因此部份廠商也搭配他們的驅動程式 driver 進行修改和開源，來方便虛擬化的製作。

但也不是所有情況都適合虛擬化

  • 大量計算程序
  • 本身的 CPU 就一直維持滿載
  • 大量 I/O 的程序
  • 原本的執行環境沒有辦法虛擬化 (虛擬化廠商沒有針對其設備)

虛擬化還必須搭載四個主要的功能：

  • 多工
  • 狀態儲存
  • 狀態復原
  • 狀態遷徙 (無延遲服務)

虛擬化技術仍有安全疑慮，如何確保資訊安全和風險保證？

平常 VMware workstation 開啟就佔了相當記憶體資源 Orz

Day 2 軟體測試與 VM 測試

用 code coverage 來決定測試好壞，是否能逆向找到 code coverage 的測試情況。

這一天的內容已經在做專題的時候，由指導教授講了好幾次，概念上差不多能理解一大半。

重點為軟體工程的運行面向

  • debug
  • test-driven develop
  • continuous integration

正常大學不會教這些軟工概念，因此在大學畢業進入職場，挺多公司還是會給一段時間來訓練這些運行模式。來教導開發方式和其價值所在，催促人做事必須先教導其價值。

debug 技術而言，從海森堡 BUG、薛丁格 BUG … 等，都是相當有意思的。《BUG 的類型》，知道 BUG 也不見得能修好，這就是現在的情況，而有些 BUG 只會在高階 (過度) 使用者身上才會見到，軟體公司甚至不會想去修 (看看邪惡的微軟便是如此)。從 printf() 開始抓 BUG 的初學技巧，演化到加入中斷點來程序慢慢清除，用 assert() 來防止不符合規格的輸入，用 #ifdef DEBUG 使用 b2g system program 來查閱狀況，雖然不太善用這些技巧，但是 assert() 和 #ifdef DEBUG 偶爾在無法一次掛載在腦部的時候就會採用。

很慶幸，在大學畢業前還有用過這些技巧來 DEBUG，雖然只是在單純的 ACM 解題上使用。

test-driven develop (測試驅動)，這在敏捷開發這套軟工方法中談到。比起程式代碼，測試資料更令人可貴，這也是為什麼挺多大學的開發團隊會藉由參加大型比賽測試資料，來拿不容易收集到的測試資料，單純只是為了測試資料而參加比賽，當然最後主辦單位最後改階段式比賽來發送資料，以免選手罷賽拿資料。

continuout integration (連續整合)，從一部分一部分的代碼中，階段式完成並且測試，確保每一步都是對的，相關的工具很多，來知道每次整合遇到了什麼問題、現在改善什麼 BUG，歷史情況是如何 … 等。

詳見敏捷開發

Day 3 工業電腦虛擬化技術簡介

這一天內容與 Day 1 類似，不過更詳細說明這門課程如何運行，不過看似就會活不下去， 3 人一組在 2 個星期後期中考、4 個星期後期末考，必須要完成的 Final project。

升大四修碩班課程果然還有點落差，問題在於資源上沒有實驗室的協助，要怎麼將實習課所需要的虛擬機器的伺服器弄出來？助教講得很輕鬆，真正有資源來完成要求的人卻很少呢。

  1. Github 使用
  2. RedMine 協助

第一點有在用，但是不專精，對我來說目前只當作是垃圾倉庫使用中。還真是慘不忍睹。

Day 4 軟體容錯 與 NCU - FTVM

  1. 虛擬容錯的處理器環境要相同，是否是相當嚴苛的條件，而這個容錯只在於軟體掛點的時候，轉移狀態給另外一台虛擬機進行程序接手，在存取空間是共用的，因是為存取空間的備份不容易完成嗎？
  2. 由於容錯功能不能與許多功能兼容，是否會造成無法長時間處於容錯狀態？
Read More +
手札日記

混了大學三年生活

文章提示：戳擊圖示展開 fancybox，隨後可用方向鍵更換圖片。

《斬赤紅之瞳》- 抖 S 女王

「我不明白！作為弱者的心情。」

《最弱副會長球磨川》第 88 箱

『即使不帥氣、即使不強大、即使不正確、即使不美麗、即使不可愛、即使不乾淨，我也想贏過那些帥氣、強大、正確、美麗、可愛、乾淨的傢伙』
－又沒贏呢。

大學三年就這麼過去，資工系在大四之後就沒有必修課，而系選修學分也相當足夠，當然如果跟其他學校比起來，專業領域的學分限制沒有這麼多，也就是說可以採用其他的一般課程通過畢業門檻。

撇開這不談，畢業門檻見鬼去吧！

女王雖然不錯，但是球球精神仍在心中。『我啊，一直是弱者的同伴。』沒有辦法贏，但是也不能輸。但是，最近也開始疲累了，拖動著愚蠢的自己－一台簡單化的學習機器，毫無思考與突變的物種，在那段日子下，不斷地被迫前進，在茫茫的道路下行走，走過得足跡也逐漸淡去。山因為累積起的土堆而高起，然而人卻不斷地失憶，這樣要如何驗證自己的進步呢。

每個人都是迷惘的，但不斷在此周旋也不是辦法。

三年下來，說明白就是太混，成績好不好似乎也不是太重要。可謂窮得只剩下過去。

現在的我正過著每天獨自一個人的生活，偶爾才會見見真人的朋友，而對方認為是不是朋友也無法得知，有人會說這樣疑神疑鬼，會這樣也是理所當然的。

最近仍舊寫寫 UVa 混混日子，也達到 2200+ 的題目數量，隨後也在 Github 在弄中文翻譯 link，慢慢整理吧，有興趣者也可以參與翻譯部分。

對 repo fork 出來後，發送 pull request 即可，雖然明白也不會有多少人去注目。「逃避英文是不好的」這句話已經聽膩了，什麼正向面對，人類會悲觀對事是經過數年的演化得來，悲觀才能對事情進行縝密的思考 (採取自《羅輯思維》)，我才沒有向你們這麼樂觀去看待學習自己一直弄不來的項目。

有段時間沒有上 QQ，居然還有人向我投來關心的留言，都不知道上次對話是哪個時候了，自己也曾會向數年不見的人傳封簡訊，但隨著年齡增加就會開始膽怯去做這件事情。浪漫天真呢。

《漫畫家與助手們》

花點時間打了這一篇，畢竟相對於之前打文章的頻率，這一半年來說的確下降了許多，準確來講是沒有作什麼偉大的事情，或者是有所成長的體悟，反倒是黑歷史不斷地增加。害怕第一字都不想要紀錄。

這個暑假有幾件事情得做

  • 先把不小心答應的暑期課程給結束掉－跟碩班上課什麼的，雖然已經升大四不是藉口，但那是吾等沒辦法突破的障礙，課程作為補品實在是太補了，總覺得會學不來。
  • 活下去的目標－談到要好朋友到底要怎麼共事，對於別人，吾等實在太過於沉重。
  • 推甄研究所的話，必須準備自傳等相關項目。反之，就準備吊高高。
  • 做點成就項目－看到目前做了什麼項目，還真是慘不忍睹
  • 其他－天真浪漫的事情就不奢求，自由隨興的糟糕習慣，想做什麼就去做什麼，連墮落也是。

最近在 facebook 常流行大學內的相關情緒討論粉絲頁，說說咱們的 “靠北中央” (諸多如 “魯蛇/表特/靠北/告白/道歉 …” + “台大/清華/交大/成大/中央 …”)，熱門的話題就是「到底要不要繳交系學會費 $\$ 5000$ 」這筆款項說少不少，說多也大不至於，四年下來差不多就繳交這麼一次，相當於學費的五分之一。

尤其在該版面上，資工系的靠北文異常地多，雖然皆採用匿名制 (撇開自曝其名的人不談)，針對咱們資工的文章還真是不少，更增添給系上不少的黑歷史，相關文章集中在編號 #1500 之前。

每次看到戰文真是又氣又笑，當然收錢那方的擁護者不少，但是有時候不是年年政策都一樣，之前的擁護者可能不知道現在到底是怎麼黑箱作業。

在轉學之前，在中興的確有繳交一樣是 $\$ 5000 $ 的款項，但是在許多活動沒有參與下，系學會的確有將款項退給我，而系服雖然設計不好，但仍然是有拿到，中興那邊人少好辦事，因此也不至於偷偷地將款項給吃了。

轉學之後，沒有繳交系費的款項，當然也盡可能地不參與系上活動，畢竟那是要花錢的，而系上活動免費的餐飲 buffet 到底能不能去吃，讓我也相當困惑。使用者付費，仔細想想沒有白吃的午餐，這項舉動還是少做為之。除了系費之外，系隊費用、轉聯會費用 … 等，通常費用會有關服裝或者是活動參與，在很多的活動下得知會有社團衣服，雖然繳交那筆錢之後，沒有去拿衣服是我的不對，但沒有像中興那種有人會來發送衣服的情況，就算遇到負責人在不同場合也不會談到這件事情，因此服裝就這麼消散，小錢是沒有什麼，但是觀感就不怎麼好，我這種宅宅不是那麼主動會想要去搭訕混熟。

平常沒有什麼機會談話，藉由發送這些活動相關項目，也可以藉此打好關係和認識吧！也許是我的幻象，這何等的幼稚思維。之後就一項活動都沒有去參與，異類就在此，總不能假裝與你們相同，這對你們來說是不尊重的。

尤其是在資工系諸如此類的人還不少，因此在很多人正常的宅宅學弟們就會明白，這筆款項是交給陽光般參與活動的人花費，而他們只是繳錢的金主 (除非是 M，否則誰願意繳交)。吾等活在黑暗中展現自己的思維與磨練自身，參與活動的記憶模式，早已被不斷地學習給淡化了，不是不願意參與活動，而是不懂得如何參與。

這場戰爭還在繼續，肯定是不會停止的。

不過裡面最令人又哭又笑的是其中一段，學弟反攻學長的制度，中間一段用了程序上的設計來比喻他們的做事行為，但是學長 (跟我同屆) 則以「學弟好好讀書行嗎 ? 這個不是這樣比喻的 …」類似的口吻回覆，結果被別系同學糾正學長對學弟指導的程序概念。在旁人眼中，到底誰才是學資工專業呢？因此也有人表示「資工系怎麼如此地殘缺」，看到貼人當下還真不知道要保持什麼心態，護衛自己系的好頓時不是主要意識，跟室友談到這一段時「就說說只是資工系少部分人就好啦！」但是心想，也許是大部分人都會錯，在渾渾噩噩的學習情境下，能真正明白自己在做什麼的人的確很少，連我也不例外。

Read More +
解題區/解題區 - UVa

UVa 12240 - Cocircular Points

Problem

You probably know what a set of collinear points is: a set of points such that there exists a straight line that passes through all of them. A set of cocircular points is defined in the same fashion, but instead of a straight line, we ask that there is a circle such that every point of the set lies over its perimeter.

The International Collinear Points Centre (ICPC) has assigned you the following task: given a set of points, calculate the size of the larger subset of cocircular points.

Input

Each test case is given using several lines. The first line contains an integer N representing the number of points in the set (1$\le$N$\le$100). Each of the next N lines contains two integers X and Y representing the coordinates of a point of the set (- 104$\le$X, Y$\le$104). Within each test case, no two points have the same location.

The last test case is followed by a line containing one zero.

Output

For each test case output a single line with a single integer representing the number of points in one of the largest subsets of the input that are cocircular.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
7 
-10 0 
0 -10 
10 0 
0 10 
-20 10 
-10 20 
-2 4 
4 
-10000 10000 
10000 10000 
10000 -10000 
-10000 -9999 
3 
-1 0 
0 0 
1 0 
0

Sample Output

1
2
3
5 
3 
2

Solution

題目描述：

給平面上 n 個點，最多有多少個點共圓？

題目解法：

窮舉三點拉外心，隨後找共圓的點，最慘會到 O(n^4)。

完全沒有剪枝，也就是說可以刻意將點保留標記，防止窮舉到相同組合，又或者是先按照 x 軸排序，直接在區間內搜索可能的共圓點之類的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
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 dist2(Pt a, Pt b) {
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(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);
}
Pt circle(Pt a, Pt b, Pt c) {
    Pt mab = (a + b)/2;
    Pt mbc = (b + c)/2;
    Pt lab = b - a, lbc = c - b;
    swap(lab.x, lab.y);
    swap(lbc.x, lbc.y);
    lab.x = -lab.x;
    lbc.x = -lbc.x;
    return getIntersection(mab, lab, mbc, lbc);
}
int main() {
    int n;
    Pt D[128];
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++) {
            scanf("%lf %lf", &D[i].x, &D[i].y);
        }
        int ret = min(2, n);
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                for(int k = j + 1; k < n; k++) {
                    if(fabs(cross(D[i], D[j], D[k])) < eps)
                        continue;
                    Pt o = circle(D[i], D[j], D[k]);
//					printf("%lf %lf %lf %lf %lf %lf\n", D[i].x, D[i].y, D[j].x, D[j].y, D[k].x, D[k].y);
//					printf("circle %lf %lf\n", o.x, o.y);
                    double d = dist2(o, D[i]);
                    int cnt = 0;
                    for(int p = 0; p < n; p++) {
                        if(fabs(d - dist2(D[p], o)) < eps)
                            cnt++;
                    }
                    ret = max(ret, cnt);
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12206 - Stammering Aliens

Problem

Dr. Ellie Arroway has established contact with an extraterrestrial civilization. However, all efforts to decode their messages have failed so far because, as luck would have it, they have stumbled upon a race of stuttering aliens! Her team has found out that, in every long enough message, the most important words appear repeated a certain number of times as a sequence of consecutive characters, even in the middle of other words. Furthermore, sometimes they use contractions in an obscure manner. For example, if they need to say bab twice, they might just send the message babab, which has been abbreviated because the second b of the first word can be reused as the first b of the second one.

Thus, the message contains possibly overlapping repetitions of the same words over and over again. As a result, Ellie turns to you, S.R. Hadden, for help in identifying the gist of the message.

Given an integer m, and a string s, representing the message, your task is to find the longest substring of s that appears at least m times. For example, in the message baaaababababbababbab, the length-5 word babab is contained 3 times, namely at positions 5, 7 and 12 (where indices start at zero). No substring appearing 3 or more times is longer (see the first example from the sample input). On the other hand, no substring appears 11 times or more (see example 2).

In case there are several solutions, the substring with the rightmost occurrence is preferred (see example 3).

Input

The input contains several test cases. Each test case consists of a line with an integer m (m$\ge$1), the minimum number of repetitions, followed by a line containing a string s of length between m and 40 000, inclusive. All characters in s are lowercase characters from a'' toz’’. The last test case is denoted by m = 0 and must not be processed.

Output

Print one line of output for each test case. If there is no solution, output none; otherwise, print two integers in a line, separated by a space. The first integer denotes the maximum length of a substring appearing at least m times; the second integer gives the rightmost possible starting position of such a substring.

Sample Input

1
2
3
4
5
6
7
3
baaaababababbababbab
11
baaaababababbababbab
3
cccccc
0

Sample Output

1
2
3
5 12
none
4 2

Solution

題目描述：

對於一個字串，找到一段最長子字串出現至少 m 次，若存有多個輸出最右邊位置的子字串。

題目解法：

建造後綴數組，得到高度數組後，二分搜索長度，然後掃描高度數組找尋是否有連續大於等於 m 次的區間。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct SuffixArray {
    int sa[40005], h[40005], n;
    int w[40005], ta[40005], tb[40005];
    char str[40005];
    void sort(int *x, int *y, int m) {
        static int i;
        for(i = 0; i < m; i++)
            w[i] = 0;
        for(i = 0; i < n; i++)
            w[x[y[i]]]++;
        for(i = 1; i < m; i++)
            w[i] += w[i-1];
        for(i = n-1; i >= 0; i--)
            sa[--w[x[y[i]]]] = y[i];
    }
    bool cmp(int *r, int a, int b, int l) {
        if(r[a] == r[b]) {
            if(a+l >= n || b+l >= n)
                return false;
            return r[a+l] == r[b+l];
        }
        return false;
    }
    void build_h() {
        int i, j, k;
        for(i = 0; i < n; i++)  ta[sa[i]] = i;
        for(i = 0; i < n; i++) {
            if(ta[i] == 0) {
                h[ta[i]] = 0;
                continue;
            }
            if(i == 0 || h[ta[i-1]] <= 1)
                k = 0;
            else
                k = h[ta[i-1]]-1;
            while(str[sa[ta[i]-1]+k] == str[sa[ta[i]]+k])
                k++;
            h[ta[i]] = k;
        }
    }
    void build() {// x: rank, y: second key
        int i, k, m = 128, p;
        int *x = ta, *y = tb, *z;
        n = strlen(str);
        x[n] = 0;
        for(i = 0; i < n; i++)
            x[i] = str[i], y[i] = i;
        sort(x, y, m);
        for(k = 1, p = 1; p < n; k *= 2, m = p) {
            for(p = 0, i = n-k; i < n; i++)
                y[p++] = i;
            for(i = 0; i < n; i++) {
                if(sa[i] >= k) {
                    y[p++] = sa[i]-k;
                }
            }
            sort(x, y, m);
            z = x, x = y, y = z;
            for(i = 1, p = 1, x[sa[0]] = 0; i < n; i++)
                x[sa[i]] = cmp(y, sa[i-1], sa[i], k) ? p-1 : p++;
        }
    }
};
SuffixArray in;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int m;
    while(scanf("%d", &m) == 1 && m) {
    	scanf("%s", in.str);
        in.build();
        in.build_h();
        if(m == 1) {
        	printf("%d %d\n", in.n, 0);
        	continue;
    	}
//        for(int i = 0; i < in.n; i++)
//        	printf("%s %d\n", in.str + in.sa[i], in.h[i]);
        int l = 1, r = in.n, mid, ret = -1, retpos;
        while(l <= r) {
        	mid = (l + r)/2;
        	int cnt = 1, mxtime = 0, mxpos = 0;
        	for(int i = 0; i <= in.n; i++) {
        		if(i != in.n && in.h[i] >= mid)
        			cnt++;
        		else {
        			if(mxtime < cnt)
        				mxtime = cnt;
        			if(cnt >= m) {
        				int j = i;
        				do {
        					j--;
        					mxpos = max(mxpos, in.sa[j]);
        				} while(in.h[j] >= mid && j >= 0);
        			}
        			cnt = 1;
        		}
        	}
        	if(mxtime >= m)
        		l = mid + 1, ret = mid, retpos = mxpos;
        	else
        		r = mid - 1;
        }
        if(ret == -1)
        	puts("none");
        else
        	printf("%d %d\n", ret, retpos);
    }
    return 0;
}
/*
1
aaaaa
2
ufzyetzjulljnkbaohjsqpiucxjo
*/
Read More +
解題區/解題區 - UVa

UVa 12194 - Isosceles Triangles

Problem

A given triangle can be either equilateral (three sides of the same length), scalene (three sides of different lengths), or isosceles (two sides of the same length and a third side of a different length). It is a known fact that points with all integer coordinates cannot be the vertices of an equilateral triangle.

You are given a set of different points with integer coordinates on the XY plane, such that no three points in the set lay on the same line. Your job is to calculate how many of the possible choices of three points are the vertices of an isosceles triangle.

Input

There are several test cases. Each test case is given in several lines. The first line of each test case contains an integer N indicating the number of points in the set (3$\le$N$\le$1000). Each of the next N lines describes a different point of the set using two integers X and Y separated by a single space (1$\le$X, Y$\le$106); these values represent the coordinates of the point on the XY plane. You may assume that within each test case no two points have the same location and no three points are collinear.

The last test case is followed by a line containing a single zero.

Output

For each test case output a single line with a single integer indicating the number of subsets of three points that are the vertices of an isosceles triangle.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5 
1 2 
2 1 
2 2 
1 1 
1000 1000000 
6 
1000 1000 
996 1003 
996 997 
1003 996 
1003 1004 
992 1000 
0

Sample Output

1
2
4
10

Solution

題目描述：

給平面 N 個點，任挑三個點有多少以某個節點為頂點的等腰三角形。

題目解法：

直接對單一頂點找到對於其他頂點的的所有距離，排序後找重複的長度進行組合計算，將複雜度 O(n^3) 降到 O(n^2 log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
    int N;
    long long X[1024], Y[1024];
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 0; i < N; i++)
            scanf("%lld %lld", &X[i], &Y[i]); 
        long long d[1024];
        long long ret = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++)
                d[j] = (X[i] - X[j]) * (X[i] - X[j]) +
                        (Y[i] - Y[j]) * (Y[i] - Y[j]);
            sort(d, d+N);
            long long cnt = 1;
            d[N] = -1;
            for(int j = 1; j <= N; j++) {
                if(d[j] != d[j-1]) {
                    ret += cnt * (cnt-1) /2;
                    cnt = 1;
                } else {
                    cnt++;
                }
            } 
        }
        printf("%lld\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12191 - File Recover

Problem

Your school has a computer that is used as a web server for hosting its institutional web site, personal pages of the staff, sites for research groups, subjects, and many others.

Recently, the hard disk table was corrupted, so the organization of all the files was lost. Sadly enough, there are no backups of that information. The only hope is to look through the entire disk data and try to find out which parts correspond to each file. Fortunately, the disk was using a file system that kept each individual file contiguous, so only contiguous pieces of data need to be inspected.

The disk data is a sequence of bytes. Each byte in this particular disk can store an English alphabet letter (distinguishing lowercase and uppercase), a decimal digit, a point or a comma, making a total of 64 different characters.

While you were thinking about how to solve the problem, you suddenly remembered that the file system also maintained multiple copies of each file, so only the pieces of contiguous bytes that are repeated had a chance of being a file. Moreover, for each repetition of the same contiguous bytes, only one copy needs to be checked. For instance, if the data is ababcabb', the contiguous subsequencesa’, b' andab’ are repeated, but nothing containing c', norba’ or `bb’ is. Therefore, we have 3 pieces of contiguous bytes that need checking in this case.

You decide to write a program that computes exactly how many sequences need checking, that is, the number of different sequences of contiguous bytes that appear at least twice in the data.

Input

There are several test cases. The input of each test case is given in exactly one line, containing a non-empty string of at most 105 characters that represents the disk data. Each character in the string is either a lowercase letter, an uppercase letter, a digit, a point or a comma.

The last test case is followed by a line containing a single asterisk.

Output

For each test case output a single line with an integer, representing the number of different contiguous subsequences that appear at least twice in the input string.

Sample Input

1
2
3
4
5
6
ababcabb 
mississippi 
aaaaaaaaaaaaaaaaaaaaaaaaaa 
012345678,abcdefg.STUVWXYZ 
say.twice,say.twice 
*

Sample Output

1
2
3
4
5
3 
9 
25 
0 
45

Solution

題目描述：

有多少不同的子字串符合出現至少兩次的條件。

題目解法：

建造後綴數組，得到高度數組後，根據遞增的情況進行計算不同字符串的個數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct SuffixArray {
    int sa[100005], h[100005], n;
    int w[100005], ta[100005], tb[100005];
    char str[100005];
    void sort(int *x, int *y, int m) {
        static int i;
        for(i = 0; i < m; i++)
            w[i] = 0;
        for(i = 0; i < n; i++)
            w[x[y[i]]]++;
        for(i = 1; i < m; i++)
            w[i] += w[i-1];
        for(i = n-1; i >= 0; i--)
            sa[--w[x[y[i]]]] = y[i];
    }
    bool cmp(int *r, int a, int b, int l) {
        if(r[a] == r[b]) {
            if(a+l >= n || b+l >= n)
                return false;
            return r[a+l] == r[b+l];
        }
        return false;
    }
    void build_h() {
        int i, j, k;
        for(i = 0; i < n; i++)  ta[sa[i]] = i;
        for(i = 0; i < n; i++) {
            if(ta[i] == 0) {
                h[ta[i]] = 0;
                continue;
            }
            if(i == 0 || h[ta[i-1]] <= 1)
                k = 0;
            else
                k = h[ta[i-1]]-1;
            while(str[sa[ta[i]-1]+k] == str[sa[ta[i]]+k])
                k++;
            h[ta[i]] = k;
        }
    }
    void build() {// x: rank, y: second key
        int i, k, m = 128, p;
        int *x = ta, *y = tb, *z;
        n = strlen(str);
        x[n] = 0;
        for(i = 0; i < n; i++)
            x[i] = str[i], y[i] = i;
        sort(x, y, m);
        for(k = 1, p = 1; p < n; k *= 2, m = p) {
            for(p = 0, i = n-k; i < n; i++)
                y[p++] = i;
            for(i = 0; i < n; i++) {
                if(sa[i] >= k) {
                    y[p++] = sa[i]-k;
                }
            }
            sort(x, y, m);
            z = x, x = y, y = z;
            for(i = 1, p = 1, x[sa[0]] = 0; i < n; i++)
                x[sa[i]] = cmp(y, sa[i-1], sa[i], k) ? p-1 : p++;
        }
    }
};
SuffixArray in;
int main() {
    while(scanf("%s", in.str)) {
    	if(!strcmp("*", in.str))
    		break;
        in.build();
        in.build_h();
//		for(int i = 0; i < in.n; i++)
//			printf("%s %d\n", in.str + in.sa[i], in.h[i]);
        long long ret = 0, base = 0;
        in.h[in.n] = -1;
        for(int i = 1; i <= in.n; i++) {
            if(in.h[i] < in.h[i-1])
                ret += in.h[i-1] - base, base = in.h[i];
        }
        printf("%lld\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12176 - Bring Your Own Horse

Problem

One of the essential activities of a knight is to compete in tournaments. Frequently, groups of knights gather around the country to compare their skills. On such a typical contest day, everyone has five hours to do ten disciplines, such as sword fighting, bow and arrow, and various forms of horseback riding. Needless to say, you have to bring your own horse.

This is not as easy as it seems. It often takes a knight several days to go from the castle where he lives to the place where a tournament is held. But horses sometimes are very, very stubborn. After having covered a certain distance on a single day, they sometimes simply stop and refuse to go any further. Luckily, they start anew on the next day. To make sure that the horse does not refuse service before the scheduled day trip is completed, a knight wants to choose an itinerary on which the longest day trip is as short as possible. Hence, a trip that takes many days with short distances is preferable over a shorter route that has the risk of a refusing horse.

Write a program which answers queries from knights spread all over the country about the best way to go from their castles to a tournament site. Given a description of the relevant places (i.e. castles, locations of tournaments, and hostels for overnight stays), the program should tell them the largest distance they have to cover on a single day so that this distance is minimal among all possible itineraries.

The places are designated by consecutive integers from 1 to $N$, while a road is represented by three integers, namely its place of origin, its destination, and its length. Every road can be used in both directions, and there is at least one route (i.e. a sequence of roads) between any two places. The knights stick to the given roads while travelling and spend their nights only at one of the $N$ places.

Input

The first line contains the total number of test cases that follow.

Each test case begins with a line that first holds the number $N$ of places ( $1 \le N \le 3000$ ) followed by the number $R$ of roads ( $1 \le R \le 100000$ ). Then there are $R$ lines with three integers each ($a$ , $b$ , and $l$ ), each of which defines a road connecting the places $a$ and $b$ ( $1 \le a, b \le N$ ) with length $l$ ( $1 \le l \le 1000000$ ).

Thereafter, each test case continues with the number $Q$ of queries on a line by itself ( $1 \le Q \le 1000$ ). Each of the next $Q$ lines holds two integers $k$ and $t$ , indicating a query by a knight who lives at place $k$ and needs to go to a tournament at place $t$ ( $1 \le k, t \le N$ , $k \neq t$ ).

Output

For each test case output a line containing the word ``Case’’, a single space, and its serial number (starting with $1$ for the first test case). Then, print one line for each query in this test case, containing the smallest maximal day trip distance as described above. Print a blank line after each test case.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
4 4
1 2 100
2 3 100
3 4 100
4 1 200
1
1 4
6 9
2 4 5
5 1 7
3 6 6
3 1 4
2 3 2
1 2 1
6 5 42
4 5 3
4 6 5
4
1 3
3 4
5 4
6 1
``` 
## Sample Output ##

Case 1
100

Case 2
2
5
3
5
```

Solution

題目描述：

騎士每天活動只會從該點移動到盡可能短的路徑到下一個點，求從起點到終點之間的最小的最長路為何。

題目解法：

由於詢問兩個點之間的路徑上的最小值最大邊，不外乎地可以先做一次最小成本樹，根據定義，拆分成 s - t 集合，最小成本樹的邊一定是 s - t 之間的最小邊。

接著詢問在樹上進行即可，因此每次詢問最慘會到 O(n)。

那我們稍微加速，採用 dp 的方式，將樹變成有根樹，記錄每一個節點向上攀升 1 個節點, 2 個節點, 4 個節點 …, 2^n 個節點的路徑上的最大最小值。

因此狀態會是 O(n log n), 建表也能在 O(n log n) 完成，接著調整兩個詢問節點的高度，先想辦法調整到兩個節點到水平高度，藉由之前的計算，高度不超過 n，因此理應可以在 O(log n) 時間內完成到調整到同一水平高度。

在同一水平下，還是需要知道 LCA 的所在高度，否則也可以水平線不斷地一步一步往上提，雖然最慘也許是 O(n) 但是經由之前的調整已經很加速很多。

本來應該套用 LCA Tarjan 的作法來加速，但是還沒有做到這樣的地步速度就很快。如果詢問次數再多一點就必須做到這一步。

有點懶惰 Orz。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
struct E {
    int x, y, v;
    E(int a=0, int b=0, int c=0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return  v < a.v;
    }
};
E D[100005];
vector<E> tree[3005];
int p[3005], rank[3005];
int findp(int x) {
    return p[x] == x ? x : (p[x] = findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int kruscal(int n, int m) {
    int sum = 0;
    
    sort(D, D+m);
    for(int i = 0; i <= n; i++) {
        p[i] = i, rank[i] = 1;
        tree[i].clear();
    }
    
    for(int i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y)) {
        	sum += D[i].v;
        	tree[D[i].x].push_back(E(D[i].x, D[i].y, D[i].v));
        	tree[D[i].y].push_back(E(D[i].y, D[i].x, D[i].v));
//        	printf("mmm %d %d %d\n", D[i].x, D[i].y, D[i].v);
        }
    }
    return sum;
}
int dp[4096][20], dpw[4096][20];
int treeLevel[4096], treePath[4096];
void dfs(int u, int p, int level) {
    treeLevel[u] = level, treePath[level] = u;	
    for(int i = 1; (1<<i) < level; i++) {
        dp[u][i] = max(dp[u][i-1], dp[dpw[u][i-1]][i-1]);
        dpw[u][i] = treePath[level-(1<<i)];
    }
    for(int i = 0; i < tree[u].size(); i++) {
        int v = tree[u][i].y;
        if(v == p)	continue;		
        dp[v][0] = tree[u][i].v;
        dpw[v][0] = u;
        dfs(v, u, level + 1);
    }
}
int query(int x, int y) {
    int hx = treeLevel[x], hy = treeLevel[y];
    int ret = 0;
    while(x != y && hx != hy) {
        for(int i = 15; i >= 0; i--) {
            if(abs(hx-hy) >= (1<<i)) {
                if(hx > hy) {
                    ret = max(ret, dp[x][i]);
                    x = dpw[x][i];
                    hx -= (1<<i);
                } else {
                    ret = max(ret, dp[y][i]);
                    y = dpw[y][i];
                    hy -= (1<<i); 
                }
            }
        }
    }
    while(x != y) {
        ret = max(ret, dp[x][0]);
        x = dpw[x][0];
        hx -= (1<<0);
        ret = max(ret, dp[y][0]);
        y = dpw[y][0];
        hy -= (1<<0); 
    }
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        int n, m, q, x, y;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < m; i++) {
        	scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].v);        	
        }
        
        int mstcost = kruscal(n, m);
        memset(dp, 0, sizeof(dp));
        memset(dpw, 0, sizeof(dpw));
        dfs(1, -1, 1);
        
//		for(int i = 1; i <= n; i++, puts("")) {
//			printf("[%2d] :", i);
//			for(int j = 0; (1<<j) <= n; j++)
//				printf("%d %d, ", dp[i][j], dpw[i][j]);
//		}
        scanf("%d", &q);
        printf("Case %d\n", ++cases);
        while(q--) {
            scanf("%d %d", &x, &y);
            printf("%d\n", query(x, y));
        }
        puts("");
    }
    return 0;
}
/*
5
10 45
1 2 15
1 3 11
1 4 48
1 5 24
1 6 45
1 7 18
1 8 12
1 9 40
1 10 11
2 3 4
2 4 9
2 5 44
2 6 23
2 7 39
2 8 48
2 9 48
2 10 22
3 4 42
3 5 37
3 6 10
3 7 18
3 8 29
3 9 8
3 10 47
4 5 7
4 6 17
4 7 25
4 8 23
4 9 32
4 10 27
5 6 26
5 7 21
5 8 38
5 9 40
5 10 39
6 7 35
6 8 11
6 9 39
6 10 1
7 8 15
7 9 10
7 10 47
8 9 28
8 10 11
9 10 1
30
1 6
5
10 45
1 2 9
1 3 12
1 4 21
1 5 4
1 6 32
1 7 20
1 8 14
1 9 28
1 10 16
2 3 12
2 4 23
2 5 27
2 6 34
2 7 43
2 8 2
2 9 33
2 10 35
3 4 41
3 5 26
3 6 16
3 7 39
3 8 2
3 9 49
3 10 44
4 5 24
4 6 2
4 7 17
4 8 26
4 9 20
4 10 2
5 6 23
5 7 5
5 8 41
5 9 12
5 10 15
6 7 48
6 8 45
6 9 13
6 10 28
7 8 25
7 9 12
7 10 37
8 9 4
8 10 5
9 10 41
30
5 4
1 7
8 4
*/
Read More +
解題區/解題區 - UVa

UVa 12045 - Fun with Strings

Problem

Zibon just started his courses in Computer science. After having some lectures on programming courses he fell in love with strings. He started to play with strings and experiments on them. One day he started a string of arbitrary (of course positive) length consisting of only {a, b}. He considered it as 1st string and generated subsequent strings from it by replacing all the b’s with ab and all the a’s with b. For example, if he ith string is abab, (i+1)th string will be b(ab)b(ab) = babbab. He found that the Nth string has the length X and Mth string has the length Y. He wondered what will be length of the Kth string. Can you help him?

Input

The first line of the input file contains an integer T (T ≤ 1000) which denotes the total number of test cases. The description of each test case is given below:

Five integers N, X, M, Y and K where (0 < N, M, X, Y, K < 109 and N ≠ M).

Output

For each test case produce one line of output giving either the number which is desired length (modulo 1000000007) or the string “Impossible”. You output Impossible if the given input is not possible.

Sample Input

1
2
3
2
3 16 5 42 6
5 1 6 10 9

Sample Output

1
2
68
Impossible

Solution

題目描述：

一開始由 a, b 構成的字串，每一次操作會將 a 換成 b, 將 b 換成 ab。
在第 N 次之後長度為 X、第 M 次之後長度為 Y，求第 K 次之後長度為何？

題目解法：

看到 a 換成 b, 將 b 換成 ab，其實只考量數量關係，很明顯是一個費式數列的關係。
因此，只要假設一開始有多少個 a，有多少個 b 在一開始的字串中，利用兩條方程式求解，之後再帶入費式數列的快速運算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Matrix {
    long long v[2][2];
    Matrix(long long a = 0) {
        memset(&v, 0, sizeof(v));
        for(int i = 0; i < 2; i++)
            v[i][i] = a;
    }
};
const long long mod = 1000000007LL;
Matrix multiply(Matrix x, Matrix y) {
    Matrix z;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++) {
                z.v[i][j] += x.v[i][k] * y.v[k][j] %mod;
                z.v[i][j] %= mod;
            }
    return z;
}
Matrix pow(Matrix x, long long y) {
    Matrix v(1);
    while(y) {
        if(y&1)
            v = multiply(v, x);
        y = y>>1, x = multiply(x, x); 
    }
    return v;
}
int main() {
    int testcase;
    long long N, X, M, Y, K;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%lld %lld %lld %lld %lld", &N, &X, &M, &Y, &K);
        Matrix mm, na, nb, nc;
        mm.v[0][0] = mm.v[0][1] = mm.v[1][0] = 1;
        na = pow(mm, N);
        nb = pow(mm, M);
        nc = pow(mm, K);
        long long a1, b1, c1, a2, b2, c2;
        long long d, dx, dy;
        a1 = na.v[0][0], b1 = na.v[1][0], c1 = X;
        a2 = nb.v[0][0], b2 = nb.v[1][0], c2 = Y;
        d = a1 * b2 - a2 * b1;
        dx = X * b2 - Y * b1, dy = a1 * Y - a2 * X;
        if(d == 0 || dx%d || dy%d || dx/d < 0 || dy/d < 0)
            puts("Impossible");
        else {
            long long a = dx/d, b = dy/d;
            printf("%lld\n", (a * nc.v[0][0]%mod + b * nc.v[1][0]%mod)%mod);
        }
//		printf("%lld A + %lld B = %lld\n", na.v[0][0], na.v[1][0], X);
//		printf("%lld A + %lld B = %lld\n", nb.v[0][0], nb.v[1][0], Y);
//		printf("%lld A + %lld B = ????\n", nc.v[0][0], nc.v[1][0]);
    }
    return 0;
}
Read More +