Awei 又在碎碎念惹: 5月 2017

2017年5月28日星期日

ITSA 50補 - [Problem 1] 猜數字 - 參考答案

Difficulty: Easy
Ref: ITSA 50補 - [Problem 1] 猜數字

/*******************************************************/
/* [Problem 1] 猜數字                                   */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/28                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

int main() {  
    int a, b;  
    char n[5], c[5];  
    scanf("%s", n);  
    while (scanf("%s", c)) {  
        if (!strcmp(c, "0000"))  
            return 0;  
        a = b = 0;  
        for (int i = 0; i < 4; i++) {  
            for (int j = 0; j < 4; j++) {  
                if (i == j && n[i] == c[j]) a++;  
                if (i != j && n[i] == c[j]) b++;  
            }  
        }  
        printf("%dA%dB\n", a, b);  
          
    }  
}

Debug： I/O
字串比較。

0A2B
0A4B
2A2B
4A0B

ITSA 51 - [Problem 5] Number Puzzle - 參考答案

Difficulty: Easy
Ref: ITSA 51 - [Problem 5] Number Puzzle

/*******************************************************/
/* [Problem 5] Number Puzzle                           */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/28                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

char buf[3][4];
int ok = 0;
void permute(int *a, int l, int r)
{
 if (ok) return;
 if (l == r) {     
  int num3 = a[buf[2][0]] * 100 + a[buf[2][1]] * 10 + a[buf[2][2]];
  if (num3 >= 300) return;
  int num1 = a[buf[0][0]] * 10 + a[buf[0][1]];
  int num2 = a[buf[1][0]] * 10 + a[buf[1][1]];
  if (num1 + num2 == num3) ok = 1;
 }
 else
 {
  char temp;
  for (int i = l; i <= r; i++)
  {
   temp = *(a + l);
   *(a + l) = *(a + i);
   *(a + i) = temp;
   permute(a, l + 1, r);
   temp = *(a + l);
   *(a + l) = *(a + i);
   *(a + i) = temp;
  }
 }
}

int main()
{
 while (scanf("%s%s%s", buf[0], buf[1], buf[2]) != EOF) {
  for (int i = 0; i < 3; i++)
   for (int j = 0; buf[i][j] != '\0'; j++)
    buf[i][j] -= 'A';

  ok = 0;
  int str[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  permute(str, 0, 9);
  if (ok)
   printf("YES\n");
  else
   printf("NO\n");
 }
 return 0;
}

Debug： I/O
窮舉法，把所有可能的答案進行排列匹配。

AB
BC
EED
AA
BB
ABA
AB
CD
DFG
AB
CD
EFG
AB
CD
CAD

YES
NO
YES
YES
NO

2017年5月22日星期一

ITSA 51 - [Problem 3] 中值濾波器 - 參考答案

Difficulty: Easy
Ref: ITSA 51 - [Problem 3] 中值濾波器

/*******************************************************/
/* [Problem 3] 中值濾波器                               */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/22                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
 int n;
 scanf("%d", &n);
 while (n--) {
  int m, seq[3];
  scanf("%d %d %d", &m, seq, &seq[1]);
  printf("%d ", seq[0]);
  m -= 2;
  while (m--) {
   scanf("%d", &seq[2]);
   if (seq[2] <= seq[0]) {
    if (seq[0] <= seq[1])
     seq[1] = seq[0];
    else if (seq[1] <= seq[2])
     seq[1] = seq[2];
   }
   else {
    if (seq[1] < seq[0])
     seq[1] = seq[0];
    else if (seq[2] < seq[1])
     seq[1] = seq[2];
   }
   printf("%d ", seq[0] = seq[1]);
   seq[1] = seq[2];
  }
  printf("%d\n", seq[2]);
 }
 return 0;
}

Debug： I/O
不斷比大小，答案就出來了。

2
9
3 3 5 3 3 9 4 4 4
10
4 15 3 4 4 1 3 4 4 8

3 3 3 3 3 4 4 4 4
4 4 4 4 4 3 3 4 4 8

2017年5月21日星期日

ITSA 51 - [Problem 2] 數數之積 - 參考答案

Difficulty: Easy
Ref: IITSA 51 - [Problem 2] 數數之積

/*******************************************************/
/* [Problem 2] 數數之積                                 */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/21                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main()
{
 char buf[40], *pch;
 while (fgets(buf, 40, stdin)) {
  unsigned long long ans = strtoull(buf, &pch, 10),temp;
  while (temp = strtoull(pch, &pch, 10))
   ans *= temp;
  printf("%llu\n", ans);
 }
 return 0;
}

Debug： I/O
一直乘。

2 7 9 40 2 
35 1 7 9 24 11

10080
582120

ITSA 51 - [Problem 1] 十進制轉二進制 - 參考答案

Difficulty: Easy
Ref: ITSA 51 - [Problem 1] 十進制轉二進制

/*******************************************************/
/* [Problem 1] 十進制轉二進制                           */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/21                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
 int n;
 scanf("%d", &n);
 while (n--) {
  int N;
  scanf("%d", &N);
  for (int i = 0; i < 8; i++){
   printf("%d", N & 128 ? 1 : 0);
   N <<= 1;
  }
  printf("\n");
 }
 return 0;
}

Debug： I/O
Bitwise operations 練習題目。

01111111
10000000
01000010

ITSA 52 - [Problem 5] Lowest Non-zero Digit of Factorial - 參考答案

Difficulty: Normal
Ref: ITSA 52 - [Problem 5] Lowest Non-zero Digit of Factorial

/*******************************************************/
/* [Problem 5] Lowest Non-zero Digit of Factorial      */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/21                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int lnzsdf(int x) {
 unsigned i = 0, j, k, l, ret = 1;
 for (k = 282475249, l = 0; k >= 1; l = k, k /= 49)
  for (i -= l, i += k; i <= x; i += k){
   for (j = i; j % 7 == 0; j /= 7);
   ret = (ret * (j % 7)) % 7;
  }
 return ret;
}

int main()
{
 int n;
 scanf("%d", &n);
 while (n--) {
  int N;
  scanf("%d", &N);
  printf("%d\n", lnzsdf(N));
 }
 return 0;
}

Debug： I/O
暴力解會超時，所以就用了點技巧來加速運算。
先投小範圍的測資，例如1~10000，會發現規律，每間格7^(2n)，其中n大於等於0時，會有同樣的循環數產生。
如果題目改為10 base的話，可以參考： Last non-zero digit of a factorial。
網路上有人說可用 Wilson’s Theorem 來解，但我是看不懂啦，只說沒實作，理論大師4ni? 黑人問號...

2017年5月20日星期六

ITSA 52 - [Problem 4] 合併排序 - 參考答案

Difficulty: Eazy
Ref: ITSA 52 - [Problem 4] 合併排序

/*******************************************************/
/* [Problem 4] 合併排序                                 */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/20                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
 char buf[512];
 while (1) {
  bool data[512] = { false };
  int lastout;

  for (int i = 0; i < 2; i++) {
   fgets(buf, 512, stdin);
   char *pch = strtok(buf, " ");
   while (pch != NULL) {
    data[lastout = atoi(pch)] = true;
    pch = strtok(NULL, " ");
   }
   if (!lastout) return 0;
  }

  for (int i = 0; i < 512; i++)
   if (data[i])
    if (lastout) {
     lastout = 0;
     printf("%d", i);
    }
    else
     printf(" %d", i);

  printf("\n");
 }
}

Debug： I/O
使用陣列做標記完成。
不用想太複雜，測資給的也很小。

2 5 6 8 12
1 4 15
1 8 9 11
2 4 5 10 13
0 0 0 0 0

1 2 4 5 6 8 12 15
1 2 4 5 8 9 10 11 13

ITSA 52 - [Problem 3] 頑皮的比爾 - 參考答案

Difficulty: Eazy
Ref: ITSA 52 - [Problem 3] 頑皮的比爾

/*******************************************************/
/* [Problem 3] 頑皮的比爾                               */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/20                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

struct Node {
 char id;
 Node *next;
};

int main() {
 Node node[102];
 int n;
 scanf("%d", &n);
 while (n--) {
  int k;
  scanf("%d", &k);
  for (int i = 0; i <= k; i++) {
   node[i].id = i;
   node[i].next = &node[i + 1];
  }

  int layer;
  while (scanf("%d", &layer)){
   if (layer == 0) break;
   Node *left = node[0].next;
   Node *center = left->next;
   Node *right = center->next;
   for (int i = 1; i < layer; i++) {
    center->next = left;
    left = center;
    center = right;
    right = right->next;
   }
   node[0].next->next = center;
   node[0].next = left;
  }

  Node *nextNode = node[0].next;
  printf("%d", nextNode->id);
  for (int i = 2; i <= k; i++) {
   nextNode = nextNode->next;
   printf(" %d", nextNode->id);
  }
  printf("\n");
 }
}

Debug： I/O
本題可以用來練習連結串列。
將每層的煎餅視為1個Node，每個Node均有獨立的id，其id代表煎餅的大小。

3
5 2 1 3 5 4 0
50 25 14 49 7 32 48 46 37 6 17 36 42 5 33 8 7 7 41 30 20 10 0

1 2 4 5 3
47 48 49 42 41 40 6 17 18 19 46 45 44 43 9 22 23 24 25 11 20 21 29 28 27 26 1 2 3 4 10 39 38 30 31 32 33 34 35 36 37 5 16 15 14 13 7 8 12 50

2017年5月19日星期五

ITSA 52 - [Problem 2] 天際線資料群 - 參考答案

Difficulty: Eazy
Ref: ITSA 52 - [Problem 2] 天際線資料群

/*******************************************************/
/* [Problem 2] 天際線資料群                             */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/19                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
 int n;
 scanf("%d ", &n);
 int xy[10][2], ans[10] = { 0 };
 for (int i = 0; i < n; i++)
  scanf("%d %d", xy[i], &xy[i][1]);

 for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++)
   if (xy[i][0] <= xy[j][0] && xy[i][1] <= xy[j][1] && (xy[i][0] < xy[j][0] || xy[i][1] < xy[j][1]) && i != j) {
     ans[i] = 1;
     break;
    }

 printf("%c", ans[0] ? 'N' : 'Y');
 for (int i = 1; i < n; i++)
  printf(" %c", ans[i] ? 'N' : 'Y');
 printf("\n");
}

Debug： I/O
比較大小的經典題目。
需要知道大於、小於、等於排列起來共9種狀態，並加以篩選即為答案。

Y N Y Y N Y

2017年5月18日星期四

ITSA 52 - [Problem 1] 撲克牌大小 - 參考答案

Difficulty: Eazy
Ref: ITSA 52 - [Problem 1] 撲克牌大小

/*******************************************************/
/* [Problem 1] 撲克牌大小                               */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/18                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 36*3 + 16*4

int main() {
 int n;
 scanf("%d ", &n);
 while (n--) {
  char buf[MAX], cards[52][4];
  fgets(buf, MAX, stdin);
  buf[strlen(buf) - 1] = '\0';

  int count = 0;
  char *pch = strtok(buf, " ");
  while (pch != NULL) {
   strcpy(cards[count++], pch);
   pch = strtok(NULL, " ");
  }

  for (int i = 0; i < count - 1; i++)
   for (int j = i + 1; j < count; j++)
    if ((cards[i][0] < cards[j][0]) || (cards[i][0] == cards[j][0]) && (atoi(&cards[i][1]) < atoi(&cards[j][1]))) {
     char temp[4];
     strcpy(temp, cards[i]);
     strcpy(cards[i], cards[j]);
     strcpy(cards[j], temp);
    }

  printf("%s", cards[0]);
  for (int i = 1; i < count; i++)
   printf(" %s", cards[i]);
  printf("\n");
 }
}

Debug： I/O
整行輸入後字串切割，使用泡沫排序法排序。
花色大小剛好對應到花色字元 ASCII 的大小，排序變得更簡單。
排序規則：如果花色比較大或花色相同但數字較大。

4
H5 D4 S2 C13
D8 S3 D10 C12 H7
H6 S3
C5 D11 S1

S2 H5 D4 C13
S3 H7 D10 D8 C12
S3 H6
S1 D11 C5

2017年5月17日星期三

ITSA 54 - [Problem 5] Momo’s Hanoi Tower - 參考答案

Difficulty: Eazy
Ref: ITSA 54 - [Problem 5] Momo’s Hanoi Tower

/*******************************************************/
/* [Problem 5] Momo’s Hanoi Tower                      */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/17                                 */
/*******************************************************/
import java.util.Scanner;
import java.math.BigInteger;

public class Main{
 public static void main(String args[]) {
  Scanner scanner = new Scanner(System.in);
  int T = scanner.nextInt();
  while (T-- > 0) {
   int K = scanner.nextInt();
   BigInteger sum = new BigInteger("0");
   while(K-- > 0) {
    BigInteger n = scanner.nextBigInteger();
       BigInteger temp = new BigInteger("1");
    temp = temp.shiftLeft(K);
    temp = temp.multiply(n);
    sum = sum.add(temp);
   }
   System.out.println(sum);
  }
 }
}

Debug： I/O
這題說起來也怪，比賽的時候 C code 可以 AC ，但開放練習後再次提交居然變成 WA ...
先寫 Hanoi Tower 來模擬本題的要求，多試幾次後會發現其實是在算 nk*(2^k) 的問題。
特別注意答案為非常大的整數！

2
30
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
30
9 8 7 6 5 4 3 2 1 9 8 7 6 5 4 3 2 1 9 8 7 6 5 4 3 2 1 9 8 7

8608845891
2126491626

2017年5月16日星期二

ITSA 54 - [Problem 4] 稀疏矩陣相乘 - 參考答案

Difficulty: Eazy
Ref: ITSA 54 - [Problem 4] 稀疏矩陣相乘

/*******************************************************/
/* [Problem 4] 稀疏矩陣相乘                             */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/16                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main() {
 int n;
 scanf("%d", &n);
 while (n--) {
  int m, v, row, col, val, matrix[11][11] = { 0 };
  scanf("%d %d", &m, &v);
  for (int i = 0; i < v; i++) {
   scanf(" (%d:%d)=%d", &row, &col, &val);
   matrix[row][col] = val;
  }

  for (int i = 1; i <= m; i++) {
   int j = 0;
   while (j < i - 1)
    printf("%d ", matrix[j++][i]);

   matrix[i - 1][++j] = 0;
   for (int k = 1; k <= m; k++)
    matrix[i - 1][j] += matrix[i][k] * matrix[j][k];

   while (j < m) {
    printf("%d ", matrix[i - 1][j]);
    matrix[i - 1][++j] = 0;
    for (int k = 1; k <= m; k++)
     matrix[i - 1][j] += matrix[i][k] * matrix[j][k];
   }
   printf("%d\n", matrix[i - 1][j]);
  }
 }
}

Debug： I/O
此稀疏矩陣又是方陣，所以 A*AT 處理起來相對簡單。
A*AT 又是 Symmetric Matrix，所以有避開重複計算。

1
10 10
(3:2)=3
(2:3)=2
(1:2)=2
(7:2)=3
(8:5)=1
(10:1)=2
(5:9)=2
(9:6)=3
(4:7)=2
(6:6)=3

4 0 6 0 0 0 6 0 0 0
0 4 0 0 0 0 0 0 0 0
6 0 9 0 0 0 9 0 0 0
0 0 0 4 0 0 0 0 0 0
0 0 0 0 4 0 0 0 0 0
0 0 0 0 0 9 0 0 9 0
6 0 9 0 0 0 9 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 9 0 0 9 0
0 0 0 0 0 0 0 0 0 4

2017年5月15日星期一

ITSA 54 - [Problem 3] 電路板溫度升高問題 - 參考答案

Difficulty: Eazy
Ref: ITSA 54 - [Problem 3] 電路板溫度升高問題

/*******************************************************/
/* ITSA 54 - [Problem 3] 電路板溫度升高問題              */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/15                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main() {
 int m;
 scanf("%d", &m);
 while (m--) {
  double Ti;
  int i;
  scanf("%lf,%d", &Ti, &i);
  printf("%2.4lf\n", Ti + 2.71828 * (1 + i) * i / 2);
 }
}

Debug： I/O
很明顯是在算三角形面積。(底乘高除以2)

10
94.87,9
94.87,8
94.87,7
94.87,6
94.87,5
94.87,4
94.87,3
94.87,2
94.87,1
94.87,0

ITSA 54 - [Problem 2] 量販店活動 - 參考答案

Difficulty: Eazy
Ref: ITSA 54 - [Problem 2] 量販店活動

/*******************************************************/
/* ITSA 54 - [Problem 2] 量販店活動                     */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/15                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main() {
 int m;
 scanf("%d", &m);
 while (m--) {
  int i, j, goods[10][2], mx_weight, n, bag[101] = { 0 };
  scanf("%d%d", &mx_weight, &n);
  for (i = 0; i < n; i++){
   scanf("%d%d", goods[i], goods[i] + 1);
   while (getchar() != '\n');
  }
  for (i = 0; i < n; i++)
   for (j = goods[i][0]; j <= mx_weight; j++) {
    int term = bag[j - goods[i][0]] + goods[i][1];
    if (term > bag[j])
     bag[j] = term;
   }
  printf("Total: %d\n", bag[mx_weight]);
 }
}

Debug： I/O
簡單的背包問題，使用動態規劃以減少時間複雜度，才能在限制時間內算出答案。
可以參考背包問題詳細說明：背包問題（Knapsack Problem）

2
15
5
6 6000 watch
4 4500 beverage
5 5500 fruit
3 2500 bread
2 2100 coke
99
9
3 2500 bread
7 6500 bagel
4 4500 yogurt
5 5500 watch
10 11500 beverage
8 8500 fruit
9 1100 jam
2 2200 coke
6 6000 juice

Total: 16600
Total: 113500

2017年5月9日星期二

ITSA 54 - [Problem 1] 最大值與最小值 - 參考答案

Difficulty: Eazy
Ref: ITSA 54 - [Problem 1] 最大值與最小值

/*******************************************************/
/* ITSA 54 - [Problem 1] 最大值與最小值                 */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/09                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
 int n;
 float number, mxterm, mnterm;
 char buf[100], *pch;
 scanf("%d\n", &n);
 while (n--) {
  fgets(buf, 128, stdin);
  pch = strtok(buf, " ");
  mnterm = mxterm = atof(pch);
  while (pch = strtok(NULL, " ")) {
   number = atof(pch);
   if (mxterm < number)
    mxterm = number;
   if (mnterm > number)
    mnterm = number;
  }
  printf("maximum:%.2f\nminimum:%.2f\n", mxterm, mnterm);
 }
}

Debug： I/O
簡單的數字比大小。

2
-2 -15.2 0 89.5 100 25.3 7 30 76 4
0 3 52.7 998 135 -256 79 95 10 16

maximum:100.00
minimum:-15.20
maximum:998.00
minimum:-256.00

訂閱：文章 (Atom)

2017年5月28日 星期日

2017年5月22日 星期一

2017年5月21日 星期日

2017年5月20日 星期六

2017年5月19日 星期五

2017年5月18日 星期四

2017年5月17日 星期三

2017年5月16日 星期二

2017年5月15日 星期一

2017年5月9日 星期二