Problem 341 Non-Stop Travel，不停的旅行

此題給你一個 n 值代表有幾個節點，再來有 n 行代表 1 ~ n 節點與其他節點單向通道的長度，所以每行一開頭，會有一個 m 值代表此節點共與 m 節點有單向通道。接下來會有 m 個 i、j 值，i 代表節點， j 代表長度。舉例：
2
1 2 4
0
此輸入例子代表 1 節點有一單向通道到 2 節點且長度為 4，而 2 節點沒有任何通道。
最後它會給你兩數字 a 和 b，請你印出 a 到 b 的最短路徑以及路徑經過的節點。

這題要用到「佛洛依德最短路徑演算法」，但須稍微修改一下，須先把陣列先建構出來，以上面例子需建構成：

索引\索引 | 1 | 2 |
---------------------
        1 | 0 | 4 |
---------------------
        2 | 0 | 0 |

再使用「佛洛依德最短路徑演算法」，並且用 p 陣列記錄路徑，關鍵程式碼如下：

for (k = 1; k <= n; k++)
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (i != j && region[i][k] != 0 && region[k][j] != 0)
            {
                int m = region[i][k] + region[k][j];
                if (region[i][j] == 0)
                    region[i][j] = m, p[i][j] = k;
                else if (m < region[i][j])
                    region[i][j] = m, p[i][j] = k; 

要求出路徑經過的節點，使用以下函式即可印出：

void path(int q, int r)
{
    if (p[q][r] != 0)
    {
        path(q, p[q][r]);
        printf(" %d", p[q][r]);
        path(p[q][r], r);
    }
}

最後只需在主程式這樣呼叫：

printf("Case %d: Path = %d", caseNum ++, i);
path(i, j);
printf(" %d; %d second delay\n", j, region[i][j]);

演算法雖辛苦學了兩個月，但用起來還真能解決很多題目。
By David.K

p341題目連結
回ACM題庫目錄
回首頁

Problem 11616 Roman Numerals，羅馬數字的轉換

此題如果給你一串羅馬數字，請你轉成十進位的數字；如果給你十進位數字，就要轉成羅馬數字。但數字不會超過 4000，而羅馬數字最大也不過是 4000。

而羅馬數字代表為下表：

Letter	I	V	X	L	C	D	M
Value	1	5	10	50	100	500	1000

這題要注意的就是有 4 與 9 數字，如果有這種情況，要先處理。
讀入字串後只需判斷第一字是否為英文字母，如果是，則是要將羅馬數字轉十進位數字；反之，則顛倒。
我判斷的方法是屬大到小慢慢累加的方法，如果第一個字母為 M，則判斷後三個字母是否都為 M，如果是就累加 4000，再把索引移到後三個字母索引的位置，如果只有後兩個為 M，就加 2000，以此類推。再判斷 C 字母時，要先判斷後一個字母是否為 M 或 D，如果是 M，就加 900；如果是 D，就加 400，如果都不是，再判斷後兩個是否都為 C，如果是，就加 300，如果只後一字母為 C，就加 200，如果啥都沒有，就加 100。
上面看不懂沒關係，提供 C 語言程式碼最實在( 只提供 M、D、C，剩下交給大家完成 )：

sum = 0;
for (i = 0; str[i]; i ++)
{
    if (str[i] == 'M')
    {
        if (str[i + 3] == 'M' && str[i + 2] == 'M' && str[i + 1] == 'M') 
        { sum += 4000; i += 3; continue; }
        if (str[i + 2] == 'M' && str[i + 1] == 'M') 
        { sum += 3000; i += 2; continue; }
        if (str[i + 1] == 'M') { sum += 2000; i += 1; continue; }
        sum += 1000; continue;
    }
    if (str[i] == 'D')
    {
        if (str[i + 3] == 'C' && str[i + 2] == 'C' && str[i + 1] == 'C')
        { sum += 800; i += 3; continue; }
        if (str[i + 2] == 'C' && str[i + 1] == 'C') 
        { sum += 700; i += 2; continue; }
        if (str[i + 1] == 'C') { sum += 600; i += 1; continue; }
        sum += 500; continue;
    }
    if (str[i] == 'C')
    {
        if (str[i + 1] == 'M') { sum += 900; i += 1; continue; }
        if (str[i + 1] == 'D') { sum += 400; i += 1; continue; }
        if (str[i + 2] == 'C' && str[i + 1] == 'C') 
        { sum += 300; i += 2; continue; }
        if (str[i + 1] == 'C') { sum += 200; i += 1; continue; }
        sum += 100; continue;
    }
    if (str[i] == 'L')
    {
        ...
    }
    if (str[i] == 'X')
    {
        ...
    }
    if (str[i] == 'V')
    {
        ...
    }
    if (str[i] == 'I')
    {
        ...
    }
}
printf("%d\n", sum);

而十進位數字其實也大同小異，C 語言程式碼如下：

sscanf(str, "%d", &n);
for (;n >= 1000 && n; n -= 1000)
    printf("M");
if (n / 100 == 9) printf("CM"), n -= 900;
for (;n >= 500 && n; n -= 500)
    printf("D"); 
if (n / 100 == 4) printf("CD"), n -= 400; 
for (;n >= 100 && n; n -= 100)
    printf("C");

...
...
...
printf("\n");

By David.K

p11616題目連結
回ACM題庫目錄
回首頁

C98010：作業十：銀行櫃台(解題)

首先將參數帶入函數中，可得到到達時間以及兩名服務員的服務時間的ArrayList使用上可照一般陣列使用只需在前加個強制轉換符號 (int)
得到參數後可以開始解題了，
step1：設一個迴圈讓其可以不斷的執行，直到總服務時間超過480分鐘

step2：首先第一塊判斷式是判斷由p1服務員服務的狀態
需要由p1服務員服務的情況有 當兩人工作時間相同時、p2還在工作的時候以及兩人同時都沒有在工作的情況下，需要由p1服務員服務

if (p1work == p2work || p1work < p2work|| cometotal - p1work >= 0)
{
    if (cometotal >= p1work)
    {
        finish = cometotal + (int)person1[p1];
        start = cometotal;
        wait = 0;
        p1++;
        p1work = finish;
    }
    else
    {
        finish = p1work + (int)person1[p1];
        start = p1work;
        wait = p1work - cometotal;
        p1++;
        p1work = finish;
    }
    Console.WriteLine(cometotal + " " + start + " " + "p1" + " " + finish + " " + wait);
}

step3：判斷由p2服務，其實這邊上面p1條件寫好，這邊只需要寫else就好

else
{
    if (cometotal >= p2work)
    {
        finish = cometotal + (int)person2[p2];
        start = cometotal;
        wait = 0;
        p2++;
        p2work = finish;
    }
    else
    {
        finish = p2work + (int)person2[p2];
        start = p2work;
        wait = p2work - cometotal;
        p2++;
        p2work = finish;
    }
    Console.WriteLine(cometotal + " " + start + " " + "p2" + " " + finish + " " + wait);
}

step4：最後統計一下題目要求的數據再列印出來即可完成本提

by Alent

題目連結
回C#語言教學目錄
回首頁