課程名稱︰計算機程式設計 課程性質︰資工系大一必帶 課程教師︰黃上恩 開課學院：電機資訊學院 開課系所︰資訊工程學系 考試日期（年月日）︰2026/10/05 考試時限（分鐘）：180 試題中的檔案均放在以下的 github repository： https://github.com/hiiragi4000/NTU-CSIE1210-02-115-Exams/tree/master/exam1 試題： A1. Single Choice Questions (8 pts) Instruction: Answer the following questions. The input will be one of SAMPLE, Q1, Q2, Q3, or Q4. Your program only needs to print the answer to the correspon- ding question, including the parentheses. For example, (A) or (C). ── SAMPLE: Q: What is the last name of the professor teaching this course? (A) Liu (B) Huang (C) Chen (D) Lin Q1: Q: Which of the following is a valid variable name in C? (A) second-place (B) second_place (C) 2nd_place (D) None of the above Q2: Q: Suppose x is an int variable safisfying 0 ≦ x ≦ 100000. Which of the follo- wing correctly computes $x^3$ and stores the result in y for every possible value of x? (A) long long y = x * x * x; (B) long long y = x * (long long)x * x; (C) long long y = x * x * (long long)x; (D) None of the above Q3: Q: Suppose an int occupies 4 bytes. Approximately how much memory is required to store $10^8$ int values in a program? Choose the closest answer. (A) 400 MB (B) 200 MB (C) 100 MB (D) 50 MB Q4: Q: What does the following program output? #include <stdio.h> int main() { int a = 5; int x = a + (a++); printf("%d\n", x); } (A) 10 (B) 11 (C) The output is not guaranteed (D) The program will fail to compile (CE) Your Task: 1. Download the file a1.c from the site. 2. Complete the code within the TODO sections. Sample Test Cases: Sample Input 1: ──────────────────────────────────────── SAMPLE ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── (B) ──────────────────────────────────────── A2. The Broken Register (8 pts) The corner grocery store got a brand-new register last week, but it hasn't been working correctly. Customers walk out with the wrong change, discounts come out strange, and the loyalty stamp cards never seem to fill up. The store owner dug up the register's source code and found that it was written in C. Unfortunately, the owner doesn't know C, but you do. The owner explains how a checkout is supposed to work: ──────────────────────────────────────── How a Checkout Works A customer buys at most three kinds of items. The i-th item costs $p_i$ dollars each, and the customer buys $q_i$ of them. If the customer buys fewer than three kinds of items, the remaining $p_i$ and $q_i$ are set to 0. Sometimes there will be events that cause the customer to receive a discount d, which means d% off the subtotal. The discount amount is rounded down to a whole dollar. After the discount, the customer can redeem stamps on their stamp card. The cus- tomer brings a stamp card holding s stamps. Every full group of 10 stamps is re- deemed for 10 dollars off, and the redeemed stamps are removed from the card. Leftover stamps stay on the card. When the customer redeems stamps, they always redeem as many full groups of 10 stamps as possible. This remains true even if the amount due is already 0 or becomes 0 before all groups have been redeemed. After redeeming, the card receives 1 new stamp for this purchase. If the total amount due at this point is 0 or less, the customer pays nothing and receives no change. Otherwise, the customer pays P dollars, and the register gives back the change. The change is handed out using as many $100 bills as possible, then as many $50 coins as possible, then $10, $5, and finally $1 coins. ──────────────────────────────────────── Your Task: 1. Download the file a2.c from the site. 2. Find ahd fix the bugs in the program. What the program does: The program reads the price and quantity of three items, followed by the amount paid, the discount percentage, and the number of stamps on the customer's card. It prints the change, how many of each bill or coin make up the change, and how many stamps are left on the card after the purchase. Constraints: ‧ $0 \le p_1, p_2, p_3 \le 1000$ ‧ $0 \le q_1, q_2, q_3 \le 100$ ‧ $p_i = 0$ iff and only if $q_i = 0$. ‧ The customer buys at least one item, i.e. at least one of $q_1, q_2, q_3$ is nonzero. ‧ 0 ≦ d ≦ 100 ‧ 0 ≦ s ≦ 1000 ‧ $1 \le P \le 3\times10^5$ ‧ The amount due after the discount and stamps is guaranteed to be at most P. Input Format: ‧ The first line contains six integers $p_1$, $q_1$, $p_2$, $q_2$, $p_3$, and $q_3$, separated by spaces. ‧ The second line contains three integers P, d, and s, separated by spaces. Output Format: ‧ The first line is Change: followed by the change. ‧ The second line is 100: a, 50: b, 10: c, 5: e, 1: f, where a, b, c, e, f are the numbers of $100, $50, $10, $5, and $1 in the change. ‧ The third line is Stamps left: followed by the number of stamps on the card after the purchase. Sample Test Cases: Sample Input 1: ──────────────────────────────────────── 30 4 25 2 15 2 160 10 23 ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── Change: 0 100: 0, 50: 0, 10: 0, 5: 0, 1: 0 Stamps left: 4 ──────────────────────────────────────── A3. Unix Permission (8 pts) On Unix-like systems, every file carries a set of permissions that decides who can do what with it. If you run ls -l in a terminal, you will see something like -rwxr-xr-- 1 hyper cprog 1210 Oct 5 09:10 exam1 The nine characters after the first - are the permission string. They are split into three groups of three characters, one group each for the file's owner, group, and others. Within a group, the characters are always in the order r (read), w (write), and x (execute); a - means that permission is not granted. Typing nine characters is tedious, so the chmod command accepts a three-digit number instead: ──────────────────────────────────────── Numeric (Octal) Permission Each digit (0 to 7) describes one group, from left to right: owner, group, others. A digit is the sum of the permissions it grants: \begin{tabular}{|c|c|c|}\hline \textbf{Permission} & \textbf{Character} & \textbf{Value}\\\hline read & \texttt r & 4\\\hline write & \texttt w & 2\\\hline execute & \texttt x & 1\\\hline \end{tabular} For example, 7 = 4 + 2 + 1 means rwx, 5 = 4 + 1 means r-x, and 4 means r--. Therefore 754 corresponds to rwxr-xr--. ──────────────────────────────────────── Your Task: 1. Download the file a3.c from the site. 2. Implement the code within the TODO section. What the program does: This program reads a three-digit numeric permission and prints the corresponding nine-character permission string. Input Format: ‧ A single line containing the three-digit permission n. Output Format: ‧ A single line containing the nine-character permission string. Constraints: ‧ The input consists of exactly three digits, each between 0 and 7 (inclusive). ‧ The input may contain leading zeros, e.g. 007. Sample Test Cases: Sample Input 1: ──────────────────────────────────────── 754 ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── rwxr-xr-- ──────────────────────────────────────── Sample Input 2: ──────────────────────────────────────── 640 ──────────────────────────────────────── Sample Output 2 ──────────────────────────────────────── rw-r----- ──────────────────────────────────────── Sample Input 3: ──────────────────────────────────────── 007 ──────────────────────────────────────── Sample Output 3: ──────────────────────────────────────── ------rwx ──────────────────────────────────────── A4. Primality Test (8 pts) A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 3 is prime because the only ways of wri- ting it as a product, 1 × 3 or 3 × 1, involve 3 itself. However, 4 is compo- site because it is a product (2 × 2) in which both numbers are smaller than 4. Note that 1 is, by definition, neither prime nor composite. The property of being prime is called primality. A simple method for checking the primality of a given number n tests whether n is divisible by any integer from 2 through n-1. However, this method is so slow that it may take more than 1 second on our machine to determine whether a prime number greater than $10^9$ is prime. A faster method tests whether n is divisible by any integer from 2 through $\sqrt n$ instead. This method works because if an integer n is compo- site, then n must have a divisor between 2 and $\sqrt n$. ──────────────────────────────────────── Proof of Sufficiency of Testing between 2 and $\sqrt n$ Suppose n is composite. Then n has a divisor $d_0$ satisfying $1 < d_0 < n$. If $d_0 \le \sqrt n$, then $d_0$ is a divisor of n between 2 and $\sqrt n$. If $d_0 > n$, note that $\frac n{d_0}$ is also a divisor of n, and \[1 < \frac n{d_0} < \frac n{\sqrt n} = \sqrt n.\] Thus, $\frac n{d_0}$ is a divisor of n between 2 and $\sqrt n$. ──────────────────────────────────────── You are given T positive integers $n_1, n_2, \ldots, n_T$. The program a4.c is intended to determine whether $n_i$ is prime from i ∈ {1, 2, ..., T}. However, it contains several bugs and may not work as expected. Your Task: 1. Download the file a4.c from the site. 2. Find and fix the bugs in the program. What the program does: The program first reads an integer T, followed by T ingeters $n_1, n_2, \ldots, n_T$. For each i ∈ {1, 2, ..., T}, the program tests whether $n_i$ is divisible by any integer from 2 through $\sqrt{n_i}$. Constraints: ‧ $1 \le T \le 10^3$ ‧ $1 \le n_i \le 4294967295\ (= 2^{32}-1)$ for each i ∈ {1, 2, ..., T}. Input Format: ‧ The first line contains a positive integer T. ‧ Each of the following T lines contains a positive integer $n_i$. Output Format: ‧ The output contains T lines. The i-th line is either "$n_i$ is prime." or "$n_i$ is not prime.", depending on whether $n_i$ is prime. Each output line must follow the format above exactly. Do not include any extra spaces, including leading or trailing spaces. Sample Test Cases: Sample Input 1: ──────────────────────────────────────── 8 1 2 3 4 5 6 2147483647 4294967295 ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── 1 is not prime. 2 is prime. 3 is prime. 4 is not prime. 5 is prime. 6 is not prime. 2147483647 is prime. 4294967295 is not prime. ──────────────────────────────────────── A5. Distinct Sums (8 pts) You have two unusual dice. The first die has n faces labeled $a_1, a_2, \ldots, a_n$, and the second die has m faces labeled $b_1, b_2, \ldots, b_m$. You roll each die exactly once and add the two numbers that appear. Therefore, if the first die lands on face i and the second die lands on face j, the sum is $a_i + b_j$. Find the number of distinct sums that can possibly appear after rolling both dice once. Different pairs of faces may produce the same numerical sum. Such a sum is counted only once. Labels on the same die are also allowed to be equal. Your Task: 1. Download the file a5.c from the site. 2. Implement the code within the TODO section. Constraints: ‧ 1 ≦ n, m ≦ 500 ‧ $1 \le a_i, b_j \le 500$ Input Format: ‧ The first line contains two integers n and m, separated by a space. ‧ The second line contains n integers $a_1, a_2, \ldots, a_n$, separated by spaces. These are the labels on the first die. ‧ The third line contains m integers $b_1, b_2, \ldots, b_m$, separated by spaces. These are the labels on the second die. Output Format: ‧ Print one integer: the number of distinct possible sums. Sample Test Cases: Sample Input 1: ──────────────────────────────────────── 4 3 1 2 2 6 1 4 5 ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── 7 ──────────────────────────────────────── Sample Input 2: ──────────────────────────────────────── 2 4 500 500 1 2 499 500 ──────────────────────────────────────── Sample Output 2: ──────────────────────────────────────── 4 ──────────────────────────────────────── B1. Buying in Convenience Stores (10 pts) Yonsen is a clever but poor boy. He is currently studying at National Taiwan University (NTU), one of the best universities in Taiwan. To scrimp and save for the future, he rarely eats anywhere except at convenience stores on the NTU cam- pus, taking advantange of the 10% discount offered to students. Recently, Yonsen found the discount calculation riveting. Suppose the total price of the items he intends to purchase is n dollars. The discount amount is given by \[\operatorname{round}\left(\frac n{10}\right),\] where round(x) denotes the nearest integer to x (e.g., round(e) = round(π) = 3). If x is halfway between two integers, the integer farther from zero is chosen (e.g., round(±4.5) = ±5). With the 10% discount, he has to pay $n - \operatorname{round}\left(\frac n{10}\right)$ dollars. After a brief investigation, Yonsen learned that he cound sometimes save more by dividing all the items he intends to purchase into several groups and paying for them separately. Today, he decides to enjoy a bento of braised pork rice with a bottle of mineral water, a combination he absolutely adores. A bento of braised pork rice and a bottle of mineral water are priced at a and b dollars, respec- tively. He wonders whether buying them separately yields greater savings. Please write a program to formulate the necessary equations and calculate how much he has to pay when buying them separately and when buying them together. Note that the output format is strictly enforced in this problem. You must fol- low the Output Format exactly; otherwise, your submission will receive no points. If in doubt, copy and paste the Sample Output. Input Format: The input contains a line with two integers a and b, separated by a space. Output Format: The output contains two lines. ‧ The first line contains the equation for buying a bento of braised pork rice and a bottle of mineral water separately. The line has the format "(a-round(a /10)) + (b-round(b/10)) = $r_1$", where $r_1 := \left(a-\operatorname{round} \left(\frac a{10}\right)\right) + \left(b-\operatorname{round}\left(\frac b {10}\right)\right)$ denotes how much Yonsen has to pay in this case. ‧ The second line contains the equation for buying a bento of braised pork rice and a bottle of mineral water together. The line has the format "(a+b) - round((a+b)/10) = $r_2$", where $r_2 := (a+b) - \operatorname{round}\left( \frac{a+b}{10}\right)$ denotes how much Yonsen has to pay in this case. Each output line must follow the format above exactly. Do not include any extra spaces, including leading or trailing spaces. You may copy and paste the Sample Output to ensure that your output format is correct. Constraints: ‧ $1 \le a, b \le 10^9$ Sample Test Cases: Sample Input 1: ──────────────────────────────────────── 35 39 ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── (35-round(35/10)) + (39-round(39/10)) = 66 (35+39) - round((35+39)/10) = 67 ──────────────────────────────────────── Sample Input 2: ──────────────────────────────────────── 33 23 ──────────────────────────────────────── Sample Output 2: ──────────────────────────────────────── (33-round(33/10)) + (23-round(23/10)) = 51 (33+23) - round((33+23)/10) = 50 ──────────────────────────────────────── B2. ABC Street (10 pts) House numbers on ABC Street run from L to R. The resident at one of them had a remarkable year: a promotion, a lottery win, and a cat that finally came home. Asked to explain it, they pointed at their front door and said their house num- ber was abundant. Nobody on ABC Street had heard that word before. Within a month everyone had, and now everyone is checking their own house numbers to see if they are abundant too. Write a program that counts how many abundant house numbers are on the street. ──────────────────────────────────────── Proper Divisors The proper divisors of a number are all the positive divisors of that number, excluding the number itself. ──────────────────────────────────────── ──────────────────────────────────────── Abundant Numbers An abundant number is a number for which the sum of its proper divisors is grea- ter than the number itself. For example, 12 is abundant: its proper divisors are 1, 2, 3, 4 and 6, and 1 + 2 + 3 + 4 + 6 = 16, which is greater than 12. ──────────────────────────────────────── Hint: In A4 we showed that testing the divisors between 2 and $\sqrt n$ is sufficient to decide whether n is prime. The same observation gives you a faster way to sum the proper divisors of n here. Constraints: ‧ $1 \le L \le R \le 10^5$ ‧ In 60% of the test cases, $R \le 10^4$. Input Format: ‧ The first line contains two integers L and R, separated by a space. Output Format: ‧ Output a single integer representing the count of abundant numbers in the range [L, R]. Sample Test Cases: Sample Input 1: ──────────────────────────────────────── 1 20 ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── 3 ──────────────────────────────────────── Sample Input 2: ──────────────────────────────────────── 13 100 ──────────────────────────────────────── Sample Output 2: ──────────────────────────────────────── 21 ──────────────────────────────────────── Sample Input 3: ──────────────────────────────────────── 1 100000 ──────────────────────────────────────── Sample Output 3: ──────────────────────────────────────── 24795 ──────────────────────────────────────── B3. Who Took the Cake? (10 pts) Something has happened to the last slice of cake in the office fridge, and three colleagues were in the building at the time. Exactly one of them took it. Each of them has given a statement about the incident. Either accusing one (might accuse themselves!) or claiming anyone's innocence. A colleague is free to lie or tell the truth, including the one who took the cake. However, by secu- rity camera footage, the office manager knows that exactly k of them are telling the truth, but not which ones. The statements given can be represented as integers $s_1$, $s_2$, and $s_3$ for the three colleagues, where a positive number indicates that the colleague is accusing someone, and a negative number indicates that the colleague is claiming innocence. The absolute value of the number indicates which colleague they are referring to (1, 2, or 3). Write a program to work out who took the cake. Hint: Take sample input 1 as an example. $s_1 = 2$ means that the colleague 1 is accu- sing the colleague 2. $s_2 = -2$ means that the colleague 2 asserts that the colleague 2 is innocent. Finally, $s_3 = 1$ means that the colleague 3 is accu- sing the colleague 1. After some logical deduction, we can conclude that if two of them are telling the truth, colleague 1 is the one who took the cake. Constraints: ‧ $s_i \in \{-3, -2, -1, 1, 2, 3\}$ for each i ∈ {1, 2, 3}. ‧ 0 ≦ k ≦ 3 Input Format: ‧ Only one line of input containing four integers $s_1$, $s_2$, $s_3$, and k, separated by spaces. Output Format: ‧ If exactly one colleague can be determined to have taken the cake, output a single integer representing the colleague who took the cake (1, 2, or 3). ‧ If no colleague can be determined to have taken the cake, output "IMPOSSIBLE". ‧ If there are multiple colleagues who could have taken the cake, output "AMBIGUOUS". Sample Test Cases: Sample Input 1: ──────────────────────────────────────── 2 -2 1 2 ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── 1 ──────────────────────────────────────── Sample Input 2: ──────────────────────────────────────── 3 -1 2 1 ──────────────────────────────────────── Sample Output 2: ──────────────────────────────────────── IMPOSSIBLE ──────────────────────────────────────── Sample Input 3: ──────────────────────────────────────── 1 2 3 1 ──────────────────────────────────────── Sample Output 3: ──────────────────────────────────────── AMBIGUOUS ──────────────────────────────────────── B4. Light (10 pts) Yuki is playing with an n × m light panel. Each cell is either off or on. The panel has an update button that changes the states of all cells according to the following rule. Whenever Yuki presses the button, every cell looks at its four adjacent cells: the ones directly above, below, to the left, and to the right. Neighbors outside the panel are simply ignored. A cell will be on after the update if an odd num- ber of its adjacent cells are currently on; otherwise, it will be off. All cells are updated simultaneously. In other words, the new state of every cell is determined from the panel before the button is pressed. Write a program that prints the state of the panel after Yuki presses the button exactly k times. Constraints: ‧ 1 ≦ n, m, k ≦ 100 ‧ Every matrix entry is either 0 or 1. Input Format: ‧ The first line contains three integers n, m, and k, separated by spaces. ‧ Each of the next n lines contains a binary string of length m describing one row of the panel's initial state. The j-th character is 0 if the j-th cell in that row is off, and 1 if it is on. Output Format: ‧ Print n lines, each containing a binary string of length m with no spaces. These lines describe the state of the panel after exactly k button presses. Sample Test Cases: Sample Input 1: ──────────────────────────────────────── 3 4 1 0100 1101 0010 ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── 0111 1010 1000 ──────────────────────────────────────── Sample Input 2: ──────────────────────────────────────── 1 5 2 10110 ──────────────────────────────────────── Sample Output 2: ──────────────────────────────────────── 01101 ──────────────────────────────────────── B5. Almost Palindromic Numbers (10 pts) A palindrome is a sequence of symbols that reads the same backwards as forwards. In English, radar, racecar, and the famous sentence "Madam, I'm Adam" are palin- dromes if punctuation is neglected. A palindromic number is a number that re- mains the same when its digits are reversed. For example, 1, 11, and 121 are pa- lindromic numbers, while 10, 765, and 2077 are not. If a number n can be made palindromic using no more than k digit substitutions, we say that n is an almost palindromic number. For example, when k = 1, the num- bers 10 and 765 are almost palindromic (10 → 11 and 765 → 565), while 2077 is not almost palindromic. Note that a substitution may not introduce a leading zero. You are given three integers k, a, and b. Find the number of integers between a and b (inclusive) that are almost palindromic. Input Format: ‧ The first line contains a nonnegative integer k. ‧ The second line contains two positive integers a and b, separated by a space. Output Format: ‧ Output a single integer representing the number of almost palindromic numbers in [a, b] with parameter k. Constraints: ‧ 0 ≦ k ≦ 8. ‧ $1 \le a \le b \le 10^{18}$. ‧ $b-a \le 10^6$. Sample Test Cases: Sample Input 1: ──────────────────────────────────────── 0 1 1000000 ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── 1998 ──────────────────────────────────────── Sample Input 2: ──────────────────────────────────────── 5 999999999999000000 999999999999999999 ──────────────────────────────────────── Sample Output 2: ──────────────────────────────────────── 468559 ──────────────────────────────────────── Hint: For Sample Input 1, since k = 0, almost palindromic numbers are exactly palin- dromic numbers. Observe that ‧ the number of palindromic numbers with lengths 1, 3, or 5 is 999 (e.g. $10 \mapsto 101$, $765 \mapsto 76567$), and ‧ the number of palindromic numbers with lengths 2, 4, or 6 is also 999 (e.g. $10 \mapsto 1001$, $765 \mapsto 765567$). The answer is therefore 999 + 999 = 1998. For Sample Input 2, since the answer for k = 6 is 1000000 (simply replace the last 6 digits with 999999 to obtain a number consisting of eighteen 9's), the answer for k = 5 is \[1000000 - 9^6\ (\text{only }0-8\text{ can be placed in the last 6 digits}) = 468559.\] C1. Big Tic-Tac-Toe (5 pts) In this problem, Alice and Bob are playing Big Tic-Tac-Toe. Alice uses X, Bob uses O, and Alice always moves first. The game is played on a 9 × 9 board. The board is divided into nine 3 × 3 small boards. Rows and columns of the large board are numbered from 1 to 9. For example, rows 1-3 and columns 4-6 form the top-middle small board. https://i.imgur.com/rGkTUBc.png \begin{tikzpicture} \draw[very thin] (0, 0) grid (9, 9); \draw[thick] (0, 3) -- (9, 3); \draw[thick] (0, 6) -- (9, 6); \draw[thick] (3, 0) -- (3, 9); \draw[thick] (6, 0) -- (6, 9); \foreach \i in {1, ..., 9}{ \foreach \j in {1, ..., 9}{ \draw[lightgray] ({\j-.5}, {9.5-\i}) node{\i,\j}; } } \end{tikzpicture} ──────────────────────────────────────── Game Rules ‧ On a turn, the current player places their mark in one empty cell of any small board that has not yet been won. ‧ A player wins a small board immediately after placing three of their marks in a horizontal, vertical, or diagonal line inside that small board. A won small board is closed, so no more marks may be placed in it. ‧ If all nine cells of a small board are occupied without a winner, that small board is a draw and belongs to neither player. ‧ Treating each small board as one cell of a larger 3 × 3 board, a player forms a large line by winning three small boards in a horizontal, vertical, or diagonal line. The first player to form a large line wins. ‧ The players alternate turns: move 1 is made by X, move 2 by O, move 3 by X, and so on. All N recorded moves are played, even if a player forms a large line before the final move. It is therefore possible for both players to have a large line on the final board; the player whose line was completed earlier is still the win- ner. There is no forced-board rule in this problem. In other words, a move does not restrict which small board the next player must play in. ──────────────────────────────────────── You are given several independent games, each represented by a legal sequence of moves. Unfortunately, the program written to determine their results contains several bugs. Your task is to find and fix them. Your Task: 1. Download c1.c from the problem website. 2. Debug the program so that it correctly simulates every move and prints the result of every game. You may modify any part of c1.c or replace its implementation entirely, but the input and output formats must remain unchanged. What the program does: The provided program uses the following data structures and helper functions: \begin{tabular}{|l|l|}\hline \textbf{Name} & \textbf{Purpose}\\\hline \texttt{board} & A global two-dimensional array that stores all marks on the 9 × 9 board.\\\hline \texttt{small\_winner} & Stores \texttt X or \texttt O for a won small board, or \texttt{'.'} if that small board has not been won.\\\hline \texttt{current\_player} & Stores the mark of the player whose turn it is. \\\hline \texttt{initialize\_game()} & Clears all game state before the program pro- cesses the next game.\\\hline \texttt{has\_small\_line()} & Checks the row, column, and diagonals contai- ning the most recently played cell.\\\hline \texttt{has\_large\_line()} & Checks the lines containing the most recently won small board.\\\hline \texttt{apply\_move()} & Places one mark, updates the corresponding small board, and then checks the large board.\\\hline \texttt{print\_board()} & Prints the final 9 × 9 board after all moves of one game have been played.\\\hline \end{tabular} The program compiles, but some parts of the implementation do not follow the rules above correctly. Constraints: ‧ 1 ≦ T ≦ 100, where T is the number of games. ‧ $0 \le N_i, \le 81$, where $N_i$ is the number of recorded moves in game i. ‧ $1 \le r_i, c_i \le 9$ for every move. ‧ Every move is legal: its cell is empty, its small board has not yet been won, and the two players move alternately starting with X. Input Format: ‧ The first line contains one integer T, the number of independent games. ‧ For each game: ﹥ The first line contains one integer N, the number of moves in this game. ﹥ Each of the next N lines contains two integers $r_i$ and $c_i$, the row and column of the i-th move on the large board. Output Format: For each game, first print the final board as nine lines of nine characters. Each character is X, O, or .; no spaces are printed between cells. Immediately after the nine board lines, print exactly one result line: ‧ X wins if Alice (X) formed the first large line; ‧ O wins if Bob (O) formed the first large line; ‧ Draw if neither player forms a large line. Sample Test Cases: Sample Input 1: ──────────────────────────────────────── 2 17 1 1 4 1 1 2 4 4 1 3 4 7 1 4 5 1 1 5 5 4 1 6 5 7 1 7 6 2 1 8 6 5 1 9 8 1 1 5 5 1 2 2 1 8 8 5 6 9 1 4 4 ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── XXXXXXXXX ......... ......... O..O..O.. O..O..O.. .O..O.... ......... ......... ......... X wins XX....... O........ ......... ...O..... ....OO... ......... ......... .......X. X........ Draw ──────────────────────────────────────── C2. Laser Mirror: Realignment (5 pts) Deep inside the lab, Hyper stumbled upon a laser maze built out of mirrors, with a target bolted to the far wall. The maze is an H × W grid of cells, rows numbered 1 to H from top to bottom and columns numbered 1 to W from left to right. A cell holds one of the following: ‧ .: empty space, which lets a beam pass straight through; ‧ / or \: a mirror; ‧ X: the target, which absorbs the beam. There is exactly one. A beam enters through one of the four sides and travels one cell at a time, tur- ning whenever it enters a cell holding a mirror: ──────────────────────────────────────── Mirror Rules https://i.imgur.com/l1Vocl2.png \begin{tabular}{*{4}{|m{2.2cm}}|}\hline \multicolumn{2}{|c|}{Mirror \texttt/} & \multicolumn{2}{c|}{Mirror \texttt \textbackslash}\\\hline \makecell{ right $\to$ up\\ \begin{tikzpicture} \path (-1, -1) -- (1, 1); \draw[gray] (-.5, -.5) rectangle (.5, .5); \draw[very thick] (-.45, -.45) -- (.45, .45); \draw[thick, blue, -stealth] (-.9, 0) -- (0, 0) -- (0, .9); \end{tikzpicture} }&\makecell{ left $\to$ down\\ \begin{tikzpicture} \path (-1, -1) -- (1, 1); \draw[gray] (-.5, -.5) rectangle (.5, .5); \draw[very thick] (-.45, -.45) -- (.45, .45); \draw[thick, blue, -stealth] (.9, 0) -- (0, 0) -- (0, -.9); \end{tikzpicture} }&\makecell{ right $\to$ down\\ \begin{tikzpicture} \path (-1, -1) -- (1, 1); \draw[gray] (-.5, -.5) rectangle (.5, .5); \draw[very thick] (-.45, .45) -- (.45, -.45); \draw[thick, blue, -stealth] (-.9, 0) -- (0, 0) -- (0, -.9); \end{tikzpicture} }&\makecell{ left $\to$ up\\ \begin{tikzpicture} \path (-1, -1) -- (1, 1); \draw[gray] (-.5, -.5) rectangle (.5, .5); \draw[very thick] (-.45, .45) -- (.45, -.45); \draw[thick, blue, -stealth] (.9, 0) -- (0, 0) -- (0, .9); \end{tikzpicture} }\\\hline \makecell{ up $\to$ right\\ \begin{tikzpicture} \path (-1, -1) -- (1, 1); \draw[gray] (-.5, -.5) rectangle (.5, .5); \draw[very thick] (-.45, -.45) -- (.45, .45); \draw[thick, blue, -stealth] (0, -.9) -- (0, 0) -- (.9, 0); \end{tikzpicture} }&\makecell{ down $\to$ left\\ \begin{tikzpicture} \path (-1, -1) -- (1, 1); \draw[gray] (-.5, -.5) rectangle (.5, .5); \draw[very thick] (-.45, -.45) -- (.45, .45); \draw[thick, blue, -stealth] (0, .9) -- (0, 0) -- (-.9, 0); \end{tikzpicture} }&\makecell{ down $\to$ right\\ \begin{tikzpicture} \path (-1, -1) -- (1, 1); \draw[gray] (-.5, -.5) rectangle (.5, .5); \draw[very thick] (-.45, .45) -- (.45, -.45); \draw[thick, blue, -stealth] (0, .9) -- (0, 0) -- (.9, 0); \end{tikzpicture} }&\makecell{ up $\to$ left\\ \begin{tikzpicture} \path (-1, -1) -- (1, 1); \draw[gray] (-.5, -.5) rectangle (.5, .5); \draw[very thick] (-.45, .45) -- (.45, -.45); \draw[thick, blue, -stealth] (0, -.9) -- (0, 0) -- (-.9, 0); \end{tikzpicture} }\\\hline \end{tabular} ──────────────────────────────────────── The beam stops as soon as it enters the target's cell — that counts as a hit. If it leaves the grid instead, it has missed. Exactly k of the mirrors sit on swivel mounts; every other mirror is bolted down. One at a time, you may walk up to a mounted mirror and turn it: / becomes \, and \ becomes /. Each of those is one turn. Turning the mounted mirrors changes where the beam goes, so with the right sequence of turns you can steer it into the target. You must finish all turns before firing the beam; mirrors cannot be turned while the beam is travelling. The mounts are stiff, so Hyper would rather not turn them more times than neces- sary. ──────────────────────────────────────── Play it first Download laser (laser.exe on Windows) from Attachments, then run ./laser 4.in in a terminal (.\laser.exe 4.in on Windows). The controls are shown in the program. Turning the mirrors and watching the beam find the target is surprisingly rela- xing :) ──────────────────────────────────────── Your Task: Write a complete C program that reads the maze, works out the fewest turns nee- ded to make the beam hit the target, and prints that number together with the mirrors to turn. ──────────────────────────────────────── Reference Code The solution to Sample Exam C2 (Laser Mirror) is provided as sample_c2_solution .c in Attachments. You may copy and modify this code for your submission. Note that it solves the sample problem; you will need to adapt it to this problem's input format and requirements. ──────────────────────────────────────── Input Format: ‧ The first line contains two integers H and W, the height and the width of the maze. ‧ Each of the next H lines contains W characters, describing one row of the maze from top to bottom. ‧ The next line contains one integer k, the number of mirrors on swivel mounts. ‧ Each of the next k lines contains two integers r and c, the row and the co- lumn of one mounted mirror. That cell of the maze always holds / or \, and no two of the k lines name the same cell. ‧ The last line contains a character S and an integer K, describing where the beam enters: \begin{tabular}{*{4}{|l}|}\hline $S$ & enters through & at & travelling\\\hline \texttt L & the left side & row $K$ & right\\\hline \texttt R & the right side & row $K$ & left\\\hline \texttt U & the top side & column $K$ & down\\\hline \texttt D & the bottom side & column $K$ & up\\\hline \end{tabular} Output Format: ‧ The first line should contain one integer, the fewest turns needed. ‧ Each of the next lines should name one mirror you turn, giving its row and its column separated by a space. Print exactly as many of these lines as the first line says. ‧ The turns may be listed in any order, and when the answer is 0 nothing fol- lows the first line. ‧ Several sets of turns may be the fewest; any one of them is accepted. Constraints: ‧ 1 ≦ H, W ≦ 50 ‧ 1 ≦ k ≦ 10 ‧ 1 ≦ r ≦ H and 1 ≦ c ≦ W for each of the k mounted mirrors. ‧ Every cell of the maze is one of ., /, \, and X, and exactly one cell is X. ‧ 1 ≦ K ≦ H when S is L or R; 1 ≦ K ≦ W when S is U or D. ‧ At least one setting of the mounted mirrors makes the beam hit the target. Sample Test Cases: Sample Input 1: ──────────────────────────────────────── 4 5 ....\ ../.. ..... ..\.X 2 2 3 1 5 L 2 ──────────────────────────────────────── Sample Output 1: ──────────────────────────────────────── 1 2 3 ──────────────────────────────────────── Sample Input 2: ──────────────────────────────────────── 4 5 ....\ ..\.. ..... ..\.X 2 2 3 1 5 L 2 ──────────────────────────────────────── Sample Output 2: ──────────────────────────────────────── 0 ──────────────────────────────────────── Sample Input 3: ──────────────────────────────────────── 9 10 ..\...\... ...\.\/../ ../../.../ /......./. ./..\...X. .\..\././. /..../\\.. ......\\.. \\/....... 3 2 10 7 1 4 9 D 5 ──────────────────────────────────────── Sample Output 3: ──────────────────────────────────────── 3 2 10 7 1 4 9 ──────────────────────────────────────── Sample Input 4: ──────────────────────────────────────── 24 24 /....................... .\...................... .....\....\....../...... ...\.......\............ ..\..................... ....//..............\... ....../................\ ...................\.\.. .......\./......\...\... ...\......../.../....... ....\............\...... ../...\............../\. ........\...../......... ./\..................... ../................./\.. ........................ ........../............. ........../....../...... ............./....../... ........\.......\....... ..../.......\........... ..............\......... ...\........././.......X ...................../.. 5 10 13 10 4 12 7 15 22 12 22 R 21 ──────────────────────────────────────── Sample Output 4: ──────────────────────────────────────── 4 10 13 10 4 15 22 12 22 ──────────────────────────────────────── --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.24.29 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1791317644.A.2F8.html ※ 編輯: xavier13540 (36.230.47.184 臺灣), 10/08/2026 14:15:33