解題區/解題區 - 其他題目

2015 Facebook Hacker Cup 資格賽

contents

［2015 Facebook Hacker Cup 資格賽］贖罪篇

windows 參賽，卡了一個 \r\n 問題，剛好有裝 git，使用以下指令做轉換

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt
  • Cooking the Books (15 points)

會計師要騙過稽查人員，可以把金融數值任意交換兩個位置上的數字，請問能交換得到的最大、最小值分別為何？並且數字不可起首為 0。

喵蛋，最簡單的這題 recover step 因 continue 指令而被忽略，窮舉兩個位置做交換，大部分可以看到寫法有 string compare, int compare，最方便是在字串下處理，接著看要轉數字或者直接用字典順序比較都行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    freopen("cooking_the_books.txt", "r", stdin);
    freopen("out.txt", "w+", stdout); 
    int testcase, cases = 0;
    char s[64];
    scanf("%d", &testcase);
    while (testcase--) {
        long long ret1, ret2, tmp;
        scanf("%s", s);
        sscanf(s, "%lld", &ret1);
        sscanf(s, "%lld", &ret2);
        int n = strlen(s);
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                swap(s[i], s[j]);
                sscanf(s, "%lld", &tmp);
                if (s[0] != '0') { 
                    ret1 = min(ret1, tmp);
                    ret2 = max(ret2, tmp);
                } 
                swap(s[i], s[j]);
            }
        }
        printf("Case #%d: %lld %lld", ++cases, ret1, ret2);
        putchar('\n');
    }
    return 0;
}
  • New Year’s Resolution (30 points)

新年新希望，目標均衡飲食，要求蛋白質、澱粉、脂肪攝取剛好的量，挑選 n 個食物，只有不選、或者是只能一樣走。求是否能辦到？

在 n 不大的時候，套用 bitmask 窮舉最為方便。用 Dfs 搜索當然喜聞樂見，如果 n 很大，而要求的量很小，則可以使用三維 dp[P][C][F] 狀態來解決。如果要求倍數關係，而數量無限的話，可以轉換成幾何分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    freopen("new_years_resolution.txt", "r", stdin);
    freopen("out.txt", "w+", stdout); 
    int testcase, n, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int GP, GC, GF;
        int P[32], C[32], F[32];
        scanf("%d %d %d", &GP, &GC, &GF);
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d %d %d", &P[i], &C[i], &F[i]);
            
        int ret = 0;
        for (int i = (1<<n)-1; i >= 0 && !ret; i--) {
            int a = 0, b = 0, c = 0;
            for (int j = 0; j < n; j++) {
                if ((i>>j)&1) {
                    a += P[j];
                    b += C[j];
                    c += F[j];
                }
            }
            ret |= a == GP && b == GC && c == GF;
        }
        printf("Case #%d: %s\n", ++cases, ret ? "yes" : "no");
    }
    return 0;
}
  • Laser Maze (55 points)

給予 2D 地圖，裡面的雷射裝置將會感應使用者的腳步，每踏一步則順時針換方向，並且發射出雷射，雷射只會因牆壁、雷射塔而被屏蔽，但是雷射跟雷射之間不會相消、折射。現在雷射裝置的起始方向各有不同，避開雷射，找最少步數抵達終點。(只能走上下左右四個方向，停留不能解決問題，雷射裝置因感測而行動。)

基礎的 Bfs，因為只有四個方向，根據時間做紀錄，每四次操作進行一個循環，則 int dist[time4][pos_x][pos_y]，考慮在哪一個 time mod 4 抵達某個位置。接下來麻煩的是檢查操作，檢查操作有兩種，其一，預處理每個時間下雷射發射，其二，從當前位置反搜索雷射光是否對著自己。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
char g[128][128];
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const char dv[] = "<^>v";
int dist[4][128][128], n, m;
int valid(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m;
}
char next(char c, int t) {
    static char v[] = "^>v<";
    for (int i = 0; i < 4; i++) {
        if (v[i] == c)
            return v[(i + t)%4];
    }
    assert(false);
}
int test(int t, int x, int y) {
    int tx, ty;
    for (int i = 0; i < 4; i++) {
        tx = x, ty = y;
        while (valid(tx, ty) && g[tx][ty] == '.')
            tx += dx[i], ty += dy[i];
        if (valid(tx, ty) && g[tx][ty] != '#') {
            char c = g[tx][ty];
            if (next(c, t) == dv[i])
                return 1;
//			printf("%c %c %d\n", next(g[tx][ty], t), dv[i], i);
        }
    }
    return 0;
}
void bfs() {
    memset(dist, 0, sizeof(dist));
    int sx, sy, ex, ey;
    int x, y, tx, ty, t;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S')
                sx = i, sy = j, g[i][j] = '.';
            if (g[i][j] == 'G')
                ex = i, ey = j, g[i][j] = '.';
        }
    }
    dist[0][sx][sy] = 1;
    queue<int> X, Y, T;
    X.push(sx), Y.push(sy), T.push(0);
    while (!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        t = T.front(), T.pop();
        int d = dist[t][x][y] + 1;
        if (x == ex && y == ey) {
            printf("%d\n", d - 2);
            return;
        }
        for (int i = 0; i < 4; i++) {
            tx = x + dx[i], ty = y + dy[i];
            if (!valid(tx, ty))
                continue;
            if (g[tx][ty] != '.')
                continue;
            if (test((t+1)%4, tx, ty))
                continue;
            if (dist[(t+1)%4][tx][ty] == 0) {
                dist[(t+1)%4][tx][ty] = d;
                X.push(tx), Y.push(ty), T.push((t+1)%4);
            }
        }
    }
    puts("impossible");
}
int main() {
    freopen("laser_maze.txt", "r", stdin);
    freopen("out.txt", "w+", stdout);
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%s", &g[i]);
        printf("Case #%d: ", ++cases);
        bfs();
    }
    return 0;
}
/*
999
2 5
##^##
S...G
2 6
###<##
S....G
2 5
##v##
S...G
1 5
S..G<
1 6
S...G<
5 5
S....
.....
.>v..
.^<..
....G
*/