買農地也跟買房子一樣

過了一個颱風，又檢視了淹水區，這次多數地區颱風還沒來就淹個七葷八素，不料仍有房仲說：偶有淹水問題，成交量還是十分穩定。除人為因素的淹水外，逢大雨就淹的地區，想自住者別買。

在地者知道哪裡會淹，多半因地勢原本就低漥，加上排水長期不良，才會下個雨就淹，但外地人多半不知，而因為房價太高，購屋都愈購愈遠，當你想買你不熟悉的區域前，請上網爬文，幾次颱風下來，都有大量報導可參考。至於南崁交流道的淹水，我看是沒救了，父母官只想炒地。

Sway

買農地也是，特別是低窪地區，或者是下風處，

通常得靠颱風照妖鏡才能顯露本相。

ProjectEuler Problem 221 -- Alexandrian Integers

ProjectEuler 剛解完一題，接下來頭腦就結屎了。

Problem 221 -- Alexandrian Integers。

1/A = 1/p + 1/q + 1/r 

=> 1/A - 1/r = 1/p + 1/q 

=> 1/r * (1-pq)/pq = 1/p + 1/q 

=> r = (1-pq)/(p+q)

這邊似乎卡住了，但如果把分子分母看成 f(p,q)/g(p,q) 多項式的除法表示，分子似乎可以降次。

r = (1 - p(p+q) + p^2)/(p+q) 

=> r = -p + (1+p^2)/(p+q).

然後又卡住了，所以我直接硬爆，現在出來疑似答案還是錯的。

BERKSHIRE HATHAWAY INC. SHAREHOLDER LETTERS 2012

錯過許多。Recap。

保險業的基本四要求 ((對比投資，根本就是異曲同工))

• understand all exposures that might cause a policy to incur losses; 
• conservatively assess the likelihood of any exposure actually causing a loss and the probable cost if it does; 
• set a premium that, on average, will deliver a profit after both prospective loss costs and operating expenses are covered;
• be willing to walk away if the appropriate premium can’t be obtained.

Many insurers pass the first three tests and flunk the fourth. They simply can’t turn their back on business that is being eagerly written by their competitors. That old line, “The other guy is doing it, so we must as well,” spells trouble in any business, but none more so than insurance.

別人做什麼，我們不必跟著做。這恐怕除了投資也能對用人生，特別是能夠引起自身欲望的玩意兒，例如爬山對我看到山兒那麼美別人也去過，實在要克制那種莫名奇妙的慾望就算行程不難但昏頭的腦兒容易翹屁股的驕傲。

戒之。

繼續看下去。

ProjectEuler 272 -- Remark (Unsolved)

Define N(n) as the number of the integers x, for which 0 <= x < n and x^3 = 1 (mod n).

Lemma 1: Let f(x) = a_n x^n + ... + a_n x^2 + a_1 x + a_0.  If f(x) = 0 (mod p) and f'(x) = 0 (mod p) has no common zeros, then #{ V(f(x) = 0 (mod p^e)) } = #{ V(f(x) = 0 (mod p)) }.

Lemma 2: If gcd(m, n) = 1, then #{ V(f(x) = 0 (mod mn)) } = #{ V(f(x) = 0 (mod m))} * #{ V(f(x) = 0 (mod n)) }.

Lemma 3: #{ V(x^k = 0 (mod p)) } = gcd(k-1, p).

So, we need to count the number of all numbers of the form p_1 p_2 ... p_5 q_1 ... where p_i are of the form 3h+1 and q_j otherwise.

C(n) = N(n) - 1. 

ProjectEuler 60 -- Backtracking TLE

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

#define SIEVE_RANGE (1000035)
#define PRIME_COUNT (78500)
#define N (5)

bool sieve_visited[SIEVE_RANGE] = {};
long long primes[PRIME_COUNT] = {};

void Sieve()
{
    int curr_pos = 0;
    for (long long i = 2; i < SIEVE_RANGE; i++)
    {
        if (!sieve_visited[i])
        {
            primes[curr_pos] = i;
            curr_pos++;
            for (long long j = i + i; j < SIEVE_RANGE; j += i)
            {
                sieve_visited[j] = true;
            }
        }
    }
}

bool IsPrime(long long n) 
{
    for (long long i = 0; 
        (i < PRIME_COUNT) && (primes[i] * primes[i] <= n); i++) 
    {
        if (n == primes[i]) 
        {
            return true;
        }
        if (n % primes[i] == 0) 
        {
            return false;
        }
    }
    return true;
}

template <class T>
inline std::string to_string(const T& t)
{
    std::stringstream builder;
    builder << t;
    return builder.str();
}

template <class T>
inline T to_type(const std::string& s)
{
    std::stringstream builder(s);
    T t;
    builder >> t;
    return t;
}

long long solution_vector[N] = {};

bool IsValid(int dimension)
{
    long long n;
    for (int i = 0; i < dimension; i++)
    {
        for (int j = i+1; j < dimension; j++)
        {
            n = to_type<long long>(
                to_string<long long>(solution_vector[i]) +
                to_string<long long>(solution_vector[j]));
            if (!IsPrime(n))
            {
                return false;
            }

            n = to_type<long long>(
                to_string<long long>(solution_vector[j]) +
                to_string<long long>(solution_vector[i]));
            if (!IsPrime(n))
            {
                return false;
            }
        }
    }
    return true;
}

void DebugSolutionVector(int dimension)
{
    for (int i = 0; i < dimension; i++)
    {
        printf("%d ", solution_vector[i]);
    }
    printf("\n");
}

void Backtrack(int dimension)
{
    if (!IsValid(dimension))
    {
        return;
    }
    DebugSolutionVector(dimension);
    if (dimension == N)
    {
        DebugSolutionVector(dimension);
        return;
    }
    for (int i = 0; i < PRIME_COUNT; i++)
    {
        if (dimension == 0 || solution_vector[dimension-1] < primes[i])
        {
            solution_vector[dimension] = primes[i];
            Backtrack(dimension + 1);
        }
    }
}

void Solve()
{
    Backtrack(0);
}

int main(int argc, char* argv[])
{
    Sieve();
    Solve();
    return 0;
}

ProjectEuler 122 -- Binary method (WA)

#include <iostream>
#include <map>
#include <set>
#include <stdio.h>

int cost[201] = {};
std::map< int, std::set<int> > intermediate_exp;

void ComputeBinaryExponentiation()
{
    cost[1] = 0;
    intermediate_exp[1].insert(1);    
    for (int k = 2; k <= 200; k++)
    {
        long long min_cost_so_far = k;
        long long min_cost_pos = 0;
        for (int i = 1; i <= k/2; i++)
        {
            if (intermediate_exp[k-i].find(i) == 
                intermediate_exp[k-i].end()) 
            {
                continue;
            }
            if (cost[k-i] < min_cost_so_far)
            {
                min_cost_so_far = cost[k-i];
                min_cost_pos = i;
            }
        }
        cost[k] = min_cost_so_far + 1;

        std::set<int>::iterator it;
        for (it = intermediate_exp[k - min_cost_pos].begin();
            it != intermediate_exp[k - min_cost_pos].end(); it++)
        {
            intermediate_exp[k].insert(*it);
        }
        intermediate_exp[k].insert(k);
    }
}

int GetBinaryCount(long long k)
{
    return intermediate_exp[k].size() - 1;
}

int GetCountLowerBound()
{
    long long bound = 0;
    long long power = 0;
    long long base = 1;
    for (long long k = 1; k <= 200; k++)
    {
        if (k > base)
        {
            power++;
            base *= 2;
        }
        bound += power;
    }
    return bound;
}

void SolveWrongly()
{
    ComputeBinaryExponentiation();
    long long total_binary_count = 0;
    for (long long k = 1; k <= 200; k++)
    {
        total_binary_count += GetBinaryCount(k);
    }
    std::cout << total_binary_count << std::endl;
}

int main()
{
    SolveWrongly();
    return 0;
}

ProjectEuler 165 -- Blum Blum Shub

聽說不錯 pseudo-random number generator，缺點速度太慢，

原因可能是計算平方項很浪費時間。

這類問題很簡單，想個演算法，估計時間複雜度。

如果時間複雜度一天以內可以解決，不彷讓程式慢慢跑繼續想其他問題，

這就是所謂的多工作業系統。

Project Euler 269 -- Brute force for small n

#include <iostream>
#include <stdio.h>

int digit[20] = {};

bool IsRoot(long long polynomial, long long root)
{
    if (root == 0)
    {
        return polynomial % 10 == 0;
    }

    int curr_pos = 0;
    long long n = polynomial;
    do
    {
        digit[curr_pos] = n % 10;
        curr_pos++;
        n /= 10;
    }
    while (n);

    long long value = 0;
    for (int i = curr_pos-1; i >= 0; i--)
    {
        value *= root;
        value += digit[i];
    }
    return value == 0;
}

bool HasIntegerRoot(long long polynomial)
{
    for (int i = 0; i > -10; i--)
    {
        if (IsRoot(polynomial, i))
        {
            return true;
        }
    }
    return false;
}

// Z(1) 0
// Z(10) 1
// Z(100) 33
// Z(1000) 172
// Z(10000) 1754
// Z(100000) 14696
// Z(1000000) 152960
long long Z(long long k)
{
    long long count = 0;
    for (long long n = 1; n <= k; n++)
    {
        count += HasIntegerRoot(n);
    }
    return count;
}

int main(int argc, char* argv[])
{
    std::cout << Z(1) << std::endl;
    std::cout << Z(10) << std::endl;
    std::cout << Z(100) << std::endl;
    std::cout << Z(1000) << std::endl;
    std::cout << Z(10000) << std::endl;
    std::cout << Z(100000) << std::endl;
    std::cout << Z(1000000) << std::endl;
    return 0;
}