APCS進階班第1次模擬考解答
===

* [d096: 00913 - Joana and the Odd Numbers](#d096)
* [b265: Q11286 - Conformity](#b265)
* [c002: 10696 - f91](#c002)
* [c123: 00514 - Rails](#c123)
* [b266: 矩陣翻轉(APCS官網例題)](#b266)

# <a id='b266'>b266: 矩陣翻轉(APCS官網例題)</a>

https://zerojudge.tw/ShowProblem?problemid=b266

範例輸入：([解答連結](http://rs-vb.blogspot.tw/2016/09/apcs-10532-c.html))

3 2 3 <- 3列 2行 3個翻轉或旋轉指令
1 1 <- 以下3列是矩陣
3 1
1 2
1 0 0 <- 0是旋轉(順時針) 1是翻轉(上下翻轉)
3 2 2
3 3
2 1
1 2
0 1

範例輸出：

3 2 <- 下面矩陣的row跟col
1 1 <- 矩陣資料
1 3
2 1

2 3 <- 下面矩陣的row跟col
2 1 3 <- 矩陣資料

1 2 3

範例解釋

輸入資訊如下
3 2 3
1 1
3 1
1 2
1 0 0

代表結果的矩陣B是這樣
1 1
3 1
1 2

B是A矩陣經過1(上下顛倒)->0(順時針旋轉)->0(順時針旋轉)
所以要求出A必須將 1 0 0 給回朔

解答

#include < iostream > 
#include < vector >
using namespace std;
const int MaxN = 10;

int a[2][MaxN][MaxN];
int rc[2]; //列高、行寬

void rev0(int s, int w) //逆旋轉
{
  int r = rc[w], c = rc[1 - w];
  int i, j;
  for (i = 0; i < r; ++i)
    for (j = 0; j < c; ++j)
      a[1 - s][c - 1 - j][i] = a[s][i][j];
}

void rev1(int s, int w) //逆翻轉
{
  int r = rc[w], c = rc[1 - w];
  int i, j;
  for (i = 0; i < r; ++i)
    for (j = 0; j < c; ++j)
      a[1 - s][r - 1 - i][j] = a[s][i][j];
}
void print(int s, int w) //印矩陣
{
  int r = rc[w], c = rc[1 - w];
  int i, j;
  cout << r << ' ' << c << endl;
  for (i = 0; i < r; ++i) {
    cout << a[s][i][0];
    for (j = 1; j < c; ++j)
      cout << ' ' << a[s][i][j];
    cout << endl;
  }
}

int main(void) {
  int i, j, k, r, c, m;
  bool first = true;
  while (cin >> r >> c >> m) {
    rc[0] = r;
    rc[1] = c;
    for (i = 0; i < r; ++i)
      for (j = 0; j < c; ++j)
        cin >> a[0][i][j];
    int s = 0, w = 0;
    // print(s,w); // 測試用印出
    int d[MaxN];
    for (i = 0; i < m; ++i) cin >> d[i];
    for (i = m - 1; i >= 0; --i) {
      if (d[i] == 0) {
        rev0(s, w); // 旋轉
        w = 1 - w;
      } else rev1(s, w); // 翻轉
      s = 1 - s;
      // print(s,w); // 測試用印出
    }
    if (first) first = false;
    else cout << endl;
    print(s, w);
  }
  return 0;
}

Allen註解版

#include <iostream>

using namespace std;
const int MaxN = 10;
int data[MaxN][MaxN];
int cmd[MaxN];
int row, col;

void reverse_cmd0() //逆旋轉(逆時針旋轉)
{
  int i, j;
  int newData[MaxN][MaxN];

  //逆時針旋轉
  for (i = 0; i < row; i++) {
    for (j = 0; j < col; j++) {
      newData[j][i] = data[i][col - j - 1];
    }
  }

  //把row與col交換
  int temp = row;
  row = col;
  col = temp;

  //把新的陣列回傳給data
  for (i = 0; i < row; i++)
    for (j = 0; j < col; j++)
      data[i][j] = newData[i][j];
}

void reverse_cmd1() //逆翻轉(翻轉逆跟不膩都是一樣的)
{
  int i, j;
  int newData[MaxN][MaxN];

  //上下顛倒
  for (i = 0; i < row; i++)
    for (j = 0; j < col; j++)
      newData[i][j] = data[row - i - 1][j];

  //把新的陣列回傳給data
  for (i = 0; i < row; i++)
    for (j = 0; j < col; j++)
      data[i][j] = newData[i][j];

}
void print() //印矩陣
{
  int i, j;
  cout << row << ' ' << col << endl;

  for (i = 0; i < row; ++i) {
    for (j = 0; j < col; ++j)
      cout << data[i][j] << " ";
    cout << endl;
  }
}

int main(void) {
  int i, j, m;

  while (cin >> row >> col >> m) {

    //依序輸入所有矩陣的資料
    for (i = 0; i < row; ++i)
      for (j = 0; j < col; ++j)
        cin >> data[i][j];

    //輸入操作矩陣的指令(0或1)
    for (i = 0; i < m; ++i) cin >> cmd[i];

    //從最後一個指令開始解析，因為我們要讓整個矩陣變成原矩陣
    for (i = m - 1; i >= 0; --i) {
      if (cmd[i] == 0) {
        reverse_cmd0(); // 逆時針旋轉
      } else {
        reverse_cmd1(); // 翻轉
      }
    }

    print();
    cout << endl;
  }
  return 0;
}

---
# <a id='c002'>c002: 10696 - f91</a>

zerojudge: https://zerojudge.tw/ShowProblem?problemid=c002

uva: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1637

• If N ≤ 100, then f91(N) = f91(f91(N + 11));
• If N ≥ 101, then f91(N) = N − 10.

---

#include < iostream >
using namespace std;

int f91(int);
int main() {
  int n;
  while (cin >> n && n != 0) {
    cout << "f91(" << n << ") = " << f91(n) << endl;
  }
}
int f91(int num) {
  if (num <= 100) return f91(f91(num + 11)); //遞迴
  else return num - 10; //終止條件
}

---

# <a id='c123'>c123: 00514 - Rails</a>

https://zerojudge.tw/ShowProblem?problemid=c123

解答

//By SCJ
//uva 514
#include < bits / stdc++.h >
using namespace std;

int main() {

  int n;
  bool fir = 0;
  while (cin >> n, n != 0) {
    while (1) {
      bool fg = 0;
      int t, cnt = 2;
      stack < int > s;
      s.push(1);
      bool ok = 1; //預設是ok
      //
      for (int i = 0; i < n; ++i) {
        cin >> t; //輸入每個車廂
        if (t == 0) { //輸入0代表造跳出
          fg = 1;
          break;
        }
        while (cnt <= n && (s.empty() || s.top() != t)) {
          s.push(cnt++);
        }
        if (s.empty() || s.top() != t) {
          //不ok
          ok = 0;
        } else {
          s.pop();
        }
      }
      //輸入0所以跳出
      if (fg) break;
      if (ok) {
        cout << "Yes" << endl;
      } else {
        cout << "No" << endl;
      }
    }
    cout << endl;
  }
}

Allen翻譯版本

//uva 514
#include < bits / stdc++.h >
using namespace std;

int main() {

  //n代表要輸入幾個火車廂
  int n;
  while (cin >> n, n != 0) {
    while (1) {
      bool flag = 0; //flag=1代表要跳出目前的測試模式
      int train;
      int cnt = 2; //代表要駛入車站的車廂號碼
      stack < int > stk; //火車站

      stk.push(1); //先讓第一節車廂開進火車站
      bool ok = true; //預設是ok，預設是會成功的，中途遇到錯誤再改成ok=false

      for (int i = 0; i < n; ++i) {
        cin >> train; //輸入每個車廂

        if (train == 0) { //輸入0代表要跳出
          flag = 1;
          break;
        }

        //還有未進站的火車 且 目前車站的車頭不是我們要的
        while (cnt <= n && (stk.empty() || stk.top() != train)) {
          //if(stk.empty())cout<<"車站沒車"<<endl;
          //cout<<"火車("<<cnt<<")進站"<<endl;
          stk.push(cnt++);
        }

        //如果車站是空的 或 要出站的火車不是我們要的
        if (stk.empty() || stk.top() != train) {
          //代表出車失敗，ok = false
          ok = false;
        } else {
          //成功出車，把火車送出停靠站，往B前進
          //cout<<"火車("<<stk.top()<<")出站"<<endl;
          stk.pop();
        }
      }

      //輸入0所以跳出
      if (flag) break;

      if (ok) {
        cout << "Yes" << endl;
      } else {
        cout << "No" << endl;
      }
    }
    cout << endl;
  }
}

---
# <a id='b265'>b265: Q11286 - Conformity</a>

[https://zerojudge.tw/ShowProblem?problemid=b265](https://zerojudge.tw/ShowProblem?problemid=b265)

需要用到 struct, sort, 且較難想的題目

#include <iostream> 
#include <string.h> 
#include <algorithm>
using namespace std;
int N;

struct Student {
  int course[5];
}
student[10005];

//比較兩個學生的所有課程編號大小
bool cmp(Student A, Student B) {
  for (int i = 0; i < 5; i++)
    if (A.course[i] != B.course[i])
      return A.course[i] < B.course[i];
  return false;
}

//檢測兩個學生的所有課程是否一樣
bool same(int x, int y) {
  for (int i = 0; i < 5; i++)
    if (student[x].course[i] != student[y].course[i])
      return false;
  return true;
}

int main() {

  //N位學生
  while (cin >> N) {
    if (N == 0) break;
    int x;

    //輸入每位學生所選的課程，最後把課程先排序
    for (int i = 1; i <= N; i++) {
      for (int j = 0; j < 5; j++) {
        cin >> student[i].course[j];
      }
      sort(student[i].course, student[i].course + 5);
    }

    //將學生們也進行排序，依照他們所選的課當依據
    sort(student + 1, student + N + 1, cmp);

    //longest代表最多人選的課程組合，有多少人選
    //now暫存的變數，紀錄相同的課程組合，重複出現幾次
    //ans是最後的答案
    int longest = 1, now = 1, ans = 0;

    //掃過每位學生，找出最多人選的組合，總共有多少人選
    for (int i = 2; i <= N; i++) {
      if (same(i, i - 1)) {
        now++; //該位同學與前一位同學的選課一模一樣，課程重複次數增加
        if (now > longest)
          longest = now; //新的最熱門課程誕生
      } else
        now = 1; //該位學生與前位學生的選課不同，重複次數重新計算
    }

    now = 1;

    //最熱門課程只有一人，代表大家選的都不同，每位學生的組合都是最熱門的組合

    //檢查最多人選的課程是否不只一種組合，如果longest是3，裡面有兩個課程組合各有3人選的話
    //那就是3+3，答案就是6
    //裡面比較特別的是當每種組合都不同(longest==1)時，要把答案先+1
    for (int i = 2; i <= N; i++) {
      if (same(i, i - 1)) {
        now++;
      } else
        now = 1;

      if (now == longest)
        ans += longest;
    }
    if(longest==1)    ans++;
    cout << ans << endl;

  }

  return 0;
}

---

# <a id='d096'>d096: 00913 - Joana and the Odd Numbers</a>

[https://zerojudge.tw/ShowProblem?problemid=d096](https://zerojudge.tw/ShowProblem?problemid=d096)

#include <iostream>
using namespace std;
int main() {
  long long n, ans, row, lineStarter, lastOdd;
  while (cin >> n) {
    //算出n個奇數該出現在第幾列，也就是row
    row = (1 + n) / 2;
    //算出第row列的開頭數字是多少
    lineStarter = (row - 1) * (row - 1) * 2 + 1;
    //該列的最後一個奇數的算法
    lastOdd = lineStarter + 2 * (n - 1);
    //lastOdd+(lastOdd-2)+(lastOdd-4) = lastOdd*3 -6
    ans = lastOdd * 3 - 6;
    cout << ans << endl;
  }
  return 0;
}