| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13260 | Nappa's Attack |
|
| 14007 | The Girl I Like Forgot Her Glasses |
|
Description
Nappa is on his way to destroy a city for some fun, however on his way there, he was stopped by an army shooting at him so Nappa decided to destroy them for fun too.
Before he destroyed them, he noticed that the men in the army form a pattern. Each group forms a triangular shape as follows:
The strongest one is at the center and is protected by layers of weaker soldiers and those soldiers are protected by even weaker soldiers.
There are many sizes and Nappa wants to see every pattern there could be so he must write a program in his scouter to show him every possibility of this pattern.
Input
The input will contain a single integer N, the strongest soldier at the center.
0<N<1000
Output
The output will require you to print the entire traingle pattern with the strongest soldier at the center having the N power level.
There need not be space between numbers but there should be a new line at the end of every line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Story Section
(You can skip this part if you know what convolution is.)
"You might think my eyes look scary, but don't worry. I'm just squinting because I couldn't see very well," the girl narrowed her beautiful eyes, turning towards me. "The truth is... I forgot my glasses."
"You forgot them?" I asked.
"Yeah... It's the first time in this month... how frustrating..."
Mie Ai, or Mie-san, is the girl whom I fell in love with. Not even once could I get her out of my mind. Seeing her being troubled by this situation, I decided to become her support, at least for today.
"Umm... Mie-san," I awkwardly spoke up, "if you don't mind, would you like me to help you?"
"Huh? You will?" her eyebrows raised. "How will you help me?"
"Well... I have a plan," I brought out a paper and a pencil. "Do you know what convolution is?"
"Convolution?" she repeated. "No, I have never heard of it."
"What about pixels? Have you heard about it before?"
"I think I have heard of it," she said. "Is it something to do with pictures, right?"
"Exactly. For computers, pictures are actually a grid of tiny squares of a specific color, called pixels," I started drawing a grid and filled it in with numbers. "The color is determined by the number in that pixel. For example, 0 means the pixel is completely black and the brightness goes up as the number goes up. When we reach 255, the pixel is completely white."
"But, Komura-kun... What does this have anything to do with convolution?""Let's say we have a smaller grid, each cell of which has a number inside. This is called a kernel," I placed a blue plastic piece on the paper. "When the kernel is placed over the grid, some number would be covered by the kernel, right? What we need to do is multiply each number in the kernel by the number that it is covering, and then add them all together."
"So this is what's called convolution?" Mie-san leaned over the paper, examining it closely.
"Not yet. We have to move the kernel over the whole grid while repeating the same thing--multiplying and adding," I slide the plastic over the paper. "After finishing this process, the output image should be completely filled with numbers. The output is called a convoluted image, while the whole process is called convolution."
Figure 1: The animation showing the algorithm in action
"So that's how it is... and how can I use this thing? It seems pretty pointless."
"It is, in fact, one of the crucial building blocks of computer vision. If we choose numbers in the kernel carefully, we can add effects, such as blurring, sharpening, and edge-highlighting, to a picture. We can even train the kernel to recognize more complex but tangible features such as eyes and ears using neural networks so that the computer can process the information like our brain does. Some applications in the real world include training self-driving cars to avoid pedestrians and medical devices that identify irregularities in X-ray films. Surely, it can help you too, Mie-san.""Sounds interesting," she smiled. "By the way, you know how to make it, right?"
"Well... erm... that is a great question..."
"Komura-kun? What's wrong? You can code this right?"
"..."
Everyone... Please help me implement this convolution algorithm. I don't want to embarrass myself in front of my crush.
Figure 2: Example of effects of kernels on the output image
Question Section
If you are here, you probably know what convolution is already. So I'm going to make a summary of the program I need you to make.
I'm going to create a pair of glasses that takes in a grayscale image of width w and height h. I want you to create an algorithm that turns it into a convoluted image of width w-2 and height h-2 using a 3-by-3 kernel that contains a single-precision floating value in each pixel. Remember to round the numbers down to integers.
Input
In the first line, there are two positive integers, w and h, representing the width and height of the image. (3 ≤ w,h ≤ 300).
Following are 9 single-precision floating point numbers distributed into a 3 x 3 grid, representing the numbers in the kernel.
The remaining h lines consist of w integers each, representing the brightness value in a w x h grayscale picture. The brightness value in each pixel is a non-negative number b (0 ≤ b ≤ 255).
Output
The resulting convolved (w-2) x (h-2) image, consisting of numbers rounded to an integer with field width 4 (the format specifier is %4d), all followed by a space. At the end of each line, print an end-line character '\n'.