【解題】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

【目錄】演算法與資料結構

演算法與資料結構解說一覽


概論

‧演算法簡介 - Introduction of Algorithm
‧資料結構簡介 - Introduction of Data Structure - coming soon...
‧複雜度分析 - Complexity Analysis
‧非確定性多項式理論 - Non-deterministic Polynomial Theory - coming soon...
‧遞迴函式 - Recursive Function


資料結構

‧堆疊 - Stack
‧佇列 - Queue
‧連結串列 - Linked List
‧樹 - Tree
‧雜湊表 - Hash Table - coming soon...


演算法

‧排序演算法 - Sorting Algorithm
　├ 氣泡排序法 - Bubble Sort
　├ 選擇排序法 - Selection Sort
　├ 插入排序法 - Insertion Sort
　├ 合併排序法 - Mergesort
　├ 快速排序法 - Quicksort
　└ 堆積排序法 - Heapsort - coming soon...

‧搜尋演算法 - Search Algorithm
　├ 循序搜尋法 - Linear Search
　├ 二分搜尋法 - Binary Search
　├ 內插搜尋法 - Interpolation Search
　└ 費氏搜尋法 - Fibonacci Search - coming soon...


經典題型

‧大數運算 - Large Integer
　├ Part 1. 介紹
　├ Part 2. 加 / 減法原理
　├ Part 3. 乘法原理
　└ Part 4. 除法原理

‧斐波那契數列 - Fibonacci Sequence
‧老鼠走迷宮 - Mouse in a Maze
‧河內塔 - Tower of Hanoi
‧八皇后問題 - Eight Queens Puzzle
‧騎士巡邏 - Knight's Tour - coming soon...
‧約瑟夫問題 - Josephus Problem - coming soon...
‧背包問題 - Knapsack Problem - coming soon...
‧漢米爾頓迴路 - Hamiltonian Circuit - coming soon...
‧裝箱問題 - Bin-Packing Problem - coming soon...

【演算】內插搜尋法 - Interpolation Search

　　內插搜尋法(interpolation search)改良自二分搜尋法(binary search)，也同樣都只能在資料已進行的情況下進行搜尋。但是，若在資料分布均勻時，其效率是會比二分搜尋法還高的。


　　既然內插搜尋法是改良自二分搜尋法，那麼實際的差異在哪呢？首先，內插搜尋法將資料的分布假設為一條直線：



　　若是一串資料於索引值 I_low 與 I_upper 的值分別為 K_low 與 K_upper。假設我們需要找的目標值為 K，且 K 的索引值 I，則我們理應可以推得：(K_upper - K_low) / (I_upper - I_low) = (K - K_low) / (I - I_low)。

　　若整理以上的算式，便可以得到公式：I = I_low + (I_upper - I_low)(K - K_low) / K_upper - K_low。


　　舉例來說，現在我們需要在下面這些資料中搜尋數值 44：

5 12 19 26 37 44 60 65 73 85

　　則 I = 1 + [(10 - 1)(44 - 5) / (85 - 5)] = 5：

5 12 19 26 37 44 60 65 73 85

　　由於 37 小於目標值，因此我們對後面的資料進行同樣的搜尋，I = 6 + [(10 - 6)(44 - 44) / (85 - 44)] = 6：

5 12 19 26 37 44 60 65 73 85

發現第 I 項資料值等於搜尋值，這樣就找到欲尋找的值了。


　　內插搜尋法的虛擬碼大致如下：

void interpolationSearch(Type data[1..n], Type search)
{
    Index low = 1;
    Index upper = n;

    while (low <= upper)
    {
        Index mid = low + (upper - low)
                      * (search - data[low])
                      / (data[upper] - data[low]);

        if (data[mid] = search)
        {
            print mid;
            return;
        }
        else if (data[mid] > search)
        {
            upper = mid - 1;
        }
        else if (data[mid] < search)
        {
            low = mid + 1;
        }
    }

    print "Not found";
}

　　平均而言，在有 n 筆資料的情況下，內插搜尋法只需要進行 log(log(n)) 次比對就可以找到資料！可見其效率之高。

　　但是，在資料並非分布均勻的最差情況下，內插搜尋法則是需要進行 n 次比對才能夠找到資料。此時的效率就比二分搜尋法低得多了。


　　以 C 語言的實作如下：

#include <stdio.h>
#include <stdlib.h>

int interpolationSearch(int[], int, int);

int main(void)
{
    int search, ans;
    int data[] = {5, 12, 19, 26, 37, 44, 60, 65, 73, 85};

    printf("請輸入欲搜尋的資料: ");
    scanf("%d", &search);

    // 呼叫函式進行搜尋
    ans = interpolationSearch(data, search, sizeof(data) / sizeof(int));

    if (ans < 0)
    {
        printf("找不到 %d\n", search);
    }
    else
    {
        printf("在第 %d 筆資料找到 %d\n", ans + 1, search);
    }

    system("pause");
}

int interpolationSearch(int data[], int search, int n)
{
    int low = 0, upper = n - 1;

    while (low <= upper)
    {
        int mid = low + (upper - low)
                      * (search - data[low])
                      / (data[upper] - data[low]);

        if (data[mid] == search)
        {
            return mid;
        }
        else if (data[mid] > search)
        {
            upper = mid - 1;
        }
        else if (data[mid] < search)
        {
            low = mid + 1;
        }
    }

    return -1;
}

【演算】樹 - Tree

　　樹(tree)是一種資料結構(data structure)，也就是我們一般所謂的「樹狀結構」或「樹狀圖」，為一個由根(root)向下延伸到葉子(leaf)的圖(graph)。




　　一棵樹由多個節點(node)，以及連結各節點的邊(edge)所組成。

　　如同上面所提及的，樹的最頂層有一個唯一的根節點(root node)，也就是上圖的節點 A，以及最末端的葉節點(leaf node)，如上圖的節點 K、J、F、L、O、P。除了這些節點外，其餘的節點被稱為內部節點(internal node)。


　　每個節點都有其階層(level)、高度(height)以及深度(depth)。節點的階層代表節點間的世代關係，以根節點為第 1 階層，其子節點為第 2 階層，再下層為第 3 階層......，以此類推；節點的高度為節點到向下最遠葉節點的距離；而深度則為節點到根節點的距離。以上圖為例，G 節點的階層為 3、高度為 2、深度為 2。


　　而與節點連接的上層節點被稱為父節點(parent node)，如上圖中的 G 即為 L 與 M 的父節點；與節點連接的下層結點被稱為子節點(child node)，如上圖的 N 即為 H 的子節點。

　　且對於每一節點而言，除了根節點不具有父節點之外，其他節點都恰有一個父節點，及零個以上的子節點(葉節點不具有子節點)。除此之外，具有相同父節點的節點，則被稱為兄弟節點(sibling node)，如上圖中的 D、E、F。


　　最後，節點的分支度(degree)代表子節點數量，如 A 節點的分支度為 2、B 節點的分支度為 3、C 節點的分支度為 2。


　　若就程式的觀點來看，樹是一個包含了其資料內容與 n (≧ 0)個指向子節點的指標的結構。一個樹的節點宣告方式大致如下：

struct Node
{
    Type data;
    Node *next1;
    Node *next2;
    Node *next3;
        .
        .
        .
    Node *nextN;
}

　　而「樹」本身，只不過是一個總括的概念，其本身又可以細分為如二元樹(binary tree)等常見的樹結構。這些讓我們之後再一一進行說明。

【作品】奧塞羅棋 - Othello (JS ver.)

　　沒錯，這個跟之前的某篇文章一樣，又是奧塞羅棋。不過這是用來練習 Javascript 的作品，算是 Web 程式設計課期末報告前的試驗作。


程式說明

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


程式連結




更新紀錄：

‧08/12/11 正式公開貼出。
‧08/12/12 修正悔棋不會變更下棋者的 bug。
‧08/12/15 修正 IE 不支援 PNG 透明背景的問題。

其他

　　IE 似乎不支援 PNG 背景底圖，所以有些圖背景會變成灰色的......。雖然已經找到方法解決，但是需要犧牲一點寫 CSS 的可維護性(?)，實在是讓我不太滿意。

　　所以，讓我趁機幫忙打個廣告，請支持 Firefox(被拖走)！