amoshyc

from operator import mul
from functools import reduce

data = \
'73167176531330624919225119674426574742355349194934' \
'96983520312774506326239578318016984801869478851843' \
'85861560789112949495459501737958331952853208805511' \
'12540698747158523863050715693290963295227443043557' \
'66896648950445244523161731856403098711121722383113' \

amoshyc

def solve():
    for a in range(500):
        for b in range(a, 500):
            c = 1000 - a - b

            e1 = min(a, b, c)
            e3 = max(a, b, c)
            e2 = a + b + c - e1 - e3
 if e1 + e2 <= e3:

amoshyc

#Minimum Scalar Product(GCJ 2008 Round 1A)

題目

To generate minimum scalar product , sort v1 in descending order while v2 in ascending order.

Code

#include <iostream>
#include 

amoshyc

Nim Game

文章節錄、翻譯、改寫自 這

玩法

1. 共有三堆石頭，分別有 3, 4, 5 顆。
2. 只有兩個玩家。兩個玩家輪流拿石頭，每次拿石頭可以從三堆中任意一堆拿走不限數量的石頭，但不可以一顆石頭都不拿。
3. 贏家為拿走最後一個石頭的人。

amoshyc

#Crazy Rows(GCJ 2009 Round 2A)

題目

Greedy, 針對第 pos 行, 向後尋找最近的、能放在第 pos 行的 row。

last[i] = the last index of '1' in row i

amoshyc

#Bribe the Prisoners(GCJ 2009 Round 1C)

題目

DP。

像無界背包問題一樣，引入 區間 性質。

position[] 記錄囚犯的位置。 (a, b) 為開區間。

amoshyc

Poj 1979

簡單 dfs

Code

#include <iostream>
#include <stack>
#include <cstring>
#include <utility>

amoshyc

#Millionaire(GCJ APAC Semifinal 2008)

題目

先離散化，然後從最後一回合的勝率往前推，直到推到第一回合。

考慮最後一回合，有以下三種情況：

1. 如果已經有錢 m, 1000000 <= m，則沒必要繼續賭下去，押注 0 元，可以以 1 的機率勝利。
2. 如果已經有錢 m, 500000 <= m < 1000000，則將所有的錢都押注，勝率為p。雖然不一定需要賭上所有的錢，但既然非贏到 1000000 才算勝利，而且必需在這個回合取勝，輸掉的話一毛錢也沒有，那乾脆全下注了。

amoshyc

Poj 2431

題目

分析

從測資中可以發現，當 stone 撞上 block 後，block 會立即消失，stone 停在 block 的前一格。

因題目有限制搜尋深度，並且為了每次遞迴不記憶整個 board，所以使用 dfs + 剪枝。在每個轉折點依 上下左右 四個方向遞迴搜尋下去（注意，只有當該方向的第一格是空的時才可遞迴該方向），每次遇到 goal，更新 result 值。

AC Code

amoshyc

ITSA 2084 題目配對

題目

分析

這題是 LIS，不容易想到… 不過測資很弱，用 O(n^2) 的解法即可，而且不用考慮極端的情形（i.e. 沒有任何配對的情況）。另外，題目的 Sample Ouput 的格式是錯的，不需要補零！

AC Code