解題區/解題區 - UVa

UVa 1592 - Database

Problem

Peter studies the theory of relational databases. Table in the relational database consists of values that are arranged in rows and columns.

There are different normal forms that database may adhere to. Normal forms are designed to minimize the redundancy of data in the database. For example, a database table for a library might have a row for each book and columns for book name, book author, and author’s email.

If the same author wrote several books, then this representation is clearly redundant. To formally define this kind of redundancy Peter has introduced his own normal form. A table is in Peter’s Normal Form (PNF) if and only if there is no pair of rows and a pair of columns such that the values in the corresponding columns are the same for both rows.

How to compete in ACM ICPC     Peter     peter@neerc.ifmo.ru
How to win ACM ICPC     Michael     michael@neerc.ifmo.ru
Notes from ACM ICPC champion     Michael     michael@neerc.ifmo.ru

The above table is clearly not in PNF, since values for 2rd and 3rd columns repeat in 2nd and 3rd rows. However, if we introduce unique author identifier and split this table into two tables – one containing book name and author id, and the other containing book id, author name, and author email, then both resulting tables will be in PNF.

$$\begin{center} \begin{tabular}{\vert l\vert l... ...\hline Notes from ACM ICPC champion & 2 \\ \hline \end{tabular} \end{center}} \begin{center} \begin{tabular}{\vert l\vert ... ...ine 2 & Michael & michael@neerc.ifmo.ru \\ \hline \end{tabular} \end{center}}$$

Given a table your task is to figure out whether it is in PNF or not.

Input

Input contains several datasets. The first line of each dataset contains two integer numbers n and m ( 1$\le$n$\le$10000, 1$\le$m$\le$10), the number of rows and columns in the table. The following n lines contain table rows. Each row has m column values separated by commas. Column values consist of ASCII characters from space (ASCII code 32) to tilde (ASCII code 126) with the exception of comma (ASCII code 44). Values are not empty and have no leading and trailing spaces. Each row has at most 80 characters (including separating commas).

Output

For each dataset, if the table is in PNF write to the output file a single word YES" (without quotes). If the table is not in PNF, then write three lines. On the first line write a single wordNO” (without quotes). On the second line write two integer row numbers r1 and r2 ( 1$\le$r1, r2$\le$n, r1$\ne$r2), on the third line write two integer column numbers c1 and c2 ( 1$\le$c1, c2$\le$m, c1$\ne$c2), so that values in columns c1 and c2 are the same in rows r1 and r2.

Sample Input

1
2
3
4
5
6
7
3 3
How to compete in ACM ICPC,Peter,peter@neerc.ifmo.ru
How to win ACM ICPC,Michael,michael@neerc.ifmo.ru
Notes from ACM ICPC champion,Michael,michael@neerc.ifmo.ru
2 3
1,Peter,peter@neerc.ifmo.ru
2,Michael,michael@neerc.ifmo.ru

Sample Output

1
2
3
4
NO
2 3
2 3
YES

Solution

題目描述：

這一題要做的是資料庫的正規化，在一個表單中，重複關係的項目都要依序剃除。
而這一條講的就是要檢查是否有某兩行中的某兩列數值相同，換句話說就是

(data(r1, c1), data(r1, c2)) === (data(r2, c1), data(r2, c2))

如果存在則輸出任何一組 r1, r2, c1, c2

題目解法：

窮舉行還是列將決定複雜度。如果窮舉行 (row) 則會達到 O(n ^ 2 m log m) 反之則是 O(m ^ 2 n log n)。

由於題目給定的 n 遠大於 m，因此窮舉列 (column) 會來得更好。為了加速字串比對速度，可以利用 hash 來完成，如果 hash 夠大，將有機會不考慮任何字串匹配 (不會發生碰撞)，這樣的速度就會非常快。

拿了不少 WA 是忘記在找到其中一組解 break; 掉。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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char data[10010][128];
int colPos[10010][16];
int hashCode[10010][16];
struct cmp {
    static int C1, C2;
    bool operator() (const pair< pair<int, int>, int>& a, 
						const pair< pair<int, int>, int>& b) const {
        if(a.first != b.first)	return a.first < b.first;
        int t;
        t = strcmp(data[a.second] + colPos[a.second][C1],
                        data[b.second] + colPos[b.second][C1]);
        if(t)	return t < 0;
        t = strcmp(data[a.second] + colPos[a.second][C2],
                        data[b.second] + colPos[b.second][C2]);
        if(t)	return t < 0;
        return false;
    }
};
int cmp::C1 = 0;
int cmp::C2 = 0;
int main() {
    int n, m;
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    while(scanf("%d %d", &n, &m) == 2) {
        while(getchar() != '\n');
        for(int i = 0; i < n; i++) {
            gets(data[i]);
            for(int j = 0, pos = 0; j < m; j++) {
                colPos[i][j] = pos;
                int hash = 0;
                while(data[i][pos] != ',' && data[i][pos] != '\0')
                    hash = ((hash<<15) + data[i][pos])&32767, pos++;
                hashCode[i][j] = hash;
                data[i][pos] = '\0', pos++;
            }
        }
        
        pair< pair<int, int>, int> D[10010];
        int flag = 0, r1, r2, c1, c2;
        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < m; j++) {
                for(int k = 0; k < n; k++) { // (hashCode[k][i], hashCode[k][j])
                    D[k] = make_pair(make_pair(hashCode[k][i], hashCode[k][j]), k);
                }
                cmp::C1 = i, cmp::C2 = j;
                sort(D, D + n, cmp());
                for(int k = 1; k < n; k++) {
                    if(!cmp()(D[k], D[k-1]) && !cmp()(D[k-1], D[k])) {
                        flag = 1;
                        r1 = D[k-1].second, r2 = D[k].second;
                        c1 = i, c2 = j;
                        i = j = m;
                        break;
                    }
                }
            }
        }
        puts(flag ? "NO" : "YES");
        if(flag)
            printf("%d %d\n%d %d\n", r1 + 1, r2 + 1, c1 + 1, c2 + 1);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11542 - Square

Given n integers you can generate $2^{n} - 1$ non-empty subsets from them. Determine for how many of these subsets the product of all the integers in that is a perfect square. For example for the set {4,6,10,15} there are 3 such subsets. {4}, {6,10,15} and {4,6,10,15}. A perfect square is an integer whose square root is an integer. For example 1, 4, 9, 16,…. .

Input

Input contains multiple test cases. First line of the input contains T(1≤T≤30) the number of test cases. Each test case consists of 2 lines. First line contains n(1≤n≤100) and second line contains n space separated integers. All these integers are between 1 and 10^15. None of these integers is divisible by a prime greater than 500.

Output

For each test case output is a single line containing one integer denoting the number of non-empty subsets whose integer product is a perfect square. The input will be such that the result will always fit into signed 64 bit integer.

Sample Input

1
2
3
4
5
6
7
8
9
4
3
2 3 5
3
6 10 15
4
4 6 10 15
3
2 2 2

Output for Sample Input

1
2
3
4
0
1
3
3

Solution

題目描述：

將 N 個數字，任挑相乘為平方數的方法數有多少？

題目解法：

將每個數字做質因數分解，對於每個質數將會有一條方程式，其參數為能貢獻的質因數的個數。

x1 = 0 表示第一個數字如果不選，x1 = 1 則表示選。

因此，最後希望所有方程式加總都必須要是偶數。

$$a_{1}x_{1} + a_{2}x_{2} + ... = even \quad for \quad prime \quad 2 \\ b_{1}x_{1} + b_{2}x_{2} + ... = even \quad for \quad prime \quad 3 \\ ...$$

使用 XOR 高斯消去法，找到任意解的變數個數 (大陸: 自由基) 即能得到所有解個數大小。

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
#include <stdio.h> 
#include <algorithm>
using namespace std;
#define maxL (500>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[505], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 500;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i; 
        }
    }
}
int main() {
    sieve();
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        
        int f[505][505] = {};
        long long x;
        for(int i = 0; i < n; i++) {
            scanf("%lld", &x);
            for(int j = 0; j < Pt; j++)
                while(x%P[j] == 0)
                    x /= P[j], f[j][i] ^= 1;
        }
        // xor gauss
        int row = Pt, col = n, arb = 0;
        for(int r = 0, c = 0; r < row && c < col; c++) {
            int k = r;
            for(int j = r + 1; j < row; j++)
                if(f[j][c])	k = j;
            for(int j = 0; j < col; j++)
                swap(f[r][j], f[k][j]);
                
            if(f[r][c] == 0) {arb++;continue;}
            
            for(int j = 0; j < row; j++) {
                if(r == j)	continue;
                if(f[j][c]) {
                    for(int k = col; k >= c; k--)
                        f[j][k] = f[j][k] ^ f[r][k];
                }
            }
            r++;
        }
        printf("%lld\n", (1LL<<arb) - 1);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11539 - Another Word Game

Problem

This is just another word game. You are given a dictionary of words. Each of the word has a weight W, which is an integer value. You are given another string S. Initially your score is zero. In each turn you can mark some consecutive characters. If these consecutive characters create a word in the given dictionary, corresponding weight will be added to your score, otherwise a penalty P will be subtracted word length times from your score. Here word length is number of character in a word, and P is an integer value. What is the maximum score you can gain?

Note that your have to make a move until all characters of S are marked, and you cannot mark one character more than once.

Input

Input will start with an integer number T (T≤20), which indicates the number of test case. Each test case starts with two integer N (N ≤ 10000) and P (0 ≤ P ≤ 10000). Here N is the number of words in the dictionary and P is the value of Penalty. Each of the next N lines will contain a word and corresponding integer weight W (0 ≤ W ≤ 10000). No word of this dictionary will contain more than 100 characters, and a word will only contain lower case alphabet (‘a’, ‘b’, … ,’z’). The last line of the input will contain string S. S will not contain more than 10000 characters, and will contain only lower case letters.

Output

For each test case you have to output one line which “Case #:” where # is replaced by the case number, then a space, then the maximum score.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
3
2 5
ab 2
cd 3
abcd
3 5
ab 2
cd 3
bc 16
abcd
1 100
abd 1
abcd

Output for Sample Input

1
2
3
Case 1: 5
Case 2: 6
Case 3: -400

Solution

題目描述：

給一個主子串 S，可以由其他小字串組合而成，這些小字串可以重複使用，每次使用可以得到相對應的單位獲益，但它們彼此之間不能重疊，如果 S 有一個字符沒有匹配，將會被罰款 W 單位。

求一個最高獲益的值為何？

題目解法：

由於考慮 dp[i] 已經匹配長度為 i 的時候，轉移會在字串匹配的時候速度非常慢，因此可以利用字串匹配的特性，對於所有小字串建一個 trie，接著建造出 AC 自動機，可以藉由失敗指針中快速找到當前有多少可以轉移的字符串可以串接。

但問題可能會在小字串長度太長效率下降，AC 只是剛好！也有人直接用 trie 搭配走訪就過去了，對於位置 i，從 root 開始往下走，一直走到位置 j，並且轉移，直到 trie 沒辦法走下去，保證不會有其他匹配情況。

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define maxKind 26
using namespace std;
struct Node{
    Node *fail;
    Node *next[maxKind];
    int cnt;
    vector< pair<int, int> > attr;
    Node() {
        fail = NULL;
        cnt = 0;
        memset(next, 0, sizeof(next));
    }
};
void build_Trie(const char* str, Node *root, pair<int, int> val) {
    Node *p = root;
    int i = 0, idx;
    while(str[i]) {
        idx = str[i] - 'a';
        if(p->next[idx] == NULL)
            p->next[idx] = new Node();
        p = p->next[idx];
        i++;
    }
    p->cnt++;
    p->attr.push_back(val);
}
void build_AC_automation(Node *root) {
    root->fail = NULL;
    queue<Node*> Q;
    Q.push(root);
    Node *tn, *p;
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        for(int i = 0; i < maxKind; i++) {
            if(tn->next[i] == NULL)
                continue;
            Q.push(tn->next[i]);
            p = tn->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                tn->next[i]->fail = root;
            else
                tn->next[i]->fail = p->next[i];
        }
    }
}
void free_AC_automation(Node *root) {
    queue<Node*> Q;
    Q.push(root);
    Node *tn, *p;
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        for(int i = 0; i < maxKind; i++) {
            if(tn->next[i] != NULL) {
                Q.push(tn->next[i]);
            }
        }
        free(tn);
    }
}
void query(const char* str, Node *root, int P) {
    Node *tn = root, *p;
    int n = strlen(str);
    int dp[100005] = {};
    for(int i = 0, idx; i < n; i++) {
        idx = str[i] - 'a';
        dp[i + 1] = dp[i] - P;
        while(tn->next[idx] == NULL && tn != root)
            tn = tn->fail;
        tn = tn->next[idx];
        tn = (tn == NULL) ? root : tn;
        p = tn;
        while(p != root) {
            if(p->cnt) {
            	for(vector< pair<int, int> >::iterator it = p->attr.begin();
                    it != p->attr.end(); it++) {
                    dp[i + 1] = max(dp[i + 1], dp[i - it->first + 1] + it->second);
                }
            }
            p = p->fail;
        }
    }
    printf("%d\n", dp[n]);
}
char buf[100001];
int main() {
    int testcase, N, P, val, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        Node *root = new Node();
        
        scanf("%d %d", &N, &P);
        for(int i = 0; i < N; i++) {
        	scanf("%s %d", buf, &val);
            build_Trie(buf, root, make_pair(strlen(buf), val));
        }
        
        build_AC_automation(root);
        scanf("%s", buf);
        printf("Case %d: ", ++cases);
        query(buf, root, P);
        free_AC_automation(root);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11523 - Recycling

Problem

Recycling involves processing used materials into new products in order to prevent the waste of potentially useful materials.

Recycling materials include things like glass, paper, plastic, metal and textiles. There are some materials that can’t be recycled such as Aerosol Cans. Aerosol cans that are not empty may leak or explode during the sorting and baling processes of recycling.

You are given a list of materials to be recycled. The materials are initially aligned in a line one after another. For every type of recyclable-material there is a corresponding bin. You are required to place each recyclable-material in its corresponding bin.

Example:

paper – glass – paper – aerosol – paper

In the example above, there are two types of recyclable-materials (paper & glass) and one type of non-recyclable-material. If we were to pick each material one by one and throw them in the bins, we would require 4 moves since there are 4 recyclable-materials. However, if we remove consecutive items in one move, provided they are of the same type, we could achieve the desired task in lesser number of moves.

Let’s see how this can be done: If we remove the glass first then the first two papers appear side by side enabling them to be moved together in the next move. Then we just have one paper remaining at the end and that requires a further move. This accumulates to a figure of 3 moves.

Illustration:

1
2
3
4
# Start  : paper – glass – paper – aerosol – paper  
# Move 1 : paper – paper – aerosol – paper [ after removing glass ]   
# Move 2 : aerosol – paper  [ after removing first 2 papers ]   
# Move 3 : aerosol [ after removing the last paper ]

Input

The first line of input is an integer T(T<50) that indicates the number of test cases. Each case starts with an integer N(N<100). The next line contains the names of N materials. The name of each material is a string containing only characters from the set [a..z] and [A..Z] and the length of each is at most 20. A recyclable-material is represented by lowercase letters only and that of non-recyclable-material by uppercase letters only.

Output

For each case, output the case number followed by the minimum number of moves required to clean up all the recyclable-materials meeting the constraints mentioned above.

Sample Input

1
2
3
4
5
6
7
3
5
paper glass paper AEROSOL paper
4
icpc icpc icpc icpc
3
NO RECYCLABLE MATERIALS

Output for Sample Input

1
2
3
Case 1: 3
Case 2: 1
Case 3: 0

Solution

題目描述：

現在把垃圾放置在一維空間，垃圾分成可回收和不可回收兩種，我們可以一次將連續個回收物拾起清除 (整個區間內的回收種類都要相同。) 並且放置回收桶。

用小寫表示可回收的種類分布，大寫為不可回收。求操作次數最少為何。

題目解法：

這一題比 UVa 10559 - Blocks 還要稍微簡單一點，可以在 O(n^3) 以內完成。UVa 10559 - Blocks 的計分方式多了一次清除的個數平方，最大化分數。

在這裡我們只需要將狀態改為，考慮區間 [l, r] 最左側 A[l] 項目是否要清除，否則將要等待 [l+1, i] 之間的項目清除之後，與 [i+1, ...] 一起清除。

  • 直接移除最左側
  • 等待中間一段的移除，隨後跟著 [i+1, ...] 最左側的一起清除。

因此轉移方程

$dp[l, r] = min(min(dp[l+1, r] + 1), min(dp[l+1, i] + dp[i+1, r]))$

記住中間轉移要保證一定取得連續相同且皆可回收，為了方便計算，連續相同的壓縮起來，直接考慮是否可回收即可。

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
// http://mypaper.pchome.com.tw/zerojudge/post/1326837348
#include <stdio.h>
#include <map>
#include <iostream>
#include <algorithm>
#include <ctype.h>
using namespace std;
int A[105], B[105];
int dp[105][105]; //[l][r][___{l, r}]
char used[105][105] = {}, usedcases = 0;
int dfs(int l, int r) {
    if(l > r)    return 0;
    if(used[l][r] == usedcases)
        return dp[l][r];
    int &ret = dp[l][r];
    used[l][r] = usedcases;
    if(A[l] == -1) {
    	ret = dfs(l + 1, r);
    	return ret;
    }
    ret = dfs(l+1, r) + 1;
    for(int i = l+1; i <= r && A[i] != -1; i++) {
        if(A[i] == A[l]) {
            ret = min(ret, dfs(l+1, i-1) + dfs(i, r));
        }
    }
    return ret;
}
int main() {
    int testcase, n, m;
    int cases = 0, i;
    char material[105][32];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        
        map<string, int> R;
        for(int i = 0; i < n; i++) {
        	scanf("%s", material[i]);
        	if(islower(material[i][0]))
        		R[material[i]] = 0;
        }
        
        int size = 0;
        for(map<string, int>::iterator it = R.begin(); it != R.end(); it++)
        	it->second = size++;
        for(int i = 0; i < n; i++)	 {
        	if(isupper(material[i][0]))
        		A[i] = -1;
        	else
        		A[i] = R[material[i]];
        }
        
        for(i = 1, B[0] = 1, m = 0; i < n; i++) {
            if(A[m] == A[i])
                B[m]++;
            else {
                A[++m] = A[i], B[m] = 1;
            }
        }
        usedcases++;
        printf("Case %d: %d\n", ++cases, dfs(0, m));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11184 - Joyful Ride

Problem

Suppose you want to own a roller coaster. Before you start, you might be interested in designing the course. The course is circular when seen from above, with n towers of equal distances on it. The figure below shows a course with n=7 (numbers inside circles are heights of towers).

To make the towers look interesting, their heights should be distinct positive integers not greater than n+1. To let customers enjoy a large variety of excitement, the height differences between neighboring towers should be all different. Since there are n height differences, each integer value between 1 and n must appear exactly once. In the example above, the height differences are: 8-1=7, 8-2=6, 7-2=5, 7-3=4, 5-3=2, 5-4=1, 4-1=3. You can check that every integer between 1 and 7 appears exactly once.

Write a program to design the ride.

Input

The input consists of several test cases. Each case contains a single integer n (2 £ n £ 1000), the number of towers. The last test case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and n numbers if the design is possible, ‘-1’ otherwise.

Sample Input

1
2
3
7
234
0

Output for Sample Input

1
2
Case 1: 1 4 5 3 7 2 8
Case 2: -1

Solution

題目描述：

找到一個擺放 N + 1 個數字的環狀，數字彼此之間的差值恰好可以湊出所有 1 到 N 之間的整數。

題目解法：

先窮舉前幾項的可能

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Case 1: -1
Case 2: 1 2 4
Case 3: 1 3 2 5
Case 4: -1
Case 5: -1
Case 6: 1 4 5 3 7 2 8
Case 7: 1 5 4 6 3 8 2 9
Case 8: -1
Case 9: -1
Case 10: 1 6 7 5 8 4 10 3 11 2 12
Case 11: 1 7 6 8 5 9 4 11 3 12 2 13
Case 12: -1
Case 13: -1
Case 14: 1 8 9 7 10 6 11 5 13 4 14 3 15 2 16
Case 15: 1 9 8 10 7 11 6 12 5 14 4 15 3 16 2 17
Case 16: -1
Case 17: -1
Case 18: 1 10 11 9 12 8 13 7 14 6 16 5 17 4 18 3 19 2 20
Case 19: 1 11 10 12 9 13 8 14 7 15 6 17 5 18 4 19 3 20 2 21

可以發現，對於 mod 4 餘 3、0 會沒有解。
仔細觀察一下規律，起頭 1，並且分別是 +-+-+- 從 -1+2-3+4 … 類推。

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
#include <stdio.h>
int main() {
    int n, cases = 0;
    while(scanf("%d", &n) == 1 && n) {
        printf("Case %d:", ++cases);
        if(n%4 != 3 && n%4 != 0)
            puts(" -1");
        else {
            int d = (n+1)/4*2-1 + (n%4 == 0);
            int sum = 1 + d;
            printf(" 1 %d", sum);
            for(int i = 1, j = 0; i < n; i++) {
                if(i == d)
                    continue;
                if(j%2 != d%2)
                    sum += i;
                else
                    sum -= i;
                printf(" %d", sum);
                j++;
            }
            puts("");
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11106 - Rectilinear Polygon

Problem

Given is n points with integer coordinates in the plane. Is it is possible to construct a simple, that is non-intersecting, rectilinear polygon with the given points as vertices? In a rectilinear polygon there are at least 4 vertices and every edge is either horizontal or vertical; each vertex is an endpoint of exactly one horizontal edge and one vertical edge. There are no holes in a polygon.

The first line of input is an integer giving the number of cases that follow. The input of each case starts with an integer 4 ≤ n ≤ 100000 giving the number of points for this test case. It is followed by n pairs of integers specifying the x and y coordinates of the points for this case.

The output should contain one line for each case on input. Each line should contain one integer number giving the length of the rectilinear polygon passing throught the given points when it exists; otherwise, it should contain -1.

Sample input

1
2
3
4
5
6
7
8
9
10
1
8
1 2
1 0
2 1
2 2
3 2
3 1
4 0
4 2

Output for sample input

1
12

Solution

題目描述：

給 N 個整數點座標，是否能構成一個直角的簡單多邊形，並請每個點都要在直角上。如果可以構成簡單多邊形，則輸出其多邊形周長為何。

題目解法：

由於每個點都必須在直角上，所以先考慮對 x = k 這一條直線上有數個點，則為了要構成簡單多邊形，保證這數個點根據 y 值排序，一定會構成 (y1, y2) (y3, y4) … 的連線，不然弄不出每一個點都在直角上。同理對於 y = k 考慮連線情況。

當我們將所有連線情況都記錄下後，要確保所有線段之間不會相交 (端點不算在相交情況中)，同時經過遍歷走訪後，所有的點都在同一個 component 上。

對於 N 個線段，可以在 O(N log N) 時間內得到是否有相交情況。代碼修改於 DJWS 演算法筆記

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
#include <stdio.h>
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define eps 1e-6
struct Pt {
    int x, y, label;
    Pt(int a = 0, int b = 0, int c = 0):
    	x(a), y(b), label(c) {}
    bool operator<(const Pt &a) const {
        if(x != a.x)	return x < a.x;
        return y < a.y;
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.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);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
int cmpX(Pt a, Pt b) {
    if(a.x != b.x)	return a.x < b.x;
    return a.y < b.y;
}
int cmpY(Pt a, Pt b) {
    if(a.y != b.y)	return a.y < b.y;
    return a.x < b.x;
}
vector<int> g[100005];
int visited[100005], dfsCnt;
void dfs(int u, int p) {
    visited[u] = 1, dfsCnt++;
    for(int i = g[u].size()-1; i >= 0; i--) {
        int v = g[u][i];
        if(v == p || visited[v])	continue;
        dfs(v, u);
    }
}
// http://www.csie.ntnu.edu.tw/~u91029/PointLinePlane2.html
struct seg {
    Pt s, e;
    seg(Pt a, Pt b):s(a), e(b) {}
};
struct Endpoint {
    int x, s, i;
    Endpoint(int a = 0, int b = 0, int c = 0):
        x(a), s(b), i(c) {}
    bool operator<(const Endpoint &a) const {
        return x < a.x || (x == a.x && s > a.s);
    }
};
struct CMP {
    static int x;
    
    double interpolate(const Pt& p1, const Pt& p2, int& x) {
        if (p1.x == p2.x) return p1.y;
        return p1.y + (double)(p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
    }
    
    bool operator()(const seg &i, const seg &j) {
        return interpolate(i.s, i.e, x) < interpolate(j.s, j.e, x);
    }
};
int CMP::x = 0;
set<seg, CMP>::iterator prevNode(set<seg, CMP>::iterator it, set<seg, CMP>& S) {
    return it == S.begin() ? it : --it;
}
set<seg, CMP>::iterator nextNode(set<seg, CMP>::iterator it, set<seg, CMP>& S) {
    return it == S.end() ? it : ++it;
}
bool segment_intersect(vector<seg> segs) {
    for(int i = 0; i < segs.size(); i++)
        if(segs[i].e < segs[i].s)
            swap(segs[i].s, segs[i].e);
            
    vector<Endpoint> e;
    set<seg, CMP> S;
    for(int i = 0; i < segs.size(); i++) {
        e.push_back(Endpoint(segs[i].s.x, 1, i));
        e.push_back(Endpoint(segs[i].e.x, -1, i));
    }
    sort(e.begin(), e.end());
    
    for(int i = 0; i < e.size(); i++) {
        CMP::x = e[i].x;
        if(e[i].s == 1) {
            set<seg, CMP>::iterator it, jt;
            it = S.lower_bound(segs[e[i].i]);
            jt = prevNode(it, S);
            if(it != S.end() && intersection(segs[e[i].i].s, segs[e[i].i].e, it->s, it->e))
                return 1;
            if(jt != S.end() && intersection(segs[e[i].i].s, segs[e[i].i].e, jt->s, jt->e))
                return 1;
            S.insert(segs[e[i].i]);
        } else {
            set<seg, CMP>::iterator it, jt, kt;
            it = S.lower_bound(segs[e[i].i]);
            jt = prevNode(it, S);
            kt = nextNode(it, S);
            if(jt != S.end() && kt != S.end() && intersection(kt->s, kt->e, jt->s, jt->e))
                return 1;
            if(it != S.end())
                S.erase(it);
        }
    } 
    return 0;
}
Pt D[100005], P[100005];
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d %d", &P[i].x, &P[i].y);
            D[i] = P[i], D[i].label = i;
        }
        
        int eflag = 0;
        for(int i = 0; i < n; i++)
            g[i].clear(), visited[i] = 0;
        sort(D, D+n, cmpX);		
        for(int i = 0; i < n && !eflag; i += 2) {
            if(i+1 < n && D[i].x == D[i+1].x) {
                g[D[i].label].push_back(D[i+1].label);
                g[D[i+1].label].push_back(D[i].label);
            } else
                eflag = 1;
        }
        sort(D, D+n, cmpY);
        for(int i = 0; i < n && !eflag; i += 2) {
            if(i+1 < n && D[i].y == D[i+1].y) {
                g[D[i].label].push_back(D[i+1].label);
                g[D[i+1].label].push_back(D[i].label);
            } else
                eflag = 1;
        }
        
        if(!eflag) { // only one component
            dfsCnt = 0;
            dfs(0, -1);
            if(dfsCnt != n)
                eflag = 1;
        }
        
        if(!eflag) {
            vector<seg> segs;
            for(int i = 0; i < n; i++) {
                for(int j = g[i].size()-1; j >= 0; j--) {
                    segs.push_back(seg(P[i], P[g[i][j]]));
                }
            }
            eflag = segment_intersect(segs);
        }
        
        if(eflag)
            puts("-1");
        else {
            int para = 0;
            for(int i = 0; i < n; i++) {
                for(int j = g[i].size()-1; j >= 0; j--) {
                    para += abs(P[i].x - P[g[i][j]].x) + abs(P[i].y - P[g[i][j]].y);
                }
            }
            printf("%d\n", para/2);
        }
    }
    return 0;
}
/*
5
6
68 81
65 33
32 94
52 80
63 44
11 41
*/
Read More +
解題區/解題區 - UVa

UVa 10877 - Diceoids

Problem

The following picture shows four dice. Or are they all dice?

Artifacts (a) and (b) are dice; (c) and (d) are not dice, but they are the same—you can see that by a suitable rotation of (d). Thus, here we have two classes of dice-like artifacts (diceoids), classified by comparison under suitable rotations.

You are given a bag of diceoids, and your job is to classify them and report how many classes there are. (Your job is not to determine how many are dice.) To facilitate description of diceoids in a text medium, we label the faces of the cube:

then a diceoid is encoded as a sequence of six numbers dA , . . . , dF , meaning that face i bears di dots. Example: 5 3 6 2 1 4 means that face A has 5 dots, face B has 3 dots, face C has 6 dots, etc. It is entirely possible that different faces have the same number of dots, e.g., 2 2 2 3 3 3, but every face has at least 1 dot and at most 6 dots.

Input

The input file contains several test cases. The description of each test case is given below:

Each test case begins with the number of diceoids n (n<=1000), followed by the description of n dicecoids.

Output

For each test case your program should output the number of classes. Follow the format specified in the output for sample input.

Sample Input

1
2
3
4
5
6
7
8
9
7
5 3 6 2 1 4
4 1 5 3 2 6
5 6 3 2 4 1
4 5 1 3 6 2
2 2 2 3 3 3
2 3 2 3 3 2
1 1 1 1 1 1
0

Output for Sample Input

1
4

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
#include<stdio.h>
#include<stdlib.h>
typedef struct {
    int dice[6];
}DICE;
void Right_turn(DICE *A) {
    static int t;
    t = A->dice[0], A->dice[0] = A->dice[4];
    A->dice[4] = A->dice[3], A->dice[3] = A->dice[1], A->dice[1] = t;
}
void Up_turn(DICE *A) {
    static int t;
    t = A->dice[0], A->dice[0] = A->dice[5];
    A->dice[5] = A->dice[3], A->dice[3] = A->dice[2], A->dice[2] = t;
}
void clockwise(DICE *A) {
    static int t;
    t = A->dice[2], A->dice[2] = A->dice[4];
    A->dice[4] = A->dice[5], A->dice[5] = A->dice[1], A->dice[1] = t;
}
DICE Data[2048];
int cmp(const void *a, const void *b) {
    static DICE *i, *j;
    static int k;
    i = (DICE *)a, j = (DICE *)b;
    for(k = 0; k < 6; k++)
        if(i->dice[k] != j->dice[k])
            return i->dice[k] - j->dice[k];
    return 0;
}
void Print(DICE A) {
    static int i;
    for(i = 0; i < 6; i++)
        printf("%d ", A.dice[i]);
    puts("");
}
void Spin_dice(DICE A, int store) {
    static int i, j;
    for(i = 0; i < 6; i++)
        Data[store].dice[i] = A.dice[i];
    for(i = 0; i < 4; i++) {
        for(j = 0; j < 4; j++) {
            if(cmp(&Data[store], &A) > 0)
                Data[store] = A;
            clockwise(&A);
        }        
        Right_turn(&A);
    }
    Up_turn(&A);
    for(i = 0; i < 2; i++) {
        for(j = 0; j < 4; j++) {
            if(cmp(&Data[store], &A) > 0)
                Data[store] = A;
            clockwise(&A);
        }        
        Up_turn(&A), Up_turn(&A);
    }
}
main() {
    int n, i, j;
    DICE A;// 前右上後左下
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++) {
        	scanf("%d %d %d %d %d %d", &A.dice[0], &A.dice[1], &A.dice[2], 
                        &A.dice[3], &A.dice[5], &A.dice[4]);
            Spin_dice(A, i);
        }
        int Ans = 1;
        qsort(Data, n, sizeof(DICE), cmp);
        for(i = 1; i < n; i++) {
            if(cmp(&Data[i], &Data[i-1]))
                Ans++;
        }
        printf("%d\n", Ans);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10769 - Pillars

Problem

The world-famous architect Mr. Fruí from Reus plans to build a colossal pillar H units high. Mr. Fruí has n black pieces with heights b1,…, bn and m white pieces with heights w1,…, wm. According to his design the pillar must have four pieces: a black piece on its bottom, a white piece above it, another black piece above, and finally a white piece on the top of the pillar.

Mr. Fruí wishes to know which of the combinations of four pieces with total height H is the most stable. Given two combinations A = [a1, a2, a3, a4] and B = [b1, b2, b3, b4] (where a1 denotes the height of the bottom (black) piece of the pillar A, a2 denotes the height of the second (white) piece of A, and so on), A is more stable than B if a1 > b1, or if a1 = b1 but a2 > b2, etc. (In other words, A is more stable than B if and only if the sequence of heights of the pieces of A is lexicographically larger than the sequence of heights of the pieces of B.)

Write a program such that, given the desired height H of the pillar, the heights of the black pieces and the heights of the white pieces, computes which pillar (if any) of height exactly H would be the most stable.

Input

Input consists of zero ore more test cases. Each test case has on the first line H, an integer between 1 and 4*108. The second and third lines of each test consist respectively of the sequence b1,…, bn and of the sequence w1,…, wm. A blank line separates two consecutive test cases. You can assume 2$\le$n$\le$100 and 2$\le$m$\le$100, and that no piece has a height larger than 108.

Output

For every test case, print one line with the sequence of heights of the pieces of the most stable pillar. If no solution exists, print “no solution”.

Sample Input

1
2
3
4
5
6
7
100
20 20
30 10 30 50
 
100
20 10 4
50 30 45

Sample Output

1
2
20 50 20 10
no solution

Solution

題目描述：

這位世界著名的建築師，設計一個黑白相間的柱子，而這個柱子高度必須為 H，並且由四塊石塊來完成，分別是黑 (底部)、白、黑、白 (底部)。

每一種顏色的石塊都有自己的高度，請輸出恰好能組成高度 H 且字典順序最小的組合。

題目解法：

依序窮舉組合。

當初想要偷吃步加快操作，反而吃了一些字典順序的閉門羹。

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
#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <sstream>
#include <functional>
using namespace std;
vector<int> getLineNumber(char s[]) {
    stringstream sin(s);
    vector<int> ret;
    int x;
    while(sin >> x)
        ret.push_back(x);
    return ret;
}
int main() {
    char s[1024];
    int H;
    while(gets(s)) {
        sscanf(s, "%d", &H);
        vector<int> B, W;
        gets(s), B = getLineNumber(s);
        gets(s), W = getLineNumber(s);
        gets(s);
        sort(B.begin(), B.end(), greater<int>());
        sort(W.begin(), W.end(), greater<int>());
        
        int f = 0;
        for(int i = 0; i < B.size(); i++)
        for(int j = 0; j < W.size(); j++)
        for(int a = i+1; a < B.size(); a++)
        for(int b = j+1; b < W.size(); b++) {
            if(B[i]+W[j]+B[a]+W[b] == H) {
                printf("%d %d %d %d\n", B[i], W[j], B[a], W[b]);
                i = a = B.size();
                j = b = W.size();
                f = 1;
            }
        }
        if(!f)
            puts("no solution");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10744 - The Optimal Super-Highway

In our real life when we look for help we find that only a few people are willing to help us but when we look for suggestions there are thousands waiting with their bag of suggestions. In the country named Culabura a similar situation is creating a lot of trouble. Culabura is a country containing around 20000 important places and infinite land area. The president of Culabura wants to build a super highway through his country. This super highway can be expressed by a straight line that fulfills the following two properties:
a) It must be parallel to another road that connects the two most important cities (denoted by A and B) of the country.

b) The summation of distances of all-important places from it must be minimum.

The advisers of the king of Culabura are giving random and meaningless suggestions to solve this problem (As always is the case with advisers). Now your job is to find the minimum summation of distance. For example in the above picture you will have to find the minimum possible value of (d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8). In other words you will have to place the superhighway in such a place so that (d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8) is minimum and you will have print this minimum value. In this problem we will call such minimum value sum_d_min. Your solution must be very efficient. /Looking for an O(n) solution /

Input

The input file contains a single set of input. First line of each input set contains two integers N (0<N<20001) and Q(0<Q<101). Here N is the number of important places and Q is the number of queries. Each of the next N lines contains a pair of integer xi and yi (|xi|, |yi|<=100), where (xi, yi) is the coordinate of the i-th (0<=i<=N-1) important place. Each of the next Q lines contains four integers Ax, Ay, Bx, By, where (Ax, Ay) and (Bx, By) are the coordinates of A and B respectively and the optimal super highway must be parallel to street (or line) AB. You must not consider A and B as part of the N important places. Some important places may be present more than in the list to give them extra importance. You don’t need to worry about that and just consider them as two different places. Also remember that place A and B will always be two different places.

Output

For each query produce one line of output. This line contains the serial of output followed by the value of sum_d_min for that particular query. All the output numbers should be rounded to nearest integer. Look at the output for sample input for details.

Sample Input

1
2
3
4
5
6
7
8
9
6 2
1 1
1 10
20 12
2 4
1 1
2 4
10 10 11 11
2 3 3 4

Output for Sample Input

1
2
Case 1: 15
Case 2: 15

Solution

題目描述：

給平面上 N 個點座標，接著詢問平行兩個點的線中，找到一條當作高速公路，使得每一個點到線上最短距離總和最小。

題目解法：

套用點線距公式，可以發現其符合中位數性質，如果不用中位數的方式，也可以藉由排序後採用 DP 的方式找到一個距離最小的線分布 (線一定會經過其中一個點)。

為了加速，捨棄掉$\frac{|ax + by + c|}{\sqrt{a^{2}+b^{2}}}$ 的分母部分，留到最後再除即可。

如果只求中位數，可以針對 Selection Algorithm，在 O(n) 時間內找到，速度快於排序的 O(n 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
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
#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 {
    int x, y;
    Pt(int a = 0, int 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 {
        Pt ret;
        ret.x = x - a.x;
        ret.y = y - a.y;
        return ret;
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double distProjection(Pt as, Pt at, Pt s, double &div) {
    long long a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    div = a * a + b * b;
    return (a * s.x + b * s.y + c) /* / hypot(a, b) */;
}
int main() {
    int cases = 0, n, q;
    Pt D[32767], a, b;
    while(scanf("%d %d", &n, &q) == 2) {
        for(int i = 0; i < n; i++) {
            scanf("%d %d", &D[i].x, &D[i].y);
        }
        for(int i = 0; i < q; i++) {
            scanf("%d %d", &a.x, &a.y);
            scanf("%d %d", &b.x, &b.y);
            
            vector<double> dist;
            double div;
            for(int j = 0; j < n; j++)
                dist.push_back(distProjection(a, b, D[j], div));
            sort(dist.begin(), dist.end());
            
            double sum = 0, ret;
            for(int j = 0; j < n; j++)
                sum += dist[j] - dist[0];
            ret = sum;
            for(int j = 1; j < n; j++) {
                sum = sum - (dist[j] - dist[j-1]) * (n - j) + (dist[j] - dist[j-1]) * j;
                ret = min(ret, sum);
            }
            printf("Case %d: %.0lf\n", ++cases, ret / sqrt(div));
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10732 - The Strange Research

Professor A. Karim is working on a project of measuring the surface area of an unknown unearthly object. After a lot of calculation he finds that the surface area of that object is (a+b)(1-ab), where a and b are two parameters related to surface area of that object. With the help of some more advanced experiments he finds N floating-point numbers, which can be possible values of a and b. From the N numbers he can select two values for a and b in NC2 ways (Note that the selections a=2, b=3 and a=3, b=2 are considered same because (a+b)(1-ab) is equal to (b+a)(1-ba)). Karim needs to do some more expensive experiments to find out the real value of a and b, but before doing that he wants to keep only the obvious choices: the selections, which cause the surface of the object to be positive (Greater than zero). Your job is to help Prof. Karim to count how many of the NC2 selections (the value of a and b) causes (a+b)(1-ab) to be positive. Please note that your method must be efficient. (An O(N2) solution will not do)

Input

The input fine contains maximum 7 sets of inputs.

First line of each set contains an integer N (0<N<=10000). Each of the next N lines contains one floating-point number F (|F|<30000.0). The meaning of N is given in the problem statement.

The Input can have the same number twice or even more times. In such cases two same numbers should be considered different.

Input is terminated by a case where the value of N is zero. This case should not be processed.

Output

For each set of input produce one line of output. This line contains the serial no of output followed by an integer which indicates how many of the NC2 selections will cause the value of the expression (a+b)(1-ab) to be positive. Look at the output for sample input for details. You can consider any value greater than 10-15 is positive.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
5
8197.4013
-3622.8175
-1495.5118
-3958.2735
-678.2750
5
-1208.8234
1465.1943
2699.873
-6665.3587
-4344.6286
0

Output for Sample Input

1
2
Case 1: 10
Case 2: 5

Solution

題目描述：

從一堆數字中，任挑兩個實數出來，計算 (a + b) * (1 + a * b) > 1e-15 的對數有多少個。

題目解法：

固定其中一個數字 a 後，可以找到 b 的一元二次方程式，找到區間解的個數即可。
將輸入的數字排序，二分根的位置即可，但是麻煩的地方在於 > 1e-15，因此這部分做了些許的微調。

// 因為沒有考慮 1e-15 吞了不少 WA。

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int n, cases = 0;
    double v[32767];
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++)
            scanf("%lf", &v[i]);
            
        sort(v, v+n);
        int ret = 0, pos = 0;
        for(int i = 0; i < n; i++)
            if(v[i] > 0)
                pos ++;
        for(int i = 0; i < n; i++) {
            double a = -v[i], b = (1 - v[i]*v[i]), c = v[i];
            double r1, r2;
            if(b*b - 4*a*c < 0)	continue;
            if(fabs(a) < eps) {
                ret += pos;
                continue;
            }
            r1 = (-b - sqrt(b*b - 4*a*c))/2/a;
            r2 = (-b + sqrt(b*b - 4*a*c))/2/a;
            if(r1 > r2)	swap(r1, r2);
            
            int l = lower_bound(v, v + n, r1) - v;
            int r = upper_bound(v, v + n, r2) - v;
            int cnt = 0;
//			printf("%lf %lf %d %d\n", r1, r2, l, r);
            if(v[i] > 0) { // [l, r)
                while(l >= 0 && (v[l] + v[i])*(1 - v[l]*v[i]) > 1e-15)
                    l--;
                l++;
                while(l < n && (v[l] + v[i])*(1 - v[l]*v[i]) <= 1e-15)
                    l++;
                while(r < n && (v[r] + v[i])*(1 - v[r]*v[i]) > 1e-15)
                    r++;
                if(l <= i && i < r)
                    cnt--;
                cnt += r - l;
//				for(int j = 0; j < n; j++) {
//					if(j == i)	continue;
//					if(v[j] > r1 && v[j] < r2)
//						ret++;
//				}
            } else {
                while(l >= 0 && (v[l] + v[i])*(1 - v[l]*v[i]) <= 1e-15)
                    l--;
                l++;
                while(l < n && (v[l] + v[i])*(1 - v[l]*v[i]) > 1e-15)
                    l++;
                while(r < n && (v[r] + v[i])*(1 - v[r]*v[i]) <= 1e-15)
                    r++;
                if(i < l || i >= r)
                    cnt--;
                cnt += l + (n - r);
//				for(int j = 0; j < n; j++) {
//					if(j == i) 	continue;
//					if(v[j] < r1 || v[j] > r2)
//						ret++;
//				}
            }
//			int cnt2 = 0;
//			for(int j = 0; j < n; j++) {
//				if(i == j)	continue;
//				cnt2 += (v[i] + v[j]) * (1 - v[i]*v[j]) > 1e-15;
//			}
//			if(cnt != cnt2) {
//				printf("%lf %d %d %lf %lf, %lf %lf\n", v[i], cnt, cnt2, r1, r2, v[l], v[r-1]);
//				return 0;
//			}
            ret += cnt;
        }
        printf("Case %d: %d\n", ++cases, ret/2);
    }
    return 0;
}
/*
2
0
0
*/
Read More +