Morris' Blog

2013年1月4日星期五

[ZJ] d416. 投影最大值

http://zerojudge.tw/ShowProblem?problemid=d416

內容：

給定長方體三邊長M、N、L
1<=M、N、L<=150
空間中有一平面a使得長方體投影在平面a上的面積有最大值
可以想像這個投影後的圖形應當是個六邊形(不一定正六邊形)會最大
所以請輸出這面積最大值

輸入說明：

每行輸入三正整數M、N、L
1<=M、N、L<=150

輸出說明：

請輸出此長方體在空間對所有平面的投影中面積的最大值
並且測資保證答案可以表示為a_/b的形式
其中a、b為正整數
特別的當a=1只要輸出_/b
b=1只要輸出a

    範例輸入    ：  

6 6 83 12 150 0 0

    範例輸出    ：

12_/41189

提示：

背景知識： math

出處：

david (管理：david942j)

題目都提示整數囉
那我就猜答案是 sqrt((mn)^2 + (ml)^2 + (ln)^2)
看單位跟數據，猜出來的

/**********************************************************************************/
/* Problem: d416 "投影最大值" from david                                    */
/* Language: C                                                                   */
/* Result: AC (96ms, 408KB) on ZeroJudge                                         */
/* Author: morris1028 at 2011-05-31 23:19:24                                     */
/**********************************************************************************/

#include<stdio.h>
#include<math.h>
int gcd(int x, int y) {
   int t;
   while(x%y) {
        t = x, x = y, y = t%y;
   }
   return y;
}
long long P[5200], pt = 0;
void P_Sieve() {
   char mark[100000] = {};
   int a, b;
   P[pt++] = 2;
   for(a = 3; a <= 50000; a += 2)
        if(mark[a] == 0) {
            P[pt++] = a;
            for(b = 3; a*b <= 50000; b += 2)
                mark[a*b] = 1;
        }
}
main() {
   P_Sieve();
   int M, N, L, t, tx, a;
   while(scanf("%d %d %d", &M, &N, &L) == 3) {
        if(M + N + L == 0) break;
        tx = gcd(M, gcd(N, L)), M/=tx, N/=tx, L/=tx;
        if(M > L) t = M, M = L, L = t;
        if(N > L) t = N, N = L, L = t;
        if(M > N) t = N, N = M, M = t;
        long long V = N*L*N*L + M*M*(N*N+L*L);
        long long t1 = 1, t2 = V;
        for(a = 0; a < pt && t2 >= P[a]*P[a]; a++)
            while(t2%(P[a]*P[a]) == 0)
                t1 *= P[a], t2 /= P[a]*P[a];
        t1 *= tx * tx;
        if(t1 == 1 && t2 != 1)
            printf("_/%lld\n", t2);
        else if(t2 != 1)
            printf("%lld_/%lld\n", t1, t2);
        else
            printf("%lld\n", t1);
   }
   return 0;
}

[ZJ] d825. 隔熱紙

http://zerojudge.tw/ShowProblem?problemid=d825

內容：

喵嗚建設公司最近由北到南蓋了一整排共n棟的大樓，且每棟大樓是緊緊貼在一起的

而喵嗚建設公司希望能夠帶給住戶舒適的住宅環境，因此決定在東面窗上貼滿隔熱紙

然而預算有限，不能有任何隔熱紙被浪費，又切割隔熱紙是一向充滿麻煩的工程

你可以幫喵嗚建設公司算出至少要幾張矩形的隔熱紙才能貼滿整排大樓的東側嗎？

輸入說明：

第一行有一個正整數 n(n<=100000)，代表有幾棟大樓

接下來n行每行有兩個正整數(<=1,000,000,000)，依序代表每棟大樓的寬度及高度

輸出說明：

輸出最少所需要的隔熱紙數

    範例輸入    ：  

51 21 32 22 51 4

    範例輸出    ：

提示：

不能浪費隔熱紙即隔熱紙間不能重疊，且隔熱紙需完全緊貼在大樓東面上

出處：

(管理：shik)

/**********************************************************************************/
/* Problem: d825 "隔熱紙" from                                                */
/* Language: C                                                                   */
/* Result: AC (20ms, 649KB) on ZeroJudge                                         */
/* Author: morris1028 at 2011-06-01 19:01:25                                     */
/**********************************************************************************/

#include<stdio.h>
main() {
   int n, x, t = 0, A = 0, stack[100000] = {};
   scanf("%d", &n);
   while(n--) {
       scanf("%d %d", &x, &x);
       while(x < stack[t]) A++, t--;
       if(x != stack[t]) stack[++t] = x;
   }
   printf("%d\n", A + t);
   return 0;
}

[ZJ] d826. 暗門

http://zerojudge.tw/ShowProblem?problemid=d826

內容：

在一個其大無比的空間裡，有 n 個房間相鄰著，譬如第5間的左側是第4間、右側是第6間

現在有 m 個人分別不同的房間。

但因為有些房間太空，有些則是太擠，所以我們要做一些調整，

使得每個房間裡面的人數一樣多。為了達到節能減炭的目的，

我們要讓所有人移動總距離最小。

移動距離的計算方式是：某人從第i移動到第j間，則距離為 |i-j|

輸入說明：

每組包含多比測試資料。
第一行給定兩個整數n,m (m為n的倍數)。接著第二行有m個整數，並用空格隔開

分別表示這m個人在哪一個房間裡面。
0 <= n <= m <= 100000。

輸出說明：

輸出一個整數，代表總移動距離。

    範例輸入    ：  

4 81 4 2 3 1 1 2 2

    範例輸出    ：

提示：

出處：

(管理：shik)

/**********************************************************************************/
/* Problem: d826 "暗門" from                                                   */
/* Language: C                                                                   */
/* Result: AC (49ms, 659KB) on ZeroJudge                                         */
/* Author: morris1028 at 2011-06-01 19:58:12                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
int Input() {
    char cha;
    unsigned int x = 0;
    while(cha = getchar())
        if(cha != ' ' && cha != '\n' || cha == EOF) break;
    if(cha == EOF) return -1;
    x = cha-48;
    while(cha = getchar()) {
        if(cha == ' ' || cha == '\n') break;
        x = x*10 + cha-48;
    }
    return x;
}
main() {
   int n = 5, m =250 , x;
   while(scanf("%d %d", &n, &m) == 2) {
       int a, room[100002] = {0}, U = 1, Ans = 0;
       for(a = 0; a < m; a++) {
           x = Input(), room[x]++;
       }
       m /= n;
       for(a = 1; a <= n; a++) {
           while(room[a] > m) {
               while(room[U] >= m)   U++;
               if(room[a] - m >= m - room[U])
                   Ans += (m-room[U])*abs(U-a), room[a]-= m-room[U], room[U] = m;
               else
                   Ans += (room[a]-m)*abs(U-a), room[U]+= room[a]-m, room[a] = m;
           }
       }
       printf("%d\n", Ans);
   }
   return 0;
}

[ZJ] d985. Gran Turismo 5

http://zerojudge.tw/ShowProblem?problemid=d985

內容：

最近，
學姊籌錢買了一片 Gran Turismo 5 回家做賽車夢，
又另外買了 G27 方向盤，
但在賽車場上的表現始終不如人意。

"車，不是這麼開的。"
說完爸爸接過了方向盤，
將記錄一次又一次的刷新。
給你每一圈的時間紀錄，
請算出 Best Lap 與平均時間。
我一定要成為車神！

輸入說明：

第一行有一個數字 N (0 < N ≤ 10)
代表接下來有 N 組測試資料
每組測試資料第一行有一個數字 M (0 < M ≤ 100)
接著有 M 行資料
每行兩個數字 A, B (0 ≤ A, B ≤ 60)
代表該圈所花費時間為 A 分 B 秒

輸出說明：

Track X:
Best Lap: X minute(s) X second(s).
Average: X minute(s) X second(s).
Average 為整數，小數部份無條件捨去
詳請參考範例測資

    範例輸入    ：  

341 542 021 581 5031 231 421 3753 002 563 042 503 01

    範例輸出    ：

Track 1:Best Lap: 1 minute(s) 50 second(s).Average: 1 minute(s) 56 second(s).Track 2:Best Lap: 1 minute(s) 23 second(s).Average: 1 minute(s) 34 second(s).Track 3:Best Lap: 2 minute(s) 50 second(s).Average: 2 minute(s) 58 second(s).

提示：

出處：

學姊 (管理：example)

/**********************************************************************************/
/* Problem: d985 "Gran Turismo 5" from 學姊                                    */
/* Language: C                                                                   */
/* Result: AC (6ms, 258KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-06-01 20:03:58                                     */
/**********************************************************************************/

#include<stdio.h>
main() {
   int N, M, a, C = 0;
   scanf("%d", &N);
   while(N--) {
       scanf("%d", &M);
       int x, y, bx = 10000, sum = 0;
       for(a = 0; a < M; a++) {
           scanf("%d %d", &x, &y), x = x*60 + y;
           if(x < bx) bx = x;
           sum += x;
       }
       sum /= M;
       printf("Track %d:\n", ++C);
       printf("Best Lap: %d minute(s) %d second(s).\n", bx/60, bx%60);
       printf("Average: %d minute(s) %d second(s).\n\n", sum/60, sum%60);
   }
   return 0;
}

[ZJ] d984. 棄保效應

http://zerojudge.tw/ShowProblem?problemid=d984

內容：

台灣的選舉法令禁止各陣營及媒體在投票日前的一個星期內公佈民調結果，其中最重要的一個因素是要避免「棄保效應」。所謂的「棄保效應」是指選民在得知自己所支持的候選人當選無望時，有可能會把票投給其他比較可能當選的人，以免浪費了自己的一票。假設某選舉有三位候選人來競選一個職位，在「棄保效應」發揮到極致的情形下，所有民調第三名的候選人的支持者都會把票投民調第二名的候選人，也就是他們都會「棄三保二」。給你 A, B, C 三個候選人的支持者人數，請判斷誰會當選？

輸入說明：

輸入有若干筆測試資料，每筆一行。每行有三個以空白隔開的整數 a, b, c 代表候選人 A, B, C 的支持者人數，0 ≤ a, b, c ≤ 2147483647。你可以假設在「棄保效應」之後，不會有相同票數的情形發生。

輸出說明：

請輸出將會當選的人是 A, B 或 C。

    範例輸入    ：  

3 4 51 3 5

    範例輸出    ：

BC

提示：

出處：

板橋高中教學題 (管理：snail)

刷題目要緊，先不寫漂亮了

/**********************************************************************************/
/* Problem: d984 "棄保效應" from 板橋高中教學題                       */
/* Language: C                                                                   */
/* Result: AC (2ms, 260KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-06-01 20:08:39                                     */
/**********************************************************************************/

#include<stdio.h>
struct data{
   long long x, y;
}D[3], t;
main() {
   while(scanf("%lld %lld %lld", &D[0].x, &D[1].x, &D[2].x) == 3) {
       D[0].y = 0, D[1].y = 1, D[2].y = 2;
       if(D[0].x > D[2].x) t = D[0], D[0] = D[2], D[2] = t;
       if(D[1].x > D[2].x) t = D[1], D[1] = D[2], D[2] = t;
       if(D[0].x > D[1].x) t = D[0], D[0] = D[1], D[1] = t;
       D[1].x += D[0].x;
       if(D[1].x > D[2].x)   printf("%c\n",D[1].y + 'A');
       else printf("%c\n",D[2].y + 'A');
   }
   return 0;
}

[ZJ] d881. 作業苦多

http://zerojudge.tw/ShowProblem?problemid=d881

內容：

學校作業何其多~~老二為此苦惱了許久，現在又有一份數學作業，他想節省時間，所以想找一個程式來解決此問題，你能幫嗎?詳細題目如下:

計算一級數

每項的差形成一個等差數列

每一題給定一等差數列的公差

此等數列有50項，第一項為1

輸出此數列和(1+到50項)

例如輸入為1(此為各項差形成的等差級數的公差)

答案要輸出1+2+4+7+11+......(到50項)

若輸入為2

答案要輸出1+2+5+10+17+26+37...... (到五十項)

輸入說明：

每次輸入一個測資d，代表公差(d<=100)

輸出說明：

輸出級數和(1+到50項)

    範例輸入    ：  

    範例輸出    ：

提示：

出處：

CSDC (管理：leepupu)

作法 : 數字很小，懶得導公式，直接硬爆

/**********************************************************************************/
/* Problem: d881 "作業苦多" from CSDC                                        */
/* Language: C                                                                   */
/* Result: AC (2ms, 256KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-06-01 20:12:36                                     */
/**********************************************************************************/

#include<stdio.h>
main() {
   int d;
   while(scanf("%d", &d) == 1) {
       int sum = 0, a, t = 1;
       for(a = 0; a < 50; a++)
           sum += t, t = 1+(2+a*d)*(a+1)/2;
       printf("%d\n", sum);
   }
   return 0;
}

[ZJ] d827. 買鉛筆

http://zerojudge.tw/ShowProblem?problemid=d827

內容：

鉛筆一支 5 元，一打 50 元。小明需要幫班上每位同學買一枝鉛筆，請問要多少錢？由於小明很注重環保，他絕不會為了省錢而多買任何不需要的東西。也就是說，小明買的鉛筆數量一定等於班上的人數。

輸入說明：

輸入只有一行，含有小明班上的人數 n，1 ≤ n ≤ 200。

輸出說明：

請輸出一個數字，代表這次採購的金額。

    範例輸入    ：  

    範例輸出    ：

提示：

背景知識：算術運算子

出處：

板橋高中教學題 (管理：snail)

/**********************************************************************************/
/* Problem: d827 "買鉛筆" from 板橋高中教學題                          */
/* Language: C                                                                   */
/* Result: AC (3ms, 263KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-06-01 20:13:45                                     */
/**********************************************************************************/

#include<stdio.h>
main() {
   int n;
   while(scanf("%d", &n) == 1)
       printf("%d\n", n/12*50 + n%12*5);
   return 0;
}

訂閱：文章 (Atom)

2013年1月4日 星期五

2013年1月4日星期五