| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13812 | Advanced Convolution |
|
| 14471 | Pocky Challenge |
|
| 14472 | Roman to Integer |
|
Description
In this problem, you have to implement a 2D convolution operation with zero-padding and stride.
Convolution is an operation that you elementwise multiply the sub-region in the original image(A larger 2D array) and the provided kernel(A smaller 2D array) and the summation of the multiplied values will be the new values in the output map(The size may be different from the original image). The multiplication follows a sliding window, so once we reach the bottom-right, we'll get a brand new 2D map.
Once you understand how to do simple convolution, another trick in convolution is that you can pad the original map with zeros, which is called zero-padding.
Last, we can decide the step size of the sliding window, which is called stride.
To sum up, you'll be given a 2D image and a 2D kernel, you are asked to do the convolution with the given padding size and stride.
Testcase 4: No padding, stride > 1 (Only considering stride)
Testcase 5: With padding, stride =1 (Only considering padding)
Testcase 6: With padding, stride > 1
Note that you only have to do the convolution in the valid region.
Input
The first line contains 2 integers, the height and the width of the 2D image, respectively. (1 <= height, width <= 1024)
Next, you have to read the whole 2D image.
The following line contains 2 integers, the height and the width of the 2D kernel, respectively. (1 <= height, width <= 10)
Then, you have to read the whole 2D kernel.
The last line will be the the size of stride and padding, respectively. (0 <= size of stride and padding <= 10)
All the values mentioned above are integers.
It is guaranteed every value of 2D images <= 255 and and 2D kernel is <= 10
Output
Please print the calculated 2D map.
The elements are separated by whitespace and you have to print '\n' at the end of each row.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Pocky is a sweet snack food, a biscuit stick that is very delicious!
As we are a CS students, our Pocky is described by 1D array with length N blocks. The pocky could be eaten from the most left or most right.
Also since 福昌 is a light eater, he won't eat all of the pocky, as he only can eat K blocks, however he want the maximum value from eating K blocks
For example given the Pocky array:
If the K = 3, The maximum value can be gathered from eating from the right block three times, as total value = 1 + 15 + 2 = 18
If the K = 5, The maximum value could be get by eating 2 block from the right side, and then 3 block from the left side, as total value = 1 + 15 + 1 + 7 + 8 = 32
Your task is to calculate the maximum value from given Pocky array and K.
There are 2 ways to solve this problem
1. Make 2 prefix sum from beginning of the array and end of the array, and compare each value related to K
2. Try to do this iteratively:
Calculate the sum of first K elements
Calculate the sum of first K-1 elements and one lastest element
Calculate the sum of first K-2 elements and 2 lastest elements
And so on ...
until you calculate sum of lastest K elements
Input
There are T testcases
Each testcase has
- N and K, separated by space in the first line
- ao, a1, a2, ..., aN-1 in the second line
1 <= T <= 50
1 <= K <= N <= 50000
1 <= ai <= 109
Output
print the maximum value followed by newline character for each testcase
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Roman numbers are represented by symbols I, V, X, L, C, D, and M, and below is the table of each symbol value
| Symbol | Value |
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
Here is the rule of legal roman:
- Symbol can be repeated to representing some value
I,X, andC, andMcan be repeated, for a maximum of 3 times, example:
IIIrepresenting 3 (1+1+1 = 3)
XXrepresenting 20
CCCCis illegal (more than 3 consecutive symbols)
VVis illegal (only I, X, C, and M is allowed) - Some combinations can represent subtractive notation, the full list is:
IVrepresenting 4 (5-1)
IXrepresenting 9 (10-1)
XLrepresenting 40 (50-40)
XCrepresenting 90 (100-10)
CDrepresenting 400 (500-100)
CMrepresenting 900 (1000-100)
Other subtractive notation combinations (e.g.IC)are illegal - The roman must be in descending order (Biggest to Lowest) to make a combination for example:
XXVIIrepresenting 27 (10+10+5+1+1)
Subtractive notation can be also put as long as it's in order, for example:
XIVrepresenting 14 (10 + (5 - 1))
MXCIrepresenting 1091 (1000 + (100 - 10) + 1)
XXXIXis legal, representing 39 (10 + 10 + 10 + 9)
MICis illegal as it's not in descending order and the symbolICis not included in rule number 2
MDDis illegal as it violate rule number 1
XXLis illegal asXL>XandL>XX, no correct combination here
XLXLis illegal (the correct way to represent 80 isLXXX, the same subtractive notation can't be consecutive)
IXIis illegal (there is a more simple way to represent 10, which isX)
Your task is to determine if the number is legal or illegal, if it's legal try to convert the roman to integer representation
Input
There are T testcases
1 <= T <= 100
Each testcase will have only 1 string
Length of string will be <= 20
For testcase 4~5: no illegal format, subtractive notation exist
For testcase 6: no further restriction
Output
For each testcase, please print the number in integer, following by newline character
If it's in illegal format, print "QQ" without the quotes