2431 - I2P(I)2021_Yang_lab7 Scoreboard

Time

2021/11/23 18:30:00 2021/11/23 20:30:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team

# Problem Pass Rate (passed user / total user)
12481 Frog Jumping
13179 Matching Strings Ⅱ

12481 - Frog Jumping   

Description

There’re N stones on the river. The height of the i-th stone is hi for 1iN.
Frog Pepe is on the 1-st stone at the beginning and he wants to cross this river with several jumps.
For each jump, Pepe can jump to the (i+1)-th or the (i+2)-th stone from the i-th stone.
The energy cost of jump is |hihj|, where j is the stone to land on.

Because Pepe is too lazy to move, can you help Pepe to find out the minimun energy cost as few jumps as possible to cross the river?

Explantation of Sample I/O:
The mininum energy is 40. There’re 3 routes having the same cost:

  • Stone 1 -> 2 -> 4 -> 5 -> 6, 4 jumps
  • Stone 1 -> 2 -> 4 -> 6, 3 jumps
  • Stone 1 -> 3 -> 5 -> 6, 3 jumps.

Choose jumps as few as possible.
Therefore, the output is 40, 3.

Input

An integer N on the first line.
h1,h2...hN on the second line.

  • 1N25
  • 1hi100,000

Output

On the first line, two integers C and J, which mean the minimun energy cost and the number of jumps.
Remember ‘\n’ on the end of line.

 

Sample Input  Download

Sample Output  Download

Tags




Discuss




13179 - Matching Strings Ⅱ   

Description

In this problem, you are asked to implement a more efficient string matching method, called "rolling hash". In this method, strings are first mapped to integer hash values. Then, when two strings can be mapped to the same hash value, the two strings are said to be "matched".

The "rolling hash" maps a given string to an integer using the following function:

,

where a=9487 is a constant and c1, c2, ..., ck are the chars of the given string.

Note that, the H hash value can be very large, so please use long long int type and module it by M=99999989 (the largest 8-digit prime number) in each add or multiply operation.

For example: 

H("abc")=((((9487*9487)%M*'a')%M+(9487*'b')%M)%M+'c')%M=31238175

H("123")=((((9487*9487)%M*'1')%M+(9487*'2')%M)%M+'3')%M=10630166

Thus, "abc" is mapped to 31238175, while "123" to 10630166.

(It is guaranteed that in the test cases, no two different strings will be mapped to the same hash value if you follow the suggested hash function implementation.)

For complete problem description, please refer to 13277.

 

Given a set of strings S1 and another set of some query strings S2. In this problem, based on the "rolling hash" method, for each string in S2, you need to determine whether it exists in set S1 or not.

 

Hint.

  • Suggested procedure to solve this problem:
  1. For each string of S1:
  • convert the string into its hash value and store the value in an array.
  1. For each string of S2:
  • convert the string into its hash value and search for the hash value in the array you created.
  • Partial code for your reference:
  1. #define a 9487
  2. #define mod 99999989
  3.  
  4. long long int hash(char s[]) {
  5.     int len = strlen(s);
  6.     int i;
  7.     long long int ret = 0;
  8.  
  9.     for (i = 0; i < len; i++) {
  10.         ret = (ret * a % mod + s[i]) % mod;
  11.     }
  12.  
  13.     return ret;
  14. }
  15.  
  16. int main() {
  17.     // your code
  18. }

 

Input

The first line contains 2 integers n and m, which are the sizes of S1 and S2, respectively. (0 < n,m <= 1000) 

Next, there're n lines, each representing a string in S1.

Last, m lines are provided, each representing a string in S2.  

The lengths of the strings are not greater than 5*10^4.

Output

Print m lines. Each line contains "Yes" or "No", which means whether the i-th string in S2 exists in S1 or not.

Print '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Tags




Discuss