【介紹】USACO - How To Start

　　延續前一篇的介紹，現在讓我們看看要如何申請一組 USACO Trainng 的帳號，並開始我們的解題之路！



　　首先，來到 USACO Trainng 的首頁，點選 "Register here for a username/password" 開始註冊。


　　接著就依照欄位，把資料填完就可以了。

　　選填欄位可以先全部不填，等收到認證信登入之後，網站會再要求你把需要的選填資料填完。


　　註冊成功之後，應該會看到如上圖的畫面。

　　接著到註冊用的電子郵件信箱收信之後，應該會收到一封主旨為 "USACO Training Registration Info with Password" 的信。內文如下：

Here is the information you need to participate in the USACO Training Program:

* Use http://ace.delos.com/usacogate as the gateway URL.

* Your permanent personalized username and password are:
　　Name: (你的名字)
　　UserName: (你的帳號)
　　Password: (你的密碼)

Please save this UserName and Password as they are permanently assigned to you.

Rob Kolstad, Head Coach

USA Computing Olympiad * kolstad@ace.delos.com * 877-753-3567

　　然後回到首頁，用剛剛信上寫著的帳號密碼登入。


　　如果剛剛沒有填國家的話，應該會顯示上圖的畫面。

　　找到自己的國家名稱，點下去就對了。


　　如果剛剛沒有填中學畢業年的話，應該會顯示上圖的畫面。

　　基本上，網頁上面有說：假如不想洩漏(我是懶得查XD)畢業年的話，直接填入 "9999" 即可。


　　接著就能進入上圖的畫面了。

　　不過記得，由於密碼是網站給你的，為了避免忘記密碼，請記得點選上方的 "Change Password" 修改密碼。


　　假如點選了 "Change Password"，照著填上去按下 "Submit" 送出就好了。


　　回到剛才的頁面。

　　一開始還不能開始寫題目，我們需要先點選 "TEXT Introduction"，看官方的介紹文章。


　　大致上是介紹 USACO 跟這個網站的內容。有興趣的人可以仔細看看。


　　回到剛才的頁面，發現 Section 1.1 的文字變成連結了。

　　接著請點選 "TEXT Submitting Solutions"，裡面會告訴你 USACO Trainng 上傳程式的方式與程式格式。

　　簡單來說，就是上傳的程式裡，前幾行必須用註解標記一些相關資訊。以 C++ 為例，你需要在開頭加入：

/*
ID: (你的帳號)
PROG: (題目名稱)
LANG: C++
*/

　　並記得在 main() 主函式中加入 "return 0;"。

　　基本上裡面寫得很仔細，一定要先仔細讀過。


　　接著來實際演練一遍。

　　在文章裡把它的範例程式複製下來(記得將 ID 修改成自己的)，上傳程式原始碼就可以了。


　　接著會顯示上傳後的結果。

　　假如結果有錯，網頁會列出你錯誤的那筆測試資料與正確答案，以方便除錯。

　　假如都沒有錯誤，網頁就會列出所有測試資料，與你的程式跑每筆測試資料所花的時間。


　　終於，我們可以來正式挑戰 USACO Trainng 的題目了。



　　題目內文裡面，會標示程式名稱、輸入檔名稱與輸出檔名稱，記得不要搞錯了。


　　當解出題目之後，題目連結後面會出現一個 [ANALYSIS] 的連結。


　　點進去之後，就是官方的題目分析，與參考的程式碼了。


　　當解完所有 Section 1.1 的題目後，才可以開始寫 Section 1.2，所以寫題目只能照著章節跑。

　　只要能解完 Section 1 到 Section 6 的題目，你就成功闖關 USACO Trainng 了！祝各位好運。 展開全文文章收合

【解題】錄製專輯 - Record

台北市96學年度高中資訊學科能力競賽 - 錄製專輯 (Record)


問題描述

　　Jolin是個愛唱歌的小孩，每次總喜歡邊唱邊用電腦把自己的歌聲錄下來，因此長久下來，在她的電腦裡，已儲存了為數不小的個人歌唱作品。由於耶誕節快要到了，為了準備一份特別的耶誕禮物給爸爸，Jolin準備從電腦中儲存的個人歌唱作品，挑選幾首歌製成一張個人專輯CD。由於每張CD的容量有限，而Jolin的個人歌唱作品早已遠遠超過一張CD可收錄的容量，因此Jolin希望你可以幫她想辦法，讓她所製作的專輯中，能有數目最多的歌曲(請注意：每一首歌只能被收錄一次)，同時必需剛好裝滿整張CD，不留下任何未使用的空間。


輸入檔格式(C:\record\input.txt)

　　輸入檔中的第一行為一個正整數N，代表Jolin的個人歌唱作品數目。第二行則有N個以空白相間隔的正整數Xi，分別代表第i首個人歌唱作品的大小(單位為MBytes)。第三行則有一個正整數S，代表CD的容量(單位為MBytes)。

　　為簡化計算過程起見，我們假設每一首歌唱作品的大小皆不相同，同時N≦100，Xi≦200，S≦10000。


輸出檔格式 (C:\record\output.txt)

　　請根據輸入檔的資料，在輸出檔中依序印出兩個正整數L與K。其中，L代表最多可以在CD中收錄的歌曲數目，K代表共有幾種方式可以收錄L首歌曲於CD中。注意，若歌曲曲目相同，但排列順序不同，仍視為不同的收錄方式。

　　若沒有任何方法可以錄滿整片CD，則L=K=0。


輸入檔範例1

5
10 50 30 70 60
80


輸出檔範例1

2 4


輸入檔範例2

5
10 50 30 70 60
20


輸出檔範例2

0 0


解題思考

　　對於這一題，我們首先需要得知，哪些歌加起來可以剛好裝滿整張CD。接著，由於歌曲順序不同仍視為不同的收錄法，因此假設n首歌剛好可以裝滿整張CD，就會有n!種收錄方式。

　　所以，現在的問題就在於：該如何得知，哪幾首歌剛好可以裝滿整張CD呢？根據建議，這裡提供一張圖做參考：



　　我的作法是，以迴圈搭配遞迴的方式選歌。假設現在取到第一首歌，容量是30。接著，再藉由遞迴的方式選第二首歌。由於第二首歌的大小為60，兩首歌的總容量超過CD大小，因此第二首歌並不能列入CD當中。以此類推，直到抓到最後一首歌，或是CD容量已滿為止。

　　或許你會注意到，除了CD剩餘容量外，參考圖片中還有一個"歌曲剩餘"的大小。這個數值代表的意義是：還沒被判斷是否可以放入CD的歌曲總容量(即圖片中未圈選及劃叉的歌曲)。

　　記錄這個數字做什麼呢？因為只要這個數字小於CD的剩餘容量，就算這些歌全都收錄在CD中，也不會到題目要求的"剛好裝滿"CD。因此，只要歌曲剩餘大小小於CD剩餘大小，就代表目前的選擇並不可行。

　　只要掌握這些概念，程式應該就能夠輕易的實現了。


　　結果答案完全是錯的。


　　這一題用這種方式來作，若是測試資料的 n 過大，將會導致執行結果超時。因此，勢必要使用別的方式來解才行。 (感謝網友 大丁丁 指正)

　　其實，這樣的題型就是所謂的背包問題(knapsack problem)。若是要解出這種題型，比較高效率的方法是利用動態規劃(dynamic programming)。

　　首先，先要得出一套「公式」，來求得只在前 i 首歌中做選擇，且恰好能裝滿容量為 v 的專輯的最大歌曲數。我們將之設為 f(i, v)。其中，若是我們選了第 i 首歌，則 f(i, v) 將可以看作 f(i - 1, v - x[i]) + 1。也就是「只在前 i - 1 首歌中做選擇，且恰好能裝滿容量為 v - x[i] (因為 x[i] 的空間被第 i 首歌佔據了)的專輯的最大歌曲數加一(第 i 首歌本身)」。

　　而若是我們不選第 i 首歌，則 f(i, v) 將可以看作 f(i - 1, v)。也就是「只在前 i - 1 首歌中做選擇，且恰好能裝滿容量為 v (因為不選第 i 首歌)的專輯的最大歌曲數」。如此，便可以得出 f(i, v) = maximum(f(i - 1, v - x[i]) + 1, f(i - 1, v))。

　　再加上定義出 f(0, 0) = 0 (因為 0 首歌裝滿容量為 0 的專輯能裝的最大歌曲數也為 0 首)，且 f(0, v) = -∞ (選 0 首歌裝滿容量大於 0 的專輯的情況必不可能出現)，再搭配迴圈就能得到正確的結果了。


　　那麼，要如何在不考慮順序情況下，得出的最大歌曲組合數量呢？

　　同樣的，若我們設 g(i, v) 為「只在前 i 首歌中做選擇，且恰好能裝滿容量為 v 的專輯的最大歌曲組合數」，再循著類似的原理累加，便可以得出結果。最後，以 g(i, v) 作為係數，乘以 f(i, v) 階層，就是包含各種不同順序的最大歌曲組合數量了。


　　還有要注意的一點是，計算出來的結果數字會相當大(畢竟牽扯到階層)，所以要用大數來存。這邊允許我偷個懶，直接用我以前寫的大數類別吧。

　　其實，這題我還很蠢的把題目的「最大裝滿專輯的歌曲組合數量」，誤解成「能裝滿專輯的歌曲組合數量」，大大的把題目給複雜化了。結果我好不容易寫出來之後，才發現跟大丁丁那弄來的 AC code 跑出的結果有那麼「一點點」不一樣。經過如此改正之後，這題我才算真正解出來。

參考解答(C++)

#include <iostream>
#include <fstream>

#include "include/Large.h"

using namespace std;

int main(void)
{
    ifstream in("C:/record/input.txt");
    ofstream out("C:/record/output.txt", ios_base::trunc);

    cout << "讀入資料 . . ." << endl;

    int n;
    in >> n;
    cout << n << endl;

    int *x = new int[n];
    for (int i = 0; i < n; i++)
    {
        in >> x[i];
        cout << x[i] << " ";
    }

    int s;
    in >> s;
    cout << endl << s << endl;

    in.close();

    int *dp = new int[s + 1];
    dp[0] = 0;
    memset(dp + 1, 0xFF, sizeof(int) * s);

    large *g = new large[s + 1];
    g[0] = 1;

    // dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + 1)
    for (int i = 0; i < n; i++)
    {
        for (int j = s; j >= x[i]; j--)
        {
            if (dp[j - x[i]] >= 0)
            {
                // 找到比當前最多歌曲組合更多歌曲的組合
                if (dp[j - x[i]] + 1 > dp[j])
                {
                    dp[j] = dp[j - x[i]] + 1;
                    g[j] = g[j - x[i]];
                }
                else if (dp[j - x[i]] + 1 == dp[j])
                {
                    // 累加最多歌曲組合的數量
                    g[j] += g[j - x[i]];
                }
            }
        }
    }

    // 計算順序不同的組合
    large number = g[s];
    for (int i = 2; i <= dp[s]; i++)
    {
        number *= i;
    }

    if (dp[s] < 0) { dp[s] = 0; }

    // 輸出得到的結果
    out << dp[s] << " " << number << endl;
    out.close();

    cout << endl << dp[s] << " " << number << endl;
    cout << "輸出資料在 ouput.txt" << endl;

    delete [] x;
    delete [] dp;
    delete [] g;

    system("pause");
}

展開全文文章收合

【介紹】USACO - What's This

　　USACO (United States of America Computing Olympiad，美國資訊奧林匹亞)是美國為其中學生所舉辦的程式設計競賽，能使用的程式語言包含 C、C++、Java 以及 Pascal。

　　USACO 舉辦的目的在於訓練美國中學生的邏輯思考與解決問題的能力，並從中選拔出每年 IOI (International Olympiad in Informatics，奧林匹亞資訊學科) 的參賽選手。而為了確實培訓將來要參加 IOI 的國手，USACO 特別建立了所謂的 USACO Training。




　　USACO Training 是一個線上的網路題庫，主要是用來訓練程式設計、活用演算法與資料結構的能力。題目的內容五花八門，涵蓋了各式各樣的問題。且 USACO Training 題目依照難易度，由簡到難共分為 6 個章節，必須以章節順序依次將題目完成。

　　除了循序漸進之外，USACO Training 還提供了許多程式設計相關的教學文章，像是貪婪演算法(Greedy Algorithm)、深度優先搜尋(Depth-First Search，DFS)、廣度優先搜尋(Breadth-First search，BFS)、動態規劃(Dynamic Programming，DP)等等。

　　看完教學文章之後，再利用題庫中的題目做練習，學習的效果相當顯著。若是程式有錯誤，網站還會列出程式的錯誤訊息、或是錯誤的那筆測試資料與正確答案的對照，以便於除錯。而在解出題目之後，USACO Training 還有詳細的題目分析講解與參考程式。

　　貼心的是，遇上某些太難的題目，USACO Training 還會提供一些小提示。只要順著提示的引導，往往就可以寫出那一題的答案了。


　　總而言之，我覺得 USACO Training 的題目其實還滿有意思的。在一邊寫的同時，感覺也學到了不少東西。所以新年新希望，就是能夠將 USACO Training 中的題目全部寫完囉(笑)。


　　以下是一些相關網站及參考資料，有興趣的人可以參閱：

．USA Computing Olympiad
．USACO Training Program Gateway
．USACO Contest Gateway
．United States of America Computing Olympiad - Wikipedia 展開全文文章收合

【解題】Is This Integration?

ACM Volume CII 10209 - Is This Integration?


The Problem

In the image below you can see a square ABCD, where AB = BC = CD = DA = a. Four arcs are drawn taking the four vertexes A, B, C, D as centers and a as the radius. The arc that is drawn taking A as center, starts at neighboring vertex B and ends at neighboring vertex D. All other arcs are drawn in a similar fashion. Regions of three different shapes are created in this fashion. You will have to determine the total area if these different shaped regions.




Input

The input file contains a floating-point number a (0 <= a <= 10000) in each line which indicates the length of one side of the square. Input is terminated by end of file.


Output

For each line of input, output in a single line the total area of the three types of region (filled with different patterns in the image above). These three numbers will of course be floating point numbers with three digits after the decimal point. First number will denote the area of the striped region, the second number will denote the total area of the dotted regions and the third number will denote the area of the rest of the regions.


Sample Input

0.1
0.2
0.3


Sample Output

0.003 0.005 0.002
0.013 0.020 0.007
0.028 0.046 0.016


解題思考

　　這題是數學題，求出公式這題就搞定了。雖然如此，這題我還是想了好久。

　　其實，只要能畫出那條關鍵的輔助線，這題並沒有那麼難：



　　看出來了嗎？


　　為了方便起見，我們將黃色區域面積設為 A，綠色區域面積設為 B，藍色區域面積設為 C。

　　由於圖中的 BF 線段(即圓半徑)長度為 a，BE 線段長度為 a / 2，我們便可得到：∠BFE = ∠CBF = 30°。於是，我們就可以求出，圖中八分之一的藍色區域面積為：a × (a / 2) - [(a / 2) × (√3 a / 2)] / 2 - a × a × π / 12。

　　經過整理，便可得到：C = a × a × [4 - √3 - (2π / 3)]。


　　接著，由於整個圖形面積為 A + B + C = a × a，又因為圖中的四分之一圓面積為 A + 3B / 4 + C / 2 = a × a × π / 4。經過聯立消去法之後得到：B + 2C = a × a × (4 - π)。

　　將 C 帶入上述算式中，便可得到：B = a × a × [-4 - 2√3 + (π / 3)]。


　　同樣的，把 B 與 C 代入 A + B + C = a × a 中，也可以得出：A = a × a × [1 + (π / 3) - √3]。


參考解答(C++)

#include <iostream>
#include <iomanip>
#include <cmath>

#define PI 2.0 * acos(0.0)
#define A(r) (r) * (r) * (1  + PI * 1.0 / 3.0 - sqrt(3))
#define B(r) (r) * (r) * (-4 + PI * 1.0 / 3.0 + sqrt(3) * 2)
#define C(r) (r) * (r) * (4  - PI * 2.0 / 3.0 - sqrt(3))

using namespace std;

int main(void)
{
    double a;

    // 設定顯示至小數點第三位
    cout << setiosflags(ios::fixed) << setprecision(3);

    while (cin >> a)
    {
        cout << A(a) << " " << B(a) << " " << C(a) << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

展開全文文章收合

【解題】Request for Proposal

ACM Volume CI 10141 - Request for Proposal


The Problem

When government, military, or commercial agencies wish to make a major purchase, they first issue a Request for Proposal (RFP) which lists a number of requirements that must be met by a successful proposal. Competing suppliers issue Proposals, indicating which of the requirements are met, and a price that will be charged should the proposal be accepted by the agency issuing the RFP.

Because the agencies are staffed by bureaucrats and are accountable to other agencies staffed by bureaucrats, it is necessary to remove all human judgement from the selection process. To this end, those evaluating the proposals are given feature sheets, which have one column for each requirement and and additional column for price, and one row for each Proposal. The evaluator reads each proposal and identifies each requirement that is met; for each such requirement a check mark is placed in the corresponding row (for the Proposal) and column (for the requirement). After all proposals have been evaluated, the number of check marks in each row is added. Any proposal that has the same number of check marks as the number of requirements is said to be compliant; otherwise the proposal is said to be partially compliant. Many agencies award the contract to the lowest compliant proposal; that is the compliant proposal with the lowest price. If there is no compliant proposal, many agencies evaluate partial compliance according to the following formula:

compliance = number_of_requirements_met / number_of_requirements

Your job is to select the Proposal with the highest compliance; if several proposals have the same compliance you are to select from these proposals the one with the lowest price. If several proposals have the same compliance and price you are to select the first one in the input.


Input

Your input will consist of the information for a number of RFPs and associated proposals. The information for each RFP will consist of:

• a line containing two integers: 0 < n <= 1000, the number of requirements, and p the number of proposals. The line 0 0 indicates there are no more RFPs.
• n lines naming the requirements. Each requirement is a string up to 80 characters long, terminated by the end of line. All strings are case sensitive.
• for each of the p proposals:
  • a line naming the proposal (up to 80 characters terminated by end of line)
  • a line containing a floating point number d and an integer 0 <= r <= n: d is the price; r is the number of met requirement lines to follow.
  • for each met requirement, the name of the requirement, each on a separate line. All requirements are from the RFP requirement list, and no requirements are duplicated.

Output

For each RFP, give the number of the RFP (see sample) followed by the name of the best proposal, optimizing the criteria given above. Leave a blank line between the output for each pair of RFPs.


Sample Input

6 4
engine
brakes
tires
ashtray
vinyl roof
trip computer
Chevrolet
20000.00 3
engine
tires
brakes
Cadillac
70000.00 4
ashtray
vinyl roof
trip computer
engine
Hyundai
10000.00 3
engine
tires
ashtray
Lada
6000.00 1
tires
1 1
coffee
Starbucks
1.50 1
coffee
0 0


Sample Output

RFP #1
Cadillac

RFP #2
Starbucks


解題思考

　　這題沒什麼技巧，照著題目的意思來即可：

　　首先，挑選廠商的第一條件是符合採購需求的數量。若是有兩家廠商符合需求的數量相同，則挑選兩家廠商中價錢較低的那個。若是兩家廠商的價錢又相同，則挑選較前面的廠商。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    string str;
    int rep = 1;
    while (1)
    {
        int n, p;
        cin >> n >> p;

        if (!n && !p) { break; }

        if (rep > 1) { cout << endl; }

        // 讀入需求項目
        cin.get();
        for (int i = 0; i < n; i++)
        {
            getline(cin, str);
        }

        string best_name;
        double best_price;
        int best_meet;
        for (int i = 0; i < p; i++)
        {
            // 讀入廠商名稱
            getline(cin, str);

            // 讀入報價及符合需求數
            double price;
            int meet;
            cin >> price >> meet;

            // 根據需求選擇廠商
            if (!i || meet > best_meet ||
                (meet == best_meet && price < best_price))
            {
                best_name = str;
                best_price = price;
                best_meet = meet;
            }

            // 讀入廠商符合需求的項目
            cin.get();
            for (int j = 0; j < meet; j++)
            {
                getline(cin, str);
            }
        }

        cout << "RFP #" << rep++ << endl;
        cout << best_name << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

展開全文文章收合

【解題】What is the Median?

ACM Volume CI 10107 - What is the Median?


The Problem

Median plays an important role in the world of statistics. By definition, it is a value which divides an array into two equal parts. In this problem you are to determine the current median of some long integers.

Suppose, we have five numbers {1,3,6,2,7}. In this case, 3 is the median as it has exactly two numbers on its each side. {1,2} and {6,7}.

If there are even number of values like {1,3,6,2,7,8}, only one value cannot split this array into equal two parts, so we consider the average of the middle values {3,6}. Thus, the median will be (3+6)/2 = 4.5. In this problem, you have to print only the integer part, not the fractional. As a result, according to this problem, the median will be 4!


Input

The input file consists of series of integers X ( 0 <= X < 2^31 ) and total number of integers N is less than 10000. The numbers may have leading or trailing spaces.


Output

For each input print the current value of the median.


Sample Input

1
3
4
60
70
50
2


Sample Output

1
2
3
3
4
27
4


解題思考

　　這一題要求我們輸出「到每筆輸入資料為止的中位數」。我的方法很直觀，也許還太笨了點。

　　其實就是每次輸入一筆資料之後，就把該筆資料插入到數列中適合的地方，使數列永遠是已排序狀態的。

　　接著，就直接透過索引值，輸出中位數就可以了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    int x, num[10000], n = 0;
    while (cin >> x)
    {
        // 將新輸入的數字插入到適合的位置
        int i = (n++) - 1;
        while (i >= 0 && num[i] > x)
        {
            num[i + 1] = num[i];
            i--;
        }

        num[i + 1] = x;


        // 找出中位數
        int mid = n / 2;
        if (n % 2)
        {
            cout << num[mid] << endl;
        }
        else
        {
            cout << (num[mid] + num[mid - 1]) / 2 << endl;
        }
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

展開全文文章收合

【作品】卡坦島 - The Settlers of Catan

　　Web Programming Final Project。


程式說明

　　還沒完成，等完成再來更新。


程式連結




更新紀錄：

‧09/01/04 完成第一階段，正式貼出。

碎碎念

　　怎麼最近都是沒完成的東西阿 Orz 展開全文文章收合