1054 - 106學年度碩士班甄試入學上機考 Scoreboard

Time

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

Clarification

# Problem Asker Description Reply Replier Reply Time For all team

# 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   

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.

Sample Input  Download

Sample Output  Download

Tags




Discuss




11175 - Big Mod   

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.

Sample Input  Download

Sample Output  Download

Tags




Discuss




11176 - Stable Sort   

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.)

Sample Input  Download

Sample Output  Download

Tags




Discuss




11177 - Minimum Spanning Tree   

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.

Sample Input  Download

Sample Output  Download

Tags




Discuss




11178 - Mouse Maze   

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.

Sample Input  Download

Sample Output  Download

Tags




Discuss