Description

There will be some sample code for this problem . 

The first line contains a string s.

There will be only lowercase Latin characters in s.

The second line will be an integer T, which is the change time. And T< 10⁷.

For the next T line , each line will contains two character x, y , which means for any x in s should be replacement as y .

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

Input

| s | < 10000

x, y will be  lowercase Latin characters 

For the testcase one , there is  no change to original string s.

If you get any Runtime error in testcase one, think twice what's wrong with your pointer :D .

Output

In the end , output the string s one time !

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

APP stands for "Another Palindrome Problem".

Given a string str with length n and an integer k, is it possible to transform str to a palindrome(回文) by removing at most k characters?

Explanation of sample io

You are given str = "fadicaf" and you can remove 3 characters at most. In this case you can remove 'd', 'i', and get "facaf", which is a palindrome. Therefore please output "Yes". Note that there may be multiple ways to transform str to a palindrome.

Maybe useless hints

Maybe useful hints

Draw the recursion tree, and then observe how many recursive function calls with same arguments are re-calculated. Is it possible to store the result of each recursive function call once it is calculated? If so, is it possible to use the results you have stored instead of re-calculate?

Input

The first line is two integers n, k, which are string length and max number of characters you can remove.

The second line is a string str.

• 1 <= n <= 1000

• 1 <= k <= 20, for the 1-5 th test case

• 1 <= k <= 1000, for the 6 th test case. Some tricks must be applied to pass this test case.

• str is of length n, consisting of lower case characters (a-z) only

Output

Output "Yes" (without quotation mark) in a line if str can be transformed to a palindrome by removing at most k characters, otherwise output "No" (without quotation mark) in a line.

Sample Input  Download

Sample Output  Download

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

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

Description

Split String by given a specific pattern is the common operation for string manipulation. In python code, you can write below code to use it conveniently.

However, in this problem, you are asked to implement split function by yourself 

In this problem, you are asked to design two functions
    1.

char **split_str_by_pattern(char* str, char* pattern, int* split_num);

implement split string function by given input string and pattern, then malloc a 2d char array to store the split result and return it. (also set correct split_num)

    2.

void free_result(char **result, int split_num);

Free the memory space of your array that was previously allocated by using malloc. Be careful about the memory uage of your program allocated dynamically so as to avoid MLE.

The two functions have been declared in function.h, and you are asked to complete the function definitions in function.c.

Note: 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.

hint: you can use strlen function to get the lenght of input string (already include header file in main.c)

Input

S_input

S_p

S_input: The input string should be splited ,  20 <= S_input < 500

S_p:  The pattern string ,  1 <= S_p < 10

Output

output the strings splited by given pattern. (followed by a newline character at the end of each output string)  

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

As a student studying in computer science,

your parents and your friends always think of you as a hacker.

To impress them, you want to build a hacker script.

After several days of scripting, you finally got the system's administration password.

But the system has a protection mechanism,

which replace some consecutive letters into a '#' character as the system settings.

After that, there may be one or more '#' character,

and each '#' character represent one to many arbitary letters.

To get the whole control of the system,

you must know the exactly characters replaced by each '#' character.

Now, your goal is to print all possible combinations of each '#' character.

For the output order, please refer to the sample I/O.

The output order is also formally defined as follows.

Assume that the password you get is a string S,

and S[L, R] represent the substring from L_th character to the R_th character of string S.

For any 2 possible combinations A and B,

if the i_th '#' in combination A replaced S[AL_i, AR_i] to '#',

the i_th '#' in combination B replaced S[BLi, BR_i] to '#',

and for the smallest i that AL_i ≠ BL_i and AR_i ≠ BR_i,

if AL_i < BL_i or (AL_i = BL_i and AR_i < BR_i),

then combination A should be output before combination B,

otherwise the combination B should be output before combination A.

If there is no any possible combinations,

output "What the hack!?" (without quotes).

ouo.

Input

Input contains 2 lines.

There first line contains a string S, represent the password of the system.

The second line contains a string P, represent the string you get after the protection mechanism replaced some character from S to '#'.

It is guaranteed that:

1 <= |S| <= 20, and S contains only lowercase letters,

1 <= |P| <= 20, and P contains only lowercase letters and at least 1 character '#'.

Output

If there is any possibles combination,

output one line per combination,

and separate the representation of each '#' by spaces.

Notice that the output order of combinations should follow the rules in the description.

If there is no any possible combination,

output "What the hack!?" (Without quotes)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Last time, you build a hacker script that hack the system password.

So the system's protection were strengthen after your attack.

This time, you also got the system password,

and the system's protection mechanism has replaced some consecutive letters into a '#',

or replaced some consecutive and identical letters into a '$' as the system settings.

After that, there will be zero to many '#' character and zero to many '$' character,

and each '#' character represent one to many arbitary letters,

each '$' character represent one to many identity letters.

For example, if the password is 'abcdefff',

then the system can replace 'a' to '#', replace 'def' to '#' and replace the last 2 'f' to '$',

the the password will become '#bc#$'.

To get the whole control of the system,

you must know the exactly letters replaced by each '#' and '$'.

Now, your goal is to find the number of combinations for all '#' and '$'.

ouo.

For Sample Input 1, 3 possibles combinations are:

(#₁, #₂, #₃) = (b, cde, g), (bc, de, g), (bcd, e, g)

For Sample Input 2, 4 possibles combinations are:

($₁, $₂) = (aaaa, a), (aaa, aa), (aa, aaa), (a, aaaa)

For Sample Input 3, 2 possibles combinations are:

($₁, #₁, $₂) = (b, baaa, b), (bb, aaa, b)

Input

The first line of input contains an integer T,

represents that there are T testcases.

For each testcase contains 2 lines of input data,

There first line contains a string S, represent the password of the system.

The second line contains a string P, represent the string you get after the system replaced some character from S to '#' or '$'.

It is guaranteed that:

1 <= T <= 10,

1 <= |S| <= 20, and S contains only lowercase letters,

1 <= |P| <= 20, and P contains only lowercase letters, '#' or '$'.

And there must be at least 1 '#' or '$' in P.

For testcase 1 and 2, there is no '$' character in P.

For testcase 3, there is no '#' character in P.

Output

For each testcase,

output contains only 1 line,

the number of combinations for all '#' and '$' with a newline character.

Note that the number of combinations may be zero.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a xyz-space, a box lies on the coordinate axes, with O=(0,0,0) and P=(A,B,C), referring to the figure below:

A ball is placed inside the box. At t=0, its initial position is (x0, y0, z0) and its initial velocity is (u0, v0, w0), where u0, v0, w0 is the initial velocity component relative to x-axis, y-axis, and z-axis. The ball always moves with constant velocity except that it bounces when colliding the walls of the box. The collision obeys law of reflection: After collision with a wall, the velocity component normal to the wall is negated. For example, if the ball with velocity (u, v, w) collides the wall on plane z=0, after collision the ball bounces and has velocity (u, v, -w).

Please calculate the position of the ball at time N.

Explanation on sample io

On plane z=0, the movement of the ball is illustrated in the figure below:

Input

Each input contains multiple test cases. The first line of the input is an integer T, being the number of test cases.

The first line of each test case are three integers A, B, C.

The second line of each test case are three integers x0, y0, z0.

The third line of each test case are three integers u0, v0, w0.

The last line of each test case is an integer N.

• 1 <= T <= 10^4

• 1 <= A, B, C <= 10^6

• 0 <= x0 <= A

• 0 <= y0 <= B

• 0 <= z0 <= C

• -10^6 <= u0, v0, w0 <= 10^6

• 1 <= N <= 100 for small input, 1 <= N <= 10^9 for large input

Output

For each test case, please output three integers x, y, z separated with a single space between them, describing the position at time N. Note that there should be no trailing space in the end (which means no space after z) and remember to add a \n in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss