UVA 910 TV game

dp uva dfs

我一開始看錯了題目, 以為是只有走 ‘1’ 的邊才把總值加一.
我是想到了用 dfs, 但是又怕時間太長, 結果看了別人才敢動手.
這一點真的要改一下.

More...

UVA 11623 Tic Tac Toe

uva

這題基本思路不難, 但實作很麻煩. 要把所有 Error case 找出來. 我第一次的答案 TLE 了. 花了太多時間, 不想再拖下去, 找了一下其他答案, 參考一下, 自己再寫.

注意, 這答案沒有考慮當一直線長度超過 m*2 - 1　的情況, 不過 uva 似乎沒有這個 test case, 所以是 AC

More...

UVA 998 Many Paths, One Direction

uva dfs

看到問題就覺得是 dfs, 交了去 uva 之後一直都就是 in the judging queue 的狀態. 所以用空間換取時間, 把於每個Event的結果儲起來, 省去重疊的計算.

交完之後就 AC ,但前一次的 submission 還是in the judging queue ….

More...

UVA 11198 Dancing Digits

uva bfs

用 bfs 把所有可能跑一次. 當中要用到 hash 去記綠試了那些可能性.
我面對 BFS 和 DFS 的問題時, 總是會覺得有其他方法. 到最後才試 bfs, 浪費了不少時間.

More...

UVA 11500 - Vampires

math uva

這是賭徒破產理論, 想了好久, 最後還是看別人教學了.
這大概就是數學問題的特點 - 如果你根本不知道相關理論, 問題是很難解的. (即使是數學家也要花不少時間才想出他的理論呢). 但如果你知道公式, 直接帶入公式就 AC 了.

當嬴的概率是 0.5 時

p1 when a is 3
p2 when a is 3

當嬴的概率不是 0.5 時

p1 when a != 3
p2 when a != 3

不過wiki的公式是玩家破產的概率. 而我們要的是嬴的概率, 也就是對方破產的概率.　
所以我們是用 P2 的公式. wiki 中的介紹還滿容易明白的, 可以仔細看一下.

wiki 連結

uva11500.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <cmath>

int main () {
    int ev1, ev2, at, d;

    while (scanf("%d%d%d%d", &ev1, &ev2, &at, &d) != EOF && ev1) {
        int ev1c = ceil( (double)ev1/d );
        int ev2c = ceil( (double)ev2/d );
        double winchance = at/6.0;
        double qp = (1 - winchance)/winchance;

        if(at == 3)
            printf("%.1lf\n", 100 * (double)ev1c/(ev1c + ev2c));
        else
            printf("%.1lf\n", (double)((1 - pow(qp, ev1c)) * 100 )/(1 - pow(qp, ev1c + ev2c)) );
    }

    return 0;
}