| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1000 | The A+B Problem |
|
| 10451 | EEDS 樂透對獎程式 |
|
| 10736 | EEDS (Fall 2015) 對帳程式 |
|
| 10783 | EEDS Polynomial Calculator |
|
| 10835 | EEDS Brackets and quotation marks |
|
| 10836 | EEDS2 Chinese checker's random walk |
|
| 10837 | EEDS Inverse KMP's failure function |
|
| 10838 | EEDS Spaceship calculator |
|
| 10877 | EEDS D-ary min heap |
|
Description
We want to write a program to check whether we win the lottery or not.
Input
The first input character indicates the algorithm we want the program to use (students are required to implement three algorithms in a program).
I: iterative
R: recursive
S: STL
A number following the character declares the total number of sets of winning numbers.
For example, in the sample input, there are three sets of winning numbers.
This number can be 1 to 999.
Corresponding unsorted winning numbers follow the number.
A number following the winning numbers declares the total number of lotteries we bought.
For example, In the sample input, there are two sets of our bought lotteries.
This number is equal to or greater than 1.
Corresponding unsorted lotteries follow the number.
The 28th test case is just the same as the following sample input.
Output
Most of the information from input are repeated, except ...
Winning numbers are sorted, both internal to each set and among the sets.
Our bought lotteries are sorted, only internal to each set.
We don't need to perform among-set sorting for our lotteris.
Whether we win the lottery (six numbers are the same to a set of winning numbers) is shown.
Y means yes, and N means no.
Furthermore, please also show which set of winning numbers (after sorting) is matched. (1-based instead of 0-based)
The 28th test case expects just the same as the following sample output.
Especially, the last output line should not contain a newline character.
A C++ program that can pass the 28th test case is as follows.
#include
using namespace std;
int main()
{
char c;
while(cin >> c); // read all input
// expected output for the 28th test case
cout << "R" << endl
<< "3" << endl
<< "01 04 14 25 29 39" << endl
<< "02 10 26 29 40 45" << endl
<< "11 16 17 25 33 41" << endl
<< "2" << endl
<< "02 10 26 29 40 45 Y 2" << endl
<< "01 06 15 17 23 24 N";
return 0;
}
Sample Input Download
Sample Output Download
Tags
Discuss
Description
請設想：
將來有一天你競選總統，很多同學、校友們...等熱心人士捐款給你。
你希望能巨細靡遺地公布收到的捐款金額明細。
因此，你需要寫個程式，幫忙核對競選服務處記錄的捐款數額 vs 銀行的對帳單。
Input
第一個數字是：競選服務處共記錄了幾筆捐款數額 (sample input 的例子是 28 筆)。
接下來逐一列出競選服務處所記錄下的數額。
接著的數字是：銀行的對帳單共有幾筆捐款數額 (sample input 的例子是 27 筆)。
接下來逐一列出銀行的對帳單所記錄下的數額。
Output
先印一行"L1 L2"(中間以 tab 隔開) 代表第一與第二個 list。
第二行印出兩者各有幾筆數額 (以 sample input 為例，會如下圖印出分別是 28 與 27筆)。
把競選服務處所記錄的捐款數額由小至大排序。同樣的，也把銀行對帳單的捐款數額由小到大排序。然後把兩份數字相互比較、逐行併列印出、並且把不一致的地方標記X (以 sample input 為例，會如下圖所示，銀行對帳單(L2那欄)多了 1460與 2190，但少了 1330、1720、及2170)
最後一行，總結有幾個不同 (下圖是 5 differences)。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
We would like to design a program that helps us in performing polynomial calculations. We want our calculator to support the following features:
- A human-readable polynomial expression, e.g., x^7 +2*x^3 -x +10
- The four fundamental operations, +, -, *, and /.
- Successive operations in an formula, e.g., A * B / C - D + E, where A, B, C, D, and E are all polynomials.
Input
Each input line contains a polynomial or an operation.
A polynomial is in a human-readable expression, e.g., x^7 +2*x^3 -x +10. The coefficients are integers, and the exponents are non-negative integers. A polynomial is in a descending order of exponents.
An operation is one of the four character, +, -, *, and /.
The formulas to calculate are in a "postfix" representation, which is directly evaluated from left to right. For example, let X, Y, and Z are polynomials.
- X Y + means (X + Y)
- X Y + Z - means ((X + Y) - Z)
- X Y - Z * means ((X - Y) * Z)
We can assume the following for simplicity:
- Except for the first polynomial, each polynomial is followed by exact one operation.
-
The values of the coefficients and exponents are not excessive large; 32-bit int variables should be able to perform the calculation.
-
When a division is performed, the dividend is a multiple of the divisor. The results are quotient with integer coefficients and non-negative integer exponents without any remainder.
Output
The output first repeats the input.
The last line of the output contains a equation mark, =, followed by the calculation result.
Please note the conventions of expressing a polynomial. Let us take x^5 -3*x^2 +x +7 for example. The following variants of the polynomial are not good:
+x^5 -3*x^2 +x + 7 (we should omit the leading plus mark)
+1*x^5 -3*x^2 +x + 7 (we should omit the leading +1* coefficient)
x^5 + -3*x^2 +x + 7 (we should omit this plus mark for breavity)
x^5 +0*x^4 -3*x^2 +x + 7 (we should omit any zero term)
x^5 -3*x^2 +1*x + 7 (we should omit any 1* coefficient)
x^5 -3*x^2 +x^1 + 7 (we should omit an ^1 exponent)
x^5 -3*x^2 +x + 7x^0 (we should omit x^0)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
We want a program to check whether the brackets and quotation marks in our strings are balanced or not. By "balanced" we mean each opening bracket (quotation mark) has a corresponding closing bracket (quotation mark), and brackets (quotation marks) are properly nested. The program only needs to check the following six types of characters:
| opening curly bracket | { |
| closing curly bracket | } |
| opening square bracket | [ |
| closing square bracket | ] |
| opening round bracket | ( |
| closing round bracket | ) |
| opening/closing double quoatation mark | " |
| opening/closing single quoatation mark | ' |
For spaces and other characters in a string, our program can ignore them.
The following exampling strings are not balanced:
| strings | notes |
| ( a [ b ) ] | clearly, the square brackets are not properly nested with others |
| a " ( ' b ) c " ' | clearly, the single quoation marks are not properly nested with others |
| { " a ' ' " bcd | The first opening curly bracket does not has a corresponding closing bracket |
Input
There are more than one lines, each line being a string for our program to check.
Please note that all the characters of an input line belong to the string. Please do not view the line as a C/C++/Python string in which single and double qouatation marks stand for delimiters.
Output
For each string in the input, if the string is good, please output "OK", followed by a colon mark and a space, then the string.
Otherwise, please output "NG", followed by a colon mark and a space, then the string.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
We want to simulate a Chiness checker piece that randomly walks on the gameboard. The following figure dipicts the shape of the gameboard, the starting position of our checker piece (the starred position), nine positions (1~9) that are already occupied by other checker pieces, and six moving direcrtions (0~5) of our checker piece. The right half of the figure dipicts examples of valid (green) and invalid (red) moves of Chinese checker pieces.
Input
The input consists of multiple lines, each line consisting of
- A number, 0~5, indicates a dirrection our checker piece attempts to move toward. Please note that only our checker piece moves. Checker pieces 1~9 are still.
- A newline character
Output
The above figure depicts what are the results our checker piece moves according to a sequence of moving attempts, 5-4-4-5-4-4-0-0-4-2.
The output consists of multiple lines describing these results.
Each line consists of the following information
- The direction our checker piece attempts to move toward (i.e., a number between 0 and 5). This part actually repeats the input.
- A space
- The distance our checker piece actually moves (i.e., a number, 0~2) corresponding to a moving attempt. 0 corresponds to an invalid move (and our checker piece holds its position), 1 corresponds to a valid move, and 2 corresponds to a valid move over an occupied checker piece.
- If our checker piece moves to a position that has not been visited, the program additionally outputs a space and a word "new"
- A newline character
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The KMP algorithm describes how we can derive failure function given a pattern. Reversely, here we want to design an algorithm that can
- Produce the first valid pattern (in dictionary order) that satisfies a given KMP's failure function, if such a pattern exist
- Report an error if such a pattern does not exist
By first valid pattern in dictionary order, we mean that, for example, although abbb, abbc, abcb, abcc, abcd ... all satisfy the failure function 0000, we want the program to pick the first one, abbb, instead of others.
Input
Input consists of multiple lines. Each line is a failure function consisting of many integers.
Integers are separated by spaces.
The failure funcitons given in the input are 0-based (the first number is 0 in a failure funciton), while in some textbooks, failure functions are -1-based (the first number is -1). If you prefer the latter one, please subtract each number by 1.
Output
For each input failure function, please do the follows:
- Output the failure function again
- Print the first valid pattern (in dictionary order) that satisfies the failure function if available.
Please insert single space between every two characters for better readibility. - Print a lowercase x if the patter is unavailable (i.e, the failure function is not valid)
- Print "-----" and a newline character as a separator line
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Houston, we have had a problem! Our spaceship accindentally flew into a black hole. Time and space thus all distorrrrrrrt. Believe or not, even the priority of our familiar arithmetic operators are changed!
The priority of arithmetic operators in this black hole is as follows:
| - | the highest |
| * / | middle |
| + | the lowest |
Other rules are the same as integer arithmetics on Earth.
Let us take 7/9-8+5*7*1 for example. What we are familair with on Earth is:
7/9-8+5*7*1
= ((7/9)-8)+((5*7)*1)
= (0-8)+(35)
= 27
However, in this black hole we have:
7/9-8+5*7*1
= (7/(9-8))+((5*7)*1)
= 42
Very strange, right? Even worse, the navigation calculator of our spaceship stops working because of this difference, and thus we cannot find the right path back to Earth now.
Fortunately, some students at NTHU are helping us reprogramming the navigation calculator. They arrrrre our future!!
Input
There are multple lines, each being an arithemetic expression.
Each expression can contain
- Several single-digit, integer operands, 0, 1, .., 9 (i.e., each operand is a char)
- Several arrithmetic operators, + - * /
- A few parentheses
An expression contains no space characters in between operands, operators, and delimiters.
Each expression ends up with a newline character.
Output
For each expression, please perform the following four lines
- Output the expression
- Output "= " followed by the parenthesized expression based on the priority in the black hole
- Output "= " followed by the result
- Five dash characters, "-----", as a separator
Please note that
- Output "= NaN" (i.e., Not a Number) for an expression that causes division by zero
- Please adopt integer division. For exmape, 5/6=0, 1/(2-4)=0
- Please output the parenthesized expression without the outermost pair of parenthesis, which is redundant, e.g., the red parenthese in the folllowing example.
7/9-8+5*7*1
= ((7/(9-8))+((5*7)*1))
= 42
Sample Input Download
Sample Output Download
Tags
Discuss
Description
We want to build a ternary min heap given a sequence of push and pop. In a d-ary heap, each node can have up to d children. In a min heap, each parent node has a key no greater than that of its children.
Input
The first line contains the degree of the heap (d), the max. number of children a node can have.
The second line contains the number of operations (push and pop) made to the ternary min heap.
Then, each line is a push (with an int key value) or pop operation.
There's no duplicate keys and no underflow cases (i.e., requesting an empty heap to perform pop).
Output
Print out the level-order sequence of the ternary min heap after all operations are made.