Level 4
Turn Over Game

Như trong, có một cái bàn kích thước 4×4. Trong một lưới của bàn, có những viên đá màu trắng hoặc đen. Khi bạn chọn một vị trí của viên đá ngẫu nhiên, viên đá và bốn viên đá liền kề với các mặt trên, dưới, trái và phải của viên đá sẽ chuyển sang màu đối diện giống như biến một viên đá trắng thành đen và một viên đá đen thành trắng. Giả sử quá trình này như một phép tính.

Sử dụng phép tính như vậy, bạn muốn đổi tất cả các viên đá trên bàn thành toàn màu trắng hoặc toàn màu đen. Tìm số lượng thao tác tối thiểu tại thời điểm này.

Giới hạn thời gian: 1 giây (java: 2 giây)

[Đầu vào]

Level 4
Tuần Trăng Mật (2 dong endl)
Tuần trăng mật

Đám cưới anh Uranus diễn ra rất vui vẻ, chỉ có Tomoky là có chút hậm hực. Sau đám cưới, anh Uranus muốn đi tuần trăng mật ở thành phố Đà Lạt xinh đẹp.

Thành phố Đà Lạt gồm n điểm du lịch trọng điểm, được đánh số từ 1 tới n. Hệ thống giao thông trong vùng gồm m (m <= n*(n-1)) tuyến đường một chiều khác nhau, tuyến đường thứ j (j = 1,2,…m) cho phép đi từ địa điểm u_j tới địa điểm v_j với chi phí đi lại là số nguyên dương c(u_j, v_j).

Anh Uranus muốn xuất phát từ điểm du lịch 1 và đi thăm k địa điểm du lịch s_1, s_2, …, s_k (khác địa điểm 1) và sau đó quay về địa điểm xuất phát 1 với tổng chi phí là nhỏ nhất.

Level 4
Tiết Kiệm Điện
Tiết kiệm điện

Văn phòng APS hiện tại đang có N bóng đèn và có K khóa. Các khóa được nối vào các bóng đèn theo quy luật như sau:

Khóa thứ K sẽ được nối vào các bóng đèn thứ K+n(K+1) (n>=0; 0<=K+n(K+1) <=N).

Ví dụ:

Level 4
Qua Cầu
Có 1 số cây cầu làm bằng gỗ. Trải qua 1 thời gian,những  cây cầu trở nên hư hại và xuất hiện những lỗ thủng trên đó. Được biết những cây cầu đó luôn có độ rộng M = 5(bước đi) và độ dài trong khoảng3

Công việc:

Có 1 người luôn luôn đứng giữa ở 1 phía của cây cầu. Nhiệm vụ của bạn là phải đưa người đó qua được cầu với số đồng xu nhặt được là lớn nhất. Được biết trên cầu có 1 số đồng xu bị đánh rơi và người đó chỉ có thể đi thẳng, đi chéo trái hoặc đi chéo phải. Ngoài ra người đó có mang 1 tấm ván. Nó có thể vá được 1 lỗ thủng trên cầu giúp người đó có thể đi qua được.

Lưu ý : không có nhiều hơn 1 đồng xu tại 1 địa điểm.

evel 4
Prime Ring
Một vòng gồm N phần tử hình tròn. Trong mỗi hình tròn sẽ chứa một số nguyên P và tổng hai số nguyên trong hai hình tròn cạnh nhau trên vòng tròn tạo thành một số nguyên tố. Nhiệm vụ của bạn là với một chuỗi gồm N phần tử số nguyên, đưa ta tổng số cách xếp N phần tử đó vào vòng tròn thỏa mãn yêu cầu trên.

Ví dụ

Ta có đầu vào là một dãy gồm 6 phần tử: 1, 2, 3, 4, 5, 6. Thì đầu ra sẽ có 2 cách xếp là cách 1: 1 - 4 - 3 - 2 - 5 - 6 và cách 2: 1 - 6 - 5 - 2 -  3 - 4

Input

Cấp độ 4
Pizza Location - Địa điểm Pizza
Người bạn Picko của chúng tôi rất có tầm với và anh ấy muốn mở nhiều nhà hàng giao hàng tận nơi. Món ăn chính tất nhiên sẽ là pizza. Anh ấy có một số địa điểm tiềm năng cho các nhà hàng và anh ấy biết vị trí của các quán bar solitaires với nhiều người thường là khách hàng của anh ấy. Việc giao hàng của mỗi nhà hàng sẽ bao phủ tất cả các quán bar solitaires trong bán kính nhất định.

Picko chỉ có thể mở một số lượng nhà hàng hạn chế và anh muốn các nhà hàng đó nằm ở những địa điểm có thể phục vụ được nhiều người nhất trong trò chơi một người.

Viết chương trình tính số người tối đa mà chúng ta có thể giao hàng.

 

Level 4
Painting

Nhóm thiết kế tại SAMSUNG Electronics đang cân nhắc một thiết kế sáng tạo cho sản phẩm mới.

Hình bên trái là sơ đồ cơ bản và nhóm thiết kế cố gắng phân biệt từng khu vực được đánh dấu bằng chữ cái trong bảng chữ cái bằng bốn màu.

Khi tiến hành, nhóm thiết kế theo đuổi sự hoàn hảo bằng cách nghiên cứu sự kết hợp của tất cả các màu sắc và chọn một trong số chúng.

Tuy nhiên, họ gặp khó khăn vì không biết tổng số trường hợp kết hợp màu sắc.

Level 4
Nâng cấp máy tính
Time limit: 1 giây với C/C++, 2 giây với Java.

Submission limit: 5 lần.

Memory limit: 256MB cho tổng cộng các vùng nhớ heap, global và static (chỉ 1MB cho vùng nhớ stack).

Level 4
Mời Đám Cưới
Mời đám cưới

Anh Uranus sắp tổ chức đám cưới, hôm nay anh muốn đi phát thiệp mời đến những người bạn trong team. Thấy Uranus đi mời cưới nên Tomoky giả vờ đi ra ngoài có việc để trốn. Uranus rất tức và quyết tâm tìm được Tomoky để mời.

Giả sử đường đi trong công ty tạo thành 1 đồ thị và, giữa hai điểm bất kỳ đều tồn tại đường đi trực tiếp hoặc gián tiếp thông qua một số điểm trung gian.

Do hỏi anh VenG nên anh Uranus biết trước điểm bắt đầu và điểm kết thúc trên đường đi của Tomoky, nhưng anh lại không biết Tomoky sẽ đi đường nào, do đó anh muốn tìm những điểm mà anh Tomoky bắt buộc phải đi qua trong hành trình của mình (trừ điểm đầu và điểm cuối)

Level 4
Mario Climb


Mario cần phải di chuyển từ vị trí có giá trị bằng 2 và ăn vàng ở ô có giá trị bằng 3

0 là nhữngô Mario không thể qua

1 là nhữngô Mario có thể qua

Level 4
Little Elephants

Level 4
Little Elephants
The Little Elephant and his friends from the Zoo were returning from the party. But suddenly they were stopped by the policeman Big Hippo, who wanted to make an alcohol test for elephants.

There were N elephants ordered from the left to the right in a row and numbered from 0 to N-1.Let R[i] to be the result of breathalyzer test of i-th elephant.

Considering current laws in the Zoo, elephants would be arrested if there exist K consecutive elephants among them for which at least M of these K elephants have the maximal test result among these K elephants.

Level 4
Hugo về nhà
 

Hugo đang trền đường về nhà và cần đi qua 1 đoạn đường B.

Trên đoạn đường đi qua có N cổng. Tại mỗi cổng có 1 số lượng binh sĩ và giá để đi qua cổng đó. Muốn đi qua mỗi cổng Hugo có 3 cách lựa chọn.

1. Pass

Level 4
Hugo thi chạy
Hugo thi chạy

Sắp tới công ty nên Hugo làm việc tổ chức sự kiện Olympic dành cho toàn bộ nhân viên. Có rất nhiều bộ môn thi đấu như Bóng bàn, cầu long, cờ vua, cờ tướng, bơi lội, và có cả thể thao điện tử nữa. Là một người quan tâm tới sức khỏe của bản thân vì vậy Hugo thường xuyên chạy bộ để rèn luyện sức khỏe. Thật may trong các môn thi đấu Olympic có hạng mục này. Trong quá trình tập luyện Hugo đã luyện cho mình được 5 kiểu chạy khác nhau, mỗi kiểu chạy sẽ tiêu tốn số lượng năng lượng nhất định và thời gian chạy hết 1km là khác nhau. Mỗi kiểu chạy sẽ sử dụng cho 1km.

Năng lượng của Hugo là có hạn, nếu sử dụng vượt Hugo sẽ bị bệnh.


Sau khi tham khảo thông tin Hugo biết được quãng đường cần chạy bộ D của cuộc thi. Nhân viên y tế có thể giúp Hugo tính toán được số năng lượng tối đa của Hugo.

Level 4
Hugo quản lý tàu

Trên một con tàu có N vị trí ngồi, Có 3 cửa để lên tàu. Hành khách đang đợi ở mỗi cửa là khác nhau

Để tránh xung đột và rối loạn, hành khách lên tàu cần thực hiện như sau:
1. Chỉ 1 cửa được mở tại một thời điểm, khi cửa mở tất cả hành khách sẽ được lên tàu.

2. Khi cửa mở, lần lượt hành khách sẽ được lên tàu, và hành khách sẽ đi tới vị trí trống gần nhất từ vị trí cửa

Level 4
Hugo Giao Hàng
Hugo Giao Hàng

Hugo đang làm việc cho công ty Samsung, tuy mức lương ở Samsung không hề nhỏ nhưng vì Hugo là lao động duy nhất trong nhà, vợ của Hugo mới sinh em bé. Hugo muốn kiếm thêm thu nhập để có thể có thêm tiền sữa, bỉm cho con. Hugo quyết định nhận giao bánh pizza ngoài giờ làm. Mỗi ngày, sau khi tan ca Hugo sẽ nhận N chiếc bánh pizza để giao tới N địa điểm khác nhau sau đó trở về nhà. Tuy nhiên do giá xăng dầu đang leo thang, Hugo cần phải giảm tối đang lượng xăng phải tiêu thụ, vì vậy Hugo muốn tính toán xem quãng đường đi giao bánh pizza từ công ty sau đó về nhà là ngắn nhất.

Hãy giúp Hugo với nhé.

Đầu vào

Level 4
Hugo và chị ong nâu nấu nâu nấu lầu nâu
Hugo và chị ong nâu là hàng xóm của nhau. Tuy nhiên Hugo thì lười nhưng lại muốn lấy mật ăn, còn chị ong nâu thì chăm chỉ kiếm mật để đầy tổ của mình. Vì thèm ăn mật ong mà mãi chị ong nâu không cho nên sau 1 thời gian nằm gai nếm mật rình mò Hugo đã phát hiện ra các bố trí của các thùng chứa mật và số mật trong mỗi thùng ở nhà chị ong nâu. Mật ở nhà chị ong nâu được biểu diễn bằng 1 ma trận NxM ô, mỗi ô một thùng mật. Mỗi ô chứa lượng mật nhất định và có thể liên kết với 6 ô xung quanh theo cách bố trí của tổ ong. 2 ô được gọi là có liên kết nếu chúng có chung cạnh.

Hôm nay Hugo phát hiện chị ong nâu đi sang khu rừng bên cạnh để lấy mật. Hugo sẽ vào nhà chị ong nâu để ăn trộm mật ong của chị. Để không bị phát hiện Hugo chỉ có thể lấy tối đa 4 thùng ở 4 ô có liên kết với nhau. Hãy giúp Hugo tìm ra bình phương tổng lượng mật lớn nhất có thể lấy.

Ex: M = 5 , N = 3

Trong ví dụ trên, bình phương tổng lượng mật là

Level 4
Hugo

Có thử thách dành cho Hugo như sau: Hugo được thả vào 1 khu rừng có rất nhiều kim cương, tuy nhiên đồng thời lúc đó có các đám cháy xuất hiện. Các đám cháy này sẽ lây lan ra các khu vực lân cận theo bốn hướng sau 1 giờ. Tuy nhiên trong khu rừng có một số hồ nhỏ, và lửa không thể cháy lan trên hồ.

Thời gian để Hugo di chuyển giữa các khu đất là 1 giờ, qua khu hồ là 2 giờ. Hãy giúp Hugo thoát khỏi khu rừng cùng với số lượng kim cương lớn nhất có thể và đảm bảo Hugo không bị lửa thiêu.

Lưu ý khu rừng chỉ tồn tại một số lượng nhất định lối thoát, tại danh giới của khu rừng, và Hugo không bao giờ quay lại khu vực mình đã đi qua.

Input

Level 4
8-Queen: Maximum Score

Vua Narnia không có con, vì vậy ông đã quyết định rằng đất nước sẽ được chia thành  k phần riêng biệt sau khi ông qua đời và mỗi phần sẽ được  thừa kế bởi bất kỳ ai thực hiện tốt nhất trong một số bài kiểm tra. Bất kỳ cá nhân nào cũng có thể thừa kế nhiều hơn một hoặc thậm chí là tất cả các phần. Để đảm bảo rằng chỉ những người cực kỳ thông minh cuối cùng mới trở thành người kế vị của mình, Nhà vua đã nghĩ ra một bài kiểm tra khéo léo. Trong một hội trường lớn có đặt k  bàn cờ vua . Mỗi bàn cờ có các số từ 1 đến 99 được viết trên mỗi ô vuông và được cung cấp 8 quân hậu cờ vua. Nhiệm vụ mà mỗi người kế vị tiềm năng phải đối mặt là đặt 8 quân hậu trên bàn cờ vua theo cách mà không có quân hậu nào đe dọa đến quân hậu khác và sao cho tổng các số trên các ô vuông được chọn như vậy bằng một số ít nhất là cao bằng một số mà Nhà vua đã chọn . 

Lưu ý: Theo luật cờ vua, mỗi hàng và cột của bàn cờ có đúng một quân hậu, và mỗi đường chéo không có quá một quân hậu.  

Viết chương trình nhập vào số lượng và thông tin chi tiết của các bàn cờ và xác định điểm số cao nhất có thể cho mỗi bàn cờ trong những điều kiện này.

Đầu vào

Level 4
Đi Ăn Cưới
Đi ăn cưới

Do không trốn được Uranus nên Tomoky đành ngậm ngùi nhận thiệp và hôm nay là ngày cưới của Uranus, anh dậy từ rất sớm để đến công ty đón xe đi ăn cưới.

Đường đi từ công ty đến nhà anh Uranus được biểu diễn bằng 1 đồ thị.

Có N đỉnh được nối với nhau bằng M đường một chiều, các đỉnh đánh số từ 1 đến N. Giả sử công ty là đỉnh 1, nhà anh Uranus - nơi tổ chức đám cưới là đỉnh 2.

Level 4
Cover rectangle with dominos

Bạn được cung cấp 28 loại domino khác nhau, mỗi loại domino có kích thước 1x2 với 2 số trên đó như sau
0 0, 0 1, 0 2, 0 3, 0 4, 0 5, 0 6, 1 1, ..., 5 6, 6 6.

Và một bàn cờ có kích thước 7x8, nhiệm vụ của bạn là phủ kín bàn cờ bằng các quân domino sao cho chỉ có thể đặt một quân domino lên hai ô vuông liền kề trên bàn cờ nếu số ô vuông và số quân domino bằng nhau.

Có bao nhiêu cách khác nhau để che bảng?

Level 4
Connect processors
Bộ xử lý di động mới được phát triển Maxinos của Samsung có số lượng ô là N x N.

Trong 1 cell có thể có 1 lõi hoặc 1 dây dẫn điện.

Nguồn điện chạy dọc theo rìa Maxinos.

Dây kết nối lõi và nguồn điện chỉ có thể được lắp theo đường thẳng.

Level 4
Cleaning Robot
We have to plan a path for a cleaning robot to clean a rectangular room floor of size NxM. The room floor paved with square tiles whose size fits the cleaning robot (1 × 1). There are clean tiles and dirty tiles, and the robot can change a dirty tile to a clean tile by visiting the tile. Also there may be some obstacles (furniture) whose size fits a tile in the room. If there is an obstacle on a tile, the robot cannot visit it. The robot moves to an adjacent tile with one move. The tile onto which the robot moves must be one of four tiles (i.e., east, west, north or south) adjacent to the tile where the robot is present. The robot may visit a tile twice or more.

Your task is to write a program which computes the minimum number of moves for the robot to change all dirty tiles to clean tiles, if ever possible.

Time limit: 1s (C/C++), 2s (Java)

Submit limit: 10 times

Level 4
Chess rook

Trong cờ vua, quân xe là quân cờ có thể di chuyển bất kỳ số ô nào theo chiều dọc hoặc chiều ngang.

Trong bài toán này, chúng ta sẽ xem xét những bàn cờ nhỏ (tối đa là 4 × 4) có thể chứa những bức tường mà quân xe không thể di chuyển qua.

Mục tiêu là đặt càng nhiều quân xe lên bàn cờ càng tốt sao cho không có quân xe nào có thể bắt được nhau.

Một cấu hình quân xe được coi là hợp lệ với điều kiện không có hai quân xe nào nằm trên cùng một hàng ngang hoặc cột dọc trừ khi có ít nhất một bức tường ngăn cách chúng.

Level 4
Checking cube
Given a integer N. Find number of possible ways to represent N as a sum of at most five cubes.

Input

First line contains N.

1<=N<=125000.

Level 4
Biểu thức Zero
Cho một số tự nhiên N ≤ 9. Giữa các số từ 1 đến N hãy thêm vào các dấu + và - sao cho kết quả thu được bằng 0. Hãy viết chương trình tìm tất cả các khả năng có thể.

[Input]

Dòng đầu tiên là T số testcase. T dòng tiếp theo là các số tự nhiên N <= 9.