课程名称︰基础程式设计(C++)
课程性质︰AI学程联盟选修
课程教师︰温宏斌
考试日期（年月日）︰2025/10/20
考试时限（分钟）：180
试题 :
Instructions:
● You may pick an arbitrary number of problems to solve with a total score of
up to 100%.
● Please strictly follow the input and output specifications described in each
problem. Any deviation that causes test case errors will result in point de-
ductions, for which the student is fully responsible.
● Name your files by problem number: Problem 1 → p1.cpp, ...
● Zip all program files into one archive named with your student ID (e.g.,
411511004.zip or 411511004.7z). Submit through NTU Cool. If the system is
slow, other methods will be announced.
● You have a 10-minute grace period (until 12:10 PM) to submit.
● Submissions after 12:10 PM will not be accepted.
● You are allowed to open any notes or books. However, you are not allowed to
copy others' code AND browse on the internet. Otherwise, you'll get 0% in
this examination and be punished by the school regulations.
● Carefully read the statements and requirements of each problem.
Problem 01 (10%)
Sum of digits. Calculate the sum of every digit of a positive integer.
4583 → 4 + 5 + 8 + 3 = 20
Input Format
$n$
其中 $n$ 为一不超过 $10^9$ 的正整数。
Output Format
$s$
其中 $s$ 为 $n$ 的各位数字和。
Sample Input 1
4813
Sample Output 1
16
Sample Input 2
12345
Sample Output 2
15
Sample Input 3
7543824
Sample Output 3
33
Problem 02 (10%)
Given two points of two rectangles, please calculate the overlapping area. Input
format: The first four numbers are the x, y of the bottom left and top right
points of the same rectangle. The last four numbers are the x, y of the bottom
left and top right points of the other rectangle.
The area will always be greater than 0.
Input Format
$x_1$ $y_1$ $x_2$ $y_2$ $x_3$ $y_3$ $x_4$ $y_4$
其中
‧ 对于所有的 $i \in \{1, 2, 3, 4\}$，均有 $x_i, y_i$ 为两整数且 $-100 \le x_i,
y_i \le 100$。
‧ $x_1 < x_2$ 且 $y_1 < y_2$。
‧ $x_3 < x_4$ 且 $y_3 < y_4$。
‧ 四顶点为 $(x_1, y_1), (x_1, y_2), (x_2, y_2), (x_2, y_1)$ 的长方形与四顶点为
$(x_3, y_3), (x_3, y_4), (x_4, y_4), (x_4, y_3)$ 的长方形的交集面积必定大于
0。
Output Format
$a$
其中 $a$ 为两长方形的交集面积。
Sample Input 1
-1 3 7 9 5 1 10 8
Sample Output 1
10
Sample Input 2
1 3 8 9 6 7 9 10
Sample Output 2
4
Sample Input 3
3 -1 7 9 -1 2 5 11
Sample Output 3
14
Problem 03 (10%)
Create a C++ program that calculates the least common multiple (LCM) of two in-
tegers. The inputs are two integers a and b, and a function named find_LCM will
return their LCM.
(The least common multiple of two positive integers is the smallest positive in-
teger that is divisible by both numbers.)
Hint. 最小公倍数
Input:
‧ Two integer numbers (a & b) separated by a space
‧ Both a and b are integers, and at least one of them is nonzero. (That is, you
only need to handle the case where on the the numbers is 0.)
Output:
‧ The least common multiple (LCM) of a and b. The result of this problem will
not exceed the range of an integer.
Input Format
$a$ $b$
其中 $a$ 与 $b$ 均为不超过 1000 的非负整数，且 $a\ne0$ 或 $b\ne0$。
Output Format
$m$
其中 $m$ 为 $a$ 与 $b$ 的最小公倍数，即
‧ 若 $a\ne0$ 且 $b\ne0$，则 $m$ 为最小且同时能被 $a$ 与 $b$ 整除的正整数；
‧ 若 $a=0$ 或 $b=0$，则 $m=0$。
Sample Input 1
10 12
Sample Output 1
60
Sample Input 2
5 7
Sample Output 2
35
Sample Input 3
0 30
Sample Output 3
0
Problem 04 (10%)
Create a program that converts an amount in New Taiwan Dollars (NTD) into U.S.
Dollars (USD) and breaks it down into denominations. The exchange rate is 1 USD
= 30 NTD.
Your program should first convert the input NTD amount into USD (using floating-
point division), then calculate:
‧ $a$: number of 100-dollar bills
‧ $b$: number of 10-dollar bills
‧ $c$: number of 1-dollar bills
‧ $d$: number of 10-cent coins
‧ $e$: remaining NTD after exchange
◆ Exchange rule (uniqueness requirement):
Always use the largest denominations first to exchange as much as possible. For-
mally, decompose the USD amount (in cents) greedily in this order:
■ $100 bills →
■ $10 bills →
■ $1 bills →
■ 10-cent coins.
Finally, output the result in the following format:
a = ...
b = ...
c = ...
d = ...
e = ...
You can follow this flow:
n = 5000
→ The amount in USD (U) = n/30 = 166.66666666......
→ a = integer part of U/100 = 1
→ b = integer part of (U-a*100)/10 = 6
→ c = integer part of (U-a*100-b*10)/1 = 6
→ d = integer part of (U-a*100-b*10-c*1)*10 = 6
→ e = round of (U-a*100-b*10-c*1-d*0.1)*30 = 2
Input:
◆ A single integer $n$ representing the amount in New Taiwan Dollars (NTD).
◆ n is a non-negative integer. Test cases may include values that are not divi-
sible by 30.
Output:
◆ The number of each denomination (a, b, c, d) and the remaining NTD (e).
Input Format
$n$
其中 $n$ 为一不超过 $10^9$ 的非负整数。
Output Format
a = $a$
b = $b$
c = $c$
d = $d$
e = $e$
其中 $a, b, c, d, e$ 均为非负整数，代表 $n$ 新台币最多能换出 $a$ 张 100 美元钞票
，接着再换出 $b$ 张 10 美元钞票，接着再换出 $c$ 张 1 美元钞票，接着再换出 $d$ 枚
10 美分硬币，最后剩下 $e$ 新台币。
Sample Input 1
5000
Sample Output 1
a = 1
b = 6
c = 6
d = 6
e = 2
Sample Input 2
90
Sample Output 2
a = 0
b = 0
c = 3
d = 0
e = 0
Sample Input 3
95
Sample Output 3
a = 0
b = 0
c = 3
d = 1
e = 2
Problem 05 (10%)
Write a simple time-conversion program.
Given a conversion type and time values, your program converts between total se-
conds and hours—minutes—seconds (H:M:S) formats.
There are two conversion types:
‧ Type 1: Convert from total seconds to H:M:S.
‧ Type 2: Convert from H:M:S to total seconds.
The input format depends on the conversion type.
Type 1 — Input should contain two integers.
‧ The first integer is 1, which represents type 1.
‧ The second integer represents the total number of seconds.
Type 2 — Input should contain four integers.
‧ The first integer is 2, which represents type 2.
‧ The next three integers represent hours, minutes, and seconds, respectively.
Output Format
Type 1:
Output the time in the format HH:MM:SS (with leading zeros, e.g., 01:01:01, 00:
59:30).
Type 2:
Output a single integer representing the total number of seconds.
Notes:
‧ Assume all inputs are valid and non-negative
‧ Hours are not required to wrap around (Hours can be more than 24)
‧ The input fits in 32-bit signed integers
‧ Output for Type 1 must include leading zeros
Input Format
$t$ $a_1$ $a_2$ $\ldots$ $a_{l_t}$
其中 $t$ 为 1 或 2 且 $(l_1, l_2) = (1, 3)$。
当 $t = 1$ 时，有
‧ $n := a_1$ 为小于 360000 的非负整数。
当 $t = 2$ 时，有
‧ $h := a_1$ 为小于 100 的非负整数，
‧ $m := a_2$ 为小于 60 的非负整数，且
‧ $s := a_3$ 为小于 60 的非负整数。
Output Format
当 $t = 1$ 时，请输出
$f_\text{02d}(h)$:$f_\text{02d}(m)$:$f_\text{02d}(s)$
其中
‧ $f_\text{02d}$ 为不足 2 位时在前面补 0 至 2 位的整数 formatter（e.g.
$f_\text{02d}(12)$ 为 12 而 $f_\text{02d}(0)$ 为 00），
‧ $h, m, s$ 均为非负整数，
‧ $m$ 与 $s$ 均小于 60，
代表 $n$ 秒等于 $h$ 时 $m$ 分 $s$ 秒。
当 $t = 2$ 时，请输出
$n$
代表 $h$ 时 $m$ 分 $s$ 秒等于 $n$ 秒。
Sample Input 1
1 3661
Sample Output 1
01:01:01
Sample Input 2
2 1 1 1
Sample Output 2
3661
Sample Input 3
1 888
Sample Output 3
00:14:48
Problem 06 (10%)
The number pattern problem prints a square pattern of concentric layers of num-
bers. The outermost layer starts with the number n, and each inner layer de-
creases the number by 1 until reaching the center, which is 1.
Input Format
A single integer n (1 ≦ n ≦ 9).
Output Format
Print the concentric square pattern of numbers. The output should be a square of
size (2n-1) × (2n-1).
Input Format
$n$
其中 $n$ 为不超过 9 的正整数。
Output Format
$
a_{1, 1}a_{1, 2}\ldots a_{1, 2n-1}\\
a_{2, 1}a_{2, 2}\ldots a_{2, 2n-1}\\
\vdots\\
a_{2n-1, 1}a_{2n-1, 2}\ldots a_{2n-1, 2n-1}
$
其中最外圈的 $a_{i, j}$ 皆为 $n$；次外圈的 $a_{i, j}$ 皆为 $n-1$；…；最内圈（即
中央）的 $a_{i, j}$ 皆为 1。
Sample Input 1
2
Sample Output 1
222
212
222
Sample Input 2
3
Sample Output 2
33333
32223
32123
32223
33333
Sample Input 3
5
Sample Output 3
555555555
544444445
543333345
543222345
543212345
543222345
543333345
544444445
555555555
Problem 7 (10%)
You're building a delivery fee calculator. The final fee should be calculated
based on:
(1) the price of the meal.
(2) current weather conditions (raining or not).
(3) the customer's VIP status.
All fees are integers. Apply the steps in this order:
1. Base fee by meal price
If meal_price < 200 → base fee = 100
If 200 ≦ meal_price < 500 → base fee = 50
If meal_price ≧ 500 → base fee = 20
2. Rain surcharge
If is_rain = true → add 20
If is_rain = false → add 0
3. VIP discount
If is_vip = true → apply 50% off to the current subtotal (integer division)
If is_vip = false → no discount
4. Lower bound
Ensure final fee ≧ 15
Input Format
Three lines:
Line 1: meal_price (integer)
Line 2: is_rain (boolean: true or false, lowercase)
Line 3: is_vip (boolean: true or false, lowercase)
Output Format
One line: the final delivery fee (integer).
Constraints
0 < meal_price < 100000
is_rain ∈ {0, 1}
is_vip ∈ {0, 1}
Input Format
$p$
$r$
$v$
其中
‧ $p$ 为一小于 $10^5$ 的正整数，代表餐点价格；
‧ $r$ 为 0 或 1，代表是否下雨；
‧ $v$ 为 0 或 1，代表是否为 VIP。
Output Format
$f$
其中 $f$ 为一整数，代表外送费。
Sample Input 1
180
1
0
Sample Output 1
120
Sample Input 2
520
1
1
Sample Output 2
20
Sample Input 3
250
0
0
Sample Output 3
50
Problem 08 (10%)
Read an integer seed and an integer R (roll count). Initialize the C RNG with
std::srand(seed) and roll a fair six-sided die exactly R times. Report:
1. the counts of each face 1..6,
2. the sample mean,
3. the unbiased sample variance.
Input Format
Two lines:
Line 1: seed (integer)
Line 2: R (number of rolls, integer)
Output Format
COUNTS: c1 c2 c3 c4 c5 c6
Counts of faces 1..6 over the R rools (integers).
MEAN ($\bar x$): m.mm
Sample mean of the R rolls, 2 decimals (小数点后 2 位), standard rounding.
\[\bar x = \frac1R\sum_{i=1}^Rx_i\]
MAX COUNT FACE:
Print the most frequent face.
MIN COUNT FACE:
Print the least frequent face.
For the test cases, seeds are chosen so that no two faces occur the same number
of times over R rolls.
Constraints
‧ 0 < seed < 1,000,000
‧ 1 ≦ R ≦ 1,000,000
Hint:
‧ std::srand(seed)
‧ std::rand()
‧ std::setprecision(x)
‧ std::fixed (remember to #include <iomanip>)
Input Format
$s$
$r$
其中 $s$ 为乱数种子，$r$ 为乱数生成次数，满足
‧ $s$ 为一小于 $10^6$ 的正整数，
‧ $r$ 为一不超过 $10^6$ 的正整数，且
‧ 呼叫 std::srand($s$) 后，若令执行 $r$ 次 rand() 除以 6 余 $k$ 的次数为 $a_k$
，则 $a_0, a_1, \ldots, a_5$ 两两相异。
Output Format
COUNT: $c_1$ $c_2$ $c_3$ $c_4$ $c_5$ $c_6$
MEAN: $f_\text{.2f}(\bar x)$
MAX COUNT FACE: $x_\max$
MIN COUNT FACE: $x_\min$
其中
‧ 对于所有的 $i \in \{1, 2, \ldots, 6\}$，均有骰子掷出 $i$ 点的次数为 $c_i$；
‧ $f_\text{.2f}$ 为一四舍五入至小数以下 2 位的浮点数 formatter（e.g. $f_\text{
.2f}(4)$ 为 4.00 而 $f_\text{.2f}(3.625)$ 为 3.63）；
‧ $\bar x$ 为掷出点数的平均值；
‧ $x_\max$ 为掷出次数最多的点数；
‧ $x_\min$ 为掷出次数最少的点数。
Sample Input 1
1234
70
Sample Output 1
COUNTS: 12 11 16 14 10 7
MEAN: 3.29
MAX COUNT FACE: 3
MIN COUNT FACE: 6
Sample Input 2
228
88000
Sample Output 2
COUNTS: 14691 14812 14820 14480 14565 14632
MEAN: 3.49
MAX COUNT FACE: 3
MIN COUNT FACE: 4
Sample Input 3
7777
7777
Sample Output 3
COUNTS: 1330 1253 1265 1322 1233 1374
MEAN: 3.51
MAX COUNT FACE: 6
MIN COUNT FACE: 5
Problem 09 (10%)
You have been hired by the CIA Hotel to write a simple billing program.
Your task is to calculate the total amount for each guest and print a formatted
table.
Two monetary values (Price, Total Price) must be rounded and displayed with exa-
ctly two digits after the decimal point.
Input:
‧ The input consists of 3 lines in the following format:
<name_1 (string)> <price_per_day_1 (double)> <days_1 (int)>
<name_2 (string)> <price_per_day_2 (double)> <days_2 (int)>
<name_3 (string)> <price_per_day_3 (double)> <days_3 (int)>
Output Format:
‧ Print a table with the following four columns, each with a width of 10 char-
acters:
。 Name — left aligned
。 Price — right aligned, two decimal places
。 Days — right aligned
。 Total — right aligned, two decimal places
(Total = <price_per_day (double)> * <days (int)>)
‧ The first line should display the column headers.
‧ The next three lines should display the data for each guest.
Constraints -
‧ length(name) < 7 (有误；详见之后的 Input Format 节)
‧ Each name consists of only one word
‧ 0 < all the input values < 100000 (有误；详见之后的 Input Format 节)
‧ 0 < all the calculation results < 100000
Hint:
‧ setprecision() automatically performs rounding, so you don't need to round
the value manually.
Input Format
$s_1$ $p_1$ $d_1$
$s_2$ $p_2$ $d_2$
$s_3$ $p_3$ $d_3$
其中对于任意 $i \in \{1, 2, 3\}$，有
‧ $s_i$ 为一以大小写英文字母组成且长度不超过 7 的非空字串，
‧ $p_i \in (0, 10^5)$ 为一双精度浮点数，
‧ $d_i$ 为一不超过 $10^5$ 的正整数，且
‧ $d_ip_i < 10^5$。
Output Format
$
f_\text{-10s}(\texttt{Name})f_\text{10s}(\texttt{Price})f_\text{10s}(\texttt{
Days})f_\text{10s}(\texttt{Total})\\
f_\text{-10s}(s_1)f_\text{10.2f}(p_1)f_\text{10d}(d_1)f_\text{10.2f}(t_1)\\
f_\text{-10s}(s_2)f_\text{10.2f}(p_2)f_\text{10d}(d_2)f_\text{10.2f}(t_2)\\
f_\text{-10s}(s_3)f_\text{10.2f}(p_3)f_\text{10d}(d_3)f_\text{10.2f}(t_3)
$
其中
‧ $f_\text{-10s}$ 为宽度为 10 且靠左对齐的字串 formatter（e.g. 若将空格换成底线
，$f_\text{-10s}(\texttt{hello})$ 为 "hello_____"（不含引号））；
‧ $f_\text{10s}$ 为宽度为 10 且靠右对齐的字串 formatter（e.g. 若将空格换成底线
，$f_\text{10s}(\texttt{hello})$ 为 "_____hello"（不含引号））；
‧ $f_\text{10.2f}$ 为宽度为 10、靠右对齐、四舍五入至小数以下 2 位的浮点数 form-
atter（e.g. 若将空格换成底线，$f_\text{10.2f}(12.345)$ 为 "_____12.35"（不含
引号））；
‧ $f_\text{10d}$ 为宽度为 10 且靠右对齐的整数 formatter（e.g. 若将空格换成底线
，$f_\test{10d}(12345)$ 为 "_____12345" （不含引号））；
‧ 对于任意的 $i \in \{1, 2, 3\}$，$t_i$ 为顾客 $i$ 的住宿费用。
Sample Input 1
Amy 1234.5 2
Bob 999.99 5
Clara 2500 1
Sample Output 1
Name Price Days Total
Amy 1234.50 2 2469.00
Bob 999.99 5 4999.95
Clara 2500.00 1 2500.00
Sample Input 2
Zoe 88.8 10
John 10000 3
Mia 123.456 7
Sample Output 2
Name Price Days Total
Zoe 88.80 10 888.00
John 10000.00 3 30000.00
Mia 123.46 7 864.19
Sample Input 3
AoA 0.00001 100000
NoN 1.111 77777
QoQ 3.333333 3
Sample Output 3
Name Price Days Total
AoA 0.00 100000 1.00
NoN 1.11 77777 86410.25
QoQ 3.33 3 10.00
Problem 10 (10%)
The kingdom is holding a small talent show. Each performer has a score g and a
name (which may contain spaces). The king has a special number k, and he want to
find the performer with the highest score that is divisible by k. Write a pro-
gram to help the king find this performer.
Input:
‧ The input contains several lines in the following format:
。 Line 1: an integer k
。 Starting from line 2, the input comes in pairs of lines:
■ First line of each pair: the score g (int)
■ Second line of each pair: name (string)
。 When g = 0, stop reading.
Output:
‧ Print the name of the performer with the largest score divisible by k.
‧ If no score is divisible by k, print: "None".
Hint:
‧ You can use the following way to assign a string value to another one:
std::string a, b;
std::cin >> a;
b = a; // This copies the entire string stored in a to b
Constraints -
◆ 0 < g, k < 10000, the last g = 0,
◆ all g values are unique
◆ Number of input lines < 50
◆ length (each name) < 50
Attention:
If the sample input lines contains trailing whitespace (行尾多余空格) on your
end, please remove it manually to avoid errors between cin and getline().
Input Format
$k$
$g_1$
$s_1$
$g_2$
$s_2$
$\vdots$
$g_n$
$s_n$
$g_{n+1}$
其中
‧ $k$ 为一小于 10000 的正整数；
‧ 对于任意的 $i \in \{1, 2, \ldots, n\}$，均有
。 $g_i$ 为一小于 10000 的正整数，且
。 $s_i$ 为一以英数字、底线与空白组成且长度小于 50 的非空字串；
‧ $g_{n+1} = 0$，且 $g_1, g_2, \ldots, g_{n+1}$ 间两两相异；
‧ 输入的行数（即 $2n+2$）小于 50。
Output Format
若有参赛者能让国王满意，请输出
$s_{i^*}$
其中 $i^*$ 满足
‧ $g_{i^*}$ 能被 $k$ 整除，且
‧ 在所有能被 $k$ 整除的 $g_i$ 中，$g_{i^*}$ 是最大的。
若没有任何参赛者能让国王满意，请输出
None
Sample Input 1
5
10
Alice Smith
7
Bob
15
Charlie Brown
0
Sample Output 1
Charlie Brown
Sample Input 2
5
6666
Tan Gan Dee
7777
ALA Hsieh
0
Sample Output 2
None
Sample Input 3
1
99
Naval_officer 1
88
Naval_officer 2
77
Naval_officer 3
66
Naval_officer 4
55
Naval_officer 5
999
Naval_officer 6
4
Naval_officer 7
2
Naval_officer 8
789
Naval_officer 9
0
Sample Output 3
Naval_officer 6