# Time

 2016/11/04 09:30:00 2016/11/04 12:30:00

# Clarification

# Problem Pass Rate (passed user / total user)
11174 Find the Longest Palindrome
11175 Big Mod
11176 Stable Sort
11177 Minimum Spanning Tree
11178 Mouse Maze

## 11174 - Find the Longest Palindrome

Status  |  Limits

### Description

Palindrome is a string that is identical to its reverse, like "level" or "aba". Given a string, find the longest palindrome in the string.

### Input

The input consists of multiple lines. Each line contains a string.  The length of each string is no more than 1000.

case 1: the length of each string <= 50

case 2: the length of each string <= 100

case 3: the length of each string <= 500

case 4: the length of each string <= 1000

### Output

In each test case, output the longest palindrome in the string. If there are many palindromes of the same length, output the first one in the string.

## 11175 - Big Mod

Status  |  Limits

### Description

Calculate R = (BP) mod M for large B, P, and M. Integer B is in the range 0 to 232 inclusive. Integer P is in the range 0 to 231 inclusive. Integer M is in the range 1 to 65600 inclusive. Note that you cannot calculate R directly because BP is too large.

### Input

There are multiple test cases. Each test case is given in three lines, containing B, P, and M in each line.

Case 1: 0 <= B <= 215, 0 <= P <= 215, 1 <= M <= 46340
Case 2: 0 <= B <= 215, 0 <= P <= 231, 1 <= M <= 46340

Case 3: 0 <= B <= 231, 0 <= P <= 231, 1 <= M <= 46340
Case 4: 0 <= B <= 232, 0 <= P <= 231, 1 <= M <= 65600

### Output

For each test case, output the answer R in a single line.

## 11176 - Stable Sort

Status  |  Limits

### Description

Given the grades of N people. Please output the sorted result. (Increasing order)

### Input

The input includes multiple test cases.

In each test case, the first line contains one integer N. The following N lines specify the name Si and the grade Gi.

1 <= |Si| <= 10 (Only contain a-z, A-Z)
0 <= Gi <= 100 (Gi is an integer.)

Test Case 1 : 1 <= N <= 102
Test Case 2 : 1 <= N <= 104
Test Case 3 : 1 <= N <= 105
Test Case 4 : 1 <= N <= 106

### Output

For every test case, output the result in N lines. Every line contains the name and the grade. If more people’s grades are same, output by input order. (That means it uses stable sort. And also please use faster input/output.)

## 11177 - Minimum Spanning Tree

Status  |  Limits

### Description

Given a simple, undirected weighted graph G = (VEW), output the weight of its minimum spanning tree.

### Input

The input includes multiple test cases. The first of the input is an integer T (T <= 1000) specifying the number of test cases. For each case, the first line contains two integers: the number of the node N and the number of the edges M. In the following M lines, each line contains three integers (sieici), 1 <= siei <= N, 1 <= ci <= 100, representing the indices of end vertices of an edge and the weight of the edge.

Case 1: 2 <= N <= 102, 1 <= M <= 103
Case 2: 2 <= N <= 103, 1 <= M <= 103
Case 3: 2 <= N <= 103, 1 <= M <= 104
Case 4: 2 <= N <= 103, 1 <= M <= 105

### Output

For each case, output a single line that indicates the weight of the minimum spanning tree of the graph.

## 11178 - Mouse Maze

Status  |  Limits

### Description

Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting point to the final point.

The maze type is shown in following figure:

S\$###
\$\$#\$\$
\$\$\$##
##\$\$F

it consists of S (starting point), #(walls), \$(road) and F (final point).

In above case, it needs 7 steps from S to F as following figure,

S\$###
\$\$#\$\$
\$\$\$##
##\$\$F

and the mouse can move in the four directions: up, down, left, right. There may be more than one way to reach final point, the program only need to print the least steps.

If there is no way from S to F, then print -1.

### Input

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

For each case, the first line has two integers. The first and second integers R and C (3<=R, C<=500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R x C.

The following R lines, each containing C characters, specify the elements of the maze.

### Output

Print out the least steps for each case, and there is a new line character at the end of each line.