【Google谷歌大中华区2014校园招聘在线笔试经历了三轮，分别在2013年9月14日（历时）、9月23日、10月12日举行，google原链接：https://code.google.com/codejam/contests.html】
Google of Greater China Test for New Grads of 2014
Practice Round China New Grad Test 2014【 2013年9月14日】
Problem A. Bad Horse
ProblemAs
the leader of the Evil League of Evil, Bad Horse has a lot of problems
to deal with. Most recently, there have been far too many arguments and
far too much backstabbing in the League, so much so that Bad Horse has
decided to split the league into two departments in order to separate
troublesome members. Being the Thoroughbred of Sin, Bad Horse isn't
about to spend his valuable time figuring out how to split the League
members by himself. That what he's got you  his loyal henchman  for.
InputThe first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a positive integer M on a line by itself  the number of troublesome pairs of League members. The next M lines each contain a pair of names, separated by a single space.
OutputFor each test case, output one line containing
"Case #x: y", where x is the case number (starting from 1) and y is
either "Yes" or "No", depending on whether the League members mentioned
in the input can be split into two groups with neither of the groups
containing a troublesome pair.
Limits1 ≤ T ≤ 100.
Each member name will consist of only letters and the underscore character.
Names are casesensitive.
No pair will appear more than once in the same test case.
Each pair will contain two distinct League members.
Small dataset1 ≤ M ≤ 10.
Large dataset1 ≤ M ≤ 100.
Sample
Input

Output

2
1
Dead_Bowie Fake_Thomas_Jefferson
3
Dead_Bowie Fake_Thomas_Jefferson
Fake_Thomas_Jefferson Fury_Leika
Fury_Leika Dead_Bowie

Case #1: Yes
Case #2: No

Problem B. Captain Hammer
ProblemThe
Hamjet is a true marvel of aircraft engineering. It is a jet airplane
with a single engine so powerful that it burns all of its fuel instantly
during takeoff. The Hamjet doesn't have any wings because who needs
them when the fuselage is made of a special Wonderflonium isotope that
makes it impervious to harm.
Piloting the Hamjet is a not a job for your typical, meekbodied
superhero. That's why the Hamjet belongs to Captain Hammer, who is
himself impervious to harm. The Gforces that the pilot endures when
taking a trip in the Hamjet are legendary.
The Hamjet takes off at an angle of θ degrees up and a speed of V meters per second. Vis
a fixed value that is determined by the awesome power of the Hamjet
engine and the capacity of its fuel tank. The destination is D meters away. Your job is to program the Hamjet's computer to calculate θ given V and D.
Fortunately, the Hamjet's Wondeflonium hull is impervious to air
friction. Even more fortunately, the Hamjet doesn't fly too far or too
high, so you can assume that the Earth is flat, and that the
acceleration due to gravity is a constant 9.8 m/s2 down.
InputThe first line of the input gives the number of test cases, T. T lines follow. Each line will contain two positive integers  V and D.
OutputFor each test case, output one line containing
"Case #x: θ", where x is the case number (starting from 1) and θ is in
degrees up from the the horizontal. If there are several possible
answers, output the smallest positive one.
An answer will be considered correct if it is within 106 of the exact answer, in absolute or relative error. See the FAQ for an explanation of what that means, and what formats of floatingpoint numbers we accept.
Limits1 ≤ T ≤ 4500;
1 ≤ V ≤ 300;
1 ≤ D ≤ 10000;
It is guaranteed that each test case will be solvable.
Sample
Input

Output

398 98098 490299 1234

Case #1: 45.0000000Case #2: 15.0000000Case #3: 3.8870928

Problem C. Moist
ProblemMoist
has a hobby  collecting figure skating trading cards. His card
collection has been growing, and it is now too large to keep in one
disorganized pile. Moist needs to sort the cards in alphabetical order,
so that he can find the cards that he wants on short notice whenever it
is necessary.
The problem is  Moist can't actually pick up the cards because they
keep sliding out his hands, and the sweat causes permanent damage. Some
of the cards are rather expensive, mind you. To facilitate the sorting,
Moist has convinced Dr. Horrible to build him a sorting robot. However,
in his rather horrible style, Dr. Horrible has decided to make the
sorting robot charge Moist a fee of $1 whenever it has to move a trading
card during the sorting process.
Moist has figured out that the robot's sorting mechanism is very
primitive. It scans the deck of cards from top to bottom. Whenever it
finds a card that is lexicographically smaller than the previous card,
it moves that card to its correct place in the stack above. This
operation costs $1, and the robot resumes scanning down towards the
bottom of the deck, moving cards one by one until the entire deck is
sorted in lexicographical order from top to bottom.
As wet luck would have it, Moist is almost broke, but keeping his
trading cards in order is the only remaining joy in his miserable life.
He needs to know how much it would cost him to use the robot to sort his
deck of cards.
InputThe first line of the input gives the number of test cases, T. T test cases follow. Each one starts with a line containing a single integer, N. The next N lines each contain the name of a figure skater, in order from the top of the deck to the bottom.
OutputFor each test case, output one line containing
"Case #x: y", where x is the case number (starting from 1) and y is the
number of dollars it would cost Moist to use the robot to sort his deck
of trading cards.
Limits1 ≤ T ≤ 100.
Each name will consist of only letters and the space character.
Each name will contain at most 100 characters.
No name with start or end with a space.
No name will appear more than once in the same test case.
Lexicographically, the space character comes first, then come the upper case letters, then the lower case letters.
Small dataset1 ≤ N ≤ 10.
Large dataset1 ≤ N ≤ 100.
Sample
Input

Output

2
2
Oksana Baiul
Michelle Kwan
3
Elvis Stojko
Evgeni Plushenko
Kristi Yamaguchi

Case #1: 1
Case #2: 0

Round A China New Grad Test 2014 【2013年9月23日】
Problem A. Read Phone Number
ProblemDo you know how to read the phone numbers in English? Now let me tell you.
For example, In China, the phone numbers are 11 digits, like:
15012233444. Someone divides the numbers into 344 format, i.e. 150
1223 3444. While someone divides the numbers into 335 format, i.e. 150
122 33444. Different formats lead to different ways to read these
numbers:
150 1223 3444 reads one five zero one double two three three triple four.
150 122 33444 reads one five zero one double two double three triple four.
Here comes the problem:
Given a list of phone numbers and the dividing formats, output the right ways to read these numbers.
Rules:
Single numbers just read them separately.
2 successive numbers use double.
3 successive numbers use triple.
4 successive numbers use quadruple.
5 successive numbers use quintuple.
6 successive numbers use sextuple.
7 successive numbers use septuple.
8 successive numbers use octuple.
9 successive numbers use nonuple.
10 successive numbers use decuple.
More than 10 successive numbers read them all separately.
InputThe first line of the input gives the number of test cases, T. T linestest cases follow. Each line contains a phone number N and the dividing format F,
one or more positive integers separated by dashes (), without leading
zeros and whose sum always equals the number of digits in the phone
number.
OutputFor each test case, output one line containing
"Case #x: y", where x is the case number (starting from 1) and y is the
reading sentence in English whose words are separated by a space.
Limits1 ≤ T ≤ 100.
Small dataset1 ≤ length of N ≤ 10.
Large dataset1 ≤ length of N ≤ 100.
Sample
Input


315012233444 34415012233444 33512223 23


Output

Case #1: one five zero one double two three three
triple fourCase #2: one five zero one double two double three triple
fourCase #3: one two double two three

Problem B. Rational Number Tree
ProblemConsider
an infinite complete binary tree where the root node is 1/1 and left
and right childs of node p/q are p/(p+q) and (p+q)/q, respectively. This
tree looks like:
1/1 ____________   1/2 2/1
______ ______    1/3 3/2 2/3 3/1...It is
known that every positive rational number appears exactly once in this
tree. A levelorder traversal of the tree results in the following
array:1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...
Please solve the following two questions:

Find the nth element of the array, where n starts from 1. For example, for the input 2, the correct output is 1/2.

Given p/q, find its position in the array. As an example, the input 1/2 results in the output 2.
InputThe first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line. The line
contains a problem id (1 or 2) and one or two additional integers:

If the problem id is 1, then only one integer n is given, and you are expected to find the nth element of the array.

If the problem id is 2, then two integers p and q are given, and you are expected to find the position of p/q in the array.
OutputFor each test case:

If the problem id is 1, then output
one line containing "Case #x: p q", where x is the case number (starting
from 1), and p, q are numerator and denominator of the asked array
element, respectively.

If the problem id is 2, then output one
line containing "Case #x: n", where x is the case number (starting from
1), and n is the position of the given number.
Limits1 ≤ T ≤ 100; p and q are relatively prime.
Small dataset1 ≤ n, p, q ≤ 2161; p/q is an element in a tree with level number ≤ 16.
Large dataset1 ≤ n, p, q ≤ 2641; p/q is an element in a tree with level number ≤ 64.
Sample
Input

Output

41 22 1 21 52 3 2

Case #1: 1 2Case #2: 2Case #3: 3 2Case #4: 5

Problem C. Sorting
ProblemAlex
and Bob are brothers and they both enjoy reading very much. They have
widely different tastes on books so they keep their own books
separately. However, their father thinks it is good to promote exchanges
if they can put their books together. Thus he has bought an onerow
bookshelf for them today and put all his sons' books on it in random
order. He labeled each position of the bookshelf the owner of the
corresponding book ('Alex' or 'Bob').
Unfortunately, Alex and Bob went outside and didn't know what their
father did. When they were back, they came to realize the problem: they
usually arranged their books in their own orders, but the books seem to
be in a great mess on the bookshelf now. They have to sort them right
now!!
Each book has its own worth, which is represented by an integer.
Books with odd values of worth belong to Alex and the books with even
values of worth belong to Bob. Alex has a habit of sorting his books
from the left to the right in an increasing order of worths, while Bob
prefers to sort his books from the left to the right in a decreasing
order of worths.
At the same time, they do not want to change the positions of the
labels, so that after they have finished sorting the books according
their rules, each book's owner's name should match with the label in its
position.
Here comes the problem. A sequence of N values s0, s1, ..., sN1 is given, which indicates the worths of the books from the left to the
right on the bookshelf currently. Please help the brothers to find out
the sequence of worths after sorting such that it satisfies the above
description.
InputThe first line of input contains a single integer T, the number of test cases. Each test case starts with a line containing an integer N, the number of books on the bookshelf. The next line contains N integers separated by spaces, representing s0, s1, ..., sN1, which are the worths of the books.
OutputFor each test case, output one line containing "Case #X: ", followed by t0, t1, ..., tN1 in order, and separated by spaces. X is the test case number (starting from 1) and t0, t1, ...,tN1 forms the resulting sequence of worths of the books from the left to the right.
Limits1 ≤ T ≤ 30.
Small dataset1 ≤ N ≤ 100
100 ≤ si ≤ 100
Large dataset1 ≤ N ≤ 1000
1000 ≤ si ≤ 1000
Sample
Input

Output

255 2 4 3 175 12 87 2 88 20 11

Case #1: 1 4 2 3 5Case #2: 5 88 11 20 2 12 87

Problem D. Cross the maze
ProblemEdison, a robot, does not have a right hand or eyes. As a brave robot, he always puts his left hand on the wall no matter he walks or turns around. Because he thinks it is too dangerous, Edison does not walk backward.
Assume that Edison has found himself in a squareshaped maze of NxN square cells which is surrounded by walls from the outside. In the
maze, some of the cells are also walls. Edison can only move between two
empty cells in four directions, north, south, west and east. In order
to get out of the maze, he drafts a plan. He uses his left hand to lean
on the wall and goes by following the wall.
Here is the question, is Edison able to get out of the maze in at most
10,000 steps? If he can make it, output the path. By getting out of the
maze, he only needs to be in the exit cell. If the starting cell is the
same as the exit, Edison won't need to move and can directly get out of
the maze.
InputThe first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with an integer N. N is the size of the maze. The following N lines, each line contains N characters which may be '.' or '#'. '.' is an empty cell, '#' is a wall. Followed by a line which contains four integers: sx, sy, ex, ey. (sx, sy) means that Edison is standing on row sx and column sy as his starting cell, (ex, ey) is the exit of the maze. (sx, sy)
is guaranteed to be at one of the 4 corners of the maze, and Edison can
only touch the wall on 4 adjacent cells(not 8) initially. (ex, ey) can be anywhere in the maze. Note that the topleft corner is at position (1,1).
OutputFor each test case, output a line containing
"Case #x: y", where x is the case number (starting from 1) and y is
"Edison ran out of energy." (without the quotes) if Edison can't reach
the exit of the maze in at most 10,000 steps, otherwise y should be the
number of steps followed by another line which contains y characters to
describe the path (each character should be E for east, S for south, W
for west or N for north). There is no character to represent the turning
around. We don't care about the turning around steps, please only
output the path of how Edison will cross the maze.
Limits1 ≤ T ≤ 30.
1 ≤ sx, sy, ex, ey ≤ N.
The starting cell and the exit of the maze will always be an empty cell.
And the starting cell and the exit of the maze won't be the same.
Small dataset2 ≤ N ≤ 10.
Large dataset2 ≤ N ≤ 100.
Sample
Input

Output

32.##.1 1 2 25.##.#........#..###....#.1 1 5 33....#....1 1 3 3

Case #1: Edison ran out of energy.Case #2: 22SEEENSESSSNNNWWSWWSSEECase #3: 4EESS

Note:
In the 2nd test case after moving 1 cell down from his starting cell,
Edison will still be able to lean on the wall at the cell (1,2) by his
left hand.
In the third test case, due to Edison can't touch the wall at cell (2,2) initially, so he has to go east in his first step.
Problem E. Spaceship Defence
ProblemThe
enemy has invaded your spaceship, and only superior tactics will allow
you to defend it! To travel around your spaceship, your soldiers will
use two devices: teleporters andturbolifts.
Teleporters allow your soldiers to move instantly between rooms. Every
room contains a teleporter, and rooms are colorcoded: if a soldier is
in a room with some color, she can use the teleporter in that room to
immediately move to any other room with the same color.
Turbolifts allow your soldiers to move between rooms more slowly. A
turbolift is like an elevator that moves in many directions. Each
turbolift moves from one room to one other room, and it takes a certain
amount of time to travel. Notes about turbolifts:

Turbolifts are not twoway: if a turbolift moves soldiers from
room a to room b, the same turbolift cannot move soldiers from room b to
room a, although there might be another turbolift that does that.

More than one soldier can use the same turbolift, and they do not interfere with each other in any way.
You will be given the locations and destinations of several soldiers.
For each soldier, output the minimum amount of time it could take that
soldier to travel from his location to his destination.
InputThe first line of the input gives the number of test cases, T. T test cases follow.
For every test case:
The first line of every test case contains an integer N, which is the number of rooms in your spaceship. The rooms are numbered from 1 to N. The following N lines each contain a string telling the color of the rooms, from room 1 to room N.
The strings only contain characters az (the lowercase English
letters) and 09 (the number 0 to 9), and the length of each string will
be less than or equal to 2.
The next line in the test case is an integer M, which indicates the number of turbolifts in your spaceship. The following M lines each contain 3 spaceseparated integers ai, bi, ti, telling us that there is a turbolift that can transport soldiers from room ai to room bi in tiseconds.
The next line in the test case contains an integer S, which is the number of soldiers at your command. The following S lines each contain two integers: the location and destination of one soldier, pj and qj.
OutputFor each test case, output one line containing
only the string "Case #x:", where x is the number of the test case
(starting from 1). On the next S lines, output a single integer: on line j, the smallest number of seconds it could take for a soldier to travel from pj to qj. If there is no path from pj to qj, the integer you output should be 1.
Limits1 ≤ S ≤ 100.
1 ≤ ai, bi ≤ N.
0 ≤ ti ≤ 1000.
1 ≤ pj, qj ≤ N.
Small dataset1 ≤ T ≤ 10.
1 ≤ N ≤ 1000.
0 ≤ M ≤ 3000.
Large datasetT = 1.
1 ≤ N ≤ 80000.
0 ≤ M ≤ 3000.
Sample
Input

Output

33glt3t331 2 2173 2 5671 1 2122 12 34cablbl8z031 22 31 18reb7yegr0l0lyeb774 1 192 4 212 5 3174 5 344 7 34 8 2658 6 7134 32 61 4

Case #1:10Case #2:100Case #3:3551

Round B China New Grad Test 2014【2014年10月12日】
Problem A. Sudoku Checker
ProblemSudoku is a popular single player game. The objective is to fill a 9x9 matrix
with digits so that each column, each row, and all 9 nonoverlapping 3x3
submatrices contain all of the digits from 1 through 9. Each 9x9
matrix is partially completed at the start of game play and typically
has a unique solution.
Given a completed N2xN2 Sudoku matrix, your task is to determine whether it is a validsolution. A valid solution must satisfy the following criteria:

Each row contains each number from 1 to N2, once each.

Each column contains each number from 1 to N2, once each.

Divide the N2xN2 matrix into N2 nonoverlapping NxN submatrices. Each submatrix contains each number from 1 to N2, once each.
You don't need to worry about the uniqueness of the problem. Just check if the given matrix is a valid solution.
InputThe first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with an integer N. The next N2 lines describe a completed Sudoku solution, with each line contains exactly N2 integers. All input integers are positive and less than 1000.
OutputFor each test case, output one line containing
"Case #x: y", where x is the case number (starting from 1) and y is
"Yes" (quotes for clarity only) if it is a valid solution, or "No"
(quotes for clarity only) if it is invalid. Note that the judge is
casesensitive, so answers of "yes" and "no" will not be accepted.
Limits1 ≤ T ≤ 100.
Small datasetN = 3.
Large dataset3 ≤ N ≤ 6.
Sample
Input

Output

335 3 4 6 7 8 9 1 26 7 2 1 9 5 3 4 81 9 8 3 4 2 5 6
78 5 9 7 6 1 4 2 34 2 6 8 5 3 7 9 17 1 3 9 2 4 8 5 69 6 1 5 3 7 2 8 42 8
7 4 1 9 6 3 53 4 5 2 8 6 1 7 931 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 91 2 3 4
5 6 7 8 91 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 91 2 3 4 5 6
7 8 91 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 935 3 4 6 7 8 9 1 26 7 2 1 9 5 3 4
81 9 8 3 4 2 5 6 78 5 9 7 6 1 4 2 34 2 6 8 999 3 7 9 17 1 3 9 2 4 8 5
69 6 1 5 3 7 2 8 42 8 7 4 1 9 6 3 53 4 5 2 8 6 1 7 9

Case #1: YesCase #2: NoCase #3: No

Problem B. Meet and party
ProblemLittle
Sin lives in a Manhattangrid city, a 2D plane where people can only go
north, west, south or east along the grid. The distance from (x1, y1)
to (x2, y2) is x1  x2 + y1  y2.
Little Sin really likes to party and is hoping to host a house party in
Manhattan this Sunday. Little Sin has collected a list of people who
will attend, and now needs to decide at whose home she will host the
party.
Little Sin invited all of the people in several rectangular areas, and
all of those people have said yes. A rectangular area is denoted as (x1,
y1, x2, y2), where x1 ≤ x2, y1 ≤ y2. People who live in a rectangular
area fill all integral points inside it. So there are a total of (x2 
x1 + 1) * (y2  y1 + 1) people in the rectangular area (x1, y1, x2, y2).
Little Sin knows the coordinates of those rectangular areas. She wants
the party to be hosted at the home of one of the people who is
attending, but she also doesn't want everyone else to have to travel
very far: she wants to minimize the sum of all distances from all
attendees' houses to the party. Can you help her?
InputThe first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer: the number of rectangular areas, B. Blines
follow. Each line contains 4 integers: x1, y1, x2, y2, denoting the
coordinates of a rectangular area of people Little Sin has invited to
her party.
OutputFor each test case, output one line containing
"Case #t: x y d", where t is the case number (starting from 1) and (x,
y) is the coordinates of the person whose home the party should be
hosted. If there are multiple positions with the same minimum total
distance, choose the one with the smallest x. If there are still
multiple positions, choose the one with the smallest y. The value d is
the sum of the distances from all attendees' houses to the point (x, y).
Limits1 ≤ T ≤ 10.
x1, y1, x2, y2 ≤ 109.
x1 ≤ x2, y1 ≤ y2.
The rectangular areas within a test case don't intersect.
Small dataset1 ≤ B ≤ 100.
1 ≤ Total number of people in each test case ≤ 1000.
Large dataset1 ≤ B ≤ 1000.
1 ≤ Total number of people in each test case ≤ 1000000.
Sample
Input

Output

210 0 2 231 2 1 20 0 0 01 3 1 3

Case #1: 1 1 12Case #2: 1 2 6

Problem C. Hex
ProblemThis
problem was inspired by a board game called Hex, designed independently
by Piet Hein and John Nash. It has a similar idea, but does not assume
you have played Hex.
This game is played on an NxN board,
where each cell is a hexagon. There are two players: Red side (using red
stones) and Blue side (using blue stones). The board starts empty, and
the two players take turns placing a stone of their color on a single
cell within the overall playing board. Each player can place their stone
on any cell not occupied by another stone of any color. There is no
requirement that a stone must be placed beside another stone of the same
color. The player to start first is determined randomly (with equal
probability among the two players).
The upper side and lower sides of the board are marked as red, and the
other two sides are marked as blue. The goal of the game is to form a
connected path of one player's stones connecting the two sides of the
board that have that player's color. The first player to achieve this
wins. Note that the four corners are considered connected to both
colors.
The game ends immediately when one player wins.
Given a game state, help someone new to the game determine the status of a game board. Say one of the following:

"Impossible": If it was impossible for two players to follow the rules and to have arrived at that game state.

"Red wins": If the player playing the red stones has won.

"Blue wins": If the player playing the blue stones has won.

"Nobody wins": If nobody has yet won the game. Note that a game of Hex can't end without a winner!
Note that in any impossible state, the only correct answer is
"Impossible", even if red or blue has formed a connected path of stones
linking the opposing sides of the board marked by his or her colors.
Here's a an example game on a 6x6 gameboard where blue won. Blue was the
first player to move, and placed a blue stone at cell marked as 1. Then
Red placed at cell 2, then blue at cell 3, etc. After the 11th stone is
placed, blue wins.
InputThe first line of input gives the number of test cases, T. T test cases follow. Each test case start with the size of the side of the board, N. This is followed by a board of N rows and N columns consisting of only 'B', 'R' and '.' characters. 'B' indicates a
cell occupied by blue stone, 'R' indicates a cell occupied by red
stone, and '.' indicates an empty cell.
OutputFor each test case, output one line containing
"Case #x: y", where x is the case number (starting from 1) and y is the
status of the game board. It can be "Impossible", "Blue wins", "Red
wins" or "Nobody wins" (excluding the quotes). Note that the judge is
casesensitive, so answers of "impossible", "blue wins", "red wins" and
"nobody wins" will be judged incorrect.
Limits1 ≤ T ≤ 100.
Small dataset1 ≤ N ≤ 10.
Large dataset1 ≤ N ≤ 100.
Sample
Input

Output

71.1B1R2BRBB4BBBBBBB.RRR.RRRR4BBBBBBBBRRR.RRRR6........R...BBBBBB..R.R...RR........

Case
#1: Nobody winsCase #2: Blue winsCase #3: Red winsCase #4:
ImpossibleCase #5: Blue winsCase #6: ImpossibleCase #7: Blue wins

Problem D. Dragon Maze
ProblemYou
are the prince of Dragon Kingdom and your kingdom is in danger of
running out of power. You must find power to save your kingdom and its
people. An old legend states that power comes from a place known as
Dragon Maze. Dragon Maze appears randomly out of nowhere without notice
and suddenly disappears without warning. You know where Dragon Maze is
now, so it is important you retrieve some power before it disappears.
Dragon Maze is a rectangular maze, an N x M grid of cells. The top left corner cell of the maze is (0,0) and the bottom right corner is (N1, M1).
Each cell making up the maze can be either a dangerous place which you
never escape after entering, or a safe place that contains a certain
amount of power. The power in a safe cell is automatically gathered once
you enter that cell, and can only be gathered once. Starting from a
cell, you can walk up/down/left/right to adjacent cells with a single
step.
Now you know where the entrance and exit cells are, that they are
different, and that they are both safe cells. In order to get out of
Dragon Maze before it disappears, you must walk from the entrance cell
to the exit cell taking as few steps as possible. If there are multiple
choices for the path you could take, you must choose the one on which
you collect as much power as possible in order to save your kingdom.
InputThe first line of the input gives the number of test cases, T. T test cases follow.
Each test case starts with a line containing two integers N and M, which give the size of Dragon Maze as described above. The second line of each test case contains four integers enx, eny, exx, exy, describing the position of entrance cell (enx, eny) and exit cell (exx, exy). Then N lines follow and each line has M numbers, separated by spaces, describing the N x M cells of Dragon Maze from top to bottom. Each number for a cell is
either 1, which indicates a cell is dangerous, or a positive integer,
which indicates a safe cell containing a certain amount of power.
OutputFor each test case, output one line containing
"Case #x: y", where x is the case number (starting from 1). If it's
possible for you to walk from the entrance to the exit, y should be the
maximum total amount of power you can collect by taking the fewest steps
possible. If you cannot walk from the entrance to the exit, y should be
the string "Mission Impossible." (quotes for clarity). Please note that
the judge requires an exact match, so any other output like "mission
impossible." or "Mission Impossible" (which is missing the trailing
period) will be judged incorrect.
LimitsThe amount of power contained in each cell will not exceed 10,000.
1 ≤ T ≤ 30.
0 ≤ enx, exx < N.
0 ≤ eny, exy < M.
Small dataset1 ≤ N, M ≤ 10.
Large dataset1 ≤ N, M ≤ 100.
Sample
Input

Output

22 30 2 1 02 1 53 1 64 40 2 3 21 1 1 21 1 1 12 1 1 11 1 1 1

Case #1: Mission Impossible.Case #2: 7

Problem E. Ignore all my comments
ProblemGood programmers write fabulous comments. Igor is a programmer and he likes the old Cstyle comments in /* ... */ blocks. For him, it would be ideal if he could use this style as a
uniform comment format for all programming languages or even documents,
for example Python, Haskell or HTML/XML documents.
Making this happen doesn't seem too difficult to Igor. What he will need
is a comment preprocessor that removes all the comment blocks in /*, followed by comment text, and by another */. Then the processed text can be handed over to the compiler/document renderer to which it belongs—whatever it is.
Igor's preprocessor isn't quite that simple, though. Here are some cool things it does:
The comments the preprocessor reads can be nested the same way brackets
are nested in most programming languages. It's possible to have
comments inside comments. For example, the following code block has an
outer level of comments that should be removed by the comment
preprocessor. The block contains two inner comments.printf("Hello /* a
comment /* a comment inside comment */ inside /* another comment
inside comment */ string */ world");After the preprocess step,
it becomes:printf("Hello world");Igor recognizes comments can appear
anywhere in the text, including inside a string"/*...*/", a constant
number 12/*...*/34 or even in a character escape \/*...*/nOr more
formally:
text: textpiece textpiece
remainingtexttextpiece: charsequencewithout/* emptystringremainingtext: commentblock
textcommentblock: /* commentcontent
*/commentcontent: commentpiece commentpiece
remainingcommentcommentpiece: charsequencewithout/*or*/ emptystringremainingcomment: commentblock
commentcontentchar: letters digits punctuations whitespacesOur
preprocessor, given a text, removes all commentblock instances as specified.
NotesIgor only needs to remove the comment in one pass.
He doesn't remove additional comment blocks created as a result of the
removal of any comment block. For example://*no recursion*/* file header
*/should generate:/* file header */The * character in any /* or /*cannot be reused in another /* or */. For example the following does NOT form a proper comment block/*/InputA text document with comment blocks in /* and */. The input file is valid. It follows the specification of text in the problem statement. The input file always terminates with a newline symbol.
OutputWe only have one test case for this problem. First we need to output the following line.
Case #1:Then, print the document with all comments removed, in the way
specified in the problem statements. Don't remove any spaces or empty
lines outside comments.
LimitsThe input program contains only:
Letters: az, AZ,Digits: 09Punctuation: ~ ! @ # % ^ & * ( )  + = :
; " ' < > , . ?  / \ { } [ ] _Whitespace characters: space,
newline
Small datasetThe small input contains a program of less than 2k bytes.
Large datasetThe large input contains a program of less than 100k bytes.
Sample
Input


//*no recursion*/* file
header***********/************* Sample input program
***********/**************/int spawn_workers(int worker_count) { /* The
block below is supposed to spawn 100 workers. But it creates many
more. Commented until I figure out why. for (int i = 0; i <
worker_count; ++i) { if(!fork()) { /* This is the worker. Start
working. */ do_work(); } } */ return 0; /* successfully
spawned 100 workers */}int main() { printf("Hello /*a comment inside
string*/ world"); int worker_count = 0/*octal number*/144; if
(spawn_workers(worker_count) != 0) { exit(1); } return 0;}


Output

Case #1:/* file header*************************/int
spawn_workers(int worker_count) { return 0; }int main()
{ printf("Hello world"); int worker_count = 0144; if
(spawn_workers(worker_count) != 0) { exit(1); } return 0;}
