解題區/解題區 - UVa

UVa 12042 - Colorful Eggs

Problem

Little Mou is very fond of eggs. She has n baskets for keeping her colorful eggs. Each basket contains eggs of different colors. The baskets are numbered from 1 to n. She has a strange hobby about these eggs. On each day, she takes each basket starting from the nth basket. When she is doing this for basket i, she counts all eggs placed in baskets 1 to i (inclusive) and takes their sum. Let this value of sum be counti. She removes all old eggs from the ith basket and keeps counti new eggs in the ith basket. After that she puts all the old eggs of the ith basket in the (i-1)th basket removing the old eggs of the (i-1)th basket. As Mou is very fond of eggs, she eats all old eggs of the (i-1)th basket. And when she has finished eating, she repeats the work for this (i-1)th basket. If she reaches the 1st basket, she stops her work and doesn’t eat any more eggs and goes to sleep!

For example let Mou has 3 baskets at day 1. 1st basket contains 1 egg, 2nd basket contains 1 egg and the 3rd basket contains 2 eggs.

So simulation for day 3 follows:

Basket Index => 3 2 1

….. 略

Now the problem is given n, d and the number of eggs in each basket eggi, your job is to find the number of eggs in each basket after d days. As the number can be very big output answer modulo 1,000,000,007.

Input

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

Two integers N (1 ≤ n ≤ 60) and d (1 ≤ d ≤ 1,000,000,000), followed by n integers denoting the number of eggs in each basket starting from 1 to n.
Output

For each test case print one line of output containing the number of eggs in each basket after d days have passed separated by single spaces between them. See the sample output for more details. As the numbers can be very big output answer modulo 1,000,000,007.

Sample Input

1
2
3
4
5
6
7
3
3 7
1 2 3
2 2
4 5
2 1
1 10

Sample Output

1
2
3
129 189 277
5 9
1 10

Solution

題目描述：

一開始有 n 籃雞蛋，每一籃有各自個雞蛋數量。

每一次的操作從最右邊 (編號大的那籃開始) 進行，將所有比它小的編號的雞蛋總數加到這一籃，並且將原本的雞蛋總數指派給下一個籃。

問第 d 天後的結果。

題目解法：

建造轉移矩陣，使用 D&C 完成。

觀察一下可以發現，矩陣肯定長成這副德性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[1, 1, 1, ..., 1, 1, 1]
[1, 0, 1, ..., 1, 1, 1]
[1, 0, 0, 1, ..., 1, 1] = M
[1, 0, 0, 0, ..., 1, 1]
...
[1, 0, 0, 0, ..., 0, 0]
[an]
[an-1]
[an-2] = A(1)
...
[a1]
M x A(1) = A(2)
M x M x A(1) = A(3)
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
#include <stdio.h> 
#include <string.h>
const long long mod = 1000000007LL;
struct Matrix {
    long long v[64][64];
    int row, col; // row x col
    Matrix(int n, int m, long long a = 0) {
        memset(v, 0, sizeof(v));
        row = n, col = m;
        for(int i = 0; i < row && i < col; i++)
            v[i][i] = a;
    }
    Matrix operator*(const Matrix& x) const {
        Matrix ret(row, x.col);
        for(int i = 0; i < row; i++)
            for(int j = 0; j < x.col; j++)
                for(int k = 0; k < col; k++)
                    ret.v[i][j] += v[i][k] * x.v[k][j] %mod,
                    ret.v[i][j] %= mod;
        return ret;
    }
    Matrix operator^(const int& n) const {
        Matrix ret(row, col, 1), x = *this;
        int y = n;
        while(y) {
            if(y&1)	ret = ret * x;
            y = y>>1, x = x * x;
        }
        return ret;
    }
};
int main() {
    int testcase, n, d, a[105];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &d);
        d--;
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        Matrix x(n, n), A(n, 1);
        for(int i = 0; i < n; i++)
            A.v[i][0] = a[n-i-1];
        for(int i = 0; i < n; i++)
            x.v[0][i] = 1;
        for(int i = 1; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                x.v[i][j] = 1;
            }
            x.v[i][0] = 1;
        }
        Matrix y = x ^ d;
        Matrix r = y * A;
        for(int i = r.row-1; i >= 0; i--) { 
            printf("%lld", r.v[i][0]);
            if(i)	putchar(' ');
        } 
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12040 - Again Lucky Numbers

Problem

Some people believe that 13 is an unlucky number. So they always want to avoid the number 13. But I believe that 7 is an unlucky number and want to avoid it. So unlucky number is different for man to man. If 13 is an unlucky number and in a number there is no 13 (i.e. no ‘1’ is followed by a ‘3’) then we can call it a lucky number. For example, if we consider 13 as an unlucky number then 12345 is a lucky number. But if any number contains 13 then it is not a lucky number, such as 13254 and 21345 are not lucky numbers. Given the number of digits N in a number and the unlucky number M, you have to find out how many lucky numbers are possible with N digits considering that M is unlucky number. Note that leading 0’s are not allowed. So, 011 is not a valid three digit number.

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:

Two positive integers N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 10100).

Output

For each test case print the number of lucky numbers of N digits considering that M is the unlucky number. The result may be very large. You have to output the result modulo 10000007.

Sample Input

1
2
3
4
3
1 3
2 13
2 1

Sample Output

1
2
3
9
89
72

Solution

題目描述：

找到長度為 n 的數字，並且數字中不會出現指定的數字為 substring，求符合數字的總數。

題目解法：

特別考慮以 0 開頭的情況 (n 位數字前導不可為 0，但 n = 1 位數字可以是 0)。
最後，建造一台 AC 自動機，接著對於每一個節點著手 dp 轉移。

也就是考慮再將字串進行 AC 自動機匹配時所會遇到的所有轉移情況，因此我們要避免出現指定的字符串時，在結尾處標記不可轉移即可。

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
// http://mypaper.pchome.com.tw/zerojudge/post/1324462879
// AC 自動機 DP
#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
struct Node {
    Node *next[10], *fail, *prev;
    int eos;//prefix has a string end
    long long dp[105]; // [string length]
    int ASCII;
    Node() {
        fail = NULL, prev = NULL;
        memset(next, 0, sizeof(next));
        memset(dp, 0, sizeof(dp));
        eos = 0;
        ASCII = 0;
    }
};
void insertTrie(const char str[], Node *root, int label) {
    static Node *p;
    static int i, idx, eos;
    p = root, eos = 0;
    for(i = 0; str[i]; i++) {
        idx = str[i] - '0';
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
            p->next[idx]->prev = p;
            p->next[idx]->ASCII = idx;
        }
        eos |= p->eos;
        p = p->next[idx];
        p->eos |= eos;
    }
    p->eos |= label;
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
        delete nd;
    }
}
void buildACautomation(Node *root) {
    queue<Node*> Q;
    Node *nd, *p;
    root->fail = NULL;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] == NULL)
                continue;
            Q.push(nd->next[i]);
            p = nd->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                nd->next[i]->fail = root;
            else {
                nd->next[i]->fail = p->next[i];
                nd->next[i]->eos |= p->next[i]->eos;//special for dp
            }
        }
    }
}
const int mod = 10000007;
long long dp(Node *root, int len) {
    queue<Node*> Q;
    Node *nd, *p;
    root->dp[0] = 1;
    int k, i, j;
    long long ans, ret = 0;
    for(k = 0; k <= len; k++) {
        Q.push(root);
        ans = 0;
        while(!Q.empty()) {
            nd = Q.front(), Q.pop();
            for(i = (k == 0); i < 10; i++) { // leading 0's are not allowed
                if(nd->next[i] != NULL) {
                    if(nd->next[i]->eos)
                        continue;//not safe
                    nd->next[i]->dp[k+1] += nd->dp[k];
                    nd->next[i]->dp[k+1] %= mod;
                    Q.push(nd->next[i]);
                } else {
                    p = nd;
                    while(p != root && p->next[i] == NULL)
                        p = p->fail;
                    p = p->next[i];
                    if(p == NULL) // error message
                        puts("NULL");
                    if(p->eos)
                        continue;//not safe
                    p->dp[k+1] += nd->dp[k];
                    p->dp[k+1] %= mod;
                }
            }
            ans += nd->dp[k];
            ans %= mod;
        }
        if(k == len) {
            ret += ans;
            ret %= mod;
        }
    }
    return ret;
}
int main() {
    int n, p, i;
    int cases = 0, testcase;
    char pattern[105], s[105];
    scanf("%d", &testcase);
    while(testcase--) {
        Node *root = new Node();
        scanf("%d %s", &n, pattern);
        insertTrie(pattern, root, 1);
        for(int i = 0; i < 10; i++) {
        	s[0] = i + '0', s[1] = '\0';
        	insertTrie(s, root, 0);
        }
        buildACautomation(root);
        long long ret = dp(root, n);
        freeTrie(root);
        if(n == 1 && strcmp("0", pattern))
        	ret++;
        printf("%lld\n", ret);
    }
    return 0;
}
/*
3
1 3
2 13
2 1
*/
Read More +
解題區/解題區 - UVa

UVa 12010 - Boring Homework

Problem

Professor Z. always gives his students lots of boring homework. Last week, after explaining binary search trees (BSTs), he asked his students to draw a picture of BST according to the list of numbers inserted into the tree sequentially. Maryanna spent so much time playing the game “Starcraft II” that she can’t finish her homework in time. She needs your help.

  • A binary search tree, which may sometimes also be called ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.
    -from Wikipedia

To draw a picture of BST, you may follow the rules listed below:

  • The picture of a 1-node BST, whose size is 1*1, is a single ‘o’ (15th small Latin letter).
  • If a BST has a non-empty subtree, draw a single ‘|’ just above the subtree’s root, and a single ‘+’ just above previous drawn ‘|’. Finally, in the row of ‘+’, use the least number (including 0) of ‘-‘s to connect ‘+’ (denoting the left subtree and right subtree) and ‘o’ (denoting the parent node of the subtree)
  • The left subtree (if exists) must be drawn on the left side of its parent. Similarly, the right subtree (if exists) must be drawn on the right side of its parent.
  • The column of the BST’s root must not contain any character from left subtree or right subtree.
  • Any column containing any characters from BST’s left subtree must not contain any characters from BST’s right subtree, and vice versa. That is, for a node of the BST, the picture of its left subtree and the picture of its right subtree do not share common columns in the picture of the whole tree.

The sample output may give a clear clarification about the format of the picture.

Input

The first line contains T ( T$\le$2500), the number of test cases. T lines follow. Each line contains a positive integer N (N < 80), followed by N integers - a permutation of 1 to N. The permutation indicates the insert order for the BST.

Output

For each test case:

Output the case number counting from 1 in the first line. The next lines should be the image described above without any trailing spaces. See the sample for more format details.

Note: Notice that no trailing whitespaces after the last visible characters of each line are allowed.

Sample Input

1
2
3
4
3
3 3 1 2
6 4 5 6 1 3 2
5 3 4 5 2 1

Sample Output

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

Solution

題目描述：

請先依序插入節點，並且建造一棵二分搜尋樹，接著打印出來。

以 o 表示節點，而用 + 表示左右子樹的存在，並且用 - 來移動其位置。盡可能用最少的 - 來完成。並且每一列 (縱向) 只會有一個 o 存在。

題目解法：

根據中序搜索，可以得到由左至右的打印節點順序，根據這個打印順序著手左右的 - 計算。

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
#include <stdio.h>
#include <string.h>
struct Node {
    int v, l, r, porder;
};
Node BST[128];
char g[256][128];
int porder = 0, mxdep;
void build(int nd, int dep) {
    if(dep > mxdep)	mxdep = dep;
    if(BST[nd].l != -1)
        build(BST[nd].l, dep+2);
    BST[nd].porder = porder++;	
    if(BST[nd].r != -1)
        build(BST[nd].r, dep+2);
        
    if(BST[nd].l != -1) {
        g[dep][BST[BST[nd].l].porder] = '+';
        g[dep+1][BST[BST[nd].l].porder] = '|';
        for(int i = BST[BST[nd].l].porder + 1; i < BST[nd].porder; i++)
            g[dep][i] = '-';
    }
    g[dep][BST[nd].porder] = 'o';
    if(BST[nd].r != -1) {
        for(int i = BST[BST[nd].r].porder - 1; i > BST[nd].porder; i--)
            g[dep][i] = '-';
        g[dep][BST[BST[nd].r].porder] = '+';
        g[dep+1][BST[BST[nd].r].porder] = '|';
    }
}
int main() {
    int testcase, cases = 0, N;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &N);
        memset(BST, -1, sizeof(BST));
        scanf("%d", &BST[0].v);
        int size = 1, x;
        for(int i = 1; i < N; i++) {
            scanf("%d", &x);
            int idx = 0;
            do {
                if(x < BST[idx].v) {
                    if(BST[idx].l != -1)
                        idx = BST[idx].l;
                    else
                        BST[idx].l = size, BST[size++].v = x, idx = 0;
                } else {
                    if(BST[idx].r != -1)
                        idx = BST[idx].r;
                    else
                        BST[idx].r = size, BST[size++].v = x, idx = 0;
                }
            } while(idx);
        }
        porder = 0, mxdep = 0;
        memset(g, ' ', sizeof(g));
        build(0, 0);
        printf("Case #%d:\n", ++cases);
        for(int i = 0; i <= mxdep; i++) {
            for(int j = N; g[i][j] == ' '; j--)
                g[i][j] = '\0';
            printf("%s\n", g[i]);
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11990 - ``Dynamic'' Inversion

Problem

You are given a permutation {1,2,3,…,n}. Remove m of them one by one, and output the number of inversion pairs before each removal. The number of inversion pairs of an array A is the number of ordered pairs (i,j) such that i < j and A[i] > A[j].

Input

The input contains several test cases. The first line of each case contains two integers n and m (1<=n<=200,000, 1<=m<=100,000). After that, n lines follow, representing the initial permutation. Then m lines follow, representing the removed integers, in the order of the removals. No integer will be removed twice. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each removal, output the number of inversion pairs before it.

Sample Input

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

Output for the Sample Input

1
2
3
4
5
2
2
1

Explanation

(1,5,3,4,2)->(1,3,4,2)->(3,4,2)->(3,2)->(3)

Solution

題目描述：

找尋一維數列的逆序對總數，每一次詢問請輸出當時的逆序對個數，隨後將該數字從數列中移除。

題目解法：

一開始可以利用傳統的 D&C 或者是線段樹之類的區間查詢來完成全部的逆序對總數。

隨後要移除某個特定的數字時，要查找該數字前面有多少比它大的數字，以及後面有多少比它小的數字。也就是說，找尋前綴大於某個數字的個數，和找尋後綴小於某個數字的個數，算出有多少對逆序對減少。

這裡使用類似歸併樹的做法，類似合併排序，將會切分成數個區間做排序。並且在每一個區間中會建立一棵離散化後的 binary indexed tree，如果一來記憶體可以在 O(n log n) 解決。

由於我們只需要前綴和後綴的操作，所以說是線段樹可能還有所不及。

每次將前綴拆分成線段樹的數個區間，利用 binary indexed tree，查找當前有多少小於該數字 x 數字被刪除，得到有多少小於 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
104
105
106
107
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 200005
int N, M, DEL;
int ST[20][MAXN], BIT[20][MAXN];
int MP[MAXN];
long long invPair;
void modifySUM(int BIT[], int x, int v, int L) {
    while(x <= L) {
        BIT[x] += v;
        x += x&(-x);
    }
} 
int querySUM(int BIT[], int x) {
    int ret = 0;
    while(x) {
        ret += BIT[x];
        x -= x&(-x); 
    } 
    return ret;
} 
void buildST(int k, int l, int r, int dep) {
    for(int i = l; i <= r; i++)
        ST[dep][i] = ST[dep-1][i], BIT[dep][i] = 0;
    if(l >= r)	return ;
    int m = (l + r)/2;
    buildST(k<<1, l, m, dep+1);
    buildST(k<<1|1, m+1, r, dep+1);
    sort(ST[dep] + l, ST[dep] + r+1);
}
void queryPrefix(int k, int l, int r, int dep, int x, int y, int val) {
    if(x <= l && r <= y) {
        int pos = upper_bound(ST[dep] + l, ST[dep] + r+1, val) - ST[dep];
        int pre = querySUM(BIT[dep]+l-1, pos - l);
        invPair -= (r - pos + 1) - (querySUM(BIT[dep]+l-1, r-l + 1) - pre);
        return ;
    }
    if(l >= r)	return ;
    int m = (l + r)/2;
    if(x <= m)
        queryPrefix(k<<1, l, m, dep+1, x, y, val);
    if(y > m)
        queryPrefix(k<<1|1, m+1, r, dep+1, x, y, val);
}
void querySuffix(int k, int l, int r, int dep, int x, int y, int val) {
    if(x <= l && r <= y) {
        int pos = upper_bound(ST[dep] + l, ST[dep] + r+1, val) - ST[dep];
        int pre = querySUM(BIT[dep]+l-1, pos - l);
        invPair -= (pos - l) - pre;
        return ;
    }
    if(l >= r)	return ;
    int m = (l + r)/2;
    if(x <= m)
        querySuffix(k<<1, l, m, dep+1, x, y, val);
    if(y > m)
        querySuffix(k<<1|1, m+1, r, dep+1, x, y, val);
}
void update(int k, int l, int r, int dep, int x, int val) {
    if(l == r) {
        modifySUM(BIT[dep]+l-1, 1, 1, r-l+1);
        return;
    }
    if(l >= r)	return ;
    int m = (l + r)/2;
    if(x <= m)
        update(k<<1, l, m, dep+1, x, val);
    else
        update(k<<1|1, m+1, r, dep+1, x, val);
    int pos = lower_bound(ST[dep] + l, ST[dep] + r+1, val) - ST[dep];
    modifySUM(BIT[dep]+l-1, pos - l + 1, 1, r-l+1);
}
int main() {
    while(scanf("%d %d", &N, &M) == 2) {
        invPair = 0;
        for(int i = 1; i <= N; i++)
            BIT[0][i] = 0;
        for(int i = 1; i <= N; i++) {
            scanf("%d", &ST[0][i]);
            MP[ST[0][i]] = i;
            invPair += i - 1 - querySUM(BIT[0], ST[0][i]);
            modifySUM(BIT[0], ST[0][i], 1, N);
        }
        buildST(1, 1, N, 1);
        
        while(M--) {
            scanf("%d", &DEL);
            printf("%lld\n", invPair);
            queryPrefix(1, 1, N, 1, 1, MP[DEL] - 1, DEL);
            querySuffix(1, 1, N, 1, MP[DEL] + 1, N, DEL);
            update(1, 1, N, 1, MP[DEL], DEL);
        }
    }
    return 0;
}
/*
5 4
1
5
3
4
2
5
*/
Read More +
解題區/解題區 - UVa

UVa 11722 - Joining with Friend

Problem

You are going from Dhaka to Chittagong by train and you came to know one of your old friends is going from city Chittagong to Sylhet. You also know that both the trains will have a stoppage at junction Akhaura at almost same time. You wanted to see your friend there. But the system of the country is not that good. The times of reaching to Akhaura for both trains are not fixed. In fact your train can reach in any time within the interval [t1, t2] with equal probability. The other one will reach in any time within the interval [s1, s2] with equal probability. Each of the trains will stop for w minutes after reaching the junction. You can only see your friend, if in some time both of the trains is present in the station. Find the probability that you can see your friend.

Input

The first line of input will denote the number of cases T (T < 500). Each of the following T line will contain 5 integers t1, t2, s1, s2, w (360 ≤ t1 < t2 < 1080, 360 ≤ s1 < s2 < 1080 and 1 ≤ w ≤ 90). All inputs t1, t2, s1, s2 and w are given in minutes and t1, t2, s1, s2 are minutes since midnight 00:00.

Output

For each test case print one line of output in the format “Case #k: p” Here k is the case number and p is the probability of seeing your friend. Up to 1e-6 error in your output will be acceptable.

Sample Input

1
2
3
2
1000 1040 1000 1040 20
720 750 730 760 16

Output for Sample Input

1
2
Case #1: 0.75000000
Case #2: 0.67111111

Solution

題目描述：

有兩位朋友，分別在 [t1, t2] 和 [s1, s2] 之間內可能會抵達，並且在那邊最多停留 w 單位時間。

問兩個人碰面的機率為何。

題目解法：

將兩個人分別至於 X Y 軸，利用幾何面積找到概率。

對於面積 [t1, t2]x[s1, s2] 只要符合 |t - s| <= w 的面積比例。

由於排容上可能不好理解，直接套用凸包交集的算法，兩個凸包交一定也是凸包。

p11722.png

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
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
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;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    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 val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
typedef Pt Vector;
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;
}
struct Seg {
    Pt s, e;
};
int calcIntersection(Seg a, Seg b, Pt &p) {
    double a1, b1, c1, a2, b2, c2;
    double d, dx, dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    d = a1*b2 - a2*b1;
    dx = c1*b2 - c2*b1;
    dy = a1*c2 - a2*c1;
    if(fabs(d) < eps) // NONE or LINE
        return 0;
    p.x = dx / d, p.y = dy / d;
    /*printf("%lf %lf - %lf %lf\n", a.s.x, a.s.y, a.e.x, a.e.y);
    printf("%lf %lf - %lf %lf\n", b.s.x, b.s.y, b.e.x, b.e.y);
    printf("%lf %lf\n", p.x, p.y);*/
    return onSeg(a.s, a.e, p) && onSeg(b.s, b.e, p);
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
           cnt++;
    }
    return cnt&1;
}
double calcArea(Pt p[], int n) {
    if(n < 3)   return 0.0;
    double ret = 0;
    int i;
    p[n] = p[0];
    for(i = 0; i < n; i++)
        ret += p[i].x * p[i+1].y - p[i].y * p[i+1].x;
    return fabs(ret)/2;
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
int main() {
    Pt a[64], b[64], ret[64], ch[64];
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
    	int t1, t2, s1, s2, w;
    	int n = 4, m = 4, q;
    	scanf("%d %d %d %d %d", &t1, &t2, &s1, &s2, &w);
    	a[0] = Pt(t1, s1), a[1] = Pt(t2, s1);
    	a[2] = Pt(t2, s2), a[3] = Pt(t1, s2);
    	b[0] = Pt(0, w), b[1] = Pt(0, -w);
    	b[2] = Pt(t2, t2-w), b[3] = Pt(t2, t2+w);
        Seg seg1, seg2;
        int retN = 0;
        for(int i = 0, j = n-1; i < n; j = i++) {
            seg1.s = a[i], seg1.e = a[j];
            for(int p = 0, q = m-1; p < m; q = p++) {
                seg2.s = b[p], seg2.e = b[q];
                if(calcIntersection(seg1, seg2, ret[retN])) {
                    retN++;
                    /*printf("%lf %lf - %lf %lf\n", s1.s.x, s1.s.y, s1.e.x, s1.e.y);
                    printf("%lf %lf - %lf %lf +++\n", s2.s.x, s2.s.y, s2.e.x, s2.e.y);*/
                }
            }
        }
        for(int i = 0; i < n; i++)
            if(inPolygon(b, m, a[i]))
                ret[retN++] = a[i];
        for(int i = 0; i < m; i++)
            if(inPolygon(a, n, b[i]))
                ret[retN++] = b[i];
        q = monotone(retN, ret, ch);
        double area = calcArea(ch, q);
        printf("Case #%d: %.8lf\n", ++cases, area / ((t2 - t1) * (s2 - s1)));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11266 - Equations

Problem

Find the number of solutions, the equation ∑Xi = s have, if Ai≤Xi≤Bi for each i = 1…n.

For example,

X1 + X2 + X3 = 10

-1 ≤ X1 ≤ 3

2 ≤ X2 ≤ 4

6 ≤ X3 ≤ 7

The above set of equations has 6 solutions. They are: {1,4,7}, {0,3,7}, {0,4,6}, {1,2,7}, {1,3,6} and {2,2,6}.

You are given n the number of variables and the range of them. Your task is to calculate the number of solutions of that equation.

Input

First line of the Input contains T (≤50) the number of test cases. Then T test cases follow. First line of each test case contains 2 integer n (1≤n≤10) and s (-50000 ≤ s ≤ 50000). Next n lines each contain 2 integers describing the range of each variable. The ith line Ai and Bi (10000 ≤ Ai ≤ Bi ≤10000). Xi can take any integral value in the range [Ai, Bi].

Output:

For each test case output contains one integer denoting the number of solutions of the given equations. Output the value modulo 200003.

Sample Input

1
2
3
4
5
1
3 10
-1 3
2 4
6 7

Sample Output

1
6

Solution

題目描述：

對於每一個變數範圍，找到符合等式的解個數。

題目解法：

直接著手動態規劃，對於 dp[i][j] 定義為使用前 i 個變數，總合為 j 的方法數。

為了加快迴圈操作，必須修改成滑動窗口，為了省記憶體，又使用滾動數組。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int shift = 100000;
int dp[2][200005];
int main() {
    int testcase, n, s;
    int A[16], B[16];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &s);
        for(int i = 0; i < n; i++)
            scanf("%d %d", &A[i], &B[i]);
            
        memset(dp, 0, sizeof(dp));
        for(int i = A[0]; i <= B[0]; i++)
            dp[0][i + shift] = 1;
        int f = 1;
        for(int i = 1; i < n; i++) {
            memset(dp[f], 0, sizeof(dp[f]));
            int l = -B[i], r = -A[i], sum = 0;
            for(int j = 0 - B[i]; j <= 0 - A[i]; j++) {
                if(j < 0 || j >= 200005)
                    continue;
                sum += dp[!f][j];
                sum %= 200003;
            }
            for(int j = 0; j < 200005; j++) {
                dp[f][j] = sum;
                if(l >= 0 && l < 200005)
                    sum -= dp[!f][l];
                if(r + 1 >= 0 && r + 1 < 200005)
                    sum += dp[!f][r+1];
//				if(sum)
//					printf("%d %d %d\n", i, j - shift, sum);
                sum %= 200003;
                l++, r++;
            }
            f = !f;
        }
        printf("%d\n", (dp[!f][s + shift] + 200003)%200003);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11243 - Texas Trip

Problem

After a day trip with his friend Dick, Harry noticed a strange pattern of tiny holes in the door of his SUV. The local American Tire store sells fiberglass patching material only in square sheets. What is the smallest patch that Harry needs to fix his door?

Assume that the holes are points on the integer lattice in the plane. Your job is to find the area of the smallest square that will cover all the holes.

Input

The first line of input contains a single integer T expressed in decimal with no leading zeroes, denoting the number of test cases to follow. The subsequent lines of input describe the test cases.

Each test case begins with a single line, containing a single integer n expressed in decimal with no leading zeroes, the number of points to follow; each of the following n lines contains two integers x and y, both expressed in decimal with no leading zeroes, giving the coordinates of one of your points.

You are guaranteed that T <= 30 and that no data set contains more than 30 points. All points in each data set will be no more than 500 units away from (0,0).

Output

Print, on a single line with two decimal places of precision, the area of the smallest square containing all of your points. An answer will be accepted if it lies within 0.1 of the correct answer.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
4
-1 -1
1 -1
1 1
-1 1
4
10 1
10 -1
-10 1
-10 -1

Sample Output

1
2
4.00
242.00

Solution

題目描述：

給平面上 N 個點，找到最小面積的正方形覆蓋所有點。

題目解法：

做一次凸包，得到逆時針的點順序，對於每一個凸包頂點進行，使用三分搜索找到相對應的寬。

進行三分搜索的線段為如下圖所示

p11243.png

對於通過 B 點的所有線段，考慮與下一個凸包頂點所夾的角度( < 180 度)，如圖範例所示即三分再 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
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
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
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;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    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 val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
typedef Pt Vector;
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;
}
double distProjection(Pt as, Pt at, Pt s) {
    double a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
struct Seg {
    Pt s, e;
};
int calcIntersection(Seg a, Seg b, Pt &p) {
    double a1, b1, c1, a2, b2, c2;
    double d, dx, dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    d = a1*b2 - a2*b1;
    dx = c1*b2 - c2*b1;
    dy = a1*c2 - a2*c1;
    if(fabs(d) < eps) // NONE or LINE
        return 0;
    p.x = dx / d, p.y = dy / d;
    /*printf("%lf %lf - %lf %lf\n", a.s.x, a.s.y, a.e.x, a.e.y);
    printf("%lf %lf - %lf %lf\n", b.s.x, b.s.y, b.e.x, b.e.y);
    printf("%lf %lf\n", p.x, p.y);*/
    return onSeg(a.s, a.e, p) && onSeg(b.s, b.e, p);
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
           cnt++;
    }
    return cnt&1;
}
double calcArea(Pt p[], int n) {
    if(n < 3)   return 0.0;
    double ret = 0;
    int i;
    p[n] = p[0];
    for(i = 0; i < n; i++)
        ret += p[i].x * p[i+1].y - p[i].y * p[i+1].x;
    return fabs(ret)/2;
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
#define INF 1e+30 
// ternary search
double calcSquare(double m, Pt p, Pt ch[], int n) {
    double a, b, c, lab;
    double w = 0, hl = 0, hr = 0, h;
    a = sin(m), b = -cos(m), c = - (a * p.x + b * p.y), lab = hypot(a, b);
    
    int pp = 0, qq = 0;
    for(int i = 0; i < n; i++) {
        double d = fabs(a * ch[i].x + b * ch[i].y + c) / lab;
        w = max(w, d);
        if(a * ch[i].x + b * ch[i].y + c < - 1e-6)
            pp++;
        if(a * ch[i].x + b * ch[i].y + c > 1e-6)
            qq++;
    }
//	printf("%d %d\n", pp, qq);
    a = cos(m), b = sin(m), c = - (a * p.x + b * p.y), lab = hypot(a, b);
    for(int i = 0; i < n; i++) {
        double d = fabs(a * ch[i].x + b * ch[i].y + c) / lab;
        if(a * ch[i].x + b * ch[i].y + c < 0)
            hl = max(hl, d);
        else
            hr = max(hr, d);
    }
    h = hl + hr;
    return max(w, h) * max(w, h);
}
const double pi = acos(-1);
double ternary_search(double l, double r, Pt p, Pt ch[], int n) {
    double mid, midmid, md, mmd;
    double ret = INF;
    while(fabs(l-r) > eps) {
        mid = (l+r)/2;
        midmid = (mid+r)/2;
        md = calcSquare(mid, p, ch, n);
        mmd = calcSquare(midmid, p, ch, n);
        ret = min(ret, md);
        ret = min(ret, mmd);
        if(md < mmd)
            r = midmid;
        else
            l = mid;
    }
//	printf("best %lf %lf\n", l / pi * 180, ret);
    return ret;
}
double smallSquare(int n, Pt ch[]) {
    double ret = INF;
    
    for(int i = 0, j = n-1; i < n; j = i++) {
//		printf("pt[%lf %lf]\n", ch[i].x, ch[i].y);
        double l = atan2(ch[j].y - ch[i].y, ch[j].x - ch[i].x);
        double r = atan2(ch[(i+1)].y - ch[i].y, ch[(i+1)].x - ch[i].x) - pi;
//		printf("l r [%lf %lf]\n", l, r);
        r = l + fmod(fmod(r - l, 2 * pi) + 2 * pi, 2 * pi);
        if(l <= r) {
            ret = min(ret, ternary_search(l, r, ch[i], ch, n));
        } else {
            ret = min(ret, ternary_search(l, pi, ch[i], ch, n));
            ret = min(ret, ternary_search(-pi, r, ch[i], ch, n));
        }
    }
    return ret;
}
int main() {
    Pt p[2048], ch[2048];
    int n, m;
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%d", &n);
    	for(int i = 0; i < n; i++)
    		scanf("%lf %lf", &p[i].x, &p[i].y);
        m = monotone(n, p, ch);
//        for(int i = 0; i < m; i++)
//        	printf("%lf %lf\n", ch[i].x, ch[i].y);
    	
    	if(m == 1) {
    		printf("%.2lf\n", 0);
    		continue;
    	}
        double ret = smallSquare(m, ch);
        printf("%.2lf\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11215 - How Many Numbers

Problem

You might have heard the game of 24: given 4 integers, you’re to make an expression to get the number 24. For example, given 4, 4, 10, 10, you can write (1010-4)/4=24, given 1, 5, 5, 5, you can write (5-1/5)5=24.

In this problem, your task is a little bit harder: count the number of numbers that can be made. Don’t forget to count negative numbers and non-integers. You can use binary additions, subtractions, multiplications and divisions with parenthesis (unary operations are not allowed). Numbers cannot be concatenated to form a larger number (e.g. you cannot concatenate 1 and 2 to get 12).

For example, given two 1’s, exactly 3 numbers can be made: 1+1=2, 1-1=0, 1*1=1. You cannot get 11 or -1.

Input

The input consists of at most 30 test cases. Each case begins with a line containing a single integer n (1 < n < 7), the number of integers given. The next line contains n non-negative integers not greater than 10. The last case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and the number of numbers that can be made.

Sample Input

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

Output for the Sample Input

1
2
3
Case 1: 3
Case 2: 47
Case 3: 255

Solution

題目描述：

對於給定的數字，考慮所有加減乘除括號的所有計算方案，計算出有多少不同種的運算結果。

題目解法：

類似矩陣鏈乘積，考量每一種排列方式。

對於其中一種排列方式，紀錄狀態 [l, r] 之間所有可能的運算結果，當要合併兩個區間時，枚舉兩個區間的所有可能，並且將其兩兩合併。

[l, r] = [l, k](+-*/)[k+1, r]

使用 double 以為小數點誤差影響不太，但怎麼做都 WA，最後直接用分數的方式進行計算，最後拿了很慢的 AC。

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
#include <stdio.h> 
#include <algorithm>
#include <set>
#include <math.h>
using namespace std;
#define eps 1e-3
struct Fraction {
    long long a, b;
    Fraction(long long x=0, long long y=1) {
        long long g = __gcd(x, y);
        a = x / g;
        b = y / g;
        if(b < 0)	a = -a, b = -b;
    }
    Fraction operator+(const Fraction &x) const {
        return Fraction(a * x.b + x.a * b, b * x.b);
    }
    Fraction operator-(const Fraction &x) const {
        return Fraction(a * x.b - x.a * b, b * x.b);
    }
    Fraction operator*(const Fraction &x) const {
        return Fraction(a * x.a, b * x.b);
    }
    Fraction operator/(const Fraction &x) const {
        return Fraction(a * x.b, b * x.a);
    }
    bool operator<(const Fraction &x) const {
        return a * x.b < b * x.a;
    }
};
int main() {
    int n, cases = 0, A[10];
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        set<Fraction> ret;
        sort(A, A+n);
        do {
            set<Fraction> dp[10][10];
            for(int i = 0; i < n; i++)
                dp[i][i].insert(Fraction(A[i]));
            for(int i = 1; i < n; i++) {
                for(int j = 0; i + j < n; j++) {
                    for(int k = j; k < j+i; k++) {
                        for(set<Fraction>::iterator it = dp[j][k].begin();
                            it != dp[j][k].end(); it++)
                        for(set<Fraction>::iterator jt = dp[k+1][j+i].begin();
                            jt != dp[k+1][j+i].end(); jt++) {
                            Fraction a = *it, b = *jt;
                            dp[j][j+i].insert(a+b);
                            dp[j][j+i].insert(a-b);
                            dp[j][j+i].insert(a*b);
                            if(b.a)
                                dp[j][j+i].insert(a/b);
                        }
                    }
                }
            }
            for(set<Fraction>::iterator it = dp[0][n-1].begin();
                it != dp[0][n-1].end(); it++)
                ret.insert(*it);
        } while(next_permutation(A, A+n));
        printf("Case %d: %d\n", ++cases, ret.size());
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11200 - Sapitaur's labyrinth

Background

In the distant planet Omicron Persei 8, there is a huge ocean of rotten dark water. In the middle of the ocean, there is the island of Nevreturn, where the damned Omicronian prisoners are sent. And on the island, there is an intricate labyrinth; only those prisoners who are able to escape from the labyrinth are given the merciful death. The labyrinth is surrounded by a deep abysm, where the mythical Sapitaur –half frog, half bull– lives, eating all those Omicronians who took a wrong course in the labyrinth.

You are an unfortunate Omicronian prisoner. Will you be able to escape from the labyrinth?
The Problem

Sapitaur’s Labyrinth consists of a matrix of cells. There are two kinds of cells, as shown in the figure below:

  • NOWSE. There is a wall extending from the North-West of the cell to the South-East.

  • NESOW. There is a wall extending from the North-East of the cell to the South-West.

Left: the two kinds of cells. Middle: a sample labyrinth with 3x3 cells, and 2 paths to escape. Right: a labyrinth with 15x10 cells, and only 1 path to escape (in red).

As you can see in the figure above, the entrance to the labyrinth is in the north (the upper row of the matrix), the exit is in the south (the lower row of the matrix), and the abysm extends along both sides of the labyrinth (beyond the first and last column of the matrix).

You have to count how many different paths exist to go from the entrance to the exit of the labyrinth. Obviously, these paths cannot go through the abysm.

The Input

The first line of the input contains an integer M, indicating the number of test cases.

For each test case, the first line contains two integers N M, between 1 and 500, where N is the width of the labyrinth (number of columns) and M is the height (number of rows). M lines follow; each line has N characters: “\” for NOWSE cells; and “/“ for NESOW cells.

The Output

For each test case, the output should consist of an integer indicating the number of different paths from the entrance to the exit of the labyrinth.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3 3
///
\\\
///
15 10
////\\\////\\//
/\\\\\/\/\/\\/\
\\\//\\\/\////\
//\\\/\///\//\\
\/\//\\/\\\\/\\
////////\\///\/
\\\\\\//\\\\\/\
\\/\//////\\///
\/\\/////\/\/\/
\///\///\\\\//\

Sample Output

1
2
2
1

Solution

題目描述：

給定用 \、/ 構成的迷宮，找到從上方進入且可以抵達下方的路徑總數。

題目解法：

這題目看似非常難，由於在建表處理上非常不方便。

但是仔細想想，考慮當前所在的格子類型，再考慮進來的方向，就能推出下一步會到達的格子。
(類似於鏡子反射的現象)

路徑總數不會太多，直接使用 DFS 進行搜索枚舉即可。

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
#include <stdio.h> 
#include <string.h>
char g[512][512];
int ret = 0, n, m;
const int dx[] = {1, 0, -1, 0}; // N, E, S, W
const int dy[] = {0, 1, 0, -1};
void dfs(int x, int y, int fdir) {
    if(x == n)	ret++;
    if(x < 0 || y < 0 || x >= n || y >= m)
        return;
    int dir = 0;
    if(g[x][y] == '\\') {
        switch(fdir) {
            case 0: dir = 1; break;
            case 1: dir = 0; break;
            case 2: dir = 3; break;
            case 3: dir = 2; break;
        }
    } else {
        switch(fdir) {
            case 0: dir = 3; break;
            case 3: dir = 0; break;
            case 1: dir = 2; break;
            case 2: dir = 1; break;
        }
    }
    dfs(x + dx[dir], y + dy[dir], dir);
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &m, &n);
        for(int i = 0; i < n; i++)
            scanf("%s", g[i]);
            
        ret = 0;
        for(int i = 0; i < m; i++)
            dfs(0, i, 0);
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10173 - Smallest Bounding Rectangle

Problem

Given the Cartesian coordinates of n (> 0) 2-dimensional points, write a program that computes the area of their smallest bounding rectangle (smallest rectangle containing all the given points).

Input

The input file may contain multiple test cases. Each test case begins with a line containing a positive integer n (< 1001) indicating the number of points in this test case. Then follows n lines each containing two real numbers giving respectively the x- and y-coordinates of a point. The input terminates with a test case containing a value 0 for n which must not be processed.

Output

For each test case in the input print a line containing the area of the smallest bounding rectangle rounded to the 4th digit after the decimal point.

Sample Input

1
2
3
4
5
6
7
8
9
10
3
-3.000 5.000
7.000 9.000
17.000 5.000
4
10.000 10.000
10.000 20.000
20.000 20.000
20.000 10.000
0

Sample Output

1
2
80.0000
100.0000

Solution

題目描述：

給予平面上 N 個點，找到一個最小矩形覆蓋所有點座標。

題目解法：

做一次單調鏈，得到逆時針的凸包順序，接著第一步找到四邊平行 XY 軸的最小矩形。

接著對於卡邊四邊上的頂點，找到矩形邊與凸包邊夾角最小的頂點，進行向量的旋轉，然後再進行計算矩形的長寬。

對於矩形的長寬，直接套用點線投影公式。

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
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
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;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    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 val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
typedef Pt Vector;
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;
}
double distProjection(Pt as, Pt at, Pt s) {
    double a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
struct Seg {
    Pt s, e;
};
int calcIntersection(Seg a, Seg b, Pt &p) {
    double a1, b1, c1, a2, b2, c2;
    double d, dx, dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    d = a1*b2 - a2*b1;
    dx = c1*b2 - c2*b1;
    dy = a1*c2 - a2*c1;
    if(fabs(d) < eps) // NONE or LINE
        return 0;
    p.x = dx / d, p.y = dy / d;
    /*printf("%lf %lf - %lf %lf\n", a.s.x, a.s.y, a.e.x, a.e.y);
    printf("%lf %lf - %lf %lf\n", b.s.x, b.s.y, b.e.x, b.e.y);
    printf("%lf %lf\n", p.x, p.y);*/
    return onSeg(a.s, a.e, p) && onSeg(b.s, b.e, p);
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
           cnt++;
    }
    return cnt&1;
}
double calcArea(Pt p[], int n) {
    if(n < 3)   return 0.0;
    double ret = 0;
    int i;
    p[n] = p[0];
    for(i = 0; i < n; i++)
        ret += p[i].x * p[i+1].y - p[i].y * p[i+1].x;
    return fabs(ret)/2;
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
#define INF 1e+30 
double smallRect(int n, Pt ch[]) {
    double lx, ly, rx, ry;
    int up, down, left, right;
    double ret = INF;
    lx = ly = INF;
    rx = ry = -INF;
    
    up = down = left = right = 0;
    for(int i = 0; i < n; i++) {
        if(ch[i].x > rx)	rx = ch[i].x, right = i;
        if(ch[i].y > ry)	ry = ch[i].y, up = i;
        if(ch[i].x < lx)	lx = ch[i].x, left = i;
        if(ch[i].y < ly)	ly = ch[i].y, down = i;
    }
    
    int corner[] = {up, down, left, right};
    Pt vec[] = {Pt(-1, 0), Pt(1, 0), Pt(0, -1), Pt(0, 1)};
    
    ret = (rx - lx) * (ry - ly);
    for(int j = 0; j < 4; j++) {
        while(true) {
            Pt a = ch[corner[j]], b = ch[(corner[j]+1)%n], c = vec[j];
            if(fabs(cross2(b - a, c)) < eps)
                corner[j] = (corner[j] + 1)%n;
            else
                break;
        }
    }
//	for(int j = 0; j < 4; j++) {
//		Pt a = ch[corner[j]], b = vec[j];
//		printf("Pt[%lf %lf], Vector[%lf %lf]\n", a.x, a.y, b.x, b.y);
//	}	
    for(int i = 0; i < n; i++) {
        double mxVal = -INF, cos, sin;
        int mxIdx = 0;
        for(int j = 0; j < 4; j++) {
            Pt a = ch[corner[j]], b = ch[(corner[j]+1)%n], c = vec[j];
            double cosA = dot(b - a, c) / dist(b, a) / dist(c, Pt(0, 0));
            if(mxVal < cosA)
                mxVal = cosA, mxIdx = j;
//			printf("cos %lf\n", cosA);
        }
        cos = mxVal, sin = sqrt(1 - cos * cos);
//		printf("sin %lf cos %lf\n", sin, cos);
        for(int j = 0; j < 4; j++) {
            double tx, ty;
            tx = vec[j].x * cos - vec[j].y * sin;
            ty = vec[j].x * sin + vec[j].y * cos;
            vec[j] = Pt(tx, ty);
//			printf("%lf %lf\n", tx, ty);
        }
//		for(int j = 0; j < 4; j++) {
//			Pt a = ch[corner[j]], b = vec[j];
//			printf("Pt[%lf %lf], Vector[%lf %lf]\n", a.x, a.y, b.x, b.y);
//		}		
        for(int j = 0; j < 4; j++) {
            while(true) {
                Pt a = ch[corner[j]], b = ch[(corner[j]+1)%n], c = vec[j];
                if(fabs(cross2(b - a, c)) < eps)
                    corner[j] = (corner[j] + 1)%n;
                else
                    break;
            }
        }
        double w = distProjection(ch[corner[0]], ch[corner[0]]+vec[0], ch[corner[1]]);
        double h = distProjection(ch[corner[2]], ch[corner[2]]+vec[2], ch[corner[3]]);
//		printf("w %lf h %lf area %lf\n\n", w, h, w * h);
        ret = min(ret, w * h);
    }
    return ret;
}
int main() {
    Pt p[2048], ch[2048];
    int n, m;
    int testcase, cases = 0;
    while(scanf("%d", &n) == 1 && n) {
    	for(int i = 0; i < n; i++)
    		scanf("%lf %lf", &p[i].x, &p[i].y);
        m = monotone(n, p, ch);
//        for(int i = 0; i < m; i++)
//        	printf("%lf %lf\n", ch[i].x, ch[i].y);
    	
    	if(m < 3) {
    		printf("%.4lf\n", 0);
    		continue;
    	}
        double ret = smallRect(m, ch);
        printf("%.4lf\n", ret);
    }
    return 0;
}
Read More +