UVa Online Judge -- 400 AC

寫到快吐血了。

今天還是寫很多水題，包括 Circular (Primes)，

之前誤以為是 Anagrammatic Primes，

傻傻的直接把 22 丟到 Project Euler Problem 35 吃 WA。



PS. Project Euler 的 Confirmation Code 很機歪，7 跟 1 長的超級像的 = ="

UVa 332 - Rational Numbers from Repeating Fractions

Problem

這是很好玩的題目，國中有教怎麼把循環小數變成最簡分數。

如果不是循環小數，當然也可以變成最簡分數。



Source Code

接下來是細節，讀取 I/O。

2 0.318
1 0.3
2 0.09
6 0.714285
-1

這個很容易使用 double / float 去存 0.318 小數部份，

但如果使用 C++ native double / float data type，

又很容易產生本質上的誤差，乾脆把 0.318 當成字串處理還比較直覺。

((Java BigDecimal 就是採用這種處理方式))

除非逼不得已，盡量少用 double / float，

如果吃到 WA，還得慢慢嘗試把答案補上 1e-7 類似這種魔術數字。

UVa World Rank < 1000

終於洗到 1000 名以內了。

題目來自 Competitive Programming Edition 1 ~ 3，

每個題目都有分程度 (Level)，打怪要從簡單的怪開始打，數字越小越簡單。

最近 Competitive Programming Edition 1 作者贈送免費電子版，

大家可以抓下來研究研究，端詳一下高手怎麼寫題目的

((難怪會輸慘慘))

除了以上題目，我也會挑一些數學題目做爽爽，

# submissions 很低的題目不見得是難題，那僅僅表示 # submissions 很低而已，

大家要勇敢一點，把那些怪打掉。

UVa 11462 -- Age Sort

Problem

Counting sort.

不過不是要講這個，而是一個 online judge system 擺上一題需要 25MB 測資，

限時 5 秒的題目，很容易被 DDoS 攻擊。

UVa 11343 - Isolated Segments

Problem: UVa 11343 - Isolated Segments

AC code: https://github.com/Meng-Gen/UVa/blob/master/UVa/acm_11343.cc



CLRS, Introduction to Algorithm, 3/e.

Chapter 33: Computational Geometry 第一節就有教，

直接把書上演算法抄成 C++ 就可以了，其他都是實做上的細節，

與整個演算無關。

UVa 429 - Word Transformation

http://uva.onlinejudge.org/external/4/429.html

單純的 BFS，因為 |V| 夠小，又是多次詢問最短距離，

所以可以用 Floyd-Warshall algorithm 簡單實作。

V_i 與 V_j 相連的條件就是兩字串一樣長，而且只差一個 letter。

#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <stdio.h>

#define INFINITY_WEIGHT (999)

int T[205][205] = {};

inline int minimum(int a, int b) 
{
    return (a < b) ? a : b;
}

bool HasTransformation(const std::string& a, const std::string& b)
{
    if (a.size() != b.size())
    {
        return false;
    }

    int diff_count = 0;
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] != b[i])
        {
            diff_count++;
        }
    }
    return (diff_count == 1);
}

int main(int argc, char* argv[])
{
    int num_testcases;
    std::cin >> num_testcases;
    for (int case_id = 0; case_id < num_testcases; case_id++)
    {
        if (case_id)
        {
            putchar('\n');
        }

        std::map<std::string, int> word_map;
        std::map<int, std::string> word_id_map;
        std::string word;
        int dictionary_size = 0;
        while (std::cin >> word && word.compare("*"))
        {
            word_map[word] = dictionary_size;
            word_id_map[dictionary_size] = word;
            dictionary_size++;
        }

        // Initialize.
        for (int i = 0; i < dictionary_size; i++)
        {
            for (int j = 0; j < dictionary_size; j++)
            {
                if (i != j)
                {
                    T[i][j] = INFINITY_WEIGHT;
                }
            }
        }

        for (int i = 0; i < dictionary_size; i++)
        {
            for (int j = i+1; j < dictionary_size; j++)
            {
                if (HasTransformation(word_id_map[i], word_id_map[j]))
                {
                    T[i][j] = 1;
                    T[j][i] = 1;
                }
            }
        }

        // Floyd-Warshall algorithm.
        // The graph is quite small (|V| = 200), and thus constructing 
        // all shortest paths for O(1) query is good for this problem.
        for (int k = 0; k < dictionary_size; k++)
        {
            for (int i = 0; i < dictionary_size; i++)
            {
                for (int j = 0; j < dictionary_size; j++)
                {
                    T[i][j] = minimum(T[i][j], T[i][k] + T[k][j]);
                }
            }
        }

        // Query.
        getchar();
        std::string query;
        while (getline(std::cin, query) && query.size())
        {
            unsigned int found = query.find_first_of(" ");
            std::string word[2] = {
                query.substr(0, found), query.substr(found + 1)
            };
            printf("%s %d\n", 
                query.c_str(), 
                T[word_map[word[0]]][word_map[word[1]]]);
        }
    }

    return 0;
}