Aug 28 2014

UVa 11071 - Permutation Representation

Problem

給定一個置換群，要我們表示成以下特定的形式，1 ≤ n ≤ 200000。

由右至左看，第一次為了填5必須移動2位，第二次移動填4也是移動2位
3 2 5 1 4 -> 1 4 3 2 5 移動 2
1 4 3 2 5 -> 3 2 1 4 5 移動 2
3 2 1 4 5 -> 2 1 3 4 5 移動 2
2 1 3 4 5 -> 1 2 3 4 5移動 1

解題者：李育賢
解題日期：2008 年 3 月 21 日

Sample Input

Sample Output

1 2	0 1 2 2 2 0 0 0 2

Solution

李育賢他的解法使用線段樹，靜態操作 shift rotate 和 remove 的問題，仔細想想似乎也不難，但是沒想到我用了模擬的塊狀鏈表解決這一道題目。

為了解決 shift，還必須增加數字的映射，否則沒辦法再 O(sqrt(n)) 時間內完成操作。

塊狀鏈表相當暴力模擬，最簡單地盡可能讓塊差不多是 sqrt(n) 個元素，這樣再 shift 的時候，可以將 head 指標移動次數卡在 sqrt(n) 將給一個操作都限制在 O(sqrt(n))。

塊狀鏈表看看就好，還是回去寫線段樹吧！

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
// 11071 - Permutation Representation
#define MAXN 262144
int A[MAXN], B[MAXN], C[MAXN];
struct PILE {
    int v[512], size;
    PILE *next;
    int label;
    static int MAXSIZE, BUFSIZE;
    static PILE *head;
    PILE() {
        size = label = 0;
        next = NULL;
    }
};
int PILE::MAXSIZE = 512, PILE::BUFSIZE = 0;
PILE* PILE::head = NULL;
int mp[MAXN]; // map
PILE* removePileElement(PILE *where, int pos) {
    if (pos == where->size - 1) {
        where->size--;
        return where->next;
    }
    assert(pos < where->size);
    PILE::BUFSIZE++;
    PILE *m = new PILE();
    m->label = PILE::BUFSIZE;
    assert(m->size == 0);
    for (int i = pos + 1; i < where->size; i++) {
        m->v[m->size++] = where->v[i];
        assert(where->v[i] < MAXN);
        mp[where->v[i]] = m->label;
    }
    where->size = pos;
    m->next = where->next;
    where->next = m;
    return m;
}
int shrinkList() {
    for (PILE *i = PILE::head; i->next != PILE::head; ) {
        PILE *next = i->next;
        int prevsize = i->size;
        int nextsize = next->size;
        if (prevsize + nextsize <= PILE::MAXSIZE) {
            for (int j = 0; j < next->size; j++) {
                i->v[i->size++] = next->v[j];
                mp[next->v[j]] = i->label;
            }
            i->next = next->next;
            delete next;
        } else
            i = i->next;
    }
    return 0;
}
void printPile() {
    PILE *i = PILE::head;
    do {
        for (int j = 0; j < i->size; j++) {
            printf("%d -> ", i->v[j] + 1);
        }
        printf(" | ");
        i = i->next;
    } while (i != PILE::head);
    puts("\n====");
}
void solve(int n) {
//    printPile();
    for (int i = n - 1; i >= 0; i--) {
        PILE *where = NULL;
        int pos = -1;
//        printf("%d\n", i);
        for (PILE *j = PILE::head; ; j = j->next) {
            if (j->label == mp[i]) {
                where = j;
                break;
            }
        }
        assert(where != NULL);
        for (int j = 0; j < where->size; j++) {
            if (where->v[j] == i) {
                pos = j;
                break;
            }
        }
        assert(pos >= 0  && pos < where->size);
        int shift = where->size - pos - 1;
//        printf("%d %d %d\n", node[where].size, pos, shift);
        for (PILE *j = where->next; j != PILE::head; j = j->next) {
            shift += j->size;
        }
//        printf("shift %d\n", shift);
        C[i] = shift;
        PILE::head = removePileElement(where, pos);
        shrinkList();
//        printPile();
    }
    for (PILE *i = PILE::head, *j = i->next; j != PILE::head; j = i->next) {
        delete i;
        i = j;
    }
}
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &B[i]);
        }
//        for (int i = 0; i < n; i++) {
//            A[i] = i + 1;
//            B[i] = A[i];
//        }
//        for (int i = 0; i < n; i++) {
//            int x = rand()%n;
//            int y = rand()%n;
//            swap(B[x], B[y]);
//        }
        for (int i = 0; i < n; i++) {
            C[A[i] - 1] = B[i] - 1;
        }
        
        PILE *node = new PILE();
        PILE::MAXSIZE = (int)sqrt(n) + 1;
        PILE::head = node;
        PILE::BUFSIZE = 0;
        PILE::BUFSIZE++;
        node->label = PILE::BUFSIZE, node->next = node;
        for (int i = 0; i < n; i++) {
            node->v[node->size++] = C[i];
            mp[C[i]] = node->label;
            if (node->size == PILE::MAXSIZE) {
                PILE *tmp = new PILE();
                PILE::BUFSIZE++;
                tmp->label = PILE::BUFSIZE;
                tmp->next = node->next;
                node->next = tmp;
                node = node->next;
            }
        }
        
        solve(n);
        
        for (int i = 0; i < n; i++) {
            printf("%d%c", C[i], i == n - 1 ? '\n' : ' ');
        }
    }
    return 0;
}
/*
 5
 1 2 3 4 5
 3 2 5 1 4
 4
 1 2 3 4
 3 4 1 2
*/

Read More +

Aug 28 2014

解題區►解題區 - UVa

UVa 10694 - Combinatorial Summation

Problem

對於組合公式，輸出其結果。

Sample Input

1
2
3

2
3
4

Sample Output

1
2

7
14

Solution

暴力法將前幾項找出來，發現其相鄰兩項之差恰好有規律。

1 2	0 1 3 7 14 26 46 79 133 0 2 4 7 12 20 33 54

其規律是前兩項總和再加一。

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
	public static void main(String[] args) {
		BigInteger[] f1 = new BigInteger[1024];
		BigInteger[] f2 = new BigInteger[1024];
		f1[1] = BigInteger.valueOf(2);
		f1[2] = BigInteger.valueOf(4);
		f2[0] = BigInteger.valueOf(0);
		f2[1] = BigInteger.valueOf(1);
		for (int i = 3; i < f1.length; i++)
			f1[i] = f1[i - 2].add(f1[i - 1]).add(BigInteger.ONE);
		for (int i = 2; i < f2.length; i++)
			f2[i] = f2[i - 1].add(f1[i - 1]);
		Scanner cin = new Scanner(System.in);
		int testcase = cin.nextInt();
		while (testcase-- != 0) {
			int n = cin.nextInt();
			if (n < 0)
				n = 0;
			System.out.println(f2[n]);
		}
	}
}
/*
 * 0 1 3 7 14 26 46 79 133 
 	 0 2 4 7 12 20 33 54
 */

Read More +

Aug 28 2014

解題區►解題區 - UVa

UVa 1635 - Irrelevant Elements

Problem

題目給定一種亂數產生方式，一開始先給定 n 個數字序列 ai (1 <= i <= n)，之後相鄰兩兩相加得到 n - 1 個數字的序列，最後這一個數字 mod m = ? 來決定最後要輸出的亂數。

請問最後產生出來的數字無關序列的第幾項。

Sample Input

3 2

Sample Output

1
2

1
2

Solution

其實可以見到的，第 i 個數字會在最後使用 C(n-1, i) 次，無關的意思，也就是說恰好 C(n-1, i) == 0 mod m，不管 ai 為何皆不影響最後產生出來的數字。

為了加速運算，我們必須先質因數分解 m 的結果。

對於 C(a, b) = a! / (b!(b-a)!) 是否整除 m，查閱 m 的所有質因數 p 的個數是否符合需求。

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
#define maxL (50000>>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[5500], Pt = 0;
void sieve() {
    register int i, j, k, l;
    SET(1);
    int n = 50000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(j = i + i; j <= n; j += i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
int isPrime(int n) {
    for(int i = 0; i < Pt && P[i] * P[i] <= n; i++) {
		if(n%P[i] == 0) {
			return 0;
		}
	}
    return 1;
}
vector< pair<int, int> > factor(int n) {
	vector< pair<int, int> > R;
	
	for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
		if(n%P[i] == 0) {
			for(j = 0; n%P[i] == 0; n /= P[i], j++);
			R.push_back(make_pair(P[i], j));
		}
	}
	if(n != 1)	R.push_back(make_pair(n, 1));
	return R;
}
int g(int n, int p) {
    int ret = 0;
    long long pp = p;
    while (n >= pp) {
        ret += n / pp;
        pp *= p;
    }
    return ret;
}
int main() {
    sieve();
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        vector< pair<int, int> > f = factor(m);
        vector<int> solution;
        n--;
        for (int i = 0; i <= n; i++) {
            int ok = 1;
            for (int j = 0; j < f.size() && ok; j++) {
                int p = f[j].first;
                int cnt = g(n, p) - g(i, p) - g(n - i, p); // C(n, i) has p^cnt.
                if (cnt < f[j].second) {
                    ok = 0;
                }
            }
            if (ok) {
                solution.push_back(i + 1);
            }
        }
        printf("%d\n", (int)solution.size());
        for (int i = 0; i < solution.size(); i++) {
            printf("%d%s", solution[i], i == solution.size() - 1 ? "" : " ");
        }
        puts("");
    }
    return 0;
}

Read More +

Aug 28 2014

解題區►解題區 - UVa

UVa 1594 - Ducci Sequence

Problem

將序列根據步驟轉換，是否會產生迴圈或者是回歸到 0。

Sample Input

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

Sample Output

ZERO 
LOOP 
ZERO 
LOOP

Solution

用 hash (RS hashing) 來壓縮一下儲存的方式，碰撞的機率應該是挺低的。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <map>
#include <algorithm>
using namespace std;
int nextSeq(int A[], int n) {
    int B[32];
    A[n] = A[0];
    for (int i = 0; i < n; i++)
        B[i] = abs(A[i] - A[i+1]);
    for (int i = 0; i < n; i++)
        A[i] = B[i];
    return 1;
}
int main() {
    int testcase, n, A[32];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        map<int, int> R;
        do {
            int ok = 1, hash = 0;
            int a = 63689, b = 378551;
            for (int i = 0; i < n; i++) {
                hash = hash * a + A[i], a = a * b;
                ok &= A[i] == 0;
            }
            if (ok) {
                puts("ZERO");
                break;
            }
            int &f = R[hash];
            if (f) {
                puts("LOOP");
                break;
            }
            f = 1;
        } while (nextSeq(A, n));
    }
    return 0;
}
/*
 4
 4
 8 11 2 7
 5
 4 2 0 2 0
 7
 0 0 0 0 0 0 0
 6
 1 2 3 1 2 3
 */

Read More +

Aug 28 2014

解題區►解題區 - UVa

UVa 1590 - IP Networks

Problem

找在同一個區域的 IP 中的 IP 遮罩。

Sample Input

3 
194.85.160.177 
194.85.160.183 
194.85.160.178

Sample Output

1 2	194.85.160.176 255.255.255.248

Solution

也就是說我們必須找到其最長共同前綴，知道共同前綴的長度直接輸出 1111111…111000。

用 trie 對於這一道題目，只會用到 0/1 兩種字符，也可以直接暴力掃描，用 trie 沒有甚麼特別快的好處。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Trie {
    int n, label, dist;
    int link[2];
} 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]-'0'] == 0) {
			TrieSize++;
			memset(&Node[TrieSize], 0, sizeof(Node[0]));
			Node[TrieSize].label = TrieSize;
			Node[TrieSize].dist = i + 1;
			Node[idx].link[str[i]-'0'] = TrieSize;
		}
		idx = Node[idx].link[str[i]-'0'];
	}
	Node[idx].n ++;
	return Node[idx].label;
}
void binaryIP(const int ip[], char buf[]) {
    int idx = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 8 - 1; j >= 0; j--) {
            buf[idx++] = '0' + ((ip[i]>>j)&1);
        }
    }
    buf[idx] = '\0';
}
void getAllLCP(char buf[]) {
    int idx = 0, bidx = 0;
    do {
        int branch = 0, next = 0, c = 0;
        for (int i = 0; i < 2; i++) {
            if (Node[idx].link[i]) {
                branch++, next = Node[idx].link[i], c = i;
            }
        }
        if (branch != 1)
            break;
        buf[bidx++] = c + '0', idx = next;
    } while (true);
    buf[bidx] = '\0';
}
int main() {
    int n, ip[4];
    char bip[128];
    while (scanf("%d", &n) == 1) {
        TrieSize = 0;
        memset(&Node[0], 0, sizeof(Node[0]));
        for (int i = 0; i < n; i++) {
            scanf("%d.%d.%d.%d", &ip[0], &ip[1], &ip[2], &ip[3]);
            binaryIP(ip, bip);
            insertTrie(bip);
        }
        getAllLCP(bip);
        int m = (int)strlen(bip);
        for (int i = 0; i < 4; i++) {
            int bb = 0;
            for (int j = 8 - 1; j >= 0; j--) {
                if (i * 8 + 7 - j < m) {
                    if (bip[i * 8 + 7 - j] == '1') {
                        bb |= 1<<j;
                    }
                }
            }
            printf("%d%c", bb, i == 3 ? '\n' : '.');
        }
        for (int i = 0; i < 4; i++) {
            int bb = 0;
            for (int j = 8 - 1; j >= 0; j--) {
                if (i * 8 + 7 - j < m) {
                    bb |= 1<<j;
                }
            }
            printf("%d%c", bb, i == 3 ? '\n' : '.');
        }
    }
    return 0;
}
/*
 3
 194.85.160.177
 194.85.160.183
 194.85.160.178
*/

Read More +

Aug 28 2014

解題區►解題區 - UVa

UVa 816 - Abbott's Revenge

Problem

給每一個路口的可行進方向，請問從起點到終點的最短路徑為何。

Sample Input

SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END

Sample Output

SAMPLE
  (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1)
  (2,2) (1,2) (1,3) (2,3) (3,3)
NOSOLUTION
  No Solution Possible

Solution

忘記有可能起點和終點一樣，所以刷了不少 WA。

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string.h>
using namespace std;
int g[32][32][4];
char dirName[1024] = "NESW";
const int dx[] = {-1, 0, 1, 0}; // N, E, S, W
const int dy[] = {0, 1, 0, -1};
void bfs(int sx, int sy, int sdir, int ex, int ey) {
    int visited[32][32][4] = {};
    int fdir[] = {-1, 1, 0}, tx, ty;
    queue<int> X, Y, D;
    pair<int, pair<int, int> > from[32][32][4];
    int ox = sx, oy = sy;
    sx += dx[sdir], sy += dy[sdir];
    X.push(sx), Y.push(sy), D.push(sdir);
    visited[sx][sy][sdir] = 1;
    from[sx][sy][sdir] = make_pair(-1, make_pair(-1, -1));
    while (!X.empty()) {
        sx = X.front(), X.pop();
        sy = Y.front(), Y.pop();
        sdir = D.front(), D.pop();
        if (sx == ex && sy == ey) {
            int tx, ty, dir;
            stack< pair<int, int> > stk;
            tx = sx, ty = sy, dir = sdir;
            while (tx >= 0) {
                stk.push(make_pair(tx, ty));
                int ttx = from[tx][ty][dir].second.first;
                int tty = from[tx][ty][dir].second.second;
                int tdd = from[tx][ty][dir].first;
                tx = ttx, ty = tty, dir = tdd;
            }
            stk.push(make_pair(ox, oy));
            int output = 0;
            while (!stk.empty()) {
                if (output%10 == 0) {
                    printf("\n ");
                }
                pair<int, int> pt = stk.top();
                stk.pop();
                printf(" (%d,%d)", pt.first, pt.second);
                output++;
            }
            puts("");
            return ;
        }
        for (int i = 0; i < 3; i++) {
            if (g[sx][sy][sdir]&(1<<i)) {
                int dir = (sdir + fdir[i] + 4)%4;
                tx = sx + dx[dir], ty = sy + dy[dir];
                if (visited[tx][ty][dir] == 0) {
                    visited[tx][ty][dir] = 1;
                    X.push(tx), Y.push(ty), D.push(dir);
                    from[tx][ty][dir] = make_pair(sdir, make_pair(sx, sy));
                }
            }
        }
    }
    printf("\n  No Solution Possible\n");
}
int main() {
    char testcase[1024], sdir[1024];
    int x, y, sx, sy, ex, ey;
    while (gets(testcase) && strcmp("END", testcase)) {
        memset(g, 0, sizeof(g));
        scanf("%d %d %s %d %d", &sx, &sy, sdir, &ex, &ey);
        while (scanf("%d", &x) == 1 && x) {
            scanf("%d", &y);
            char token[10];
            while (scanf("%s", token) == 1 && token[0] != '*') {
                int dir = find(dirName, dirName+4, token[0]) - dirName;
                int follow = 0;
                for (int i = 1; token[i]; i++) {
                    switch (token[i]) {
                        case 'L': follow |= 1; break;
                        case 'R': follow |= 2; break;
                        case 'F': follow |= 4; break;
                    }
                }
                g[x][y][dir] = follow;
            }
        }
        int dir = find(dirName, dirName+4, sdir[0]) - dirName;
        printf("%s", testcase);
        bfs(sx, sy, dir, ex, ey);
        while (getchar() != '\n');
    }
    return 0;
}
/*
SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END
 
 
 SAMPLE
 3 1 N 3 3
 1 1 WL NR *
 1 2 WLF NR ER *
 1 3 NL ER *
 2 1 SL WR NF *
 2 2 SL WF ELF *
 2 3 SFR EL *
 0
 NOSOLUTION
 3 1 N 3 2
 1 1 WL NR *
 1 2 NL ER *
 2 1 SL WR NFR *
 2 2 SR EL *
 0
 MyMaze 1
 3 1 N 1 1
 0
 MyMaze 2
 3 1 N 3 1
 0
 MyMaze 3
 3 1 N 2 1
 0
 MyMaze 4
 2 2 W 3 2
 1 1 NR *
 1 2 ER *
 2 1 WR *
 2 2 SF *
 0
 MyMaze 5
 2 2 N 2 3
 1 1 WL *
 1 2 NL *
 2 1 SF *
 2 2 NR *
 3 1 SL *
 3 2 EL *
 0
 Circle
 2 1 N 2 1
 1 1 NR *
 1 2 ER *
 2 2 SF *
 3 1 WR *
 3 2 SR *
 0
 Robert Abbott's Atlanta Maze
 4 2 N 4 3
 1 1 NR WL *
 1 2 NLR WF EFR *
 1 3 EFR WFR NL *
 1 4 ER NL *
 2 1 SFL WL NFR *
 2 2 EL SFLR WFRL NFL *
 2 3 EFLR SF NF WFRL *
 2 4 SR ELR NF *
 3 1 WR SL *
 3 2 EFL SLR WR NF *
 3 3 EFL SLR WL *
 3 4 EL SR *
 0
 END
 */

Read More +

Aug 28 2014

解題區►解題區 - UVa

UVa 721 - Invitation Cards

Problem

ACM 參賽選手要到比賽會場，公車都是單向運行，求選手們來回的最少花費。

給一個有向圖，求從編號 1 到所有點的最短路徑總和，以及所有點到編號 1 的最短路徑總和。

Sample Input

Sample Output

1
2

46
210

Solution

對一開始給定的圖，從編號 1 做一次 SSSP (單源最短路徑)，隨後再對題目給的反向圖做一次 SSSP 即可以得到所有點到編號 1 的最短路徑。

這一題很類似於 zerojudge 的地道問題。

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 1048576
vector< pair<int, long long> > g[MAXN], invg[MAXN];
long long dist[MAXN];
int inq[MAXN];
long long spfa(int source, int n, vector< pair<int, long long> > g[]) {
    for (int i = 0; i < n; i++) {
        dist[i] = 1LL<<60, inq[i] = 0;
    }
    queue<int> Q;
    int u, v;
    long long w;
    Q.push(source), dist[source] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].first, w = g[u][i].second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    Q.push(v), inq[v] = 1;
                }
            }
        }
    }
    long long ret = 0;
    for (int i = 0; i < n; i++) {
        ret += dist[i];
    }
    return ret;
}
int main() {
    int testcase, N, M;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &M);
        for (int i = 0; i < N; i++) {
            g[i].clear(), invg[i].clear();
        }
        for (int i = 0; i < M; i++) {
            int x, y, c;
            scanf("%d %d %d", &x, &y, &c);
            x--, y--;
            g[x].push_back(make_pair(y, c));
            invg[y].push_back(make_pair(x, c));
        }
        long long ret = 0;
        ret += spfa(0, N, g);
        ret += spfa(0, N, invg);
        printf("%lld\n", ret);
    }
    return 0;
}
/*
 2
 2 2
 1 2 13
 2 1 33
 4 6
 1 2 10
 2 1 60
 1 3 20
 3 4 10
 2 4 5
 4 1 50
*/

Read More +

Aug 28 2014

解題區►解題區 - UVa

UVa 561 - Jackpot

Problem

拉霸遊戲，給你每一個輪子上的情況，而你可以可以看到每個輪子的連續三個可視範圍。

可視範圍構成的 3 x 3 區塊，

如果上面一排都是相同元素，則獎金累加 5 元
如果下面一排都是相同元素，則獎金累加 5 元
如果中間一排都是相同元素，則獎金累加 10 元
如果左上到右下的對角線上都是相同元素，則獎金累加 7 元
如果右上到左下的對角線上都是相同元素，則獎金累加 7 元

求轉動一次的期望獎金為何

Sample Input

2
3 4 6
AAB
BABA
BBAAAB
12 15 18
CCCCCCCCCCCC
CCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCC

Sample Output

1 2	8.5000 34.0000

Problem

直接窮舉每一種字符的機率於每一個位置即可。

#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
int main() {
    int testcase;
    int A, B, C;
    char sa[1024], sb[1024], sc[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &A, &B, &C);
        scanf("%s %s %s", sa, sb, sc);
        int cntA[26] = {}, cntB[26] = {}, cntC[26] = {};
        for (int i = 0; sa[i]; i++) {
            cntA[sa[i] - 'A']++;
        }
        for (int i = 0; sb[i]; i++) {
            cntB[sb[i] - 'A']++;
        }
        for (int i = 0; sc[i]; i++) {
            cntC[sc[i] - 'A']++;
        }
        double ret = 0;
        for (int i = 0; i < 26; i++) {
            ret += cntA[i] * cntB[i] * cntC[i] * 7.0 / A/ B/ C * 2;
            ret += cntA[i] * cntB[i] * cntC[i] * 10.0 / A/ B/ C;
            ret += cntA[i] * cntB[i] * cntC[i] * 5.0 / A/ B/ C * 2;
        }
        printf("%.4lf\n", ret);
    }
    return 0;
}
/*
 2
 3 4 6
 AAB
 BABA
 BBAAAB
 12 15 18
 CCCCCCCCCCCC
 CCCCCCCCCCCCCCC
 CCCCCCCCCCCCCCCCCC
*/

Read More +

Aug 28 2014

解題區►解題區 - UVa

UVa 560 - Magic

Problem

根據下列幾個條件，要把一個數字移除掉這些性質。

if a number is divisible by 3: divide it by 3
if a number is divisible by 7: divide it by 7
if a 3 occurs in the decimal representation: remove this 3 (remove if possible leading zeros)
if a 7 occurs in the decimal representation: remove this 7 (remove if possible leading zeros)
if a substring of 3 times the same digit occurs in the decimal representation: remove * it (remove if possible leading zeros)
if a substring of 7 times the same digit occurs in the decimal representation: remove it (remove if possible leading zeros)
if eventually no digit is left, consider this as the number 0.

移除的位置和順序可以任意替換，請問最後最大的數字為何？

Sample Input

Sample Output

1
2
3

11
2
11

Solution

模擬這些移除的操作，使用 bfs 搜索，由於數字會越來越小，因此小於當前答案的部分可以忽略搜索，否則將很容易得到 TLE。

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
using namespace std;
string divideString(string u, int div) {
    char s[1024] = {};
    int num = 0;
    for (int i = 0; i < u.length(); i++) {
        num = num * 10 + u[i] - '0';
        s[i] = num/div + '0', num %= div;
    }
    int idx = s[0] == '0' ? 1 : 0;
    string v = s + idx;
    return v;
}
string removePos(string u, int pos, int items = 1) {
    string v = u.substr(0, pos) + u.substr(pos + items);
//    cout << u << ", " << pos <<" = " << v<< endl;
    if (v.length() == 0)
        return "0";
    return v;
}
int numicStringCompare(string u, string v) {
    if (u.length() != v.length())
        return u.length() < v.length();
    for (int i = 0; i < u.length(); i++) {
        if (u[i] != v[i])
            return u[i] < v[i];
    }
    return 0;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        char s[1024];
        scanf("%s", s);
        set<string> diff;
        queue<string> Q;
        string ret = "";
        diff.insert(s), Q.push(s);
        while (!Q.empty()) {
            string u = Q.front();
            Q.pop();
//            cout << u << endl;
            if (numicStringCompare(u, ret))
                continue;
            int r3 = 0, r7 = 0;
            int cond = 0;
            for (int i = 0; i < u.length(); i++) {
                r3 = (r3 * 10 + u[i] - '0')%3;
                r7 = (r7 * 10 + u[i] - '0')%7;
            }
            if(r3 == 0) {
                string v = divideString(u, 3);
                if (diff.find(v) == diff.end())
                    diff.insert(v), Q.push(v);
                cond = 1;
            }
            if (r7 == 0) {
                string v = divideString(u, 7);
                if (diff.find(v) == diff.end())
                    diff.insert(v), Q.push(v);
                cond = 1;
            }
            for (int i = 0; i < u.length(); i++) {
                if (u[i] == '3' || u[i] == '7') {
                    string v = removePos(u, i);
                    if (diff.find(v) == diff.end())
                        diff.insert(v), Q.push(v);
                    cond = 1;
                }
            }
            for (int i = 0; i < u.length(); i++) {
                int con3 = 0, con7 = 0;
                for (int j = i, k = 0; k < 3 && j < u.length(); j++, k++) {
                    if (u[j] == u[i])
                        con3++;
                    else    break;
                }
                for (int j = i, k = 0; k < 7 && j < u.length(); j++, k++) {
                    if (u[j] == u[i])
                        con7++;
                    else    break;
                }
                if (con3 == 3) {
                    string v = removePos(u, i, 3);
                    if (diff.find(v) == diff.end())
                        diff.insert(v), Q.push(v);
                    cond = 1;
                }
                if (con7 == 7) {
                    string v = removePos(u, i, 7);
                    if (diff.find(v) == diff.end())
                        diff.insert(v), Q.push(v);
                    cond = 1;
                }
            }
            if (cond == 0) {
                if (numicStringCompare(ret, u)) {
                    ret = u;
                }
            }
        }
        cout << ret << endl;
    }
    return 0;
}
/*
 3
 999
 273
 2331
 
 6
 4900006514979587103
 9305660497031957126752544737246
 13708976269278645181999140607
 1427490008594779
 107351103235212538538682
 65244379091939972650698
*/

Read More +

Aug 28 2014

解題區►解題區 - UVa

UVa 358 - Don't Have A Cow

Problem

有一個半徑為 R 的圓草地，接著將一頭牛綁在圓周上 (定點)，請問繩長多少的時候，恰好能夠將圓佔有 P% 的面積。

Sample input

1 2	1 100 0.33

Sample output

1	R = 100, P = 0.33, Rope = 13.24

Solution

將圓放在坐標軸上，假設綁定的位置於 (R, 0)，而接著二分另外一點 (於圓上) 可以拉到綁定的位置。

計算繩長和面積即可。

#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
#define eps 1e-8
int main() {
    int testcase;
    double R, P;
    const double pi = acos(-1);
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf %lf", &R, &P);
        double l = 0, r = pi, mid, ret = 0;
        double A = R * R * pi;
        while (fabs(l - r) > eps) {
            mid = (l + r)/2;
            ret = hypot(R * cos(mid) - R, R * sin(mid));
            double theta = (pi - mid)/2;
            double area = (ret * ret * theta/2 + (R * R * mid/2 - R * R * sin(mid)/2))*2;
            if (area < A * P)
                l = mid;
            else
                r = mid;
        }
        printf("R = %.0lf, P = %.2lf, Rope = %.2lf\n", R, P, ret);
        if(testcase)
            puts("");
    }
    return 0;
}
/*
*/

Read More +