1532 - I2P (I) 2018_Yang

#	Problem	Pass Rate (passed user / total user)
11137	Matrix Transpose
11654	yang_cheatsheet
12045	Caterpillar2
12047	Summation of sub-matrices

11137 - Matrix Transpose

Status | Limits Submit

	Time	Memory
Case 1	1 sec	32 MB
Case 2	1 sec	32 MB
Case 3	1 sec	32 MB
Case 4	1 sec	32 MB
Case 5	1 sec	32 MB

Description

A matrix A of dimension (N,M) has N*M elements in the format of N rows(橫列) and M columns(直行), and thus each element has a pair of index (i, j), where i is less than N, j is less than M, and both are greater or equal to 0. For example, a matrix A of dimension (2, 3) may look like this:

[ 1 3 5 ]
[ 2 4 6 ]

where the element A(0,1) is 3 and A(1, 0) is 2.

In linear algebra, a transpose of a matrix A, which is A^T, is to reflect the A over its main diagonal(主對角線). For each element A(i,j), the new location of the element in the A^T is (j,i).

In this problem, a matrix A is given, and you are asked to output A^T, which is the transpose of A.

Input

The input consists of 2 parts, which present the marix A:

The dimentsion of the matrix: two positive integers N and M in one line, and both are not greater than 30.
The matrix itself: N lines and each line contains M decimal integers that have one 1 digit (0-9). All integers in the a line are seperated by a space.

Output

Output is the matrix A^T, which should have M rows. All elements in a row should be seperated by a space, and make sure there is no trailing spaces at the end of each line.

Sample Input Download

2 3
1 3 5
2 4 6

Sample Output Download

1 2
3 4
5 6

11654 - yang_cheatsheet

Status | Limits Submit

Description

printf() and scanf() format

printf("%d", n);

FORMAT ARGUMENT TYPE

%d, %i int decimal

%u unsigned int

%x unsigned int hexadecimal

%#x unsigned int hexadecimal with prefix 0x

%f double

%Lf long double

%c char to print a character

%s char * string (character array ended with '\0')

scanf("%d", &n);

FORMAT ARGUMENT TYPE

%d int * &n, store the input integer in n

%ld long *

%lld long long *

%u unsigned int *

%f float * read float

%lf double * read double

%Lf long double * read long double

%c char * read 3 characters %3c

%s char * read a string until whitespace

%n int * with %s, to get string length

                   char a[100]; int len;
                 scanf("%s%n", a, &len);
                 len will have the string length

Frequently used functions

#include <string.h>
char str[10];
scanf("%s", str);
to get the string length using strlen(str)

#include <ctype.h>
isspace(ch), islower(ch), isupper(ch), isdigit(ch)
isalpha(ch), toupper(ch), tolower(ch)

To create a 5-by-5 two-dimensional array, we need to write

int a[5][5];

It will be indexed as follows:

a[0][0]	a[0][1]	a[0][2]	a[0][3]	a[0][4]
a[1][0]	a[1][1]	a[1][2]	a[1][3]	a[1][4]
a[2][0]	a[2][1]	a[2][2]	a[2][3]	a[2][4]
a[3][0]	a[3][1]	a[3][2]	a[3][3]	a[3][4]
a[4][0]	a[4][1]	a[4][2]	a[4][3]	a[4][4]

How to read the following data?
1 2 3 4 5 e
#include <stdio.h>
int main(void)
{
int x;
while (scanf("%d", &x) == 1) {
printf("x=%d\n", x);
}
return 0;
}

How to read the following data?

L 5 2
D 5 3

#include <stdio.h>

int main(void)

{

char ch;
int i, n, row, col;

scanf("%d", &n);

for (i=0; i<n; i++) {

while(getchar()!='\n');

scanf("%c%d%d", &ch, &row, &col);

}

return 0;

}

Using for loops to print a two-dimensional array

   for(i = 0; i < row; i++) {
      for (j = 0; j < col; j++) {
         printf("%5d", A[i][j]);
      }
      printf("\n");
   }

operators:
! && || == != + - * / %
> < >= <=

How to avoid common errors and how to debug for OJ

1. Put the arrays in the 'global' area. Set their size bigger than required. Avoid using variable-length arrays (e.g. int arr[n];). Keep the array size fix (e.g., int arr[1000];).

2. After writing the code for reading input data, you may print out the data to check if your code reads them correctly. Do not proceed to write subsequent code before you confirm that.

3. If your program crashes, usually it is caused by memory related errors. Check the ranges of for-loops to see if your code attempts to read or write the elements out of the arrays' boundary.

Input

Output

Sample Input Download

Sample Output Download

12045 - Caterpillar2

Status | Limits Submit

	Time	Memory
Case 1	1 sec	32 MB
Case 2	1 sec	32 MB
Case 3	1 sec	32 MB
Case 4	1 sec	32 MB
Case 5	1 sec	32 MB

Description

Have you ever seen the Caterpillar text?

here it is:

..╚⊙ ⊙╝..
.╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
....╚═(███)═╝
.....╚═(███)═╝
....╚═(███)═╝
....╚═(███)═╝
....╚═(███)═╝
...╚═(███)═╝
...╚═(███)═╝
....╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
....╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
.....╚═(███)═╝
....╚═(███)═╝
.....╚═(███)═╝
....╚═(███)═╝
....╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
....╚═(███)═╝
...╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
....╚═(███)═╝
...╚═(███)═╝
....╚═(███)═╝
....╚═(███)═╝
...╚═(███)═╝
....╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
...╚═(███)═╝
....╚═(███)═╝
...╚═(███)═╝
....╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
......╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
.......╚═(███)═╝
.......╚═(███)═╝
......╚═(███)═╝
......╚═(███)═╝
......╚═(███)═╝
......╚═(███)═╝
......╚═(███)═╝
.......╚═(███)═╝
......╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
.......╚═(███)═╝
.......╚═(███)═╝
......╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
.......╚═(███)═╝
.......╚═(███)═╝
........╚═(███)═╝
.......╚═(███)═╝
.......╚═(███)═╝
......╚═(███)═╝
......╚═(███)═╝
......╚═(███)═╝
.....╚═(███)═╝
....╚═(███)═╝
....╚═(███)═╝
...╚═(███)═╝
...╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
....╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
.╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
.╚═(███)═╝
╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
...╚═(███)═╝
....╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
.╚═(███)═╝
╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
....╚═(███)═╝
...╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
..╚═(███)═╝
...╚═(███)═╝
...╚═(███)═╝
....╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
.....╚═(███)═╝
......╚═(███)═╝
.......╚═(███)═╝
........╚═(███)═╝
.........╚═(███)═╝
..........╚═(███)═╝
...........╚═(███)═╝
..........╚═(███)═╝
...........╚═(███)═╝
............╚═(███)═╝
............╚═(███)═╝
............╚═(███)═╝
.............╚═(███)═╝
..............╚═(███)═╝
..............╚═(███)═╝
..............╚═(███)═╝
.............╚═(███)═╝
..............╚═(███)═╝
.............╚═(███)═╝
.............╚═(███)═╝
..............╚═(███)═╝
.............╚═(███)═╝
............╚═(███)═╝
.............╚═(███)═╝
..............╚═(███)═╝
...............╚═(███)═╝
..............╚═(███)═╝
...............╚═(███)═╝
................╚═(███)═╝
.................╚═(███)═╝
.................╚═(███)═╝
................╚═(███)═╝
...............╚═(███)═╝
..............╚═(███)═╝
.............╚═(███)═╝
.............╚═(███)═╝
.............╚═(███)═╝
..............╚═(███)═╝
..............╚═(███)═╝
...............╚═(███)═╝
................╚═(███)═╝
...............╚═(███)═╝
...............╚═(███)═╝
................╚═(███)═╝
.................╚═(███)═╝
................╚═(███)═╝
...............╚═(███)═╝
..............╚═(███)═╝
...............╚═(███)═╝
...............╚═(███)═╝
................╚═(███)═╝
................╚═(███)═╝
...............╚═(███)═╝
................╚═(███)═╝
...............╚═(███)═╝
...............╚═(███)═╝
................╚═(███)═╝
...............╚═(███)═╝
................╚═(███)═╝
.................╚═(███)═╝
.................╚═(███)═╝
.................╚═(███)═╝
..................╚═(███)═╝
...................╚═(███)═╝
..................╚═(███)═╝
...................╚═(███)═╝
....................╚═(███)═╝
...................╚═(███)═╝
....................╚═(███)═╝
.....................╚═(███)═╝
.....................╚═(███)═╝
.....................╚═(███)═╝
.....................╚═(███)═╝
....................╚═(███)═╝
....................╚═(███)═╝
.....................╚═(███)═╝
.....................╚═(███)═╝
.....................╚═(███)═╝
....................╚═(███)═╝
...................╚═(███)═╝
..................╚═(███)═╝
..................╚═(███)═╝
.................╚═(███)═╝
................╚═(███)═╝
...............╚═(███)═╝
..............╚═(███)═╝
.............╚═(███)═╝
..............╚═(███)═╝
.............╚═(███)═╝
............╚═(███)═╝
.............╚═(███)═╝
............╚═(███)═╝
............╚═(███)═╝
.............╚═(███)═╝
..............╚═(███)═╝
...............╚═(███)═╝
................╚═(███)═╝
.................╚═(███)═╝
................╚═(███)═╝
...............╚═(███)═╝
...............╚═(███)═╝
..............╚═(███)═╝

As you know, the Caterpillar can be very long. just like some input.

Give you the looking of the Caterpillar. output the Caterpillar.

Hint : loop

Input

The first line contains an integer L, 0 ≤ L ≤ 100000, which indicates that there will be L lines following.

Each i of the following L lines gives an integer Li, 0 ≤ Li ≤ 100000.

Output

A long long caterpillar.

First, print "..╚⊙ ⊙╝.." in the beginning!!

Then, for every input Li, output Li times '.' and add "╚═(███)═╝" in the end together with a '\n'.

The first testcase is sample output.

Sample Input Download

Sample Output Download

..╚⊙ ⊙╝..
╚═(███)═╝
.╚═(███)═╝
..╚═(███)═╝
.╚═(███)═╝
╚═(███)═╝

12047 - Summation of sub-matrices

Status | Limits Submit

	Time	Memory
Case 1	1 sec	512 MB
Case 2	1 sec	512 MB
Case 3	1 sec	512 MB
Case 4	1 sec	512 MB
Case 5	4 sec	512 MB

Description

This problem is more complex compared to other problems. It is recommended that you should try to solve the other problems first if you haven't read or finished them.

Note for submission: while TAs are designing this problem, we found that choosing the wrong compiler (C++xx) might cause an acceptable code to be judged as incorrect. So remember to choose the C compiler!

Given a 2D array Arr, find the sum of elements in a given range.

There will be multiple queries in this question.

Definition of the sum of elements in a given range X₁, Y₁, X₂, Y₂:

Sum = Σ(Arr[i][j]), X₁ ≤ i ≤ X₂, Y₁ ≤ j ≤ Y₂

This problem is an extended version of homework 12022 - prefix sum. You will need to use similar techniques to solve this problem.

Input

The first line contains 2 integers N, M that specify the matrix size.

For the next N lines, each of them contains M integers. The j-th integer in the i-th of these lines is Arr[i][j].

Then the next line (N+2-th line) contains an integer Q, meaning there will be Q queries.

Then for the next Q lines (each of them forms a query), each contains 4 integers X₁, Y₁, X₂, Y₂, indicating the range of the sub-matrix.

The array index is 1-based.

1 ≤ X₁ ≤ X₂ ≤ N, 1 ≤ Y₁ ≤ Y₂ ≤ M.

It is guaranteed that every element is less than 50 (0 ≤ Arr[i][j] ≤ 49).

Output

For each query, output one line containing an integer representing the sum of elements of the submatrix.

Sample Input Download

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 1 1 1
2 1 2 3
1 1 4 4

Sample Output Download

1
18
136