2014-09-15

UVa 12792 - Shuffled Deck

Problem

給定一種洗牌方式，請問重複多少次之後會復原到原本一開始的排列。

Sample Input

Sample Output

Solution

一道置換群的題目，將置換的方式找出，接著找一組一組循環置換集合，找到最小公倍數即可。

#include <stdio.h>
#include <algorithm>
using namespace std;
int A[1<<21], used[1<<21] = {};
int testcase = 0;
long long gcd(long long x, long long y) {
    long long t;
    while (x%y)
        t = x, x = y, y = t%y;
    return y;
}
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            if (i&1)
                A[i] = i/2;
            else
                A[i] = i/2 + n/2;
        }
        
        testcase++;
        long long lcm = 1;
        for (int i = 0; i < n; i++) {
            if (A[i] != i && used[i] != testcase) {
                int ss = 0;
                for (int j = i; used[j] != testcase; j = A[j])
                    used[j] = testcase, ss++;
                lcm = lcm / gcd(lcm, ss) * ss;
            }
        }
        printf("%d\n", lcm);
    }
    return 0;
}
/*
4
6
2
100002
*/

Read More +

2014-09-15

解題區/解題區 - UVa

UVa 12797 - Letters

Problem

找一條最短路徑從左上到右下，並且中間經過的字母不會有同時大小寫出現，也就是說 A 和 a 不能同時出現、B 和 b 不能同時出現 …

Sample Input

6
DdaAaA
CBAcca
eEaeeE
bBbabB
DbDdDc
fFaAaC
7
aAaaaaa
aAaaaAa
aAaaaAA
aaAaAaa
AaAaaAa
aaAAaAa
aaaaaAa

Sample Output

1
2

13
-1

Solution

窮舉可使用的字符，對於每一種限定方式進行 bfs 搜索。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int N, letter_cnt[128], letter_used[128];
int used[128][128] = {}, dist[128][128], testcase = 0, ret;
char g[128][128];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
void dfs(int idx) {
    if (idx == 10) {
        queue<int> X, Y;
        int tx, ty, x, y;
        if (letter_used[g[0][0]] == 0)
            return;
        testcase++;
        X.push(0), Y.push(0);
        used[0][0] = testcase;
        dist[0][0] = 1;
        while (!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            if (x == N-1 && y == N-1) {
                ret = min(ret, dist[x][y]);
                return;
            }
            for (int i = 0; i < 4; i++) {
                tx = x + dx[i], ty = y + dy[i];
                if (tx < 0 || ty < 0 || tx >= N || ty >= N)
                    continue;
                if (used[tx][ty] == testcase || letter_used[g[tx][ty]] == 0)
                    continue;
                used[tx][ty] = testcase;
                dist[tx][ty] = dist[x][y] + 1;
                X.push(tx), Y.push(ty);
            }
        }
        return ;
    }
    int c = 0;
    if (letter_cnt[idx + 'a']) {
        letter_used[idx + 'a'] = 1;
        dfs(idx+1);
        letter_used[idx + 'a'] = 0;
        c++;
    }
    if (letter_cnt[idx + 'A']) {
        letter_used[idx + 'A'] = 1;
        dfs(idx+1);
        letter_used[idx + 'A'] = 0;
        c++;
    }
    if (c == 0)
        dfs(idx+1);
}
int main() {
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++)
            scanf("%s", g[i]);
        memset(letter_cnt, 0, sizeof(letter_cnt));
        memset(letter_used, 0, sizeof(letter_used));
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                letter_cnt[g[i][j]]++;
        ret = 0x3f3f3f3f;
        dfs(0);
        printf("%d\n", ret == 0x3f3f3f3f ? -1 : ret);
    }
    return 0;
}

Read More +

2014-09-15

解題區/解題區 - UVa

UVa 12791 - Lap

Problem

在賽車運動中，常用 Lap 表示套一圈賽道所消耗的時間，現在有多名賽車手，給予最快一圈多久、最慢一圈多久，請問在最快車手第幾圈的時候，可以倒追最慢的車手。

Sample Input

Sample Output

Solution

懶得推導公式，二分倒追的時間，找到何時會產生倒追，再計算第幾圈即可。

#include <stdio.h> 
#include <math.h>
int main() {
    int X, Y;
    while (scanf("%d %d", &X, &Y) == 2) {
        double l = 0, r = 1e+30, mid;
        int ret = 0;
#define eps 1e-8
        while (fabs(l - r) > eps) {
            mid = (l + r)/2;
            if (mid * (1.0/X - 1.0/Y) >= 1)
                r = mid;
            else
                l = mid;
        }
        printf("%.0lf\n", ceil(mid/X));
    }
    return 0;
}

Read More +

2014-09-15

解題區/解題區 - UVa

UVa 11869 - SOAP Response

Problem

給一個 SOAP 的回應格式，解析給定的回應，並且提供屬性查找。

Sample Input

1
8
<a good="true" wants="no">
<b>
<c contest="running">
<d ballon="no">
</d>
</c>
</b>
</a>
4
a.b.c.d["ballon"]
a.c["contest"]
a.b.c["contest"]
c["contest"]

Sample Output

Case 1:
no
Undefined
running
Undefined

Solution

SOAP 類似 HTML XML 那種，在不少網路上的諮詢服務都會有這一套規則。

不過看到這一道題目很簡單，保證輸入格式一定可以相互匹配且完整，那使用遞迴 parsing 輸入，建造一個 tree 出來，同時子樹不會出現相同的命名。

建造樹出來之後，詢問就沿著樹走訪即可。

#include <stdio.h> 
#include <string.h>
#include <map>
#include <algorithm>
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
struct Node {
    string name;
    map<string, string> attr;
    vector<int> son;
    void init() {
        attr.clear();
        son.clear();
    }
};
Node node[32767];
int nodesize;
char s[1024];
void parsingAttr(string line, Node &p) {
    string ign = "<>=", attr, val;
    for (int i = 0; i < line.length(); i++) {
        if (ign.find(line[i]) != string::npos) {
            line[i] = ' ';
        }
    }
    stringstream sin(line);
    sin >> p.name;
    while (sin >> attr >> val) {
        p.attr[attr] = val.substr(1, val.length()-2);
//		cout << attr << "+++" << val << endl;
    }
}
int build(string line) {
    int label = ++nodesize;
    Node &p = node[label];
    p.init();
    parsingAttr(line, p);
    while (gets(s)) {
        if (s[1] == '/')
            break;
        p.son.push_back(build(s));
    }
    return label;
}
int main() {
    int testcase, cases = 0, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        while(getchar() != '\n');
        gets(s);
        nodesize = 0;
        int root = build(s);
        scanf("%d", &m);
        while (getchar() != '\n');
        printf("Case %d:\n", ++cases);
        while(m--) {
            gets(s);
            string ign = ".[]", token;
            for (int i = 0; s[i]; i++) {
                if (ign.find(s[i]) != string::npos) {
                    s[i] = ' ';
                }
            }
            stringstream sin(s);
            int pos = root;
            string res = "Undefined";
            sin >> token;
            if (token == node[pos].name) {
                while (sin >> token) {
                    if (token[0] == '"') {
                        string a = token.substr(1, token.length()-2);
                        if (node[pos].attr.find(a) != node[pos].attr.end())
                            res = node[pos].attr[a];
                        break;
                    } else {
                        int f = 0;
                        for (int i = 0; i < node[pos].son.size(); i++) {
                            if (token == node[node[pos].son[i]].name) {
                                f = 1;
                                pos = node[pos].son[i];
                                break;
                            }
                        }
                        if (!f)
                            break;
                    }
                }
            }
            printf("%s\n", res.c_str());
        } 
    }
    return 0;
}

Read More +

2014-09-12

解題區/解題區 - UVa

UVa 11651 - Krypton Number System

Problem

相鄰數字不可相同
不可前導為 0
score 分數為任兩個相鄰位數相減平方的總和

請問在 base 下，指定 score 的數字有多少個。

Sample Input

1
2
3

2
6 1
5 5

Sample Output

1 2	Case 1: 9 Case 2: 80

Solution

首先，可以知道每一次增加的總數最多為 (base - 1) (base - 1)，因此我們的狀態紀錄之少要追溯到當前分數 n - (base - 1) (base - 1)。

然而由於 score 過大，不可直接著手 dp[score][tail_digit] 之類的 dp 計算。仍可以計算於 (base - 1) * (base - 1) 以下的情況。

接著，利用遞迴公式 (線性變換矩陣 ?)，每一項為 a[score][tail_digit]，而分數必須保留到當前 score - (base - 1) * (base - 1)，因此狀態將會有 (base - 1) * (base - 1) * base，也就是矩陣最大上限 5 * 5 * 6 = 150。

矩陣的部分，可以假想每一次在尾數多增加一個 digit 上去，而在初始項部分仍必須依靠 dp 去計算。矩陣快速乘法直接套用 D&C 在 O(n^3 log k) 完成，並且計算時，盡可能將無用的 0 忽略計算，否則很容易 TLE。

#include <stdio.h> 
#include <string.h>
const unsigned long long mod = 1LLU<<32;
struct Matrix {
    unsigned long long v[150][150];
    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 k = 0; k < col; k++) {
                if (v[i][k])
                for(int j = 0; j < x.col; j++) {
                    ret.v[i][j] += v[i][k] * x.v[k][j],
                    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, cases = 0, base, score;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &base, &score);
        printf("Case %d: ", ++cases);
        int N = (base - 1) * (base - 1);
        
        unsigned long long dp[64][64] = {}; // [sum][tail_digit] = #way 
        for (int i = 0; i <= N; i++)
            dp[0][i] = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < base; j++) {
                for (int k = 0; k < base; k++) {
                    int d = (j - k) * (j - k);
                    if (i + d > N || j == k)
                        continue;
                    dp[i+d][k] += dp[i][j];
                    dp[i+d][k] %= mod;
                }
            }
        }
        
        if (score <= N) {
            unsigned long long ret = 0;
            for (int i = 1; i < base; i++)
                ret = (ret + dp[score][i])%mod;
            printf("%llu\n", ret);
            continue;
        }
        int r, c;
        r = c = (base - 1) * (base - 1) * base;
        Matrix x(r, c), y(c, 1);
        for (int i = 1; i <= N; i++)
            for (int j = 0; j < base; j++)
                y.v[(i-1) * base+j][0] = dp[i][j];
        for (int i = base; i < r; i++)
            x.v[i - base][i] = 1;
        for (int i = 0; i < base; i++) {
            for (int j = 0; j < base; j++) {
                if (i == j)	continue;
                int d = N - (i - j) * (i - j);
                x.v[(N-1)*base + i][d*base + j] = 1;
            }
        }
//		puts("");
//		for (int i = 0; i < r; i++, puts(""))
//			for (int j = 0; j < c; j++)
//				printf("%lld ", x.v[i][j]);
//		for (int i = 0; i < c; i++, puts(""))
//				printf("%lld ", y.v[i][0]);
        Matrix z = (x ^ (score - N)) * y;
        unsigned long long ret = 0;
        for (int i = 1; i < base; i++)
            ret = (ret + z.v[(N-1) * base + i][0])%mod;
        printf("%llu\n", ret);
    }
    return 0;
}

Read More +

2014-09-12

解題區/解題區 - UVa

UVa 11097 - Poor My Problem!

Problem

給一張圖 (有向圖)，請問從起始點走到特定點的路徑，花費 / 經過邊數 最小值為何？

並且最多經過 1000 條邊 (含)，邊可以重複走。

Sample Input

Sample Output

Solution

如果沒有限制最多經過的邊，將會相當難辦事，因為一直繞就可以將平均值拉下，而會繞多久可能要玩一下環狀收斂，最小平均環，然後檢查是否會經過這個環抵達目的地 …

當然這一題已經給定最大使用邊數，定義狀態為 dp[i][j] 使用 j 條邊抵達目的地 i 的最小花費。按照 spfa 的精神不斷更新即可。

#include <stdio.h> 
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct edge {
    int to, w;
    edge(int a = 0, int b = 0):
        to(a), w(b) {}
};
vector<edge> g[1024];
int dp[1024][1024], inq[1024][1024];
const int MAXE = 1000;
void solve(int source, int N) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= MAXE; j++)
            dp[i][j] = 0x3f3f3f3f;
    queue<int> X, E;
    int u, v, w, e;
    dp[source][0] = 0;
    X.push(source), E.push(0);
    while (!X.empty()) {
        u = X.front(), X.pop();
        e = E.front(), E.pop();
        inq[u][e] = 0;
        if (e == MAXE)	continue;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].to, w = g[u][i].w;
            if (dp[v][e+1] > dp[u][e] + w) {
                dp[v][e+1] = dp[u][e] + w;
                if (!inq[v][e+1]) {
                    inq[v][e+1] = 1;
                    X.push(v), E.push(e+1);
                }
            }
        }
    }
}
int main() {
    int N, M, S, Q;
    int x, y, w;
    while (scanf("%d %d %d", &N, &M, &S) == 3) {
        for (int i = 0; i < N; i++)
            g[i].clear();
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(edge(y, w));
        }
        
        solve(S, N);
        
        scanf("%d", &Q);
        while (Q--) {
            scanf("%d", &x);
            double ret = 1e+30;
            int e = -1;
            if (x == S)
                ret = 0, e = 0;
            else {
                for (int i = 1; i <= MAXE; i++) {
                    if (dp[x][i] != 0x3f3f3f3f) {
                        if ((double)dp[x][i]/i < ret) {
                            ret = (double)dp[x][i]/i;
                            e = i;
                        }
                    }
                }
            }
            if (e == -1)
                puts("No Path");
            else
                printf("%.4lf %d\n", ret, e);
        }
        puts("");
    }
    return 0;
}

Read More +

2014-09-12

解題區/解題區 - UVa

UVa 11421 - Arranging Cards

Problem

把每一種牌當作字串串在一起，請問第 k 小字典順序的排列為何？並且相同數字 (rank) 的牌不能放在一起。

Sample Input

6 1
2S 3S 3C 4S 4C 4D
6 120
2S 3S 3C 4S 4C 4D
6 121
2S 3S 3C 4S 4C 4D
16 654321234567
2S 3S 4S 5S 2C 3C 4C 5C 2D 3D 4D 5D 2H 3H 4H 5H
0 0

Sample Output

Case 1: 2S 4C 3C 4D 3S 4S
Case 2: 4S 3S 4D 3C 4C 2S
Case 3: Not found
Case 4: 5D 4S 2D 5H 3S 4H 5S 2H 3D 2C 5C 4D 2S 3C 4C 3H

Solution

題目最麻煩的地方是 k 必須使用 long long 才裝得下，然而中間運算過程中很容易超過 long long 因此在終止條件上會變得很難處理。

首先我們必須要知道那些牌可以排出哪幾種方法，但是很明顯地基礎的 dp 無法用上，少說狀態也必須是 13 * 2^50 之類的玩相鄰不可同色。

因此最後將牌壓縮成，擁有 4 張一樣、3 張、2 張、1 張的個數，擁有多少種排列方式。在寫遞迴的時候，標記上一次使用哪一類型的牌。為了逃出 overflow 的運算，使用一個 double 類別的輔助陣列，同樣計算方法數。

隨後知道固定類型的方法數，依序從字典順序小的開始窮舉是否要擺放於此位置。

#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int usedg[16][16][16][16][5];
long long dp[16][16][16][16][5];
double dp2[16][16][16][16][5];
const long long MAXVAL = 1e+18 + 10;
long long g(int f4, int f3, int f2, int f1, int last) {
    if (usedg[f4][f3][f2][f1][last])
        return dp[f4][f3][f2][f1][last];
    usedg[f4][f3][f2][f1][last] = 1; 
    long long &ret = dp[f4][f3][f2][f1][last];
    double &ret2 = dp2[f4][f3][f2][f1][last];
    if (f4 + f3 + f2 + f1 == 0) {
        ret = 1;
        ret2 = 1;
        return 1;
    }
    if (f4 > 0) {
        ret += 4 * f4 * g(f4-1, f3+1, f2, f1, 4);
        ret2 += 4 * f4 * dp2[f4-1][f3+1][f2][f1][4];
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    if (f3 > 0) {
        if (last == 4) {
            ret += 3 * (f3 - 1) * g(f4, f3-1, f2+1, f1, 3);
            ret2 += 3 * (f3 - 1) * dp2[f4][f3-1][f2+1][f1][3];
        } else {
            ret += 3 * (f3) * g(f4, f3-1, f2+1, f1, 3);
            ret2 += 3 * (f3) * dp2[f4][f3-1][f2+1][f1][3];
        }
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    if (f2 > 0) {
        if (last == 3) {
            ret += 2 * (f2 - 1) * g(f4, f3, f2-1, f1+1, 2);
            ret2 += 2 * (f2 - 1) * dp2[f4][f3][f2-1][f1+1][2];
        } else {
            ret += 2 * (f2) * g(f4, f3, f2-1, f1+1, 2);
            ret2 += 2 * (f2) * dp2[f4][f3][f2-1][f1+1][2];
        }
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    if (f1 > 0) {
        if (last == 2) {
            ret += (f1 - 1) * g(f4, f3, f2, f1-1, 1);
            ret2 += (f1 - 1) * dp2[f4][f3][f2][f1-1][1];
        } else {
            ret += f1 * g(f4, f3, f2, f1-1, 1);
            ret2 += f1 * dp2[f4][f3][f2][f1-1][1];
        }
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    return ret;
}
int card2Num(char suit, char rank) {
    int s, r;
    switch(suit) {
        case 'S': s = 3;break;
        case 'C': s = 0;break;
        case 'H': s = 2;break;
        case 'D': s = 1;break;
    }
    switch(rank) {
        case '2'...'9': r = rank-'0'-2;break;
        case 'T': r = 12;break;
        case 'J': r = 9;break;
        case 'Q': r = 11;break;
        case 'K': r = 10;break;
        case 'A': r = 8;break;
    }
    return r * 4 + s;
}
int main() {
    int cases = 0;
    int N;
    long long K;
    char psuit[] = "CDHS", prank[] = "23456789AJKQT";
    while (scanf("%d %lld", &N, &K) == 2) {
        if (N == 0 && K == 0)
            break;
        char card[10];
        int A[64];
        for (int i = 0; i < N; i++) {
            scanf("%s", card);
            int x = card2Num(card[1], card[0]);
            A[i] = x;
        }
        printf("Case %d:", ++cases);
        int ret[64];
        int NOT_FOUND = 0; 
        K--;
        for (int i = 0; i < N; i++) {
            sort(A+i, A+N);
            ret[i] = -1;
            for (int j = i; j < N; j++) {
                int ch = A[j];
                int cnt[13] = {}, f[8] = {};
                if (i && ch/4 == ret[i-1]/4) 
                    continue;
                for (int k = i; k < N; k++)
                    cnt[A[k]/4]++;
                int last = cnt[ch/4]--;
                for (int k = 0; k < 13; k++)
                    f[cnt[k]]++;
                long long way = g(f[4], f[3], f[2], f[1], last);			
//				printf("%d %d %d %d - %d %lld\n", f[4], f[3], f[2], f[1], last, way);
//				printf("%lld %lf\n", way, dp2[f[4]][f[3]][f[2]][f[1]][last]);
                if (dp2[f[4]][f[3]][f[2]][f[1]][last] > K) {
                    swap(A[i], A[j]);
                    ret[i] = ch;
                    break;
                } else {
                    K -= way;
                }
            }
            if (ret[i] == -1) {
                NOT_FOUND = 1;
                break;
            }
//			puts("------");
        }
        if (NOT_FOUND) {
            puts(" Not found");
            continue;
        }
        for (int i = 0; i < N; i++)  {
//			printf("%d\n", ret[i]);
            printf(" %c%c", prank[ret[i]/4], psuit[ret[i]%4]);
        }
        puts("");
    }
    return 0;
}
/*
50 1
2C 2D 2H 2S
3C 3D 3H 3S
4C 4D 4H 4S
5C 5D 5H 5S
6C 6D 6H 6S
7C 7D 7H 7S
8C 8D 8H 8S
9C 9D 9H 9S
TC TD TH TS
JC JD JH JS
QC QD QH QS
KC KD KH
AC AD AH
*/

Read More +

2014-09-12

解題區/解題區 - UVa

UVa 1395 - Slim Span

Problem

找一個生成樹，使得最大邊與最小邊的差最小。

Sample Input

Sample Output

Solution

窮舉最小邊權重使用，使用 kruscal 找到瓶頸的最大邊。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
struct E {
    int x, y, v;
    E(int a=0, int b=0, int c=0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return  v < a.v;
    }
};
E D[10005];
int p[1005], rank[1005];
int findp(int x) {
    return p[x] == x ? x : (p[x] = findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int kruscal(int n, int m, E D[], int &max_edge) {
    max_edge = 0;
    for(int i = 0; i <= n; i++)
        p[i] = i, rank[i] = 1;
    int ee = 0;
    for(int i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y))
        	max_edge = max(max_edge, D[i].v), ee++;
    }
    return ee == n-1;
}
int main() {
    int n, m, x, y, w;
    while (scanf("%d %d", &n, &m) == 2 && n+m) {
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            D[i] = E(x, y, w);
        }
        sort(D, D+m);
        int ret = 0x3f3f3f3f, mxedge;
        for (int i = 0; i < m; i++) {
            if (kruscal(n, m-i, D+i, mxedge))
                ret = min(ret, mxedge - D[i].v);
            else
                break;
        }
        printf("%d\n", ret == 0x3f3f3f3f ? -1 : ret);
    }
    return 0;
}

Read More +

2014-09-11

解題區/解題區 - UVa

UVa 10665 - Diatribe against Pigeonholes

Problem

包裹放置於架子上時，盡可能讓兩側的總量越重越好，而中間放置輕的物品。

找到一種放置方式，同時字典順序越小越好。

Sample Input

4
5
BDCECDCBCBCDECDABCEDVBCDBCDBCDABCAED#
7
BGFADCEDGFCDEGCFCGDGCXXDAEDACEACEGFAGFCEDGCEDGBCD#
24
AABACDEDFGHMMJNTBNHGTDFACCDLLPPPERRAMMMMKKKKJJJHHHAAAAGGGQQQLLLLPPPAA#
10
PDJFGEDFANGEHIAEJBHJGEDGJGJEINDFJHEIEDGHFFGHDHGFHAJGIE#

Sample Output

C B A E D
11 8 3 4 9
C D A B F E G
10 9 5 2 5 7 9
A L G D C B E F I O S U V W X N R T Q J K H M P
11 6 5 4 3 2 2 2 0 0 0 0 0 0 0 2 2 2 3 4 4 5 6 6
E H D A B C I F J G
8 7 6 3 1 0 4 6 7 9

Solution

很明顯地可以使用貪心策略，每一次決定方最左或者是最右邊的項目。

由於要維持最小字典順序，放置兩個物品時

如果這兩個重量相同，則字典順序最小的放前面，最大的放後面。
反之，找到挑一個 同一個重量 字典順序小的放前面。

#include <stdio.h> 
#include <algorithm>
#include <vector>
using namespace std;
bool cmp1(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second || (a.second == b.second && a.first < b.first);
}
bool cmp2(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second || (a.second == b.second && a.first > b.first);
}
int main() {
    int testcase, N;
    char s[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf ("%d %s", &N, s);
        pair<int, int> cnt[26] = {}, ret[26];
        for (int i = 0; i < N; i++)
            cnt[i].first = i + 'A';
        for (int i = 0; s[i] != '#'; i++) {
            if (s[i] >= 'A' && s[i] <= 'Z')
                cnt[s[i] - 'A'].second ++;
        }
        int l = 0, r = N - 1;
        for (int i = 0; i < N; ) {
            if (i+1 < N) {
                sort(cnt+i, cnt + N, cmp1);
                if (cnt[i].second != cnt[i+1].second) {
                    if (cnt[i].first < cnt[i+1].first) {
                        ret[l++] = cnt[i];
                        sort(cnt+i+1, cnt + N, cmp2);
                        ret[r--] = cnt[i+1];
                    } else {
                        swap(cnt[i], cnt[i+1]);
                        ret[l++] = cnt[i];
                        sort(cnt+i+1, cnt + N, cmp2);
                        ret[r--] = cnt[i+1];
                    }
                } else {
                    sort(cnt+i, cnt + N, cmp1);
                    ret[l++] = cnt[i];
                    sort(cnt+i+1, cnt + N, cmp2);
                    ret[r--] = cnt[i+1];
                }
                i += 2;
            } else {
                ret[l] = cnt[i];
                i++;
            }
        }
        for (int i = 0; i < N; i++)
         	printf("%c%c", ret[i].first, i == N - 1 ? '\n' : ' ');
     	for (int i = 0; i < N; i++)
         	printf("%d%c", ret[i].second, i == N - 1 ? '\n' : ' ');
    }
    return 0;
}

Read More +

2014-09-11

解題區/解題區 - UVa

UVa 10571 - Products

Problem

所有使用的數字不可重複
每一行、每一列恰好使用兩個數字
每行、每列的非零數字相乘恰好符合需求

Sample Input

2
2 12
3 8
3
5 8 18
2 30 12
5
54 6 12 20 88
18 9 132 32 10
10
2 12 30 56 90 132 182 240 306 380
19 36 51 64 75 84 91 96 99 200
0

Sample Output

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

Solution

直接每一行每一行搜索，過程中預處理所有因數分解，並且同時剪枝不合法的列。

#include <stdio.h> 
#include <vector>
#include <assert.h>
using namespace std;
int N, X[16] = {}, Y[16] = {};
int g[16][16] = {};
vector<int> row[16];
vector<int> f[1024];
int used[1024] = {};
int dfs(int idx) {
    if (idx == N) {
        for (int i = 0; i < N; i++, puts("")) {
            for (int j = 0; j < N; j++) {
                if (j) putchar(' ');
                printf("%3d", g[j][i]);
            }
        }
        return 1;
    }
    for (int p = 0; p < N; p++) {
        for (int q = p + 1; q < N; q++) {
            if (row[p].size() == 2 || row[q].size() == 2)
                continue;
            for (int i = 0; i < f[X[idx]].size(); i++) {
                int a, b, ok = 1;
                a = f[X[idx]][i];
                b = X[idx]/a;
                if (used[a] || used[b] || a == b) 
                    continue;
                g[idx][p] = a, g[idx][q] = b;
                used[a] = used[b] = 1;
                row[p].push_back(a);
                row[q].push_back(b);
                if (row[p].size() == 2 && row[p][0] * row[p][1] != Y[p]) 
                    ok = 0;
                if (row[q].size() == 2 && row[q][0] * row[q][1] != Y[q]) 
                    ok = 0;
                if (Y[p]%a || Y[q]%b)	
                    ok = 0;
                if (ok) {
                    if (dfs(idx + 1)) {
                        g[idx][p] = 0, g[idx][q] = 0;
                        row[p].pop_back();
                        row[q].pop_back();
                        used[a] = used[b] = 0;
                        return 1;
                    }
                }
                g[idx][p] = 0, g[idx][q] = 0;
                used[a] = used[b] = 0;
                row[p].pop_back();
                row[q].pop_back();
            }	
        }
    }
    return 0;
}
int main() {
    for (int i = 1; i < 1024; i++) {
        for (int j = 1; j <= i; j++) {
            if (i%j == 0)
                f[i].push_back(j);
        }
    }
    while (scanf("%d", &N) == 1 && N) {
        for (int i = 0; i < N; i++)
            scanf("%d", &X[i]);
        for (int i = 0; i < N; i++)
            scanf("%d", &Y[i]);
        assert(dfs(0) == 1);
        puts("");
    }
    return 0;
}
/*
2
2 12
3 8
3
5 8 18
2 30 12
5
54 6 12 20 88
18 9 132 32 10
10
2 12 30 56 90 132 182 240 306 380
19 36 51 64 75 84 91 96 99 200
0
*/

Read More +