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

Discuss

Description

Last Pokemon Contest (神奇寶貝華麗大賽) between Satoshi (小智) and Haruka (小遙) ! After Satoshi won the victory in Battle Pyramid, Satoshi and Haruka signed up for an unofficial Pokemon Contest in Terracotta Town.

Pokemon Contest is a contest in which trainers and Pokemons coordinate strength and beauty. It is divided into two stages. In the first stage, the Performance Stage, trainers and their Pokemons will perform moves to showcase their styles and skills. In the second stage, the Battle Stage, trainers battles against each other as well as demonstrating charm of their Pokemons.

Satoshi and Haruka met in the Battle stage, where Satoshi's Sceptile (蜥蜴王) fought against Haruka's Blaziken (火焰雞). In the final ten seconds of the battle, Haruka's Blaziken activates Blaze (猛火) and fires Overheat (過熱). To battle in a dazzling style, the pattern of Overheat is cleverly designed with golden ratio:

The pattern of Overheat can be expressed with a string. First, Haruka and Blaziken design two short patterns F0 and F1. Then they generate longer patterns using the following recurrence formula: Fn-2 + Fn-1 = Fn (+ means string concatenation). Finally, Haruka tells Blaziken a number n, and Blaziken fires the Overheat with pattern Fn.

Given F0, F1, n, and k, please find out the k-th character in Fn.

For full episode, please google "AG191 Satoshi vs. Haruka! Last Battle!!" or refer to this page.

Explanation on Sample IO

All test data provide same F0 = "abc", F1 = "def". We can generate the following patterns:

• F2 = "abcdef"

• F3 = "defabcdef"

• F4 = "abcdefdefabcdef"

The first test data asks 0-th character of F0, therefore output 'a'. Similarly, the outputs for the second to fifth test data are 'd', 'f', 'f', 'e', respectively.

Input

The input contains multiple test data. The first line of input contains an integer T, being number of test data. After that are T test data.

The first line of test data contains two non-empty strings F0 and F1.

The second line of test data contains two integers n and k.

• 1 <= T <= 100

• F0 and F1 contain only lower case alphabets (a-z) and have length no greater than 2000.

• 0 <= n < 60 and 0 <= k < |Fn|, where |Fn| is length of Fn

Output

For each test data, output the answer in a single line.  Remember to add new line in the end.

Sample Input  Download

Sample Output  Download

Discuss

Description

Input

The first line contains a string s, which consists of only lowercase Latin characters. The second line contains a integer Q. The next Q lines, each contains two characters A and B.

Output

Print the resulting string in one line after applying the Q operations.

(remember to print a new line character)

Sample Input  Download

Sample Output  Download

Discuss

Description

You're now in a bad mood since you quarreled with your best friend. 

Recently, your best friend keeps convince you that using semicolons for indentation is the best way to code in C. He claimed that semicolons are beautiful, so you'll be in a good mood if you put a lot of semicolons in your code. What's more, you'll never forget to add a semicolon at the end of the line anymore. You think that your friend is insane and you have a severe headache every time you read his code. 

Therefore, you decide to get rid of this terrible habit for your friend: now your friend is taking a nap, and you are going to open his computer, find his code files, and turn all of his code to space indentation.

Given lines of compilable C code. Currently, the code is indented by semicolons, and now you want to rewrite this code using spaces for indentation.

In other words, you are going to do the following operations:

• For every single line, turned every prefix semicolon into spaces.
• Add a semicolon at the end of every single line, except for the lines mentioned below: 
  • Header file included. e.g. #include <stdio.h>
  • A line that contains '{' at the very end of it.
  • A line that contains only semicolons and a single '}' at the end.

          It is guaranteed that there are no other situations that don't need a semicolon at the end of the line.

Input

Lines of compilable C code, terminated by EOF.

Output

The code using space for indentation.

Sample Input  Download

Sample Output  Download

Discuss

Description

Story

(The following story is irrelevant to the problem description.)

To save computer science students from the torture of teammates who don't know how to use git, Red Cape Flying Cat uses his knowledge from Introduction to Programming (II) to develop a git tool for everyone to use.

You, while developing alongside him, suddenly remember that you recently learned some string functions. Therefore, you decide to be responsible for some of the string processing parts.

Problem Statement

This is a partial judge problem.

In a single test case, the total number of function calls will not exceed 100000.

You need to implement the following five functions:

1. Determine Command Type

Goal

Your goal is to implement a function that determines the type of a command:

int get_command_type(const char *command);

If the command:

• starts with git add, then return 0
• starts with git commit, then return 1
• starts with git log, then return 2

Constraint

• The length of command is guaranteed not to exceed 50 characters.
• command is a git command, and its format must be one of the following three:
  1. git add <file1> <file2> ...
  2. git commit -m "<message>"
  3. git log
• File is composed of [1~10 uppercase/lowercase English letters].[1~10 uppercase/lowercase English letters].
• At least have one file
• Message length is 0~50, composed of uppercase/lowercase English letters, digits, spaces, and colons.

Example

code:

int t1 = get_command_type("git add a.txt b.txt");
if (t1 == 0) printf("Command type: add\n");

int t2 = get_command_type("git commit -m \"feat: add search bar\"");
if (t2 == 1) printf("Command type: commit\n");

int t3 = get_command_type("git log");
if (t3 == 2) printf("Command type: log\n");

output:

Command type: add
Command type: commit
Command type: log

Hint

You can use the following functions to implement the solution:

• https://en.cppreference.com/w/c/string/byte/strstr
• https://en.cppreference.com/w/c/string/byte/strncmp

 

2. Validate Commit Message

Goal

Your goal is to implement a function that checks whether a commit message is valid:

int is_valid_commit_message(const char *message);

If the length of message is between 1 and 20 (inclusive), it is considered valid, and you should return 1; if it is an empty string or its length exceeds 20 characters, return 0.

Constraint

• The length of message is 0~50 characters, composed of uppercase/lowercase English letters, digits, spaces, and colons.

Example

code:

if (is_valid_commit_message("") == 1) {
    printf("Commit message is valid\n");
} else {
    printf("Commit message is invalid\n");
}

if (is_valid_commit_message("feat: add search bar") == 1) {
    printf("Commit message is valid\n");
} else {
    printf("Commit message is invalid\n");
}

if (is_valid_commit_message("chore: I dont know what to write") == 1) {
    printf("Commit message is valid\n");
} else {
    printf("Commit message is invalid\n");
}

output:

Commit message is invalid
Commit message is valid
Commit message is invalid

Hint

You can use the following functions to implement the solution:

• https://en.cppreference.com/w/c/string/byte/strlen

3. Parse git add File List

Goal

Your goal is to implement a function that parses the list of files following a git add command:

int parse_filenames(char *filenames, char *result[]);

You need to sequentially place each file from left to right into positions 0, 1, 2... of the result array, and return the total number of files parsed.

Constraint

• filenames is a string with the format <file1> <file2> ... <fileN>, where each file is separated by exactly one space.
• At least have one file.
• file is composed of [1~10 uppercase/lowercase English letters].[1~10 uppercase/lowercase English letters].

Example

code:

char filenames[] = "a.txt b.txt c.txt";
char *result[55] = {NULL};
int k = parse_filenames(filenames, result);

printf("There have %d filenames: [%s, %s, %s]\n", k, result[0], result[1], result[2]);

output:

There have 3 filenames: [a.txt, b.txt, c.txt]

Hint

You can use the following functions to implement the solution:

• https://en.cppreference.com/w/c/string/byte/strtok

4. Truncate Commit Hash ID

Goal

Your goal is to implement a function that generates a short Hash ID:

void get_short_commit_id(const char *hex, char *result);

You need to copy the "first 7 characters" of hex into the result array, and append the C string termination character \0 at the end.

Constraint

• hex is a string with a length between 7 and 50, composed entirely of digits 0~9 and lowercase letters a~f.

Example

code:

char result[55] = {0};
get_short_commit_id("923fba7d39452eb573aa3834", result);
printf("Short commit ID: %s\n", result);

output:

Short commit ID: 923fba7

Hint

You can use the following functions to implement the solution:

• https://en.cppreference.com/w/c/string/byte/strncpy

5. Auto-generate Conventional Commit

Goal

Your goal is to implement a function that automatically applies the Commit message convention:

void generate_commit_message(const char *type, const char *message, char *result);

You need to combine them into <type>: <message> and place it into result, according to the following rules:

1. If type is exactly equal to feat, fix, or docs, directly use that type as the classification prefix.
2. If type is any string other than these three, forcibly change the classification to chore.

Constraint

• The length of type is 1~10, composed of uppercase/lowercase English letters.
• The length of message is 1~20, composed of uppercase/lowercase English letters and spaces.

Example

code:

char res1[100] = {0}, res2[100] = {0};
generate_commit_message("feat", "add search bar", res1);
generate_commit_message("random", "fix typo", res2);
printf("Generated commit message: %s\n", res1);
printf("Generated commit message: %s\n", res2);

output:

Generated commit message: feat: add search bar
Generated commit message: chore: fix typo

Hint

You can use the following functions to implement the solution:

• https://en.cppreference.com/w/c/string/byte/strcmp
• https://en.cppreference.com/w/c/string/byte/strcpy
• https://en.cppreference.com/w/c/string/byte/strcat

Input

The first line contains a single integer Q (1 <= Q <= 100000), representing the total number of operations.

Each line of input is guaranteed to be no longer than 50 characters.

The above five operations are input in the following format:

1 <command>
2 "<message>"
3 <file1> <file2> ... <fileN>
4 <hex>
5 <type> "<message>"

Output

The output should have Q lines, corresponding to the output of each operation.

Command type: <result>
Commit message is valid
There have <k> filenames: [<file1>, <file2>, ...]
Short commit ID: <result>
Generated commit message: <result>

Sample Input  Download

Sample Output  Download

Partial Judge Code

14909.c

Partial Judge Header

14909.h

Discuss

Description

Story

(The following story is irrelevant to the problem description.)

Red Cape Flying Cat is currently a teaching assistant for Introduction to Programming (II). As a TA, he must understand how the students are performing.

Red Cape Flying Cat wants to know how many ways a student can achieve a failing grade. However, he is currently on his way flying to Antarctica to see penguins, so he asks you to help him write a program to calculate it.

Problem Statement

This is a partial judge problem.

In a single test case, the total number of function calls will not exceed 10.

You need to implement the following two functions:

1. Sort an Array

Goal

Your goal is to implement a function that sorts an array:

void sort_array(const int len, int arr[]);

You are given an array of length len. You need to sort the array in ascending order and place the sorted result back into arr.

Constraint

• 1 <= len <= 8000
• 0 <= arr[i] <= 10^8

Example

code:

int arr[5] = {4, 8, 7, 6, 3};
sort_array(5, arr);
printf("Sorted arr = [%d, %d, %d, %d, %d]\n", arr[0], arr[1], arr[2], arr[3], arr[4]);

output:

Sorted arr = [3, 4, 6, 7, 8]

2. Calculate the Number of Pairs with Sum Less Than k

Goal

Your goal is to implement a function that calculates how many pairs have a sum less than k:

Please note that the answer may exceed the range of int.

long long number_of_pair_less_than_k(const int len, const int* arr[2], const int k)

You will be given two already sorted arrays, located at arr[0] and arr[1]. The length of both arrays is len. You need to calculate how many pairs have a sum less than k.

Formally, you need to calculate the number of pairs (i, j) such that 0 <= i, j < len and arr[0][i] + arr[1][j] < k.

Constraint

• 1 <= len <= 5 * 10^5
• 0 <= arr[i][j] <= 10^8
• Both arr[0] and arr[1] are increasing.

Example

code:

int a1[3] = {1, 2, 3};
int a2[3] = {4, 5, 6};
const int* arr[2] = {a1, a2};
int result = number_of_pair_less_than_k(3, arr, 8);
printf("Number of pairs less than k = %d\n", result);

output:

Number of pairs less than k = 6

Input

The first line contains a single integer Q (1 <= Q <= 10), representing the total number of operations.

The above two operations are input in the following format:

sort_array:

1
<len>
<arr[0]> <arr[1]> ... <arr[len-1]>

number_of_pair_less_than_k:

2
<len> <k>
<arr[0][0]> <arr[0][1]> ... <arr[0][len-1]>
<arr[1][0]> <arr[1][1]> ... <arr[1][len-1]>

Output

The output should have Q lines, corresponding to the output of each operation.

sort_array:

Sorted arr = [<arr[0]>, <arr[1]>, ..., <arr[len-1]>] 

number_of_pair_less_than_k:

Number of pairs less than k = <result>

Sample Input  Download

Sample Output  Download

Partial Judge Code

14911.c

Partial Judge Header

14911.h

Discuss