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

Tags

Discuss

Description

Story

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

As you know, you helped Red Cape Flying Cat develop a Git tool that became a massive success within the Computer Science department. Now, every CS student at NTHU is using the tool you two created, and Red Cape Flying Cat has become the most beloved and adorable cat in the entire department.

However, while working on his assignments on a tablet, he realized there isn't a Git tool specifically optimized for tablets, which has caused him quite a bit of frustration. Because of this, he wants to team up with you again to develop a tablet-specific Git tool so he can finally handle version control on his tablet with ease!

 

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 three functions:

 

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

void print(int result) {
    if (result == 1) printf("Commit message is valid\n");
    else printf("Commit message is invalid\n");
}

print(is_valid_commit_message(""));
print(is_valid_commit_message("feat: add search bar"));
print(is_valid_commit_message("chore: I dont know what to write"));

output:

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

---

 

2. Match Filename

 

Goal

Your goal is to implement a function that checks whether a filename matches a given pattern:

int check_filename(const char *head, const char *body, const char *tail, const char *filename);

Return 1 if all of the following conditions hold for the non-empty arguments, otherwise return 0:

• head is a prefix of filename.
• tail is a suffix of filename.
• body exists as a substring of filename, strictly after head and strictly before tail.

If any of head, body, tail is an empty string "", skip the corresponding check.

 

Constraint

• filename is composed of [1~10 uppercase/lowercase English letters].[1~10 uppercase/lowercase English letters].
• head, body, tail are each either an empty string "" or a string composed of uppercase/lowercase English letters and ..
• len of head, body, tail is between 1 and 20 (inclusive) if not empty.
• Each character appears at most once in total across head, body, and tail.

 

Example

code:

void print(int result) {
    if (result == 1) printf("Filename matches\n");
    else printf("Filename does not match\n");
}

print(check_filename("dev", "", "", "devmain.c"));
print(check_filename("dev", "main", "", "devmain.c"));
print(check_filename("dev", "main", ".c", "devmain.c"));
print(check_filename("main", "dev", "", "devmain.c"));
print(check_filename("dev", "xyz", "", "devmain.c"));
print(check_filename("dev", "main", ".py", "devmain.c"));
print(check_filename("main", "", "", "devmain.c"));
print(check_filename("dev", "", "main", "devmain.c"));

output:

Filename matches
Filename matches
Filename matches
Filename does not match
Filename does not match
Filename does not match
Filename does not match
Filename does not match

Explanation:

---

 

3. Filter Filenames

 

Goal

Your goal is to implement a function that filters a list of filenames:

int filter_filenames(const char *head, const char *body, const char *tail, char *filenames, char *result[]);

Parse filenames and place each filename that satisfies check_filename(head, body, tail, filename) into result[0], result[1], ... in order. Return the total number of matched files.

Each result[i] should point directly into filenames.

If any of head, body, tail is an empty string "", skip the corresponding check.

 

Constraint

• filenames is a string with the format <file1> <file2> ... <fileN>, where files are separated by exactly one space. At least one file is present.
• Each file is composed of [1~10 uppercase/lowercase English letters].[1~10 uppercase/lowercase English letters].
• head, body, tail are each either an empty string "" or a string composed of uppercase/lowercase English letters and ..
• len of head, body, tail is between 1 and 20 (inclusive) if not empty.
• Each character appears at most once in total across head, body, and tail.

 

Example

code:

char filenames[] = "devmain.c main.c main.cpp";
char *result[55] = {NULL};
int k = filter_filenames("main", "", "", filenames, result);
printf("There have %d filenames: [%s, %s]\n", k, result[0], result[1]);

output:

There have 2 filenames: [main.c, main.cpp]

---

 

Subtask

We strongly recommend that you complete the following subtasks in order (note: subtask 6 may be relatively easy for some people).

Input

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

Each line must not exceed 50 characters in length.

The three functions are called in the following format:

1 "<message>"
2 <head> <body> <tail> <filename>
3 <head> <body> <tail> <file1> <file2> ... <fileN>

For operations 2 and 3, use - to represent a "" argument.

Output

The output should have Q lines, corresponding to the return value of each function call.

Commit message is valid
Filename matches
There have <k> filenames: [<file1>, <file2>, ..., <filek>]

Sample Input  Download

Sample Output  Download

Partial Judge Code

14917.c

Partial Judge Header

14917.h

Tags

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 dedicated TA, he needs to keep track of the students' learning progress and academic performance.

To do this, Red Cape Flying Cat wants to figure out exactly how many different score combinations can result in a student's average score hitting a specific target value.

However, he is currently in Antarctica, busy playing and belly-sliding with baby penguins. He's having too much fun to pull himself away, so he needs your help to write the program!

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 four 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 <= 3000
• 1 <= arr[i] <= 5000

 

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. Count Pairs with Sum Strictly Less Than k

 

Goal

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

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

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

You are given two already sorted (non-decreasing) arrays arr[0] (A) and arr[1] (B), both of length len. Count the number of index pairs (i, j) such that 0 <= i, j < len and A[i] + B[j] < k.

 

Constraint

• 1 <= len <= 5 * 10^5
• 1 <= k <= 2*10^4
• 1 <= arr[0][i], arr[1][j] <= 5000
• Both (A) and (B) are non-decreasing.

 

Example

code:

int A[5] = {3, 4, 6, 7, 100};
int B[5] = {1, 2, 3, 4, 5};
const int* arr[2] = {A, B};
long long result = number_of_pairs_less_than_k(5, arr, 10);
printf("Number of pairs less than k = %lld\n", result);

output:

Number of pairs less than k = 15

---

 

3. Count Pairs with Sum Less Than or Equal to k

 

Goal

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

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

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

You are given two already sorted (non-decreasing) arrays arr[0] (A) and arr[1] (B), both of length len. Count the number of index pairs (i, j) such that 0 <= i, j < len and A[i] + B[j] <= k.

 

Constraint

• 1 <= len <= 5 * 10^5
• 1 <= k <= 2*10^4
• 1 <= arr[0][i], arr[1][j] <= 5000
• Both (A) and (B) are non-decreasing.

 

Example

code:

int A[5] = {3, 4, 6, 7, 100};
int B[5] = {1, 2, 3, 4, 5};
const int* arr[2] = {A, B};
long long result = number_of_pairs_less_than_or_equal_to_k(5, arr, 10);
printf("Number of pairs less than or equal to k = %lld\n", result);

output:

Number of pairs less than or equal to k = 17

---

 

4. Count Valid Average Triplets

 

Goal

Your goal is to implement a function that counts how many triplets (i, j, l) satisfy the condition that C[l] is the average of A[i] and B[j]:

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

long long number_of_valid_average_scores(const int len, const int* arr[3]);

You are given three already sorted (non-decreasing) arrays arr[0] (A), arr[1] (B), and arr[2] (C), all of length len. Count the number of triplets (i, j, l) such that 0 <= i, j, l < len and average of A[i] and B[j] is C[l].

 

Constraint

• 1 <= len <= 5 * 10^5
• 1 <= arr[0][i], arr[1][j], arr[2][l] <= 5000
• All three arrays are non-decreasing.

 

Example

code:

int A[3] = {1, 2, 5};
int B[3] = {1, 3, 5};
int C[3] = {1, 3, 5};
const int* arr[3] = {A, B, C};
long long result = number_of_valid_average_scores(3, arr);
printf("Number of valid average scores = %lld\n", result);

output:

Number of valid average scores = 4

explanation:

The average of 2 and 5 is not 3, the definition of average does not round the result.

 

Subtask

Input

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

Each of the following Q operations is formatted as follows:

sort_array

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

number_of_pairs_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]>

number_of_pairs_less_than_or_equal_to_k

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

number_of_valid_average_scores

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

Output

The output contains Q lines, one per function call, in order.

sort_array

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

number_of_pairs_less_than_k

Number of pairs less than k = <result>

number_of_pairs_less_than_or_equal_to_k

Number of pairs less than or equal to k = <result>

number_of_valid_average_scores

Number of valid average scores = <result>

Sample Input  Download

Sample Output  Download

Partial Judge Code

14918.c

Partial Judge Header

14918.h

Tags

Discuss