2014-08-02

UVa 12436 - Rip Van Winkle's Code

long long data[250001];
void A( int st, int nd ) {
    for( int i = st; i <= nd; i++ ) data[i] = data[i] + (i - st + 1);
}
void B( int st, int nd ) {
    for( int i = st; i <= nd; i++ ) data[i] = data[i] + (nd - i + 1);
}
void C( int st, int nd, int x ) {
    for( int i = st; i <= nd; i++ ) data[i] = x;
}
long long S( int st, int nd ) {
    long long res = 0;
    for( int i = st; i <= nd; i++ ) res += data[i];
    return res;
}

Input

The first line of input will contain T (≤ 4*105) denoting the number of operations. Each of the next T lines starts with a character (‘A’, ‘B’, ‘C’ or ‘S’), which indicates the type of operation. Character ‘A’, ‘B’ or ‘S’ will be followed by two integers, st and nd in the same line. Character ‘C’ is followed by three integers, st, nd and x. It’s assumed that, 1 ≤ st ≤ nd ≤ 250000 and -105 ≤ x ≤ 105. The meanings of these integers are explained by the code of Rip Van Winkle.

Output

For each line starting with the character ‘S’, print S( st, nd ) as defined in the code. Dataset is huge, so use faster I/O methods.

Sample Input

Output for Sample Input

1
2
3

9
0
3

Solution

紀錄該區間的首項和公差即可，保證公差可以疊加。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 262144
#define MAXM 1048576 + 10 
typedef long long LL;
LL sum[MAXM];
LL preB[MAXM], preD[MAXM]; // base, diff
LL sufB[MAXM], sufD[MAXM];
LL setB[MAXM], setD[MAXM];
void pushUp(int k) {
    sum[k] = sum[k<<1] + sum[k<<1|1];
}
void pushDown(int k, int l, int r) {
    int m = (l + r) /2;
    
    if(setB[k]) {
        setB[k<<1] = 1, setD[k<<1] = setD[k];
        setB[k<<1|1] = 1, setD[k<<1|1] = setD[k];
        preB[k<<1] = preD[k<<1] = sufB[k<<1] = sufD[k<<1] = 0;
        preB[k<<1|1] = preD[k<<1|1] = sufB[k<<1|1] = sufD[k<<1|1] = 0;
        sum[k<<1] = (m - l + 1) * setD[k];
        sum[k<<1|1] = (r - m) * setD[k];
        setB[k] = setD[k] = 0;
    }
    if(preB[k]) {
        preB[k<<1] += preB[k], preD[k<<1] += preD[k];
        preB[k<<1|1] += preB[k] + preD[k] * (m - l + 1), preD[k<<1|1] += preD[k];
        sum[k<<1] += (2 * preB[k] + (m - l) * preD[k]) * (m - l + 1)/2;
        sum[k<<1|1] += (2 * preB[k] + (r - l + m + 1 - l) * preD[k]) * (r - m)/2;
        preB[k] = preD[k] = 0;
    }
    if(sufB[k]) {
        sufB[k<<1] += sufB[k] + (r - m) * sufD[k], sufD[k<<1] += sufD[k];
        sum[k<<1] += (2 * sufB[k] + (r - m + r - l) * sufD[k]) * (m - l + 1)/2;
        sufB[k<<1|1] += sufB[k], sufD[k<<1|1] += sufD[k];
        sum[k<<1|1] += (2 * sufB[k] + (r - m - 1) * sufD[k]) * (r - m)/2;
//		printf("[%d %d] suffix %lld %lld , = %lld %lld\n", l, r, sufB[k], sufD[k], sum[k<<1], sum[k<<1|1]);
        sufB[k] = sufD[k] = 0;
    }
}
void modifyA(int k, int l, int r, int x, int y) {
    if(l > r)	return;
    if(x <= l && r <= y)  {
        preB[k] += l - x + 1, preD[k]++;
        sum[k] += (LL)(2 * (l - x + 1) + r - l) * (r - l + 1)/2;
        return;
    }
    pushDown(k, l, r);
    int m = (l+r) /2;
    if(y <= m)
        modifyA(k<<1, l, m, x, y);
    else if(x > m)
        modifyA(k<<1|1, m+1, r, x, y);
    else {
        modifyA(k<<1, l, m, x, y);
        modifyA(k<<1|1, m+1, r, x, y);
    }
    pushUp(k);
}
void modifyB(int k, int l, int r, int x, int y) {
    if(l > r)	return;
    pushDown(k, l, r);
    if(x <= l && r <= y)  {
        sufB[k] += y - r + 1, sufD[k]++;
        sum[k] += (LL)(2 * (y - r + 1) + r - l) * (r - l + 1)/2;
//		printf("BB [%d %d] %d\n", l, r, base);
        return;
    }
    int m = (l+r) /2;
    if(y <= m)
        modifyB(k<<1, l, m, x, y);
    else if(x > m)
        modifyB(k<<1|1, m+1, r, x, y);
    else {
        modifyB(k<<1, l, m, x, y);
        modifyB(k<<1|1, m+1, r, x, y);
    }
    pushUp(k);
}
void modifyC(int k, int l, int r, int x, int y, int mm) {
    if(l > r)	return;
    if(x <= l && r <= y)  {
        setB[k] = 1, setD[k] = mm;
        preB[k] = preD[k] = sufB[k] = sufD[k] = 0;
        sum[k] = (LL)mm * (r - l + 1);
//		printf("CCCC [%d %d] %lld\n", l, r, sum[k]);
        return;
    }
    pushDown(k, l, r);
    int m = (l+r) /2;
    if(y <= m)
        modifyC(k<<1, l, m, x, y, mm);
    else if(x > m)
        modifyC(k<<1|1, m+1, r, x, y, mm);
    else {
        modifyC(k<<1, l, m, x, y, mm);
        modifyC(k<<1|1, m+1, r, x, y, mm);
    }
    pushUp(k);
}
long long query(int k, int l, int r, int x, int y) {
    if(l > r)	return 0;
    pushDown(k, l, r);
    if(x <= l && r <= y) {
//		printf("qq[%d %d] %lld\n", l, r, sum[k]);
        return sum[k];
    }
    int m = (l + r)/2;
    long long ret = 0;
    if(x <= m)
        ret += query(k<<1, l, m, x, y);
    if(y > m)
        ret += query(k<<1|1, m+1, r, x, y);
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int T, st, nd, x;
    char cmd[128];
    while(scanf("%d", &T) == 1) {
        memset(sum, 0, sizeof(sum));
        memset(preB, 0, sizeof(preB));
        memset(preD, 0, sizeof(preD));
        memset(sufB, 0, sizeof(sufB));
        memset(sufD, 0, sizeof(sufD));
        memset(setB, 0, sizeof(setB));
        memset(setD, 0, sizeof(setD));
        while(T--) {
            scanf("%s", cmd);
            if(cmd[0] == 'C')
                scanf("%d %d %d", &st, &nd, &x);
            else
                scanf("%d %d", &st, &nd);
            switch(cmd[0]) {
                case 'A':
                    modifyA(1, 1, MAXN, st, nd);
                    break;
                case 'B':
                    modifyB(1, 1, MAXN, st, nd);
                    break;
                case 'C':
                    modifyC(1, 1, MAXN, st, nd, x);
                    break;
                case 'S':
                    long long ret = query(1, 1, MAXN, st, nd);
                    printf("%lld\n", ret);
                    break;
            }
        } 
    }
    return 0;
}
/*
1000
S 2 3
A 7 15
B 4 5
B 15 16
C 2 10 3
B 14 15
A 10 18
S 4 4
A 3 16
B 6 14
B 4 7
S 8 11
*/

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 12396 - Remoteland

Problem

求 N! 的因數中最大的完全平方數。

Sample Input

Sample Output

1
2
3

4
177582252
644064736

Solution

對 N! 做因數分解。

#include <stdio.h> 
#include <algorithm>
using namespace std;
#define maxL (10000000>>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[1048576], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 10000000;
    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; 
        }
    }
}
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while(y) {
        if(y&1)
            ret *= x, ret %= mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret;
}
int main() {
    sieve();
    int n;
    const long long mod = 1000000007LL;
    while(scanf("%d", &n) == 1 && n) {
        long long ret = 1;
        for(int i = 0; i < Pt; i++) {
            long long p = P[i], cnt = 0;
            while(p <= n)
                cnt += n / p, p *= P[i];
            if(cnt < 2)	break;
            ret *= mpow(P[i], cnt/2*2, mod);
            ret %= mod;
        } 
        printf("%lld\n", ret);
    }
    return 0;
}

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 12368 - Candles

Problem

現在只有 0 - 9 共計 10 根蠟燭，有 N 個人過生日，每個人的生日年紀不大於 100。

最多用 10 根蠟燭，來表示每一個人的生日。每個人的生日可以用兩個整數加總，或者單純用一個整數表示。

Sample Input

1
2
3

2 10 11
1 30
0

Output for Sample Input

1 2	Case 1: 654 Case 2: 30

Solution

預建表，找到所有數字 [1, 100] 能用哪幾種蠟燭建出來。

測資很緊，不建表會一直 TLE。

#include <stdio.h> 
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
int able[128][1024];
void build() {
    int d1, d2, d3, d4;
    for(int i = 1; i <= 100; i++) {
        if(i < 100) {
            if(i < 10) {
                d1 = i;
                able[i][1<<d1] = 1;
            } else {
                d1 = i%10, d2 = i/10;
                if(d1 != d2)
                    able[i][(1<<d1)|(1<<d2)] = 1;
            }
        }
        for(int j = 1; j < i; j++) {
            int a = j, b = i - j, mask = 0;
            if(a < 10) {
                mask |= 1<<a;
            } else {
                d1 = a%10, d2 = a/10;
                if(d1 == d2)
                    continue;
                mask |= (1<<d1)|(1<<d2);
            }
            if(b < 10) {
                if(mask&(1<<b))
                    continue;
                mask |= 1<<b;
            } else {
                d1 = b%10, d2 = b/10;
                if(d1 == d2)
                    continue;
                if(mask&((1<<d1)|(1<<d2)))
                    continue;
                mask |= (1<<d1)|(1<<d2);
            }
            able[i][mask] = 1;
        }
    }
    for(int i = 0; i < 128; i++) {
        for(int j = 0; j < 1024; j++) {
            for(int k = j; k; k = k&(k-1))
                able[i][j] |= able[i][j&(k-1)];
        }
    }
}
int main() {
    build();
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    int n, A[10], cases = 0;
    while(scanf("%d", &n) == 1 && n) {
        map<int, int> R;
        for(int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        int ret = (1<<10)-1;
        for(int i = 0; i < (1<<10); i++) {
            if(__builtin_popcount(i) >= __builtin_popcount(ret))
                continue;
            int f = 1;
            for(int j = 0; j < n && f; j++)
                f &= able[A[j]][i];
            if(f) {
                ret = i;		
            }
        }							
        printf("Case %d: ", ++cases);
        for(int i = 9; i >= 0; i--) {
            if((ret>>i)&1)
                printf("%d", i);
        }
        puts("");
    }
    return 0;
}

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 12363 - Hedge Mazes

Problem

給一無向圖，問任兩點是否存在唯一的路徑到達。

Sample Input

Sample Output

Y
N
N
-
N
Y
Y
-

Solution

唯一路徑，保證 x - y 之間走過的只會有橋 (由很多橋構成)，將所有橋找到，並且將橋兩端利用并查集合併 (構成大橋)

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[131072];
int visited[131072], depth[131072];
vector< pair<int, int> > bridge;
int findBridge(int u, int p, int dep) {
    visited[u] = 1, depth[u] = dep;
    int back = 0x3f3f3f3f;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(v == p)	continue;
        if(!visited[v]) {
            int b = findBridge(v, u, dep+1);
            if(b > dep) {
                bridge.push_back(make_pair(u, v));
            }
            back = min(back, b);
        } else {
            back = min(back, depth[v]);
        }
    }
    return back;
}
int rank[131072], parent[131072];
int findp(int x) {
    return parent[x] == x ? x : parent[x]=findp(parent[x]);
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)	return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], parent[y] = x;
    else
        rank[y] += rank[x], parent[x] = y;
}
int main() {
    int n, m, q, x, y;
    while(scanf("%d %d %d", &n, &m, &q) == 3 && n+m) {
        for(int i = 0; i < n; i++)
            g[i].clear();
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        
        bridge.clear();
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                findBridge(i, -1, 0);
            }
        }
        
        for(int i = 0; i < n; i++)
            rank[i] = 1, parent[i] = i;
        for(int i = 0; i < bridge.size(); i++)
            joint(bridge[i].first, bridge[i].second);
        for(int i = 0; i < q; i++) {
            scanf("%d %d", &x ,&y);
            x--, y--;
            puts(findp(x) == findp(y) ? "Y" : "N");
        }
        puts("-");
    }
    return 0;
}

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 12365 - Jupiter Atacks

Problem

查詢區間 hash 值、支持修改單一元素。

Sample Input

20 139 5 7
E 1 12
E 2 14
E 3 2
E 4 2
E 5 4
H 2 5
E 2 14
10 1000003 6 11
E 1 3
E 2 4
E 3 5
E 4 6
E 5 7
E 6 8
H 1 6
E 3 0
E 3 9
H 1 3
H 4 6
999999935 999999937 100000 7
E 100000 6
E 1 7
H 1 100000
E 50000 8
H 1 100000
H 25000 75000
H 23987 23987
0 0 0 0

Sample Output

Solution

線段樹套用

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long B, P; 
long long tree[262144 + 10], shiftP[131072 + 10];
void modify(int k, int l, int r, int x, int val) {
    if(l > r)	return;
    if(l == r) {
        tree[k] = val;	return ;
    }
    int m = (l + r)>>1;
    if(x <= m)	
        modify(k<<1, l, m, x, val);
    else		
        modify(k<<1|1, m+1, r, x, val);
    tree[k] = (tree[k<<1]*shiftP[r - m] + tree[k<<1|1])%P;
}
long long query(int k, int l, int r, int x, int y) {
    if(l > r)	return 0;
    if(x <= l && r <= y) {
        return tree[k]*shiftP[y - r];
    }
    int m = (l + r)>>1;
    long long ret = 0;
    if(x <= m)
        ret += query(k<<1, l, m, x, y);
    if(y > m)
        ret += query(k<<1|1, m+1, r, x, y);
    return ret%P;
}
int main() { 
    char cmd[1024];
    int a, b, n, q;
    while(scanf("%lld %lld %d %d", &B, &P, &n, &q) == 4 && n) {
        shiftP[0] = 1;
        for(int i = 1; i <= n; i++)
            shiftP[i] = (shiftP[i - 1] * B)%P;
        memset(tree, 0, sizeof(tree));
        while(q--) {
            scanf("%s %d %d", cmd, &a, &b);
            if(cmd[0] == 'E')
                modify(1, 1, n, a, b);
            else
                printf("%lld\n", query(1, 1, n, a, b));
        }
        puts("-");
    }
    return 0;
}

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 12357 - Ball Stacking

Problem

給一個球球堆起的三角堆，抽走一顆球或者使其他球滑落到其他地方 (失去支撐)，則所有落下、拿走的球將會是得到的分數。求最多能獲得多少分數。

Sample Input

Sample Output

1
2
3

7
0
6

Solution

面對三角堆，我們由左往右、由上而下考慮是否要將球移開，而這麼做很容易得到一個 O(n^3) 的做法，利用輔助數據壓縮在 O(n^2) 完成 (因為中間有一段迴圈是找後綴最大值)。

轉移的時候也很簡單，考慮兩種情況

只考慮移除自己的時候落下的所有球
考慮與前一列別處拿走所產生的交集情況

在第二種可以發現，如果考慮左側高於自己的球球被移除的情況可以忽略不計。

#include <stdio.h> 
#include <string.h>
#include <algorithm> 
using namespace std;
int g[1024][1024] = {}, w[1024][1024] = {};
int dp[1024][1024] = {}, sdp[1024][1024] = {};
int main() {
    int n;
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                scanf("%d", &g[i][j]);
                g[i][j] += g[i-1][j];
            }
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= i; j++)
                w[i][j] = g[i][j] + w[i-1][j-1];
        int ret = 0;
        memset(dp, 0, sizeof(dp));
        for(int j = 1; j <= n; j++) {
            for(int i = j; i <= n; i++) {
                dp[i][j] = w[i][j];
//				for(int k = i-1; k <= n; k++)
//					dp[i][j] = max(dp[i][j], dp[k][j-1] + g[i][j]);
                dp[i][j] = max(dp[i][j], sdp[i-1][j-1] + g[i][j]);
                ret = max(ret, dp[i][j]);
            }
            sdp[n][j] = dp[n][j];
            for(int i = n - 1; i >= j; i--)
                sdp[i][j] = max(sdp[i+1][j], dp[i][j]);
        }
        printf("%d\n", ret);
    } 
    return 0;
}

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 12338 - Anti-Rhyme Pairs

Problem

給一堆單詞，問任意兩個單詞的最常共同前綴長為何。

Sample Input

2
5
daffodilpacm
daffodiliupc
distancevector
distancefinder
distinctsubsequence
4
1 2
1 5
3 4
4 5
2
acm
icpc
2
1 2
2 2

Output for Sample Input

Case 1:
8
1
8
4
Case 2:
0
4

Solution

對每一個單詞插入到 Trie 中，詢問任兩個字串的最長共同前綴時，相當於詢問兩個節點之間的最小共同祖先距離根多遠。

解決 LCA 問題，這裡採用離線 tarjan 做法。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Trie {
    int n, label, dist;
    int link[26];
} Node[1048576];
int TrieSize;
int insertTrie(const char* str) {
    static int i, idx;
    for(i = idx = 0; str[i]; i++) {
        if(Node[idx].link[str[i]-'a'] == 0) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[TrieSize].label = TrieSize;
            Node[TrieSize].dist = i + 1;
            Node[idx].link[str[i]-'a'] = TrieSize;
        }
        idx = Node[idx].link[str[i]-'a'];
    }
    Node[idx].n ++;
    return Node[idx].label;
}
vector< pair<int, int> > Q[1048576];// query pair, v - input index.
int visited[1048576], F[1048576];
int LCA[1048576];//input query answer buffer.
int findF(int x) {
    return F[x] == x ? x : (F[x]=findF(F[x]));
}
void tarjan(int u) {// rooted-tree.
    F[u] = u;
    for(int i = 0; i < 26; i++) {//son node.
        int v = Node[u].link[i];
    	if(v == 0)	continue;
        tarjan(v);
        F[findF(v)] = u;
    }
    visited[u] = 1;
    for(int i = 0; i < Q[u].size(); i++) {
        if(visited[Q[u][i].second]) {
            LCA[Q[u][i].first] = findF(Q[u][i].second);
        }
    }
}
int main() {
    int testcase, cases = 0, x, y, n;
    int mp[131072];
    char s[32767];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        TrieSize = 0;
        memset(&Node[0], 0, sizeof(Node[0]));
        for(int i = 1; i <= n; i++) {
        	scanf("%s", s);
        	int x = insertTrie(s);
        	mp[i] = x;
        }
        scanf("%d", &n);
        
        for(int i = 0; i <= TrieSize; i++)
            visited[i] = 0, Q[i].clear();
        for(int i = 0; i < n; i++) {
        	scanf("%d %d", &x, &y);
        	Q[mp[x]].push_back(make_pair(i, mp[y]));
        	Q[mp[y]].push_back(make_pair(i, mp[x]));
        }
        tarjan(0);
        printf("Case %d:\n", ++cases);
        for(int i = 0; i < n; i++) {
            printf("%d\n", Node[LCA[i]].dist);
        }
    }
    return 0;
}

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 12316 - Sewing Buttons with Grandma

Problem

有 N 種不同顏色的鈕扣，每一種燈泡分別有 $n_{i}$ 個，請問拿 M 個鈕扣獲得的組合類型有多少種。

Sample Input

Sample Output

1
2
3

3
7
0

Solution

組合問題，相當於計算以下式子的整數解。

$$x_{1} + x_{2} + x_{3} + .. + x_{n} = M \\ 0 \le x_{i} \le n_{i}$$

事實上，利用 dp[i][j] 表示考慮前 i 種湊出 j 個組合數，得到 dp[i][j + k] += dp[i - 1][j] * C[j + 1 + k][k] 加入新種類的鈕扣。

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        BigInteger[][] C = new BigInteger[128][128];
        for (int i = 0; i < 128; i++)
            for (int j = 0; j < 128; j++)
                C[i][j] = BigInteger.ZERO;
        for (int i = 1; i < 128; i++) {
            C[i][0] = BigInteger.ONE;
            for (int j = 1; j <= i; j++)
                C[i][j] = C[i - 1][j].add(C[i - 1][j - 1]);
        }
        Scanner cin = new Scanner(System.in);
        int n, m;
        int[] A = new int[128];
        while (cin.hasNext()) {
            n = cin.nextInt();
            m = cin.nextInt();
            if (n + m == 0)
                break;
            for (int i = 1; i <= m; i++)
                A[i] = cin.nextInt();
            BigInteger[][] dp = new BigInteger[128][128];
            for (int i = 0; i < 128; i++)
                for (int j = 0; j < 128; j++)
                    dp[i][j] = BigInteger.ZERO;
            dp[0][0] = BigInteger.ONE;
            for (int i = 1; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    for (int k = 0; k <= A[i] && j + k <= n; k++)
                        dp[i][j + k] = dp[i][j + k].add(dp[i - 1][j]
                                .multiply(C[j + k + 1][k]));
                }
            }
            System.out.println(dp[m][n]);
        }
    }
}

附上一個 C++ 的版本，由於沒有使用 BigInteger 而 Wrong Answer.

#include <stdio.h> 
long long C[128][128], A[128];
int main() {
    for(int i = 1; i < 128; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
    int n, m;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        for(int i = 1; i <= m; i++)
            scanf("%lld", &A[i]);
        long long dp[128][128] = {};
        
        dp[0][0] = 1;
        for(int i = 1; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                for(int k = 0; k <= A[i] && j + k <= n; k++)
                    dp[i][j + k] += dp[i - 1][j] * C[j + 1 + k][k];
            }
        }
        printf("%lld\n", dp[m][n]);
    }
    return 0;
}

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 12302 - Nine-Point Circle

Problem

給三角形三點座標，求通過三高三點和三邊中點的圓為何？

Sample Input

1 2	0 0 10 0 3 4 -1 -1 -1 -1 -1 -1

Output for the Sample Input

1	4.000000 2.312500 2.519456

Solution

直接對三邊中點做外心即可。

#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double a) const {
        return Pt(x/a, y/a);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dist2(Pt a, Pt b) {
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
    a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
Pt circle(Pt a, Pt b, Pt c) {
    Pt mab = (a + b)/2;
    Pt mbc = (b + c)/2;
    Pt lab = b - a, lbc = c - b;
    swap(lab.x, lab.y);
    swap(lbc.x, lbc.y);
    lab.x = -lab.x;
    lbc.x = -lbc.x;
    return getIntersection(mab, lab, mbc, lbc);
}
int main() {
    Pt a, b, c, o;	
    while(true) {
        scanf("%lf %lf", &a.x, &a.y);
        scanf("%lf %lf", &b.x, &b.y);
        scanf("%lf %lf", &c.x, &c.y);
        if(a.x < 0)	break;
        o = circle((a + b)/2, (b + c)/2, (c + a)/2);
        printf("%lf %lf %lf\n", o.x, o.y, dist(o, (a + b)/2));
    }
    return 0;
}

Read More +

2014-08-02

解題區/解題區 - UVa

UVa 12300 - Smallest Regular Polygon

Problem

二維平面中，給兩個點座標，以及一個 N，找到一個正 N 邊形，邊上通過這兩個點座標。求該正 N 邊形的最小面積為何？

Sample Input

Output for the Sample Input

1
2
3

1.000000
5.257311
5.196152

Solution

最小面積的正 N 邊形，保證通過兩點一定在正 N 邊行的兩個頂點，而不會出現在邊上。

分開討論奇偶數，奇數直接是對角線，偶數則偏離一點。找到兩點與圓心(正 N 邊形外接圓)拉出的三角形，根據張開的角度計算外接圓的半徑即可。

#include <stdio.h>
#include <math.h>
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double a) const {
        return Pt(x/a, y/a);
    }
    int read() {
    	return scanf("%lf %lf", &x, &y);
    }
};
int main() {
    Pt A, B;
    const double pi = acos(-1); 
    int n;
    while(true) {
        A.read(), B.read(), scanf("%d", &n);
        if(n == 0)	break;
        double r, dist = hypot(A.x - B.x, A.y - B.y);
        if(n%2 == 0) {
            r = dist /2;
        } else {
            int m = (n - 1)/2;
            r = dist /2 / sin((double)m/2.0/n * 2 * pi);
        }
        printf("%lf\n", r * r * sin(2 * pi/n) * n/2);
    }
    return 0;
}

Read More +