ghaouse's site: 6月 2011

2011年6月26日星期日

a130: 12015 - Google is Feeling Lucky

內容：
Google 為最有名的網路搜尋引擎之一，它也提供許多網路服務與產品。在它的搜尋首面上有一個有趣的按鈕「好手氣」吸引了我們的目光。這個功能讓使用者跳過搜尋結果頁面而直接進入排名最高的頁面。真是省時又好用！
問題是，當按下「好手氣」時到底會出現哪一個頁面？Google 有個不錯的方式來處理。為了簡化問題，假設 Google 為每個頁面設定了一個整數的相關度。相關度最高的頁面就會中選。如果平分，所有的相關度最高的頁面都有可能中選。
給你 10 個頁面及相關度，請選出所有可能成為「好手氣」的頁面。

輸入說明：
輸入有多筆測資。輸入的第一行有測資的筆數 T。
每筆測資中有 10 行以描述頁面及相關度。每行含有一個不含空白的字串代表頁面的網址及一個整數 Vi 代表該頁面的相關度。網址的長度介於 1 到 100 之間(含)。(1<= Vi <= 100)

輸出說明：
對於每筆測資，輸出可能中選的頁面網址。網址出現的順序與輸入相同。輸出格式請參考輸出範例。

範例輸入：
2
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 10
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
www.university.edu.cn 9
acm.university.edu.cn 10
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 11
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
acm.university.edu.cn 9
acm.university.edu.cn 10

範例輸出：
Case #1:
www.alibaba.com www.bad.com acm.university.edu.cn
Case #2:
www.alibaba.com

出處：
UVa ACM 12015

程式碼：

#include<stdio.h>
#include<string.h>

int main()
{
    int i,j,n,associate,max_associate,point;
    char site[10][102],stemp[102];
    
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        max_associate = -1;
        point = 0;
        for(j=0;j<10;j++)
        {
            scanf("%s %d",stemp,&associate);
            if(associate > max_associate)
            {
                max_associate = associate;
                point = 0;
                strcpy(site[point++],stemp);
            }
            else if(associate == max_associate)
                strcpy(site[point++],stemp);
        }
        
        printf("Case #%d:\n",i+1);
        for(j=0;j<point;j++)
                printf("%s\n",site[j]);
        
    }
    return 0;
}

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

2011年6月21日星期二

d290: 完全數

內容：
完全數是除本身外所有因數之和等于該數的數。
  早在公元2世紀末，人們已經找到了前4个完全數：6，28，496，8128。
  直到13世紀，時隔千年，才有人找到了第5個完全數，你知道它是多少嗎？

輸入說明：
  <無>

輸出說明：
輸出第5個完全數。

程式碼：

#include<stdio.h>
#include<math.h>
int main()
{
    long i,j,test,sum,sqr,temp;
    
    for(i=11;;i++)
    {
        test = (1<<(i-1))*((1<<i)-1);//wiki公式
        sum = 1;
        sqr = sqrt(test)+1;
        
        for(j=2;j<sqr;j++)
        {
            if(test%j == 0)
            {
                temp = test / j;
                sum = sum + j + temp;
                if(j == temp)
                    sum = sum - j;
            }
        }
        sum = sum - test;
        if(sum==0)
        {
            printf("%d\n",test);
            break;
        }
    }
    return 0;
}

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

d277: 矩形对角线

內容：
同學們要在廣場上布置一個矩形花壇，計畫用“串紅”擺成對角線。如果一條對角線用了N盆，還需要多少盆“串紅”呢？

輸入說明：
每行一個N(0<n<2^31).

輸出說明：
輸出還需多少盆。

範例輸入：
38

範例輸出：
38

提示：
初中几何。

解題概念：
            o o o o
      o o o o o o o
         o o o o o o o
         o o o o o o o
還要 2盆 4盆

程式碼：

#include <stdio.h>

int main()
{
    int i;
    
    while(scanf("%d",&i)==1)
    {
        if(i%2)
            printf("%d\n",i-1);
        else
            printf("%d\n",i);
    }
    return 0;
}

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

d235: Q10929: You can say 11

內容：
你的任務是，給你一個正整數 N，判定它是否是 11 的倍數。

輸入說明：
  每列資料有一個正整數N，N 最大可能到 1000 位數。
  若 N = 0 代表輸入結束

輸出說明：
  對每個輸入的數，輸出是否為 11 的倍數。
輸出格式請參考 Sample Output。

範例輸入：
112233
30800
2937
323455693
5038297
112234
0

範例輸出：
112233 is a multiple of 11.
30800 is a multiple of 11.
2937 is a multiple of 11.
323455693 is a multiple of 11.
5038297 is a multiple of 11.
112234 is not a multiple of 11.

出處：
  ACM 10929

程式碼：

#include <stdio.h>
#include <string.h>

int main() 
{
    int i,sum;
    char s[1001];
    
    while(scanf("%s",s)==1)
    {
        if(s[0]=='0' && s[1]=='\0')
            break;
        for(sum=i=0;s[i]!='\0';i++)
        {
            sum = sum + s[i++] - '0';
            if(s[i]=='\0')
                break;
            sum = sum - s[i] + '0';
        }
        
        if(sum%11 == 0)
            printf("%s is a multiple of 11.\n",s);
        else
            printf("%s is not a multiple of 11.\n",s);
    }    
    return 0;
}

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

d212: 東東爬階梯

內容：
東東有個嗜好，爬階梯不是一次走一階，就是一次走兩階。
換句話說，假設階梯有三階，那他有三種走法
  一：第一步走一階，第二步走二階。
  二：第一步走二階，第二步走一階。
  三：全程都走一階。
  這題要問你，假設階梯有n階，那東東有幾種走法?

輸入說明：
  第一行有一個正整數n，0<n<100，表示階梯有n階。

輸出說明：
  請輸出n個階梯有幾種走法。

範例輸入：
1
2
5

範例輸出：
1
2
8

程式碼：

#include <stdio.h>

int main() 
{
    int i,n;
    long long arr[101];
    
    arr[1] = 1;
    arr[2] = 2;
    
    for(i=3;i<100;i++)
        arr[i] = arr[i-1] + arr[i-2];
    
    while(scanf("%d",&n)==1)
        printf("%lld\n",arr[n]);
    
    return 0;
}

印出所有情況的程式碼：

#include<stdio.h>

int n,map[100];

void DFS(int sum, int step)
{
    if(sum == n)
    {
        for(int i=0; i<step; i++)
            printf("%d",map[i]);
        printf("\n");
        return;
    }
    else if(sum > n)
        return;
    
    map[step] = 1;
    DFS(sum+1, step+1);
    
    map[step] = 2;
    DFS(sum+2, step+1);
}

int main()
{
    int sum, step;
    
    while(scanf("%d",&n)==1)
    {
        sum = 0;
        step = 0;
        DFS(sum, step);
    }
        
    return 0;
}

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

d170: 飛蛾撲火(一)

內容：
話說，很久很久很久很久很久很久很久很久很久很久很久很久......以前，有個奇幻美妙的地方--幻之地，在那住著一隻，名叫楓火的蛾，不妙的是，某年發生了一場天災，使的她與她的父母分散，雖然已經在幻之地找了好一段時間，但他也沒因為這樣而放棄尋找父母的下落，因為她已不在面對失敗及挫折的陰影了，反而轉個身面對燦爛美好的未來，也因此他決定要離開幻之地，尋找雙親的下落。但未來也不知有多少她得面對的困難。
她在離開之前已經打聽了N個父母的下落了，但在這個亂世裡總會有壞人的存在，想騙楓火被火燙到，現在就請你幫忙判別一下了.....

輸入說明：
第一行有一個數N，1<=N<=20，表示接下來有N組測資。
每筆測資有六個正整數，皆小於一百，X1,Y1,X2,Y2,X3,Y3，分別表示起點(X1,Y1),目的地(X2,Y2),有火的樹(X3,Y3)。

輸出說明：
如果，會被火燙到(碰到)，輸出"該死的東西!竟敢想讓我死！"
反之，輸出"父親大人!母親大人!我快到了！"

範例輸入：
2
1 1 3 2 2 80
1 1 3 3 2 2

範例輸出：
父親大人!母親大人!我快到了！
該死的東西!竟敢想讓我死！

提示：
三點皆不在同一位子！直線運動。
有問題的話，儘管發問，不才的我會解除您的困擾。

程式碼：

#include <stdio.h>

int main() 
{
    int i,n,x1,x2,x3,y1,y2,y3;
    
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);
        
        if(((x1-x2)*(y1-y3))==((y1-y2)*(x1-x3)) &&
           ((x1<=x3 && x3<=x2 && y1<=y3 && y3<=y2) ||
            (x1>=x3 && x3>=x2 && y1>=y3 && y3>=y2) ||
            (x1<=x3 && x3<=x2 && y1>=y3 && y3>=y2) ||
            (x1>=x3 && x3>=x2 && y1<=y3 && y3<=y2) ))
            printf("該死的東西!竟敢想讓我死！\n");
        else
            printf("父親大人!母親大人!我快到了！\n");
    }
    return 0;
}

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

d167: 編碼轉譯

#include <stdio.h>

int main()
{
    int i;
    char s[100],ans[13];
    
    ans[0] = '|';
    ans[1] = ' ';
    ans[6] = '.';
    ans[10] = '|';
    ans[11] = '\n';
    ans[12] = '\0';
        
    while(gets(s)!=NULL)
    {
        printf("___________\n");
        for(i=0;s[i]!='\0';i++)
        {
            ans[2] = ' ';
            ans[3] = ' ';
            ans[4] = ' ';
            ans[5] = ' ';
            ans[7] = ' ';
            ans[8] = ' ';
            ans[9] = ' ';
            if(s[i] > 63)
            {
                ans[2] = 'o';
                s[i] = s[i] - 64;
            }
            if(s[i] > 31)
            {
                ans[3] = 'o';
                s[i] = s[i] - 32;
            }
            if(s[i] > 15)
            {
                ans[4] = 'o';
                s[i] = s[i] - 16;
            }
            if(s[i] > 7)
            {
                ans[5] = 'o';
                s[i] = s[i] - 8;
            }
            if(s[i] > 3)
            {
                ans[7] = 'o';
                s[i] = s[i] - 4;
            }
            if(s[i] > 1)
            {
                ans[8] = 'o';
                s[i] = s[i] - 2;
            }
            if(s[i] > 0)
            {
                ans[9] = 'o';
                s[i] = s[i] - 1;
            }
            printf("%s",ans);
        }
        printf("|    o. o |\n"); //enter      
        printf("___________\n");
    }
    return 0;
}

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

d166: 反轉表

內容：
由1開始之連續數字a1.a2.a3...an相對有一反轉表：b1.b2...bm。其bm代表意思為：數字m的位置前面有幾個比大個個數。
2 3 6 4 0 2 2 1 0
第1個2為1前面有2個比它大的數
第2個3為2前面有3個比它大的數
第3個6為3前面有6個比它大的數....以此類推
所以答案為
5 9 1 8 2 6 4 7 3
數字1前面有2個比它大的數 5 9
數字2前面有3個比它大的數 5 9 8

輸入說明：
輸入的每一行含有一個由m個數所組成的數列(反轉表) 1<=m<=50，
單獨一個 -1 在一行代表測試資料的結束

輸出說明：
請輸出從 1 到 m 所代表的數列

範例輸入：
2 3 6 4 0 2 2 1 0
-1

範例輸出：
5 9 1 8 2 6 4 7 3

提示：
背景知識：陣列練習
感謝snail修正題目

程式碼：

#include <stdio.h>
#include <string.h>

int main() 
{
    int i,len=0,n,point,arr[52],flag[52]={0};
    char nouse;
    
    while(scanf("%d%c",&n,&nouse)==2)
    {
        if(n == -1)
            break;
        len++;
        point = 0;
        for(point=i=0;i<n+point+1;i++)
            if(flag[i] == 1)
                point++;
        
        flag[n+point] = 1;
        arr[n+point] = len;
        
        if(nouse == '\n')
        {
            for(i=0;i<len;i++)
            {
                flag[i] = 0;
                printf("%d ",arr[i]);
            }
            printf("\n");
            len = 0;
        }
    }
    return 0;
}

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

d143: Q11172: Relational Operators

內容：
有些運算子（operator）是用來檢查兩個數值之間的關係，這種運算子稱為關係運算子（relational operators）。
給你兩個數值你的工作就是要找出它們之間的關係是(1)第一個大於第二個 (2)第二個小於第一個 (3)兩個一樣大。

輸入說明：
輸入的第一列有一個整數代表共有多少組測試資料。
接下來每列有兩個整數 a 和 b （ |a|,|b| < 1000000001）。

輸出說明：
對於每組測試資料，輸出，">", "<" 或 "="，代表該二數字的關係。

範例輸入：
3
10 20
20 10
10 10

範例輸出：
<
>
=

程式碼：

#include <stdio.h>

int main()
{
    int i,n,a,b;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        if(a>b)
            printf(">\n");
        else if(a==b)
            printf("=\n");
        else
            printf("<\n");
    }
    return 0;
}

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

d126: 一、牧場圍欄

內容：
Z先生是一个大牧場主，他飼養的奶牛每年都源源不斷地運往世界各地，我們的故事也由此產生了……

Z先生有一个矩形牧場，它的長和寬分别用 a 和 b （單位：米）表示，現在需要再牧場四周修建圍欄，請編一个程式計算牧場的周長以確定用料的多少。

輸入說明：
輸入檔有多組數據，每组數據占一行，分别為 a 和 b ，以一个空格隔開。a 和 b 均為不超過1000的正整數。

輸出說明：
輸出牧場的周長。

範例輸入：
4 3

範例輸出：
14

程式碼：

#include <stdio.h>

int main()
{
    int a,b;
    
    while(scanf("%d%d",&a,&b)==2)
        printf("%d\n",(a+b)<<1);
    return 0;
}

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

d122: Oh! My Zero!!

內容：
階層運算是很令人頭疼的，因此我們要想方設法地把它簡化。

輸入說明：
輸入檔可能有大量的數據。
每一个輸入檔輸入一个不算很大的數n（請用 longint）。

輸出說明：
輸出 n！的末尾零的个數。

範例輸入：
1
2
10

範例輸出：
0
0
2

提示：
1！=1 末尾有0个零；
2！=2 末尾有0个零；
10！=3628800 末尾有2个零。
千萬别暴力，千萬别死算！！！！！！

程式碼:

#include <stdio.h>
#include <string.h>

int main() 
{
    long n,total;
    
    while(scanf("%ld",&n)==1)
    {
        total = 0;
        while(n > 4)
            total = total + (n=n/5);
        printf("%ld\n",total);
    }
    return 0;
}

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

d114: 好累的小玫

內容：
小玫,小熊跟小羊正在玩闖關遊戲，這關要摧毀101大樓，前提就是要算出一個很長很長的數，也就是過關密碼。
其中小熊經由秘密管道得知，這個數就是 1! * 2! * 3! * ......... * 100!，小玫負責算出這個數，可是因為這個數實在太長了，因此小玫算的好累好累。

現在小羊想要請你幫忙，你可以輸出 "我不想幫忙" (不含引號) 接著得到WA ,或是正確輸出這關的過關密碼，得到AC。
(因為台北101很高很高，所以你輸出的解答也必須每輸出一個數字後換一行。)
PS.姓名純屬杜撰，如有雷同純屬巧合。
(測資已更正...不好意思XDD)

輸入說明：
本題沒有輸入。

輸出說明：
請輸出一個很像答案的東西。

範例輸入：
輸入範例要很有智慧的國王才能看到。

範例輸出：
只可意會不可言傳。

程式碼：

#include <stdio.h>
#include <string.h>

int main() 
{
    int i,j,k,point=1,carry;
    int a[99999]={0};
    
    a[0] = 1;
    for(i=2;i<101;i++)
    {
        for(k=101-i;k>0;k--)
        {
            carry = 0;
            for(j=0;j<point;j++)
            {
                a[j] = a[j]*i + carry;
                carry = a[j] / 10;
                a[j] = a[j] % 10;
            }
            a[j] = a[j] + carry;
            while(a[j] > 9)
            {
                carry = a[j] / 10;
                a[j] = a[j] % 10;
                j++;
                a[j] = carry;
            }
            point = j + (carry>0);
        }
    }
    for(i=point-1;i>-1;i--)
        printf("%d\n",a[i]);
    
    return 0;
}

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

2011年6月7日星期二

d086: 態度之重要的證明

內容：
今天我們如果將a=1,b=2,c=3....以此類推下去，
將單字裏的每個文字依照上面規則轉換成數字再相加起來的話。
知識(KNOWLEDGE)只有96分，
努力(HARDWORK)只有98分，
但態度(ATTITUDE)卻是100分。
風台高中的Norton看到了上面的文章後並不相信，
他想把它們真的加起來看看，
以找到一個字可以反駁這個「態度最重要」的理論
但卻討厭換來換去的過程，
請幫他寫個程式方便他去做運算。

輸入說明：
輸入英文單字，大小寫不限，當輸入0的時候就結束程式。
長度最長為200個字。
請參照Sample Input。

輸出說明：
輸出將英文單字依照題目的規則轉換成數字後相加的結果，如果中間參雜怪異的符號，請輸出Fail；但是英文字母的大小寫並不會影響結果，也就是說A和a所代表的值是相同的。請參照Sample Output。

範例輸入：
hardwork
KNOWLEDGE
aTtitUdE
C++
0

範例輸出：
98
96
100
Fail

程式碼：

#include <stdio.h>
#include <string.h> 

int main() 
{
    int i,len,sum,check,A,a,Z,z;
    char s[201];
    
    A = 'A' - 1;
    Z = 'Z' + 1;
    a = 'a' - 1;
    z = 'z' + 1;
    
    while(scanf("%s",s)==1)
    {
        if(s[0] == '0' && s[1]=='\0')
            break;
        len = strlen(s);
        sum = 0;
        check = 0;
        for(i=0;i<len;i++)
        {
            if(A<s[i] && s[i]<Z)
                sum = sum + s[i] - 'A' + 1;
            else if(a<s[i] && s[i]<z)
                sum = sum + s[i] - 'a' + 1;
            else
            {
                check = 1;
                break;
            }
        }
        if(check)
            printf("Fail\n");
        else
            printf("%d\n",sum);
    }
    return 0;
}

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

2011年6月6日星期一

d074: 電腦教室

內容：
蝸牛老師在一個優質高中擔任電腦老師，在學校裡有一個他專用的電腦教室。最近學校有一筆經費要幫這個電腦教室更新電腦。學校的原則是，每個上課的學生都要有自己的電腦，但是不希望購買多餘的電腦。給你蝸牛老師的任教班級數及每班人數，請你幫他算出要買幾部新電腦給學生使用。

輸入說明：
輸入只有兩行。第一行有一個正整數 n，代表蝸牛老師的任教班級數。第二行有 n 個由空白隔開的正整數，代表各班人數。

輸出說明：
輸出需購買的電腦數量。

範例輸入：
5
42 39 41 43 30

範例輸出：
43

提示：
背景知識：迴圈

程式碼：

#include<stdio.h>
int main() 
{
    int i,n,max,temp;
        
    while(scanf("%d",&n)==1)
    {
        max = 0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&temp);
            if(temp > max)
                max = temp;
        }
        printf("%d\n",max);
    }
    return 0;
}

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

d073: 分組報告

內容：
電腦課要同學分組做期末報告，分組的方式為依座號順序，每 3 個人一組。如：1, 2, 3 為第一組，4, 5, 6 為第二組….以此類推。輸入同學的座號，請判斷他在哪一組。

輸入說明：
輸入只有一行，含有一個正整數 n，代表同學的座號。

輸出說明：
輸出該同學的組別。

範例輸入：
7

範例輸出：
3

提示：
背景知識：算術運算子
你能只用算術運算子，而不用 if 解出這題嗎？

程式碼：

#include <stdio.h>

int main()
{
    int i;
    
    while(scanf("%d",&i)==1)
        printf("%d\n",(i-1)/3+1);
    return 0;
}

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

d072: 文文的求婚--續集 (Case 版)

內容：
承 a004，珊珊終於學成歸國了，文文的考驗時刻也到了。走出了迎客大廳，珊珊問：「What type of year was I born in?」文文很有自信的回答：「閏年！」可是珊珊卻說：「No, It was a LEAP YEAR!」看來文文要娶到珊珊，還得先把英文練一練。

輸入說明：
輸入的第一行有一個整數 n。接下來的 n 行每行有一個正整數 y，代表珊珊生日的西元年份。

輸出說明：
對於所輸入的每個 y，要各別輸出一行。每一行由「Case i: 」開頭，其中的 i 代表第 i 筆測試資料，若 y 是閏年，請於該行接著輸出「a leap year」，否則請輸出「a normal year」。請參閱範例輸出。

範例輸入：
4
1992
1993
1900
2000

範例輸出：
Case 1: a leap year
Case 2: a normal year
Case 3: a normal year
Case 4: a leap year

提示：
背景知識： for 迴圈
西元年被4整除且不被100整除，或被400整除者即為閏年。

程式碼：

#include<stdio.h>
int main() 
{
    int i,n,y;
        
    scanf(" %d",&n);
    n++;
    for(i=1;i<n;i++)
    {
        scanf("%d",&y);
        if(y%400==0 || (y%100!=0 && y%4==0))
            printf("Case %d: a leap year\n",i);
        else
            printf("Case %d: a normal year\n",i);
    }
    return 0;
}

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

d071: 文文的求婚--續集 (EOF 版)

內容：
承 a004，珊珊終於學成歸國了，文文的考驗時刻也到了。走出了迎客大廳，珊珊問：「What type of year was I born in?」文文很有自信的回答：「閏年！」可是珊珊卻說：「No, It was a LEAP YEAR!」看來文文要娶到珊珊，還得先把英文練一練。

輸入說明：
輸入有若干行。輸入的每一行有一個正整數 y，代表珊珊生日的西元年份。輸入以 EOF 作為結束。

輸出說明：
對於所輸入的每個 y，要各別輸出一行。若 y 是閏年，請於該行輸出「a leap year」，否則請輸出「a normal year」。

範例輸入：
1992
1993
1900
2000

範例輸出：
a leap year
a normal year
a normal year
a leap year

提示：
背景知識： while 迴圈
西元年被4整除且不被100整除，或被400整除者即為閏年。

程式碼：

#include<stdio.h>
int main() 
{
    int y;

    while(scanf("%d",&y)==1)
    {
        if(y%400==0 || (y%100!=0 && y%4==0))
            printf("a leap year\n");
        else
            printf("a normal year\n");
    }
    return 0;
}

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

訂閱：文章 (Atom)

2011年6月26日 星期日

2011年6月21日 星期二

2011年6月7日 星期二

2011年6月6日 星期一

2011年6月26日星期日

2011年6月21日星期二

2011年6月7日星期二

2011年6月6日星期一