CPE 014 UVa12019-A - Dooms Day Algorithm

題目原文
題目內容

請你判斷西元2011年的某月某日是星期幾。

輸入說明:

輸入的第一列有一個表示測試資料組數的整數。接著每一列分別表示一組測試資料，其格式為M D。M表示月份(1~12)，D表示日期(1~31)，所有日期皆是合法的。

輸出說明:

請你判斷2011年的該日期是星期幾。星期一到星期日分別為 Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday。

Sample Input

8
1 6
2 28
4 5
5 26
8 1
11 1
12 25
12 31

Sample Output

Thursday
Monday
Tuesday
Thursday
Monday
Tuesday
Sunday
Saturday

解法
可以藉由原文題目裡面提到的幾個日期來為基準，來以此推算接下來的日期並找其規律。


(以上資料來源:大學程式能力檢定Collegiate Programming Examination(CPE)、中文翻譯:Ruby兔的ACM園地)

程式碼解答

#include <stdio.h>

int main()
{
 const int daymonth[]={0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};///每個月有幾天
 const char*dayweek[]={"Friday", "Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday"};///一個星期有禮拜幾
 
 int _case, month, day, i, totalday;///變數先設好舊版C語言要先設好, 新版後可以在中間運算是可以中再設
 scanf("%d", &_case);//讀入幾筆資料
 while(_case--)///運算過程
 {
  scanf("%d%d", &month, &day);
  totalday=0;///先歸零以確保
  for(i=0; i< month; i++)
  {
   totalday+=daymonth[i];
  }
  totalday+=day;
  printf("%s\n", dayweek[totalday%7]);
 }
}

程式碼打包:解法一

CPE 032 UVa10190-Divide, But Not Quite Conquer!

題目原文
題目內容

略

輸入說明:

略

輸出說明:

略

Sample Input

125 5
30 3
80 2
81 3

Sample Output

125 25 5 1
Boring!
Boring!
81 27 9 3 1

解法

簡單來說，會給你兩個值；可以直接看成一個是被除數，一個是除數。
然後如果這兩個數沒有辦法被整除到剩下1就印Boring，比較要注意的是兩數之間的大小，正常來說第一個數字要比第二個數字大，這題組主要用迴圈和矩陣來運算完成。

(以上資料來源:大學程式能力檢定Collegiate Programming Examination(CPE))

程式碼解答

#include <stdio.h>
#include <stdlib.h>
#define MAX 100000
int main()
{
 int n, m;
 int a[MAX];
 int i, j;
 while(scanf("%d %d", &n, &m)==2)///要輸入兩個值才執行
 {
  i=0;
  a[i++] = n;
  int divisible = 1;///判斷條件之一divisible = 1可以整除 =0不可整除
  int key = (m==1 || m>n)? 0: 1;///判斷條件之二key m==1 或者 m>n 則給予0 
  while(a[i-1] != 1&&key == 1 )///如果已經除到1 了 則跳出迴圈
  {
   if(a[i-1]%m!=0)///如果不整除 則讓判斷條件一等於零並且跳出迴圈
   {
    divisible = 0;
    break;
   }
   a[i]= a[i-1]/m; ///運算過程
   i = i + 1;
  }
  if(divisible && key ==1)///列印時先驗證所有條件是否成立
  {
   for(j=0; j<i; j++)
   {
    printf ("%d", a[j]);
    printf((j+1 == i)? "\n" : " ");
   }
  }
  else 
  {
   printf("Boring!\n");
  }
 }
}

程式碼打包:解法一

CPE 023 UVa11063-B2-Sequence

題目原文
題目內容

所謂「B2數列」係指一正整數數列 1<= b1 < b2 < b3 ...，其中所有的 bi + bj （i <= j）皆不相等。
您的任務是判別某一數列是否為「B2數列」。

輸入說明:

每筆測試資料有兩行，第一行代表該數列有 N 個數值（2 ≤ N ≤ 100），第二行則為該數列的N個數值。每個數值 bi 皆為整數，且 bi ≤ 10000。

輸出說明:

每筆測試資料以一行輸出，且每筆輸出資料後均需輸出一空白行。格式請參考輸出範例。

Sample Input

4
1 2 4 8
4
3 7 10 14
5
13 14 15 16 17

Sample Output

Case #1: It is a B2-Sequence.

Case #2: It is not a B2-Sequence.

Case #3: It is not a B2-Sequence.

解法
這題要使用一維矩陣來讀入資料，後面比較麻煩的是要如何判斷它的大小值有無超出範圍和是否有想加出來的值有重複到，然後本篇所使用判斷重複的方法有點類似於使用開櫃子的方法。

(以上資料來源:大學程式能力檢定Collegiate Programming Examination(CPE))

程式碼解答

#include <stdio.h>

#include <string.h>

int main()
{
 int frequence;
 int count=1;
 while(scanf("%d", &frequence)==1)//讀入他的下一筆數列有幾個
 {
  int a[frequence];
  int b2[20002];
  for(int i=0; i<frequence; i++)//讀入數列
  {
   scanf("%d", &a[i]);
  }
  

    memset(b2, 0, sizeof(b2));//把櫃子歸零

  
  int bad=0;//判斷用的變數
  for(int i=0; i<frequence; i++)
  {
   for(int j=i; j<frequence; j++)
   {
   
    int result=d[i]+d[j];

    
 if(d[i]>d[j] || b2[result]!=0)//要比前一個數字大且兩數相加不可重複
 {
    bad=1;
    break;
     
     
 }
   
    
 else  b2[result]++; //如果打開過就把變數值設為1

     
   
   }
  }
  if(bad==0) printf("Case #%d: It is a B2-Sequence.\n\n", count);//如果判斷是零就印第一個
  else printf("Case #%d: It is not a B2-Sequence.\n\n", count);
  count++;//印題號用的
 }
}

程式碼打包:解法一

CPE 033 UVa10235-Simply Emirp

題目原文
題目內容

一個比 1 大的整數如果只有 1 和他本身自己共 2 個因數，我們稱這個數為質數（prime number）。多年來質數一直被數學家們研究著。質數也常被應用在密碼學和編碼理論中。

那麼你曾經把質數倒轉過來嗎？對大部分的質數來說，你將會得到一個組合數（例如：43 變成 34）現在，我們要定義 Emirp（就是把 Prime 反過來拼）：如果你把一個質數反過來之後，他仍然是一個質數，並且和原來那個質數不同，那我們就稱這個數為 emirp number。例如：17 是一個emirp，因為 17 和 71 都是質數。在這個問題中，你必須要決定某一個整數 N 是非質數，質數，或 emirp。你可以假設 1<N<1000000。

輸入說明:

輸入的每一行測試資料有 1 個整數 N

輸出說明:

對每一輸入 N，輸出以下的訊息：

1. "N is not prime."，如果 N 不是一個質數

2. "N is prime."，如果 N 是一個質數，但是不是一個 Emirp

3. "N is emirp."，如果 N 是一個 emirp

Sample Input

17
18
19
179
199
131

Sample Output

17 is emirp.
18 is not prime.
19 is prime.
179 is emirp.
199 is emirp.
131 is prime.

解法
首先2這個數，是一個很特別的數，他是唯一是偶數的質數，所以要獨立出來特地為它設一個條件判斷，接下來想辦法把數字反轉，最後在一直取二的餘數看他是不是質數就好，反質數也只是多了一個把數字前後顛倒的步驟而已。


(以上資料來源:大學程式能力檢定Collegiate Programming Examination(CPE)，Lucky 貓)

程式碼解答

#include <stdio.h>
int isprime(int n)//專門判斷是否為質數用的
{
 int k;
 for(k=2; k<n; k++)
  if(n%k==0) break;
  
 return k==n;
}
int main()
{
 int n, n1, n2;
 while(scanf("%d", &n)!=EOF)
 {
  if(isprime(n))//第一先判斷這個值本身是不是質數
  {
   n1=n;
   n2=0;
   while(n1)//交換數字的位置
   {
    n2=n2*10+n1%10;
    n1/=10;
   }
  if(n2!=n && isprime(n2))//如果交換完還是質數且跟交換前的數字不一樣的話
   printf("%d is emirp.\n", n);
  else //只符合一開始是質數
   printf("%d is prime.\n", n);
  }
  else printf("%d is not prime.\n", n);
 }
}

程式碼打包:解法一、解法二

CPE 005 UVa10929-You can say 11

題目原文
題目內容

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

輸入說明:

每列資料有一個正整數N，N 最大可能到 1000 位數。

若 N = 0 代表輸入結束

輸出說明:

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

Sample Input

112233
30800
2937
323455693
5038297
112234
0

Sample Output

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.

解法
使用之前數學所教的奇數位的和跟偶數位的和相減看是不是11的倍數，此題建議用讀字串的方式讀入資料。
(以上資料來源:大學程式能力檢定Collegiate Programming Examination(CPE))

程式碼解答

#include <stdio.h>
#include <string.h>
int main()
{
 char number[1001];
 while (scanf("%s", number)!=EOF)
 {
  
  int i;
  long int length=strlen(number);///讀出字串長度
  if(length==1 && number[0]=='0')///判斷是否只有一個位數並且輸入的該數不能為零 
   break;
  int odd=0, even=0;
  for(i=0; i<length; i++)///分別做奇偶數位的相加
  {
   if(i%2==0)
    odd=odd+(number[i]-'0');
   else
    even=even+(number[i]-'0');
  }
  if((odd-even)%11==0)//判斷
   printf("%s is a multiple of 11.\n", number);
  else
   printf("%s is not a multiple of 11.\n", number); 
  
 }
 
 
}

程式碼打包:解法一

CPE 006 UVa10101-Bangla Numbers

題目原文
題目內容

Bangla數通常會用'kuti' (10000000), 'lakh' (100000), 'hajar' (1000), 'shata' (100)這幾個字來把一個數值轉換成文字。你的任務就是寫一個程式來作這件事。

輸入說明:

輸入檔包含多筆測試資料，每筆測試資料都是一個不超過999999999999999的數字。

輸出說明:

對每一筆測試資料輸出一列轉換後的結果，每一列的開頭必須是一個佔四個字元的case number。

Sample Input

23764
45897458973958

Sample Output

1. 23 hajar 7 shata 64
2. 45 lakh 89 hajar 7 shata 45 kuti 89 lakh 73 hajar 9 shata 58

解法
簡單來說這的意思是要我們把一組數字來用程式解成用口語表達的樣子，舉例來說1100我們會說一千一百，而不會說一一零零。
所以這題對輸入做字串分解，共可以切成五組：kuti、lakh、hajar、shata、常數。切完之後就輸出該組的值以及其代表的文字單位，常數只須輸出值即可。

若該組的值為0，則應該跳過輸出該組，例如輸入1012不應該輸出 1 hajar 0 shata 12。 

而對kuti這組來說，如果這裡面的數值長度大於2個字元，則應該繼續對裡面的數遞迴去做字串分解，參考第二個範例輸入。


(以上資料來源:大學程式能力檢定Collegiate Programming Examination(CPE))

程式碼解答

#include <stdio.h>///標頭檔

void numfunction(long long n)///運算式
{
 if(n/10000000)
 {
  numfunction(n/10000000);///由於kuit可能不只小於10000000，所以要一直呼叫在遞回
  printf(" kuti");
  
  n%=10000000;
  if(n>0) printf(" ");///一切看到這個印空白的都是為了格式= =
    ///格是真的很機車zzz
 }
 if(n/100000)
 {
  printf("%lld lakh", n/100000);
  n%=100000;
  if(n>0) printf(" ");
 }
 if(n/1000)
 {
  printf("%lld hajar", n/1000);
  n%=1000;
  if(n>0) printf(" ");
 }
 if(n/100)
 {
  printf("%lld shata", n/100);
  n%=100;
  if(n>0) printf(" ");
 }
 if(n!=0) printf("%lld", n);

}

int main()
{
 long long n;///由於數字會很大要用long long讀
 int count=1;///代表執行了起始值也代表前面表題的起始值
 while(scanf("%lld", &n)!=EOF)///讀值讀到沒有為止才停止
 {
  printf("%4d. ", count);///印題號
  if(n==0)printf("%d", n);
  else numfunction(n);
  printf("\n");//最後每題的換行
  count++;///執行完一次後便讓標題+1
 }
}

程式碼打包:解法一

CPE 015 UVa10038-Jolly Jumpers

題目原文
題目內容

有n個整數的序列我們稱為jolly jumper，如果相鄰的2個數其差的絕對值恰好為1到n-1。例如：

1 4 2 3

就是jolly jumper（n=4）。因為相鄰2數的差的絕對值為3,2,1，就是1到n-1。但是

1 4 2 -1 6 

不是jolly jumper（n=5）。因為相鄰2數的差的絕對值為3,2,3,7，並非1到n-1。

你的任務是寫一個程式來判斷一個整數序列是否為jolly jumper。

輸入說明:

每組測試資料一列，第一個正整數為 n（n < 3000），代表此整數序列的長度。接下來有n個整數，代表此整數序列。請參考Sample Input。

輸出說明:

對每一組測試資料，輸出此整數序列是否為jolly jumper。請參考Sample Output。

Sample Input

4 1 4 2 3
5 1 4 2 -1 6

Sample Output

Jolly
Not jolly

解法

一. 1 2 4 為Jolly， 因為其差值為1 2。 (差值1~(n-1[=2])皆有)

二. 1 3 4 為Jolly， 因為其差值為2 1。 (差值1~(n-1[=2])皆有)

三. 1 2 3 為Not Jolly，因為其差值為1 1。(差值1~(n-1[=2])並非都有，僅只有1而已)

簡單來說就是兩兩相差的值，是要介於1~(n-1)之間且相差的值不可於重複又或者是說倆倆相差的值剛好要等於1、2，3~(n-1)這個數列裡面每一個值都要剛好有。

(以上資料來源:大學程式能力檢定Collegiate Programming Examination(CPE)、中文翻譯來源:Lucky 貓)

程式碼解答

#include <stdio.h>///基本的函式庫
#include <stdlib.h>///因為會使用到絕對值abs所以需要導入這函式庫
#define MAX 3001
int main()
{
 int n;///存放第一個的值
 while(scanf("%d", &n)!=EOF)
 {
  int key=1;///用來判斷要印Jolly還是Not jolly用的
  int data, lastdata;
  int check[MAX]={0};///判斷有沒有重複的值所以啟始要先歸零不然會被帶入垃圾值
  for(int i=0; i<n; i++)
  {
   scanf("%d", &data);///一筆一筆讀來一筆一筆比較
   if(i&&key)///倆倆的相差運算和判斷jolly跟Not jolly的地方
   {
    int temp=abs(data-lastdata);
    
     if(temp<1 || temp>n-1 || check[temp]>0)///檢查相差值是否介於1~n-1跟有沒有重複
      key=0;
    
    check[temp]++;///開櫃子的概念
   }
   
   lastdata=data;
   
   
  }
  printf("%s\n", key? "Jolly" : "Not jolly");///答案列印
 
 
 }

}

程式碼打包:解法一

CPE031 UVa10193 - All You Need Is Love

題目原文
題目內容

IBM (International Beautiful Machines)公司發明了一種小玩意兒叫做「愛的算命機」。這台機器會回答你是否非常渴望愛情。這機器運作的情形是：請你輸入一僅含0和1的字串（稱為S），機器自己則定義一僅含0和1的字串（稱為L，Love的意思）。然後機器不斷的用S去減L（當然是2進位的減法），如果最後可以得到S=L，代表S是用Love做成的。如果最後L>S，代表S不是用Love做成的。

舉例說明：假設S="11011"，L="11"。如果我們不斷的從S減去L，我們可以得到：11011、11000、10101、10010、1111、1100、1001、110、11。所以我們得到L了，也就是S是用Love做的。由於愛的算命機的某些限制，字串不可以有以0為開頭的，也就是說"0010101"、"01110101"、"011111"這些字串都是不合法的。另外，只有一個位元的字串也是不合法的。

輸入說明:

輸入的第一列有一個整數N（N<10000），代表以下有幾組測試資料。每組測試資料2列，代表S1和S2字串，其長度都不會超過30個字元。你可以假設所有的字串都是合法的。

輸出說明:

對每一組測試資料輸出以下其中之一：

Pair #p: All you need is love! Pair #p: Love is not all you need!

在這裡p代表這是第幾組測試資料。如果S1和S2至少可以找到一個合法的L，使得S1和S2都可以用Love做成，則輸出第一種訊息。否則，請輸出第二種訊息。請參考Sample Output。

Sample Input

5
11011
11000
11011
11001
111111
100
1000000000
110
1010
100

Sample Output

Pair #1: All you need is love!
Pair #2: Love is not all you need!
Pair #3: Love is not all you need!
Pair #4: All you need is love!
Pair #5: All you need is love!

解法
使用字串把要互相比較的兩個值讀進來，之後再把它們二進位的值轉成十進位，之後再看他們是不是互值。如果是互值就印Love is not all you need!，反之印All you need is love!。
(注意:資料是兩筆兩筆一組的)


(以上資料來源:大學程式能力檢定Collegiate Programming Examination(CPE))

程式碼解答

#include <stdio.h>
int bin2sec()//二進位轉換成十進位
{
 char s[32];
 int n, i;
 scanf("%s" ,s);
 for(i=0,n=0; s[i]!='\0'; i++){
  n=n*2+(s[i]-'0');}
  return n;
}
int main()
{
 int n, i, x, y, z;
 scanf("%d\n", &n);
 for(i=1; i<=n; i++)
 {
  x=bin2sec();
  y=bin2sec();
  
  while(y>0)//輾轉相除法求出公因數
  {
   z=x%y;
   x=y;
   y=z;
  }
  if(x>1)//依照題意列印
   printf("Pair #%d: All you need is love!\n", i);
   
  else
   printf("Pair #%d: Love is not all you need!\n", i);
 }
}

程式碼打包:解法一、解法二