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#語言教學目錄
回首頁

Problem 11609 Teams

此題要求出某數字排序在最前面在的次數。

例如 2，可以分成
1 => 1, 12.
2 => 2, 21. 總共 4 次。
而 3，可以分成
1 => 1, 12, 13, 123.
2 => 2, 21, 23, 213.
3 => 3, 31, 32, 312. 總共 12 次。

可以找出公式為 p(n) = n * 2^n-1。每個數值都要 mod 1000000007 才為答案。
假設我們要找出 p(100) 的值，則為 (100 * 2⁹⁹⁹) % 1000000007 = (100 * ( ( 2¹⁰⁰ % 1000000007 )⁹ % 1000000007) * ( ( 2¹⁰ % 1000000007 )⁹ % 1000000007) * ( ( 2¹ % 1000000007 )⁹ % 1000000007) ) % 1000000007。
其實以上分解看不懂沒有關係，重點是我們要先找出 2¹ % 1000000007、2¹⁰ % 1000000007、.....、2^1000000000 % 1000000007 的數值，再將讀入 n 值利用以上分解的方式去找出答案。
所以宣告一個陣列 p[10] 裡面擺入 2¹ % 1000000007、2¹⁰ % 1000000007、.....、2^1000000000 % 1000000007 數值。 C 語言程式碼如下：

long long int p[10] = { 2, 1024, 976371285, 688423210, 905611805,
607723520, 235042059, 255718402, 494499948, 140625001};

而再主程式計算答案的程式碼如下：

int n, i, k, l;
long long int ans, tmp, m, copyM, j;
scanf("%d", &n);
for (i = 1; i <= n; i ++)
{
    ans = 1;
    scanf("%lld", &m);
    copyM = m;
    m --;
    for (j = 1000000000, k = 9; j > 0; j /= 10, k --)
    {
        tmp = m / j;
        m %= j;
        if (tmp)
        {
            while (tmp --)
                ans = ( ans * p[k]) % 1000000007;
        }
    }
    
    ans = (ans * copyM) % 1000000007;
    printf("Case #%d: %lld\n", i, ans);
}

By David.K

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

Problem 11661 Burger Time?，最短距離

此題要求出在高速公路上，餐廳與藥局最短距離為多少。

讀入整數 n，代表字串有多長，接著讀入一字串，字串有幾個字母構成，R 代表餐廳位置、D 代表藥局位置、Z 代表它餐廳和藥局都有、. 代表這位置啥都沒有。
注意：只要在判斷過程，Z 若有出現，則長度為 0。若 R 與 D 加起來的數量只有 1，長度也為 0。
我的方法就是紀錄 R 與 D 出現的索引位置，如果出現，再去減掉另外一個的索引位置，再判斷它是不是最小值，如是最小值，就紀錄；反之則否。C 語言程式碼如下：

#include <limits.h>
#define inf INT_MAX
...
主程式內...
char str[2000002], ch;
while (scanf("%d", &n) == 1 && n)
{
    getchar();
    int R = 0, D = 0, Z = 0, min = inf, tmp;  
    gets(str);
    for (i = 0; (ch = str[i]); i ++)
    {
        if (ch == '.') continue;
        if (ch == 'D')
        {
            D = i + 1;
            if (R) tmp = D - R;
            if (tmp < min && R) min = tmp;
            continue;
        }
        if (ch == 'R')
        {
           R = i + 1;
           if (D) tmp = R - D;
           if (tmp < min && D) min = tmp;
           continue;
        }
        if (ch == 'Z')
        {
            min = inf;
            break;
        }
    }
    if (min == inf) printf("0\n");
    else printf("%d\n", min);
}

By David.K

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

Problem 11650 Mirror Clock，鏡照時間

此題為簡單題，輸入一合理時間，將時間如同鏡照後輸出時間。

提供一下測試資料：

Input	Output
25 12:00 10:09 07:51 06:22 10:35 01:25 02:30 03:36 00:01 06:00 05:59 07:00 11:00 00:00 11:59 11:24 00:06 09:00 01:00 11:00 11:01 06:01 23:24 12:01 13:05	12:00 01:51 04:09 05:38 01:25 10:35 09:30 08:24 11:59 06:00 06:01 05:00 01:00 12:00 12:01 12:36 11:54 03:00 11:00 01:00 12:59 05:59 12:36 11:59 10:55

我解題的步驟如下：( H 為時針， M 為分針)
1. 時針若大於 12，就要將 H 減掉 12。

if (H >= 12) H -= 12;

2. 如果時針為 12、分針為 0 或時針為 0、分針為 0，皆印出"12:00"。

if (H == 12 && M == 0 || H == 0 && M == 0) puts("12:00");

3. 如果情況若不為步驟 2，則跳入 else 內。而在上面測試資料若不是特殊情況下，時針鏡照後，H 會變成 12 - H - 1；而分針鏡照後會變成 60 - M。如此做完，M 等於 60，要將它歸 0，再將 H 加 1。若 H 為 0，要將它變成 12。

else
{
    revH = (12 - H) - 1;
    revM = 60 - M;
    if (revM == 60) revM = 0, revH ++;
    if (revH == 0) revH = 12;    
    printf("%02d:%02d\n", revH, revM);
}

此題上傳完也是 0.000 秒。

By David.K

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

Problem 11621 Small Factors，最小因數

要先求出只有 2 和 3 因數的數值，將這些數值排序， C 語言程式碼如下：

int factor[1000] = {0}, index = 0, tmp, sIndex = 0;
void create()
{
    int k; 
    long long int i, j;
    for (i = 1; i < 2147483648LL; i *= 2)
        for (j = 1; j < 2147483648LL; j *= 3)
        {
            if (i * j  > 2147483648LL) break;
            factor[index ++] = i * j;
            for (k = index - 1; k >= 1; k --)
            {
                if (factor[k] < factor[k - 1])
                {
                    tmp = factor[k];
                    factor[k] = factor[k - 1];
                    factor[k - 1] = tmp;         
                }
                else break;
            }
        }
}

再來讀入一個 n 值，再 factor 陣列找出大於此數的最小數值，所以我們用「二分搜尋法」來實作，C 語言程式碼如下：

void location(int x, int low, int high)
{
    sIndex = 0;
    if (low > high) {sIndex = (low + high) / 2 + 1; return ;} 
    else 
    {
        int mid = 0;
        mid = (low + high) / 2;
        if (x == factor[mid]) {sIndex = mid; return ;} 
        else if (x < factor[mid]) location(x, low, mid - 1);
        else location(x, mid + 1, high);
    }
}

最後，只需在主程式呼叫：

location(n, 0, index - 1);
printf("%d\n", factor[sIndex]);

By David.K

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

Problem 10110 Light, more light，無聊至極的 mabu

有一名叫 mabu 在有 n 個燈泡的走廊上來回走 n 次，他在走第 i 次時，會關掉能被 i 除盡的燈泡編號。所以，請你求出在 n 趟後，最後一個燈泡是開的還是關著的。

其實只要判斷它開根號後是否為一整數，如果是，則燈泡在 mabu 來回走 n 次之後，會是開著的；若不為整數，則燈泡在 mabu 來回走 n 次之後，還會是關著的。

By David.K

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

Problem 11614 Etruscan Warriors Never Play Chess，Etruscan的戰士

Etruscan 部隊的戰士的行進是很有組織的，在第一排會站一個戰士，第二排會站兩個戰士，第三排會站三個戰士，以此類推。當最後一排不足一人或以上，則不為一排，也就是說，6 為 3、7 為 3、8 為 3、9 為 3、10 才為 4。

首先只需推導公式就可以很快的寫出來。S 為輸入的值。
首項為 0，公差為 1，末項為 0 + (n - 1) * 1，而

                    S < n * (n - 1) / 2
                2 * S < n * (n - 1)
                2 * S < n2 - n + 1/4 - 1/4
          2 * S + 1/4 < (n - 1/2)2
      (2 * S + 1/4)1/2 < (n - 1/2) 
(2 * S + 1/4)1/2 + 1/2 < n

則 n = (2 * S + 1/4)^1/2 + 1/2。但 n 求出後要減掉 1 才為解。參考程式碼如下：

printf("%lld\n", 
(long long int)floor(sqrt( 2.0 * (double)S + 0.25 ) + 0.5) - 1) ;

這題執行時間 0.000 秒。
By David.K

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

Problem 11734 Big Number of Teams will Solve This，檢查字串

輸入兩個字串，比對後，若字元不對，輸出"Wrong Answer"；若長度不同，輸出"Output Format Error"；以上都不是，就輸出"Yes"。

在比對時候，遇到空白字元時就不處理，繼續往下比對。若遇到字元不同時，直接跳出比對，印出"Wrong Answer"。比對完只要兩字串的索引不相等，印出"Output Format Error"，相等就印出"Yes"。C 語言程式碼如下：

char str1[25], str2[25];
gets(str1); gets(str2);
printf("Case %d: ", k);
int str1Len = strlen(str1), str2Len = strlen(str2);
int WA = 0;
for (i = 0, j = 0; i < str1Len || j < str2Len;)
{
    if (str1[i] == ' ') { i ++; continue; }
    if (str2[j] == ' ') { j ++; continue; }
    if (str2[j] == str1[i]) 
    { j ++; i ++; continue; }
    else { WA = 1; break;}
}
if (WA) printf("Wrong Answer\n");
else if (i != j) printf("Output Format Error\n");
else  printf("Yes\n");

By David.K

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

Problem 11716 Digital Fortress，陣列轉向列印

給你一串字串，請你先判斷他是否能成為一個 n * n 的陣列，若不行，印出"INVALID"；若可以，就由上到下，一列一列的印出。

例如：abcdefghijklmnop，看成 n * n 陣列後為：a b c d
e f g h
i j k l
m n o p
印出時則由上到下印出，為：aeimbfjncgkodhlp。
首先當讀入一字串時，須先判斷它的長度是否合乎 n * n 的陣列，所以先把它的長度開根號在平方回來，視它是否為同一數，若是則合乎。最後只須以它長度開根號後的長度為間隔，依序印出即可，C 語言程式碼如下：

gets(str);
int len = strlen(str);
int sqrtLen = (int)sqrt(len);
if (sqrtLen * sqrtLen != len)
    printf("INVALID\n");
else
{
    int i, j;
    for (i = 0; i < sqrtLen; i ++)
        for (j = i; j < len; j += sqrtLen)
            printf("%c", str[j]);
    printf("\n");        
}

By David.K

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

C98010：作業十：銀行櫃台

政府或服務業在臨櫃服務項目中，最常需要面對的問題是，在一個人來人往的基層政府機關或小店面要有多少人服務，而計算此一類問題的方法中，模擬是一項常用的方法。

在這次的作業中，我們要模擬一個小小的基層機構，有兩個服務人員，在面對每天來此辦公的八小時之內，探討顧客的滿意度。

顧客的滿意度往往是使用等待時間來評量。等待時間愈長，相對的顧客滿意度就愈差。在計算這種問題，我們有兩種重要參數，第一個是顧客的到達時間，第二個是服務的使用時間。

在這個問題中，我們使用平均分配來製造到達時間與服務時間，製造的函數完整C#程式碼下：

        static ArrayList getRandom(int seed, int minV, int maxV)
        {
            Random rand = new Random(seed);
            ArrayList randList = new ArrayList();
            for (int i = 0; i < 50; i++)
            {
                randList.Add(rand.Next(minV, maxV));
            }
            return randList;
        }

應用範例如後，到達時間間隔使用(100,5,20)，兩個服務人員的服務時間分別為(101,15,25)和(102,20,30)。
由於這裡的隨機函數使用C#提供的Random類別，在使用種子初始化後，該種子每次產生的隨機數序列均會相同，且每此僅產生50個變數(已足夠本作業使用)。產生的隨機數內容如下表：

到達率與處理率
編號	到達間隔	P1 處理時間	P2 處理時間
	參數(100,5,20)	參數(101,15,25)	參數(102,20,30)
1	19	19	20
2	7	19	27
3	15	18	20
4	18	16	23
5	10	23	22
6	19	23	26
7	15	16	26
8	14	16	26
9	10	19	25
10	7	20	28
11	19	22	24
12	13	18	21
13	10	15	27
14	12	15	25
15	19	21	23
16	12	16	27
17	18	18	27
18	19	21	22
19	10	19	24
20	5	19	28
21	6	17	23
22	10	21	28
23	18	15	22
24	19	18	26
25	12	20	26
26	17	19	21
27	18	22	26
28	14	17	28
29	7	19	27
30	14	19	22
31	6	19	28
32	16	15	23
33	12	24	23
34	12	20	25
35	13	24	22
36	6	16	21

在這個作業中，我們要調查的是在一天八小時中的顧客滿意度，因此在480分鐘以後到達的顧客將不再處理。

這個基層機構的排隊隊伍只有一行，顧客到達時，若P1與P2兩個服務人員皆空閒著，則顧客以P1為服務對象，若僅有單一服務人員空閒，則由該服務人員提供服務，若兩者皆忙碌，則會產生等待的情形，當然，最快完成服務的人員，將持續位下一位顧客服務，因此，根據上表的到達時間與服務時間，所產生的完整服務情形如下表。

處理統計
編號	到達時間	開始時間	受理者	完成時間	等待時間
1	19	19	P1	38	0
2	26	26	P2	46	0
3	41	41	P1	60	0
4	59	59	P2	86	0
5	69	69	P1	87	0
6	88	88	P1	104	0
7	103	103	P2	123	0
8	117	117	P1	140	0
9	127	127	P2	150	0
10	134	140	P1	163	6
11	153	153	P2	175	0
12	166	166	P1	182	0
13	176	176	P2	202	0
14	188	188	P1	204	0
15	207	207	P1	226	0
16	219	219	P2	245	0
17	237	237	P1	257	0
18	256	256	P2	282	0
19	266	266	P1	288	0
20	271	282	P2	307	11
21	277	288	P1	306	11
22	287	306	P1	321	19
23	305	307	P2	335	2
24	324	324	P1	339	0
25	336	336	P2	360	0
26	353	353	P1	374	0
27	371	371	P2	392	0
28	385	385	P1	401	0
29	392	392	P2	419	0
30	406	406	P1	424	0
31	412	419	P2	444	7
32	428	428	P1	449	0
33	440	444	P2	467	4
34	452	452	P1	471	0
35	465	467	P2	494	2
36	471	471	P1	490	0

輸出入格式
每一行為一個測試題目，每行有九個數字分別為 s1 min1 max1 s2 min2 max2 s3 min3 max3，以空白隔開，s1為到達時間的亂數種子，s2, s2則為兩個服務人員的亂數種子，min1與max1為到達時間的最小與最大範圍，而min2,max2和min3,max3為兩個服務人員時間的最小與最大範圍。每一個問題會有一行輸出，計有六個數字d1 d2 d3 d4 d5 d6，以空白隔開，內容如下：

• d1是等待時間為0的顧客累計人數


• d2是等待時間為大於0，小於等於10分鐘的顧客累計人數


• d3是等待時間為大於10，小於等於20分鐘的顧客累計人數


• d4是等待時間為大於20，小於等於30分鐘的顧客累計人數


• d5是等待時間為大於30，小於等於40分鐘的顧客累計人數


• d6是等待時間為大於40分鐘的顧客累計人數

範例
Input:
100 5 20 101 15 25 102 20 30
200 5 20 201 15 25 202 20 30
Output:
28 5 3 0 0 0
19 16 3 0 0 0

by Alent

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

Problem 624 CD，背包問題

此題為一題背包問題，參考蔡宗翰譯的「演算法--使用C++虛擬碼」書中(碁峯資訊，2004年)，第五章「回溯演算法」的方式，很快就可以完成。其實這本書老師之前也有推薦我看，但我沒有注意聽到他說這件事情，而我最近才買了這本書，講解的蠻清楚的。我推薦大家可以看看這本書。

首先宣告三個整數陣列 eTime 記錄每一個 CD 的時間，bestTime 記錄最大時間 CD 的 true/false，includeTime 為記錄臨時的最大時間。在宣告三個變數 totalTime 為限制時間， index 為 CD 片數， maxTime 為最大時間。接著寫一函式 knapsack(int i, int time) 利用回溯演算法解決 0-1背包問題。C 語言程式碼如下：

int totalTime, index, maxTime;
int eTime[21], bestTime[21], includeTime[21];

void knapsack(int i, int time)
{
    int j;
    if (i <= index ) 
    {
        if (time <= totalTime && time > maxTime)
        {
            maxTime = time;
            for (j = 0; j < index; j ++)
                bestTime[j] = includeTime[j];
        }
        includeTime[i] = 1;
        knapsack(i + 1, time + eTime[i]);
        includeTime[i] = 0;
        knapsack(i + 1, time );
    }
}

最後，在主程式要如此呼叫：

for (i = 0; i < 21; i ++)
    eTime[i] = 0, bestTime[i] = 0, includeTime[i] = 0;  
for (i = 0; i < index; i ++)
    scanf("%d", &eTime[i]);
maxTime = 0;
knapsack(0, 0);
for (i = 0; i < index; i ++)
    if (bestTime[i]) printf("%d ", eTime[i]);
printf("sum:%d\n", maxTime);

By David.K

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

Problem 11714 Blind Sorting

此題輸入 n 值後，依照一個公式：(n - 1) + (int) (log(n - 1) / log(2)) 即為解答。

By David.K

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

Problem 11703 sqrt log sin，簡單題

這題的公式很清清楚楚的寫在題目中了，如下圖：但有一點需注意就是題目上提到「no less than zero and no greater than one million.」，也就是說，數值不能超過 1000000，所超過 1000000 要取 mod 1000000 的數。關鍵 C 語言程式碼如下：

int X[1000001];

void create()
{
    X[0] = 1;
    int i;
    for (i = 1; i < 1000001; i ++)
    {
        X[i] = X[(int)floor(i - sqrt(i))] +
               X[(int)floor(log(i))] + 
               X[(int)floor(i * sin(i) * sin(i))];
        X[i] %= 1000000;       
    }
}

By David.K

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

Problem 11715 Car，行進的車子

此題問你一些對物理速度的概念，就是說一個以初速度 u (公尺/秒) 行進的車子，加速度為 a (公尺/秒²) ，再經過 t 秒之後，末速度為 v (公尺/秒) ，還有你在這時間走的距離為 s (公尺)。有四種狀況給你其中三個車子物理條件，請你求出另外兩個。

這題需要用到的只有兩個公式，為：
1. a = (v - u) / t
2. s = (u * u - v * v) / (2 * a)

》第一種狀況：已知條件 u、 v、 t。
　a = (v - u) / t
　s = (u * u - v * v) / (2 * a)
》第二種狀況：已知條件 u、 v、 a。
　t = (v - u) / a
　s = (v * v - u * u) / (2 * a)
》第三種狀況：已知條件 u、 a、 s。
　v = sqrt(u * u + 2 * a * s)
　t = (v - u) / a
》第四種狀況：已知條件 v、 a、 s。
　u = sqrt(v * v - 2 * a * s)
　t = (v - u) / a

最後照順序印出即可。

By David.K

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