Awei 又在碎碎念惹

2017年12月4日星期一

ITSA 58 - [Problem 3] 完整二元樹 - 參考答案

Difficulty: Easy
Ref: ITSA 58 - [Problem 3] 完整二元樹

/*******************************************************/
/* [Problem 3] 完整二元樹                               */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/12/04                                 */
/*******************************************************/
#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int m;
    cin >> m;
    
    while(m--) {
        int C, index = 1, binTree[16];
        char buf[100];
        
        cin >> C;
        cin.ignore(0x7fffffff, '\n');
        cin.getline(buf, 101, '\n');
        
        for(int i = 0; buf[i] != '\0'; i++)
            if(buf[i] >= '0' && buf[i] <= '9') {
                binTree[index++] = atoi(&buf[i]);
                while(buf[i+1] >= '0' && buf[i+1] <= '9') i++;
            }
        
        int innerNodes = floor(index/2);
        bool notFirstOut = false;
        
        for(int i = 1; i < innerNodes; i++) {
            if(abs(binTree[i] - binTree[i * 2]) <= C) {
                if(notFirstOut) cout << " ";
                cout << char('@' + i) << char('@' + i * 2);
                notFirstOut = true;
            }
            if(abs(binTree[i] - binTree[i * 2 + 1]) <= C) {
                if(notFirstOut) cout << " ";
                cout << char('@' + i) << char('A' + i * 2);
                notFirstOut = true;
            }
        }
        cout << endl;
    }
    return 0;
}

Debug： I/O
需修補的路段進行標示，然後統計出答案。

2
8
(A,2),(B,10),(C,13)
7
(A,2),(B,10),(C,13),(D,7),(E,8),(F,9),(G,11)

AB
BD BE CF CG

ITSA 58 - [Problem 2] 道路修補 - 參考答案

Difficulty: Easy
Ref: ITSA 58 - [Problem 2] 道路修補

/*******************************************************/
/* [Problem 2] 道路修補                                 */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/12/04                                 */
/*******************************************************/
#include <iostream> 

using namespace std;

int main() {
    int m;
    cin >> m;
    
    while(m--) {
        int n, s, e, length = 0, road[10001] = { 0 };
        
        cin >> n;
        
        while(n--) {
            cin >> s >> e;
            for(int i = s; i < e; i++)
                road[i] = 1;
        }
        
        for(int i = 0; i < 10001; i++)
            if(road[i])
                length++;
        
        cout << length << endl;
    }
    return 0;
}

Debug： I/O
需修補的路段進行標示，然後統計出答案。

10
8

ITSA 58 - [Problem 1] 計算正整數被3整除之數值之總和 - 參考答案

Difficulty: Easy
Ref: ITSA 58 - [Problem 1] 計算正整數被3整除之數值之總和

/*******************************************************/
/* [Problem 1] 計算正整數被3整除之數值之總和              */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/12/04                                 */
/*******************************************************/
#include <iostream> 

using namespace std;

int main() {
 int m, N;
 cin >> m;
 while (m-- && cin >> N) {
  N = N / 3;
  cout << N * (N + 1) * 3 / 2 << endl;
 }
}

Debug： I/O
等差數列的和。

2
100
150

1683
3825

2017年6月1日星期四

ITSA 50補 - [Problem 3] 面積逼近 - 參考答案

Difficulty: Easy
Ref: ITSA 50補 - [Problem 3] 面積逼近

/*******************************************************/
/* [Problem 3] 面積逼近                                 */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/06/01                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h> 

int main()
{
 int m;
 scanf("%d", &m);
 while (m--) {
  int n;
  scanf("%d", &n);
  double k = 1.0 / n;
  printf("%.4lf\n", k * k * k * n * (n + 1) * (2 * n + 1) / 6);
 }
 return 0;
}

Debug： I/O
(1/n)*(1/n)*(1/n) + 2*(1/n)*2*(1/n)*(1/n) + 3*(1/n)*3*(1/n)*(1/n) + ... + (1/n)^5
= (1*1 + 2*2 + 3*3 + ... + n*n) * (1/n)^3 。
觀察1~n個長方形的算式時會發現答案可以利用平方和公式來解。

ITSA 50補 - [Problem 2] 檢驗學號 - 參考答案

Difficulty: Easy
Ref: ITSA 50補 - [Problem 2] 檢驗學號

/*******************************************************/
/* [Problem 2] 檢驗學號                                 */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/06/01                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
 char buf[14];
 int n;
 scanf("%d", &n);
 while (n--) {
  scanf("%s", buf);
  int sum = 0;
  for (int i = 0; i < 12; i += 2)
   sum += buf[i] + 3 * buf[i + 1];

  sum = 26 + '@' - (sum - 24 * '0') % 26;

  if (sum == buf[12])
   printf("valid\n");
  else
   printf("invalid\n");
 }
 return 0;
}

Debug： I/O
基偶位置作 sum，然後加減乘除。

2
123456789012L
098765432100A

valid
invalid

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

訂閱：文章 (Atom)

2017年12月4日 星期一