2014-07-31

UVa 997 - Show the Sequence

The problem of finding the next term of a given sequence of numbers is usually proposed in QI tests. We want to generate the N terms of a sequence from a given codification of the sequence.

Let S = (Si)i $\scriptstyle \in$$\scriptstyle \mathbb {N}$ denote a sequence of real numbers whose i -order term is Si . We codify a constant sequence with the following operator:

S = [ n] meaning that Si = n $\displaystyle \forall$i$\displaystyle \in$$\displaystyle \mathbb {N}$,

where n$\in$$\mathbb {Z}$ . We also define the following operators on a given sequence of numbers S = (Si)i $\scriptstyle \in$$\scriptstyle \mathbb {N}$ :

V = [ m + S ] meaning that
$Vi = \displaystyle \cases{m & , $i=1$ \cr V{i-1}+ S{i-1} & , $i > 1$ \cr}; $

V = [ m * S ] meaning that
$Vi = \displaystyle \cases{m \ast S_{1} & , $i=1$ \cr V_{i-1} \ast S_i & , $i > 1$ \cr}; $

where m$\in$$\mathbb {N}$ . For example we have the following codifications:

[2 + [1]] = 2, 3, 4, 5, 6 ... 	
[1 + [2 + [1]]] = 1, 3, 6, 10, 15, 21, 28, 36 ...
[2 * [1 + [2 + [1]]]] = 2, 6, 36, 360, 5400, 113400 ...
[2 * [5 + [- 2]]] = 10, 30, 30, -30, 90, -450, 3150 ...

Given a codification, the problem is to write the first N terms of the sequence.

Input

The input file contains several test cases. For each of them, the program input is a single line containing the codification, without any space, followed by an integer N(2$\le$N$\le$50) .

Output

For each test case, the program output is a single line containing the list of first N terms of the sequence.

Sample Input

1 2	[2+[1]] 3 [2*[5+[-2]]] 7

Sample Output

1 2	2 3 4 10 30 30 -30 90 -450 3150

Solution

遞迴建造

#include <stdio.h> 
#include <string.h>
long long a[128];
void parsing(char s[]) {
    int sign = 1, i, m = 0;
    char pos;
    for(i = 1; s[i]; i++) {
        if(s[i] == '-')	sign = -1;
        else if(s[i] >= '0' && s[i] <= '9') 
            m = m * 10 + s[i] - '0';
        else {
            pos = s[i];
            break;
        }
    }
    m = sign * m;
    if(pos == '+') {
        parsing(s + i + 1);
        long long d = a[0];
        a[0] = m;
        for(int i = 1; i < 50; i++) {
            long long t = a[i];
            a[i] = a[i - 1] + d, d = t;
        }
    } else if(pos == '*') {
        parsing(s + i + 1);
        a[0] *= m;
        for(int i = 1; i < 50; i++)
            a[i] = a[i] * a[i-1];
    } else {
        for(int i = 0; i < 50; i++)
            a[i] = m;
    }
}
int main() {
    char s[1024];
    int n;
    while(scanf("%s %d", s, &n) == 2) {
        memset(a, 0, sizeof(a));
        parsing(s);
        for(int i = 0; i < n; i++)
            printf("%lld%c", a[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}
/*
[2+[1]] 3
[2*[5+[-2]]] 7
*/

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 995 - Super Divisible Numbers

Problem

For example, 22203014 is a base-4 super divisible number because 24 is divisible by 1, 224 is divisible by 2, 2224 is divisible by 3, 22204 is divisible by 4, 222034 is divisible by 5, 2220304 is divisible by 6, and 22203014 is divisible by 7.

Find the largest super divisible number of a given base which uses only digits from a given list of digits.

基底為 B 的數字 N 前綴長度 i 必需被 i 整除，找到一個最大符合條件的數字。同時會限用哪幾種 digit。

Sample Input

1 2	4 0123 10 010011

Sample Output

1 2	2220301 10

Solution

感謝天祥大大的指導，一度以為非常多解，因此逼不得以要用 dp 運行，但是仔細想想狀態太大，也無法計算。

根據窮舉的方式可以發現到，每一次窮舉時，假使前一次 mod i = X，則為了要使得 X + ? = 0 (mod i) 則 ? 的地方能填入的數字個數相當於 2 * i <= B 的解，因此答案的數量是相當少的，也就是說最多為 (B/i)! 種可能，撇開不可運行的分枝，其實符合這個條件的數字相當少。

#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int B, valid[16], path[128];
vector<string> ret[128];
void dfs(int idx) {
    for(int i = idx == 0; i < B; i++) {
        if(!valid[i])	continue;
        path[idx] = i;
        int f = 0;
        for(int j = 0; j <= idx; j++)
            f = (f * B + path[j])%(idx+1);
        if(f == 0) {
            string s = "";
            for(int j = 0; j <= idx; j++)
                s += (path[j] + '0');
            ret[s.length()].push_back(s);
            dfs(idx+1);
        }
    }
}
int main() {
    char s[1024];
    while(scanf("%d %s", &B, &s) == 2) {
        memset(valid, 0, sizeof(valid));
        for(int i = 0; i < 128; i++)
            ret[i].clear();
        for(int i = 0; s[i]; i++)
            valid[s[i]-'0'] = 1;
        dfs(0);
        for(int i = 127; i >= 0; i--) {
            if(ret[i].size()) {
                sort(ret[i].begin(), ret[i].end());
                printf("%s\n", ret[i][ret[i].size()-1].c_str());
                break;
            }
        }
    }
    return 0;
}

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 979 - The Abominable Triangleman

Problem

簡化版本的 UVA 10206 - Stars，這一題只求三角形之間的情況，並且只需要考慮相同大小、可能會任意地旋轉或者是翻轉 (鏡射)。

找到一個解輸出即可。

Sample Input

Sample Output

1
2
3

5 17
10 5
15 20

Solution

窮舉一條三角形上的邊當作 AB 邊，利用向量旋轉找到 C 點位置，查閱 C 點位置是否有存在於輸入的點集合中。

#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        if(fabs(y-a.y) > eps)
        	return y < a.y;
        return false;
    }
    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);
    }
    Pt operator*(const double a) const {
        return Pt(x *a, y *a);
    }
    int in() {
    	return scanf("%lf %lf", &x, &y) == 2;
    }
};
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);
}
int main() {
    Pt A, B, C, D[2048];
    int N, cases = 0;
    while(A.in() && B.in() && C.in()) {
        scanf("%d", &N);
        set<Pt> S;
        for(int i = 0; i < N; i++)
            D[i].in(), S.insert(D[i]);
        if(cases++)	puts("");
        double AB = dist2(A, B), BC = dist2(B, C), sqrAB = dist(A, B), sqrBC = dist(B, C);
        double aABC = angle(A - B, C - B);
        sort(D, D + N);
        
        vector<Pt> ret;
        for(int i = 0; i < N; i++) {
            for(int j = i+1; j < N; j++) {
                if(AB < (D[j].x - D[i].x) * (D[j].x - D[i].x))
                    break;
                if(fabs(AB - dist2(D[i], D[j])) < eps) {
//					printf("%lf %lf %lf %lf\n", D[i].x, D[i].y, D[j].x, D[j].y);
                    Pt vBC, tc;
                    vBC = rotateRadian(D[i] - D[j], +aABC) * (sqrBC/sqrAB);
                    tc = D[j] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }
                    
                    vBC = rotateRadian(D[i] - D[j], -aABC) * (sqrBC/sqrAB);
                    tc = D[j] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }					
                    
                    vBC = rotateRadian(D[j] - D[i], +aABC) * (sqrBC/sqrAB);
                    tc = D[i] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }
                    
                    vBC = rotateRadian(D[j] - D[i], -aABC) * (sqrBC/sqrAB);
                    tc = D[i] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }
                }
            }
        }
        if(ret.size()) {
            sort(ret.begin(), ret.end());
            for(int i = 0; i < 3; i++) {
                printf("%.0lf %.0lf\n", ret[i].x, ret[i].y);
            }
        }
    }
    return 0;
}
/*
5 15
8 5
20 10
6
5 17
5 20
20 5
10 5
15 20
15 10
*/

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 970 - Particles

Problem

化合物只會有有三種 X, Y, Z，並且兩兩化合最多也只會是這三種。每次化合只能拿相鄰的進行化合，求最後能化合出的最大化合物為何 Z > Y > X？

Sample Input

1
2

1
ZYX

Sample Output

Solution

使用矩陣鍊乘積的 dp 方法，將可以在 O(n^3) 時間內完成，但是由於測資量龐大，單純的 O(n^3) 很容易 TLE，利用剪枝的方式，若已經完成所有可能情況的化合則停止。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    int table[3][3] = { {1,0,2},{0,1,1},{2,1,0} };
    char s[1024];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%s", s);
        int dp[128][128][3] = {}, n = strlen(s);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j + i < n; j++) {
                for(int k = j; k < j + i; k++) {
                    for(int p = 0; p < 3; p++) {
                        if(dp[j][k][p])
                        for(int q = 0; q < 3; q++) {
                            if(dp[k+1][j+i][q]) {
                                dp[j][j+i][table[p][q]] = 1;
                            }
                        }
                    }
                    if(dp[j][j+i][0] && dp[j][j+i][1] && dp[j][j+i][2])
                        break;
                }
                if(i == 0)
                    dp[j][j][s[j]-'X'] = 1;
            }
        }
        for(int i = 2; i >= 0; i--) {
            if(dp[0][n-1][i]) {
                printf("%c\n", i+'X');
                break;
            }
        }
    }
    return 0;
}
/*
1
ZYX
*/

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 946 - A Pile of Boxes

Problem

一個神祕的堆疊方式，假如燒杯大小大於要放入的燒杯，在不超過其原本的燒杯高度的情況下，則可以將其放入內部，放入內部後，可能掉入底層的燒杯中。

根據這樣的方式模擬最後堆疊的最大高度。

Sample Input

Sample Output

Solution

半夜爬起來寫的，總覺得檢查事件挺麻煩的事情，因此採用遞迴的方式建造，在退回的情況下查閱是否要疊在上方。

inner 表示內部底層的燒杯、outer 表示上方的燒杯，footer 表示下方的燒杯。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int inner[105], outer[105], footer[105];
int height[105], A[105];
int place(int i, int mxI, int limit) {
//	printf("down %d %d\n", A[mxI], mxI);
    if(A[mxI] < A[i]) {
        if(height[mxI] + A[i] <= limit) {
            outer[mxI] = i, footer[i] = mxI; 
            height[i] = height[mxI] + A[i];
        }
        return height[mxI] + A[i];
    }
    if(inner[mxI] == -1) {
        int h = place(i, footer[mxI], height[mxI] - A[mxI]);
        if(h <= height[mxI] - A[mxI]) // complete
            return h;
        inner[mxI] = i, footer[i] = footer[mxI];
        height[i] = height[mxI] - A[mxI] + A[i];
        return height[i];
    } else {
        mxI = inner[mxI];
        while(outer[mxI] != -1)
            mxI = outer[mxI];
        int h = place(i, mxI, height[mxI]);
        if(h == height[mxI] - A[mxI] + A[i]) {
            h = place(i, footer[mxI], height[mxI] - A[mxI]);
//			printf("check %d %d\n", h, height[mxI] - A[mxI]);
            if(h <= height[mxI] - A[mxI])
                return h;
            inner[mxI] = i, footer[i] = footer[mxI];
            height[i] = height[mxI] - A[mxI] + A[i];
            return height[i];
        } else if(h > height[mxI]) {
            if(height[mxI] + A[i] <= limit) {
                outer[mxI] = i, footer[i] = mxI;
                height[i] = height[mxI] + A[i];
            }
            return height[mxI] + A[i];
        } else {
//			puts("hello");
            return h;
        }
    }
}
int main() {
    int n;
    while(scanf("%d", &n) == 1) {
        for(int i = 0; i <= n; i++)
            inner[i] = outer[i] = footer[i] = height[i] = -1;
        A[0] = 0, height[0] = 0;
        for(int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        int mxH = 0, mxI = 0;
        for(int i = 1; i <= n; i++) {
            int h = place(i, mxI, mxH);
            if(h > mxH) {
                outer[mxI] = i, footer[i] = mxI; 
                height[i] = height[mxI] + A[i];
            }
            h = height[i];
//			printf("[%d] %d - %d mxH = %d mxI %d\n", i, A[i], h, mxH, mxI);
//			for(int j = 1; j <= i; j++)
//				printf("--------[%d] %2d * in %2d out %2d foot %2d\n", j, A[j], inner[j], outer[j], footer[j]);
            if(h > mxH)	mxH = h, mxI = i;
        }
        printf("%d\n", mxH);
    }
    return 0;
}

Read More +

2014-07-31

解題區/解題區 - UVa

uva 921 - A Word Puzzle in the Sunny Mountains

Problem

將一個數字對應一個字母，現在已經有一些字典的單字，先將 seed 字串對應到第一組加密數字。接著找到一種對應方式，使得每一組加密數字都可以對應到字典單字中。

Sample Input

1 
11
7
1 2 3 4 5 3 0
1 5 1 0
1 6 3 4 0
7 3 4 8 1 0
9 3 4 8 1 0
9 1 9 10 11 0
10 11 6 3 0
ADORNO
ADORNO
AMOR
ANA
ARLINDO
ANTUNES
HORTA
PORTA
PORTAO
PORTAL
PAPEL
PARVO
ELMO
ESTE
ESSE
ARMADURA
HELENA
ERGONOMICO
EVA
ERVA
CARMO
COUVE
*

Sample Output

1	ADORNMHTPEL

Solution

題目看起來挺嚇人，直接窮舉即可，保證只有一解。

#include <stdio.h>
#include <string.h>
using namespace std;
int match[105][105], msize[105];
char seed[105], dictionary[105][105];
int dlen[105];
int mp[52];
int N, M, D;
int dfs(int idx) {
    if(idx == N) {
        int f = 1;
        for(int i = 1; i <= M; i++)
            f &= mp[i] != -1;
        return f;
    }
    for(int i = 0; i < D; i++) {
        if(dlen[i] != msize[idx])	continue;
        int ok = 1;
        for(int j = 0; j < msize[idx] && ok; j++) {
            if(mp[match[idx][j]] != -1 && mp[match[idx][j]] != dictionary[i][j])
                ok = 0;
        }
        if(ok) {
            int cp[52];
            for(int i = 1; i <= M; i++)	cp[i] = mp[i];
            for(int j = 0; j < msize[idx] && ok; j++)
                mp[match[idx][j]] = dictionary[i][j];
            if(dfs(idx+1))	return 1;
            for(int i = 1; i <= M; i++)	mp[i] = cp[i];
        }
    }
    return 0;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &M, &N);
        for(int i = 0; i < N; i++) {
            int j;
            for(j = 0; scanf("%d", &match[i][j]) && match[i][j]; j++);
            msize[i] = j;
        }
        scanf("%s", seed);
        memset(mp, -1, sizeof(mp));
        for(int i = 0; seed[i]; i++)
            mp[match[0][i]] = seed[i];
        for(D = 0; scanf("%s", &dictionary[D]) && dictionary[D][0] != '*'; D++) {
            dlen[D] = strlen(dictionary[D]);
        }
        dfs(0);
        for(int i = 1; i <= M; i++)		
            printf("%c", mp[i]);
        puts("");
    }
    return 0;
}

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 918 - ASCII Mandelbrot

Problem

根據題目意思，Z = 0 + 0i 開始，窮舉給定區間內的複數 C = a + bi，迭代 Z = Z * Z + C，迭代多少次使得 |Z| > 2，迭代次數將會由給定的字串依序塗色。

Sample Input

1
2
3

2
"#$&/|[]+;:-." -1.2 1.2 0.1 -2 1 0.05
"1234567890AB" -1.2 -0.8 0.02 -0.5 0.5 0.02

Sample Output

########$$$$$$$$$$&&&&&&&&&&&&&&&&&&&&&&&&&$$$$$$$$$$$$$$$$$$
#######$$$$$$$&&&&&&&&&&&&&&&&/////| +||///&&&&$$$$$$$$$$$$$$
######$$$$$&&&&&&&&&&&&&&&&//////||[]-;- |////&&&&$$$$$$$$$$$
#####$$$&&&&&&&&&&&&&&&&///////|||[+;  -+[||////&&&&&$$$$$$$$
####$$&&&&&&&&&&&&&&&&///////||[[]+      +[||||//&&&&&&$$$$$$
###$$&&&&&&&&&&&&&&//////||[]++++;:      :;+[[[ |//&&&&&$$$$$
##$$&&&&&&&&&&&&&////||||[[].               .    |/&&&&&&$$$$
##$&&&&&&&&&&&//|||||||[[[+ .                   ][|/&&&&&&$$$
#$&&&&&&&///||].]]]]]]]]]+-                     ; |//&&&&&&$$
#&&&//////|||[]:  .   -;;-                       +[//&&&&&&&$
#&//////||||[]+-                                 ]|///&&&&&&$
#/////[[[[]+.                                   +[|///&&&&&&$
                                              .+][|///&&&&&&&
#/////[[[[]+.                                   +[|///&&&&&&$
#&//////||||[]+-                                 ]|///&&&&&&$
#&&&//////|||[]:  .   -;;-                       +[//&&&&&&&$
#$&&&&&&&///||].]]]]]]]]]+-                     ; |//&&&&&&$$
##$&&&&&&&&&&&//|||||||[[[+ .                   ][|/&&&&&&$$$
##$$&&&&&&&&&&&&&////||||[[].               .    |/&&&&&&$$$$
###$$&&&&&&&&&&&&&&//////||[]++++;:      :;+[[[ |//&&&&&$$$$$
####$$&&&&&&&&&&&&&&&&///////||[[]+      +[||||//&&&&&&$$$$$$
#####$$$&&&&&&&&&&&&&&&&///////|||[+;  -+[||////&&&&&$$$$$$$$
######$$$$$&&&&&&&&&&&&&&&&//////||[]-;- |////&&&&$$$$$$$$$$$
#######$$$$$$$&&&&&&&&&&&&&&&&/////| +||///&&&&$$$$$$$$$$$$$$
########$$$$$$$$$$&&&&&&&&&&&&&&&&&&&&&&&&&$$$$$$$$$$$$$$$$$$
333333333333333333333333333333333222222222222222222
333333333333334444433333333333333332222222222222222
333333334444444444444444433333333333322222222222222
333334444444445555555444444433333333333222222222222
334444444444558866555554444444433333333332222222222
444444444445567 9B755555444444444333333333322222222
4444444444555678B9766555544444444433333333332222222
4444444445555668A0866666554444444444333333333322222
44444444555556670 A87667765444444444433333333332222
4444444555556667   08778A75544444444443333333333322
444444555555666790  99AA  6554444444444333333333332
444444555555667889  B   A76654444444444433333333333
444445555555677889A   A9876655444444444443333333333
444455555556677880A  B09876655544444444444333333333
44455555556677889A    A9877655554444444444433333333
4455555556677899       9887665555544444444443333333
4555555566789 0AB      0988765555554444444444333333
555555566680B          AAB 866555555444444444433333
5555566667A               B876555555554444444433333
55566666789AB              A76655555555444444443333
566666677880B             B977665555555554444444333

Solution

何等兇殘的題目，以前不少 testdata 是用 float 混用 double 產出來的結果，亦或者是輸出轉 float，各種神祕的方式才能恰好符號原本測資的誤差。
砸了許多混用方式才將那殘害世人的題目解決
－想到之前不少 float 拯救世界。

// 918 - ASCII Mandelbrot
// WTF for testdata, I used + 0.00000001f to pass it.
#include <stdio.h> 
#include <math.h>
int main() {
    int testcase;
    double MINI, MAXI, MINR, MAXR, PRECI, PRECR;
    char CHARS[128];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%s %lf %lf %lf %lf %lf %lf", CHARS, &MINI, &MAXI, &PRECI, &MINR, &MAXR, &PRECR);
        CHARS[0] = CHARS[13] = ' ';
        for(double a = MINI; a <= MAXI + 0.00000001f; a += PRECI) {
            for(double b = MINR; b <= MAXR + 0.00000001f; b += PRECR) {
                float za = 0, zb = 0, ca = b, cb = a, ta, tb;
                int i;
                for(i = 0; i < 12; i++) {	
                    ta = za * za - zb * zb;
                    tb = 2 * za * zb;
                    za = ta + ca, zb = tb + cb;
                    if(za * za + zb * zb > 4)
                        break;
                }
                printf("%c", CHARS[i+1]);
            }
            puts("");
        }
        if(testcase)
            puts("");
    }
    return 0;
}
/*
2
"#$&/|[]+;:-." -1.2 1.2 0.1 -2 1 0.05
"1234567890AB" -1.2 -0.8 0.02 -0.5 0.5 0.02
*/

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 915 - Stack of Cylinders

Problem

根據順序依據擺放半徑為 r 的圓，求最後的總長，以及從端點開始碰壁到另外一端所有圓編號，保證不會有三個圓相互接觸。

Sample Input

Sample Output

Solution

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n, cases = 0;
    while(scanf("%d", &n) == 1) {
        if(cases++)	puts("");
        double radius[128], posX[128];
        for(int i = 1; i <= n; i++)
            scanf("%lf", &radius[i]);
            
        double mx = 0;
        int prev[128] = {}, tail = 0;
        for(int i = 1; i <= n; i++) {
            double x = radius[i];
            for(int j = 1; j < i; j++) {
                double nx = sqrt(pow(radius[i]+radius[j], 2) - pow(radius[i]-radius[j], 2)) + posX[j];
                if(nx > x) 
                    prev[i] = j;
                x = max(x, nx);
//				printf("sqrt = %lf\n", pow(radius[i]+radius[j], 2) - pow(radius[i]-radius[j], 2));
            }
//			printf("prev[%d] %d\n", i, prev[i]);
            posX[i] = x;
            if(posX[i] + radius[i] > mx)
                tail = i;
            mx = max(mx, posX[i] + radius[i]);
        }
        printf("%.1lf\n", mx);
        vector<int> ret;
        while(tail) {
            ret.push_back(tail);
            tail = prev[tail];
        }
        printf("%d\n", ret.size());
        for(int i = ret.size() - 1; i >= 0; i--)
            printf("%d\n", ret[i]);
    }
    return 0;
}

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 909 - The BitPack Data Compression Problem

Problem

解壓縮方式

While (there is input)
   n <-- read next byte
   If (0<= n <= 127)
       copy the next n+1 bytes to the output as they are
   Else If (129<= n <=255)
       copy the next byte n-128+1 times to the output
   Else If n=128
       do nothing

找到用最少 bytes 的壓縮結果。每組測資只會有一筆，並且以 EOF 結尾。

範例輸出用 [ddd] 表示不可視的字符或者是可視字符都有可能，但是實際輸出直接輸出該數值的 bytes 而非以 [] 表示的字串。

Sample Input 1

1	aaaaaaaarstqahbbbbbbb

Sample Output 1

1	[135]a[5]rstqah[134]b

Sample Input 2

1	aaaaaaaaaa

Sample Output 2

[137]a

Sample Input 3

1	abcdefghij

Sample Output 3

1	[9]abcdefghij

Solution

討論區一而三在而三的更正解答，最後要說明的是，你們最後的答案還是錯的！此外，測試資料輸入輸出都有不可視字符是哪招，明明說一行一筆測資，以為都是可視 …
－最後討論時間為 13 年前

dp[i] 表示從 [0, i] 壓縮的最少 bytes 數量，最後使用回溯找其中一解 (任何一解都可以)。

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int dp[65536], ardp[65536], from[65536], n, bb;
char s[65536];
void travel(int i) {
    if(i == 0)	return;
    if(ardp[i] >= 129) {
        travel(from[i]);
        printf("%c%c", ardp[i], s[i]), bb += 2;
    } else {
        travel(from[i]);
        printf("%c", ardp[i]), bb++;
        for(int j = ardp[i]; j >= 0; j--)
            printf("%c", s[i - j]), bb++;
    }
}
int main() {
    int idx = 1;
    char c;
    while((c = getchar()) != EOF)
        s[idx++] = c;
    {
        n = strlen(s+1);
        assert(n < 65536);
        memset(dp, 63, sizeof(dp));
        dp[0] = 0;
        for(int i = 0; i <= n; i++) {
            int cnt = 0;
            for(int j = i+1; j <= n; j++) {
                if(s[j] == s[i+1]) {
                    cnt++;
                    if(cnt + 127 > 255)
                        break;
                    if(cnt >= 2) {
                        if(dp[j] > dp[i] + 2)
                            ardp[j] = cnt + 127, from[j] = i;
                        dp[j] = min(dp[j], dp[i] + 2);
                    }
                } else
                    break;
            }
            cnt = 0;
            for(int j = i+1; j <= n; j++) {
                cnt++;
                if(cnt - 1 > 127)	break;
                if(dp[j] > dp[i] + cnt + 1)
                    ardp[j] = cnt - 1, from[j] = i;
                dp[j] = min(dp[j], dp[i] + cnt + 1);
            }
        }
        bb = 0;
        travel(n);
//		printf("bytes %d\n", bb);
    }
    return 0;
}

Read More +

2014-07-31

解題區/解題區 - UVa

UVa 298 - Race Tracks

Problem

給定一個 N * M 的地圖，接著將會從起點出發抵達終點，一開始的速度為 (0, 0)，在下一個時刻，每一個維度的速度可以調整 -3, -2, -1, 0, 1, 2, 3 (也就是加速度)，但是速度的絕對值必須小於等於 3，同時給定這張地圖的矩形障礙物，移動的過程中不用考慮會不會遇到障礙物，只需要考慮跳躍落下的地點是否有障礙物。

Sample input

Sample output

1 2	Optimal solution takes 7 hops. No solution.

Solution

bfs 廣度搜索

#include <stdio.h> 
#include <queue>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int g[64][64];
int testcase, N, M, P;
int sx, sy, ex, ey;
void bfs() {
    int dp[64][64][8][8] = {};
    queue<int> X, Y, VX, VY;
    int x, y, vx, vy, tx, ty, dx, dy;
    dp[sx][sy][0+3][0+3] = 1;
    X.push(sx), Y.push(sy), VX.push(0), VY.push(0);
    while(!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        vx = VX.front(), VX.pop();
        vy = VY.front(), VY.pop();
        if(x == ex && y == ey) {
            printf("Optimal solution takes %d hops.\n", dp[x][y][vx+3][vy+3]-1);
            return;
        }
        for(int i = -1; i <= 1; i++) {
            for(int j = -1; j <= 1; j++) {
                dx = vx + i, dy = vy + j;
                if(abs(dx) <= 3 && abs(dy) <= 3) {
                    tx = x + dx, ty = y + dy;
                    if(tx < 0 || tx >= N || ty < 0 || ty >= M || dp[tx][ty][dx+3][dy+3])
                        continue;
                    if(g[tx][ty])
                        continue;
                    dp[tx][ty][dx+3][dy+3] = dp[x][y][vx+3][vy+3] + 1;
                    X.push(tx), Y.push(ty);
                    VX.push(dx), VY.push(dy);
                } 
            }
        }
    }
    puts("No solution.");
}
int main() {
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &N, &M);
        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        scanf("%d", &P);
        memset(g, 0, sizeof(g));
        for(int i = 0; i < P; i++) {
            int lx, ly, rx, ry;
            scanf("%d %d %d %d", &lx, &rx, &ly, &ry);
            for(int p = lx; p <= rx; p++)
                for(int q = ly; q <= ry; q++)
                    g[p][q] = 1;
        }
        bfs();
    }
    return 0;
}

Read More +