Level 4
Visit departments
Jang keeps visiting and helping a number of departments right after he comes to work.

There is a rule in his movement. He stays at a department exactly for 10 minutes.

You are given a probability graph of their movements. Fig. 1 is an example graph.

 

Level 4
Thống trị khu vực
Cho ma trận NxN (5 ≤ N ≤ 100) chứa các phần tử có giá trị 0 – 5 mô tả lãnh thổ 6
vương quốc. Yêu cầu sáp nhập các vùng số 0 về các lãnh thổ khác sao cho vùng đồng
nhất có diện tích lớn nhất (các vùng được chuyển đổi trước không được tính vào diện
tích để quyết định các vùng chuyển đổi sau), sau đó trả về số lượng vùng còn lại sau
khi sáp nhập.

Thông thường, chúng ta có thể thấy rõ rằng có hai ô 5, hai ô 4, một ô 3  và hai ô 2 gian hàng xung quanh ba ô 0 này. Tuy nhiên, vì ô 5 cũng kết nối với ô khác cùng loại (ô 5, tại vị trí [1,1] và [4,1] với màu xanh lam), diện tích sẽ trở lên tốt hơn, vì vậy chúng tôi coi tần suất của ô 5 là 4. Trong trường hợp có nhiều hơn một loại ô có cùng tần suất cao nhất, chúng tôi sẽ chọn ô có giá trị cao hơn.

Level 4
Tấn công thành trì
Sau một thời gian dài dưỡng thương ở Hán Trung, Khổng Minh đã bình phục và quyết định tấn công vào vào biên giới nước Ngụy để hoàn thành chí nguyện Bắc phạt của mình. Canh giữ biên giới của Ngụy là Tư Mã Ý, một viên tướng cực kỳ khôn ngoan và mưu trí. Trước đó, Tư Mã Ý đã cho xây dựng một hệ thống phòng thủ gồm các thành trì (tòa thành), giữa các thành trì y lại cho đắp các thành lũy (bức tường) liên kết với các thành trì  nhau để bảo vệ cho các đội quân đồn trú bên trong. Vì thế, trận địa phòng ngự của Ngụy quân rất vững chắc, tầng tầng lớp lớp.

Khổng Minh là một nhà quân sự tài ba, y đã vạch ra kế hoạch hoàn mỹ như sau:

Bước 1: Dùng máy bắn đá phá vỡ một số thành lũy liên kết giữa các thành trì của quân Ngụy, sao cho không có đội quân nào của Ngụy được bảo vệ kín bởi hệ thống thành lũy.

Bước 2: Dùng nhân tâm kế để đánh giáp lá cà với Ngụy quân.

Level 4
Phá Hủy Hệ Thống Điện
Phá hủy hệ thống điện

Sau khi biết tin Eagle xây dựng hệ thống điện và ăn bớt được rất nhiều kinh phí, VenG rất tức vì khi anh xây cầu anh đã không ăn bớt được đồng nào. Do đó anh quyết phá hệ thống điện của Eagle.

Do sợ bị phát hiện nên anh sẽ chỉ phá hệ thống điện ở trên 1 hòn đào, và anh muốn tìm hòn đảo nào sau khi phá xong thì hệ thống điện của Eagle bị chia cắt thành nhiều phần nhất.

Hãy giúp anh VenG tìm hòn đảo này.

Level 4
Mountain Walking
Cho một bản đồ kích thước NxN (2 <= N <= 100), mỗi ô mang giá trị là độ cao của ô đó (0 <= độ cao <= 110). Bác John và bò Bessie đang ở ô trên trái (dòng 1, cột 1) và muốn đi đến cabin (dòng N, cột N). Họ có thể đi sang phải, trái, lên trên và xuống dưới nhưng không thể đi theo đường chéo. Hãy giúp bác John và bò Bessie tìm đường đi sao cho chênh lệch giữa điểm cao nhất và thấp nhất trên đường đi là nhỏ nhất.

 

Input

Dòng 1: Số test case

Level 3
Hugo Đào Vàng 2
Hugo đào vàng trả nợ (BFS theo so mo vang)

Sau khi ăn trộm được mật của chị ong nâu và say sưa thưởng thức mật ngọt say đắm thì bất ngờ Hugo bị chị ong nâu phát hiện. Mặc dù đã thành khẩn nhận lỗi và xin lỗi chị ong nâu nhưng do đã đánh chén gần hết số mật đã ăn chộm nên chị ong nâu vẫn bắt Hugo phải bồi thường số mật đó. Hugo thì làm sao có thể kiếm mật được vì vậy Hugo phải đi đào vàng kiếm tiền để có tiền mua mật trả cho chị ong nâu.

Một cách tình cờ Hugo có được bản đồ của một khu vực chứa vàng, bản đồ được vẽ dựa trên một ma trận NxN. Trong ma trận có các điểm chứa vàng có thể khai thác (Tối đa 4 điểm). Hàng ngày Hugo sẽ phải đi tới mỏ vàng để khai thác và cuối ngày sẽ phải mang vàng trở về. Để tiết kiệm chi phí và thời gian, Hugo quyết định cắm trại trên gần mỏ vàng để tiện khai thác vàng. Hugo không thể di chuyển qua khu vực đá và không thể cắm trại trên đá, đồng thời Hugo cũng không thể cắm trại tại khu vực mỏ vàng, thời gian để Hugo di chuyển qua mỗi ô là 1 giờ.

Hãy giúp Hugo tìm địa điểm tối ưu để đi khai thác tất cả các mỏ vàng nhanh nhất.

Level 4
Hugo Bán Dầu
Hugo được giao bán dầu trên một mạng lưới đường ống dẫn dầu, mỗi một vị trí sẽ thiết lập một loại đường ống khác nhau dựa vào địa hình. Sau khi đi khảo sát, Hugo biết rằng mạng lưới đường ống được tạo thành từ 7 loại ống như bên dưới.

1.    Dầu có thể đi từ trái sang phải từ trên xuống dưới và ngược lại.

2.    Dầu có thể đi từ trên xuống dưới và ngược lại

3.    Dầu có thể đi từ trái sang phải và ngược lại

Level 4
Hệ thống điện
Hệ thống điện

Sau khi anh VenG đã xây dựng đường đi giữa những hòn đảo, anh Eagle được cử sang để xây dựng hệ thống điện giữa các hòn đảo cho người dân, do muốn ăn bớt kinh phí nên anh Eagle không xây dựng trạm phát điện trên tất cả các đảo mà chỉ xây trên 1 số đảo nhất định. Các đảo kết nối với nhau thành 1 mạng lưới điện. Rõ ràng những đảo nào ở càng xa nguồn phát thì điện sẽ càng yếu.

Để đảm bảo người dân không than phiền điện yếu, nên anh Eagle muốn tính toán xem điện ở đảo nào sẽ yếu nhất.

Độ yếu của điện tại đảo X được tính bằng 0 nếu đảo đó có trạm phát điện, nếu đảo X có kết nối điện với đảo Y mà đảo Y ở gần trạm phát hơn, độ yếu tại đảo X = độ yếu tại đảo Y + 1. Nếu đảo X không có điện thì có độ yếu bằng vô cùng (infinity).

Level 4
Grid Acid

Một lưới hình chữ nhật có kích thước N x M. Mỗi ô được làm bằng kim loại đặc biệt (loại A) hoặc bằng đá (loại B). 

Nếu đổ axit vào một ô lưới, axit có thể làm tan chảy ô lưới (đối với loại A: ô lưới kim loại đặc biệt) và lan rộng hơn hoặc không đi qua ô lưới (đối với loại B: ô lưới đá).

Pin được làm bằng kim loại đặc biệt (loại A) có thể tan chảy trong axit trong 1 giây và do đó cho phép axit lan rộng hơn.

Bình làm bằng đá (loại B) không phản ứng với axit và do đó không nóng chảy hoặc không cho axit đi qua.

Level 4
Fast robot
Mr. Noh is responsible for enhancing the movement of a robot faster.
Now, Mr. Noh is thinking like this: The speed of the robot decreases when it changes its direction.
Therefore, it requires a study of the acceleration in direction changes.
However, the better method than that is to use the route with the minimum number of direction changes when it moves from point A to point B.


Because of that, he studies a maze.
When the maze information is given, he tries to create a program to move it from the starting point to the arriving point based on the minimized direction changes.

Level 4
Diamond
You are asked to help diagnose class diagrams to identify instances of diamond inheritance. The following example class diagram illustrates the property of diamond inheritance. There are four classes: A, B, C and D. An arrow pointing from X to Y indicates that class X inherits from class Y.


In this class diagram, D inherits from both B and C, B inherits from A, and C also inherits from A. An inheritance path from X to Y is defined as a sequence of classes X, C1, C2, C3, ..., Cn, Y where X inherits from C1, Ci inherits from Ci + 1 for 1 ≤ i ≤ n - 1, and Cn inherits from Y. There are two inheritance paths from D to A in the example above. The first path is D, B, A and the second path is D, C, A.

A class diagram is said to contain a diamond inheritance if there exists a pair of classes X and Y such that there are at least two different inheritance paths from X to Y. The above class diagram is a classic example of diamond inheritance. Your task is to determine whether or not a given class diagram contains a diamond inheritance.

Input

Level 4
Crazy King
King Peter lives in kingdom A, and his daughter in kingdom B. King received a letter telling that her daughter gave birth to a child. King is incredibly curious to see his grandchild! Unfortunately that’s not gonna be that easy.
Kingdoms A and B are separated by a forest. There are lots of enemies in the forest, and King is not that curious to see them. If they attack king on his way to kingdom B, then he will never ever see his grandchild and daughter again because of lethal consequences.

Security Council of the King disposes information about location of the enemies, which makes the things easier for king. For some unknown reason a forest is MxN chessboard. (N is the number of rows, and M is the number of columns). N,M <=100 are positive integers.

Enemies of the King can ride horses as showed in the picture. Usually horses ride (or jump) that way in Chess. Unfortunately king can’t take an airplane from point A to point B because it is not invented yet. So he moves the same way as chess-king does (refer to picture for details).   

Capture Knight

There is a mobile piece (a Knight) and a stationary piece on the N×M chessboard.
The available moves of the mobile piece are the same as set out in the image below.

You need to capture the stationary piece by moving the mobile piece with the minimum amount of moves.　　

Write a program to find out the minimum number moves to catch a piece.

[Input]

Level 4
Bao ve nong trang
Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân John muốn đặt người canh gác trên các ngọn đồi này.

Anh ta băn khoăn không biết sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt 1 người canh gác trên đỉnh của mỗi đồi. Anh ta có bản đồ của nông trang là một ma trận gồm N (1 < N <= 700) hàng và M (1 < M <= 700) cột. Mỗi phần tử của ma trận là độ cao H_ij so với mặt nước biển (0 <= H_ij <= 10,000) của ô (i, j). Hãy giúp anh ta xác định số lượng đỉnh đồi trên bản đồ.

Đỉnh đồi là 1 hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ X không quá 1 và chênh lệch tọa độ Y không quá 1.

[Input]

Level 3
Sky map
You are making “sky map” to represent constellation (group of starts) in the sky.

In each element, 1 means star, 0 means empty.

And in a constellation, each start should have at least one connection with others via left/right/up/bottom. 

If two starts are located via diagonal, then

The problem is to investigate whether there is a route from point A to point B depicted in a map as the figure shows. There can be up to two crossroads. All roads are one way and cannot be returned.

 

Create a program to determine if there is a route from point A to point B when the roads are given.

-       Points A and B are fixed with numbers 0 and 99, respectively.

-       All roads are expressed in a number pair. In the example above, the roads starting from number 2 can be expressed in (2, 5) and (2, 9).

[Problem]

There is a maze as shown in the diagram below. In the maze in the form of a 100*100 matrix, the white background represents the road while the yellow background represents the wall.

Assuming the upper left corner block to be (0, 0), the horizontal direction to be x direction and vertical direction to be y direction, the starting point of the maze is (1. 1) and the arriving point is (13, 13).

Create a program to determine if there is a path to reach the arriving point from the starting point.

In the following example, there is the path.

Level 3
Laughing Bomb
You are busy to promote a newly released film in a movie theater. The title is ‘Biochemical Laughing Bomb’ which is about terror.
Guerrillas drop a biochemical laughing bomb in the middle of a city. Once exposed, you have to laugh all your life. The bomb will contaminate four people around it during 1 second, and another four around each of them during another one second. However, you won’t be contaminated if you are not in the adjacent four directions. as the below shows the location of the bomb and affected people, and shows contamination process in seconds and you can figure out that the whole city is contaminated in 8 seconds.
In order to protect the city from the epidemic, create a program that figures out when the city will be contaminated by the bomb for the last.

Level 3
Làng mạc
Cho bản đồ mạng lưới giao thông giữa các làng mạc. Một vùng được định nghĩa là một tập hợp các làng mà từ bất kỳ một làng nào trong vùng đều có thể đi đến một làng khác trong vùng.

Hãy tính số vùng trong bản đồ, số làng cô lập (làng không có đường đi đến bất kỳ làng khác) và số con đường đóng vai trò là “Cầu” giữa hai vùng (nếu bỏ con đường này đi thì số lượng vùng tăng lên 1).

Input

Dòng đầu có một số T là số lượng test của file input. Mỗi test được bố cục như sau: dòng đầu là một số nguyên dương N (N <= 300) N là số làng, tiếp theo là một ma trân A[i, j] trong đó A[i][j] có giá trị bằng 1 là có đường đi từ làng i tới làng j và 0 nếu không có đường từ làng i tới làng j. Dữ liệu đảm bảo nếu có đường từ làng i tới làng j thì cũng sẽ có đường ngược lại.

Level 3
Find cycle
Given a directed graph, check whether the graph contains a cycle or not. Your function should return 1 if the given graph contains at least one cycle, else return 0. 

 

Input

-------------------------