Awei 又在碎碎念惹

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月19日 星期五

2017年5月18日 星期四

2017年5月17日 星期三

2017年5月16日 星期二

2017年5月15日 星期一

2017年5月9日 星期二