Description

Consider a room of size H*W (3<=H,3<=W) in which its four walls are covered by mirrors. You need to simulate the light reflection in the room and print out the k-th reflection point.

We assume that the light is always emitted from the left mirror and moves in the upper-right direction at an angle of 45 degrees. More specifically, the starting point can be represented by (r, 1) where 1<r<H. The light will stop if it hits any corner of the room . 
 

For example, if the room size is 5*6 and the light starts at (3,1), then the first point it hits is (3,1), the second point is (1,3), the third point is (4,6), and so on. If k=3 you need to print out (4,6).

If the light hits a corner before the k-th reflection, you need to print out coordinate of that corner. For example, if k =10 and the first point is (3,1), you need to print out (1,1) because the light stops at (1,1).

Input

The first line is the height and width of the room.

The second line is the starting point (the first reflection point).

The third line is k, which means you need to print out the k-th reflection point.

Output

The coordinate of the k-th reflection point.

Note that you DO NOT need to print a newline character ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Four arrays A, B, C and D with size MxN. B, C, D are stored in an array of pointers, and A is stored in a separated array. The task is to add the designated elements of A and the corresponding element from a chosen array of B, C, D, and output the result.

Take sample input as an example. Size of the arrays are 3 rows by 2 columns, initial values are as the form below. Input number “2” in the sixth line indicates D is chosen array and we want the sum of elements with two indices (1,0), (2,0)

Therefore, the answer is A(1,0)+D(1,0)+A(2,0)+D(2,0)=2+8+4+10=24

You will be provided with the following sample code, and asked to implement function "addition".

#include <stdio.h>

int addition(int*, int, int*[], int*, int);

int main(void) {

    int a[50][50], b[50][50], c[50][50], d[50][50];
    int index_to_add[20];
    int *entry[3];
    int i, j, m, n, array_num, num_ind;

    scanf("%d %d", &m, &n);

    for(i=0; i<m; i++)
        for(j=0; j<n; j++)
            scanf("%d", &a[i][j]);
    for(i=0; i<m; i++)
        for(j=0; j<n; j++)
            scanf("%d", &b[i][j]);
    for(i=0; i<m; i++)
        for(j=0; j<n; j++)
            scanf("%d", &c[i][j]);
    for(i=0; i<m; i++)
        for(j=0; j<n; j++)
            scanf("%d", &d[i][j]);

    scanf("%d", &array_num);
    scanf("%d", &num_ind);
    for(i=0; i<num_ind*2; i=i+2)
        scanf("%d %d", &index_to_add[i], &index_to_add[i+1]);

    entry[0] = &b[0][0];
    entry[1] = &c[0][0];
    entry[2] = &d[0][0];

    printf("%d\n", addition(&a[0][0], array_num, entry, index_to_add, num_ind));

    return 0;
}

int addition(int* ptr_a, int array_num, int* entry[], int* index_to_add, int num_ind){
    /*your code*/
}

Input

The first line is the size of arrays, M rows by N columns. The following four lines are initial values arranged by row major. The sixth line tells B, C or D is chose. The next line is the number of elements k to be summed. And the last k lines are the row and column indices of elements to be add. 0 < M, N < 50. 0 < k < 10. Index starts from 0.

Output

An integer, sum of desired elements.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A mail carrier needs to deliver letters to multiple places and goes back to the post office to take a rest.

Traveling outside makes him feel tired, so he would like to come up with a shortest path.

Given all distances between every pair of places (including the post office and all destinations), please help the mail carrier figure out the best shortest path, which starts from the post office and ends at the post office.

An additional requirement is that the mail carrier can just go to each place only one time (excluding the starting point, he can go to the start point at the beginning and in the end).

Input

The first line contains an integer N, indicates there are N places (including the post office).

Then there is one N*N martix occupies N lines, with each line contains N integers (>= 0).

ith row jth column = Matrix(i,j) = distance between place i and place j.

The place with index = 0 is the post office.

For all i, j >= 0, Matrix(i,j) = Matrix(j,i), Matrix(i,i) = 0.

N is at most 10 among all test cases.

Output

Print out the minimum distance the mail carrier has to travel to complete his task.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a two-dimensional array of size R _x 5 (1 < R < 100).

We want to sort the two dimensional array according to each row.

For example:

After sorted

Note that

1.      This problem involves three files.

• function.h: Function definition of sortArray.
• function.c: Function implementation of sortArray.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.c.

2.     For OJ submission:

        Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

        Step 2. Check the results and debug your program if necessary.

Hints : bubble sort algorithm

/* Using bubble sort to rearrange an array A[n] */

for (i = n; i > 0; i--) {

   for (j = 1; j < i; j++) {

      if (A[j-1] > A[j]) {

         /* swap A[j-1] A[j] */

      }

   }

}

function.h

#ifndef FUNCTION_H #define FUNCTION_H #define COLUMN 5 void sortArray(int R, int (*array)[COLUMN]); #endif

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" int main(void) { int i,j,n,N,R; scanf("%d", &N); int (*array)[COLUMN]; // array is a pointer to an one-dimensional array of COLUMN elements for(n=0;n<N;n++){ scanf("%d", &R); array = (int(*)[COLUMN])malloc(sizeof(int)*COLUMN*R); for(i = 0; i < R; i++) for(j = 0; j < COLUMN; j++) scanf("%d", &array[i][j]); sortArray(R, array); for(i = 0; i < R; i++){ printf("%d", array[i][0]); for(j = 1; j < COLUMN; j++){ printf(" %d", array[i][j]); } printf("\n"); } if(n!=N-1) printf("\n"); free(array); } return 0; }

Input

The first line has an integer N(1<=N<=5000), which means the number of test cases.

For each case, the first line has an integer R (1<R<100) represent the numbers of rows. The following R lines, each containing 5 integers, specify the elements of the two-dimensional array.

Output

Print out all elements of the sorted array row-by-row.

All of the integers in the same line are separated by a space and there is a '\n' at the end of each line. All of the arrays should be separated by a new line character (\n).

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

In the village of hakka's, there are lots of big big mazes,
it is said that the delicious hakka mochi(麻糬) is hidden in one of the secret maze.

You, a poor programmer, work for hakkas without getting any paid,
want to find out the secret, and change the job to selling mochi,
since being a programmer is too tired, and may be died overworked.
So, one day, you sneaked into the village head's house, and stolen all the mazes' maps out.

You have got T maps,
and each map shows that the maze is N*M grids big,
and start from (1,1) (the left top corner), and the mochi is at (N,M) (the right bottom corner),
the '#' on the map represent the wall,
and the '*' on the map represent that you can walk pass that grid,
and the 'T' on the map represent the teleport device.

Walking in the hakka's maze, start from the starting point,
if you are standing on a road,
you can go to the up, right, left, or the bottom grid near you,
you cannot be on the wall,
and if you are standing on a teleport device,
you can go to the up, right, left, or the bottom grid near you, too,
but you can also teleport to any other teleport device.

You want to make sure the if it is possible to walk from the starting point (1, 1) to the ending point (N, M) of each map,
so you won't waste time finding the mochi.

ouo.

For Example, if the input is:
1
3 3
***
*#*
##*
The output should be 'Yes' (without quotes),
since you can go (right, right, down, down) to get to the ending point of the map.

Input

The first line of the input is a number T,
represent the amount of map you have.

Start from the second line, there are T maps,
the first line contains 2 number N, M, represent the maze is N*M big,
then the following N lines are M characters,
the character '#' represent the grid is a wall,
the character '*' represent the grid is a road,
the character 'T' represent the grid is a teleport device.

It is guarantee that,
for all test cases, T <= 10, 2 <= N, M <= 1000,
for the 1 test case, 2 <= N, M <= 10,
for the 2, 3 test cases, 2 <= N, M <= 200
for the 3, 6 test case, there are no teleport device.
for the 4, 5, 6 test cases, 2 <= N, M <= 1000
and (1, 1) will not be a wall.

Output

Output T lines,
if it is possible to walk from the starting point to the end point,
output 'Yes', otherwise, output 'No'. (Without quotes)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

As you know, Little Brick is a student is NTHU, major in CS,
he often told his friends that he have a dream - Grow Taller.

He said that every time he lines up in a queue,
he cannot see anything since there are always someone taller than him,
and standing in front of him.

He is furious, he hate to stand after people who is taller than him,
so, he define a formula to calculate the confort level of standing in the i_th position in a line.
The confort level f(i) is defined as the number of consecutive people standing in front of him, and are shorter than him.

That see if there is a line, and their heights are 150, 170, 180, 160, 165, fron front to end,
then f(1)=0 since there are no anyone standing in front of position 0,
f(2)=1, since 150 < 170,
f(3)=2, since 170 < 180 and 150 < 180,
f(4)=0, and f(5)=1

One day, Little Brick told you that he is waiting in a long line,
looking forward to shaking hand with his favorite idol,
which is your favorite one, too.

You called Little Brick and asked: "Where are you, Little Brick",
and Little Brick replied: "I am at the position where the comfort level is X",
you: "Wait, what the f...", but it was too late, he had already hang up the phone.

Now, inorder to find Little Brick so that you can cut in line to shake hand with your favorite idol,
you need to find where Little Brick may be at.

That is, given you 2 integers N and X,
where N is the number of people in the line,
and X is the comfort level Little Brick at.
Then N distinct numbers Ai,
representing the height of the people standing at the i_th position,
from the front to the end,
you need to find all possible position where Little Brick may be at.

ouo.

For example, the sample input:
6 2
3 1 6 2 4 5,
we can calculate the formula of all index,
f(1)=0, f(2)=0, f(3)=2, f(4)=0, f(5)=1, f(6)=2,
and X=2, so Little Brick may be at position 3 or 6.

Input

The first line contains 2 integer N, X,
N is the number of people, and X is the comfort level,
the second line contains N integer Ai, separate by a space,
representing the height of people standint at the i_th position.

It is guarantee that,
1<=N,X<=10^7,
1<=Ai<=10^9

Output

Output contains one line,
output all possible positions where Little Brick may be at,
separate by a blank.
If there is no possible position where Little Brick may be at,
output a single line "ouo" (without quote).

The index of position start from 1, and you must output the index in increasing order.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Bob and Alice are very interested in cryptography.
They always encrypt their messages when communicating with each other.
Unfortunately, Bob lost the program to decrypt messages because of the Windows Update yesterday. Therefore, he needs to decrypt the words by himself.

Now, Bob receives N strings (S1,S2...SN) from Alice in lexicographical order. He wants to know which of them have the same pattern as a certain string P and the frequency of such strings.
With these information, Bob can find out the original string by some dark magic.

Can you help discover all pairs (Si,Fi), where Si has the same pattern as P, and Fi is the frequency of Si where Fi > 0?

Note:

1. Two strings Si and P have the same pattern if and only if we can obtain P by replacing corresponding letters in Si, and vice versa. 

For example:

• Si = “abcb” and P = “theh” have the same pattern

  replace ‘a’ by ‘t’: S = "tbcb"
  replace ‘b’ by ‘h’: S = "thch"
  replace ‘c’ by ‘e’: S = “theh”

• Si = “abcb” and P = “ther” have different patterns

  It’s impossible to replace ‘b’ by both ‘h’, ‘r’

• Si = “abcb” and P = “thhh” have different patterns

  replace ‘a’ by ‘t’: S = "tbcb"
  replace ‘b’ by ‘h’: S = "thch"
  replace ‘c’ by ‘h’: S = “thhh”
  ‘b’ and ‘c’ should not be the same after replacement.

2. The frequency F of a string is its number of occurrences within the N strings (S1,S2...SN).

Ex: if Bob receives {“a”, “b”, “a”}

• F of “a” = 2 (S1,S3 = “a”)
• F of “b” = 1 (S2 = “b”)

Input

An integer N and a string P on the first line.
The next N lines give S1,S2...SN in lexicographical order.

• 0 ≤ |N| ≤ 5000
• 1 ≤ |Si|, P ≤ 5000, ∀i∈1,2,...N
• Si and P contain only lower-case English letters.

Output

Print on the first line the number M of distinct strings (from S1,S2...SN) that have the same pattern as P.
On the following M lines, print the (S,F) pair for the M strings that have the same pattern as P, one pair per line, in decreasing order of their frequencies. When the frequencies tie, please use the lexicographical order of the strings.
Remember ‘\n’ on the end of line.

Explanation of the sample I/O

There’re 5 kinds of strings {“fiv”, “oaq”, “aaa”, “fivqv”, “six”}.
Only “fiv”, “oaq”, “six” have the same pattern as “the”.

• frequency of “fiv” = 3
• frequency of “oaq” = 1
• frequency of “six” = 1

There’re 3 pairs (“fiv”, 3), (“oaq”, 1), (“six”, 1).
Print them by the rule above:

3
fiv 3
oaq 1
six 1

Sample Input  Download

Sample Output  Download

Tags

Discuss