Untitled

//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à

(300 + 410 + 185 + 95)2 = 980100

 



Trong ví dụ trên Hugo sẽ bị phát hiện và không thể lấy mật.

 

[Input]

- Dòng đầu tiên là số thử nghiệm T (T <= 50)

- Mỗi TC :

         + Dòng đầu tiên chưa kích thước ma trận M, N ( 3 ≤ N, M ≤ 15 )

         + Trong N dòng tiếp theo, lượng mật C ở mỗi ô sẽ được cho theo quy tắc bên dưới (0 ≤ C ≤ 1000)



5

5 3

300 410 150 55 370

120 185 440 190 450

165 70 95 420 50

5 5

356 55 41 453 12

401 506 274 506 379

360 281 421 311 489

425 74 276 371 164

138 528 461 477 470

 

[Output]

Ghi ra bình phương tổng lượng mật

Case #1

2250000

Case #2

3748096

Case #3

3928324

Case #4

7236100

Case #5

13104400














































//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

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

5.    Dầu có thể đi từ dưới sang phải và ngược lại

6.    Dầu có thể đi từ dưới sang trái và ngược lại

7.    Dầu có thể đi từ trên sang trái và ngược lại

1.     

 

 

 

 

 

 

 

 

 

 

2.

 

 

 

 

 

 

 

 

 

 

3.

 

 

 

 

 

 

 

 

 

 

4.

 

 

 

 

 

 

 

 

 

 

5.

 

 

 

 

 

 

 

 

 

 

6.

 

 

 

 

 

 

 

 

 

 

7.

 

 

 

 

 

 

 

 

 

 

 

Chỉ các đường ống có kết nối mới cho phép dầu đi qua. Hai đường ống được gọi là có kết nối nếu chúng có chung điểm cuối. Ví dụ:

- Trường hợp A có thể đi sang B

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A

B

 

- Nhưng trong trường hợp này, A không thể đi sang B vì A không có điểm cuối nào trùng với điểm cuối của B.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A

B

 

Tuy nhiên, để bán dầu, Hugo cần phải bơm dầu vào đường ống. Sức người có hạn, Hugo chỉ có thể bơm dầu trong một khoảng thời gian nhất định, mỗi một giờ dầu mới chảy được hết một đường ống. Ví dụ: Hugo có thể bơm dầu trong 3 giờ, điều đó có nghĩa là từ vị trí bơm dầu, dầu chỉ có thể chảy đến tối đa xa nhất cách đó 3 ô. Dầu có thể chảy theo bất kỳ hướng nào miễn là có kết nối

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Start

2

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

2

1 (Start)

2

3

 

 

Đưa ra một ma trận mạng lưới đường ống và vị trí bơm dầu của Hugo, giới hạn thể lực của Hugo, hãy tính toán và in ra tổng số đường ống mà dầu đã chảy qua.

 

 

[Constraints]

- Hugo luôn được đặt tại ô có đường ống dẫn dầu

 

[Input]

- Số trường hợp thử nghiệm T (T <= 50)

- Mỗi trường hợp thử nghiệp dòng đầu tiên chứa :

          + kích thước ma trận N x M (5 <= N, M <= 50)

          + vị trí Hugo (chỉ số bắt đầu từ 0)

          + thể lực của Hugo P (1 <= P <= 20)

- Chi tiết của ma trận được cho trong N hàng tiếp theo. Giá trị C trong mỗi ô là giá trị đại diện cho loại đường ống, tổng số 7 loại, 0<=C<=7, giá trị 0 nghĩa là không có đường ống.

5

5 6 2 1 3

0 0 5 3 6 0

0 0 2 0 2 0

3 3 1 3 7 0

0 0 0 0 0 0

0 0 0 0 0 0

5 6 2 2 6

3 0 0 0 0 3

2 0 0 0 0 6

1 3 1 1 3 1

2 0 2 0 0 2

0 0 4 3 1 1

10 10 4 3 9

0 0 0 0 0 0 0 0 0 0

0 0 0 7 5 0 5 0 0 0

0 0 3 2 2 6 0 0 0 0

0 4 7 2 2 2 7 0 0 4

0 3 0 1 1 2 2 0 0 5

0 5 6 1 1 1 1 6 2 5

7 4 1 2 0 0 4 6 0 0

5 3 1 7 0 2 2 6 5 7

7 3 2 1 1 7 1 0 2 7

3 4 0 0 4 0 5 1 0 1

...

 

[Output]

 

- The total number of pipes that fuel can flow to

Case #1

5

Case #2

15

Case #3

29






























//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

 

 

1

2

3

4

5

6

7

8

9

10

Vị trí

 

 

 

 

 

 

 

 

 

 

Khoảng cách

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Để 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

+ Khoảng cách từ cửa tới vị trí ngồi đối diện cửa là 1m. (Vị trí ngồi tại vị trí cửa)

+ Khi hành khách đi xa hơn một vị trí (sang trái hoặc sang phải), sẽ mất thêm 1m

Ví dụ: Vị trí cửa là 4, khoảng cách đến vị trí ngồi 4 là 1m, đến vị trí ngồi 3, 5 là 2m

3. Nếu có 2 vị trí ngồi trống gần nhất, hành khách có thể chọn bất kỳ chỗ nào (Bạn cần xem xét trường hợp này).

4. Sau khi 1 cửa được mở và hành khách đã lên tàu hết thì tiếp tục mở cửa tiếp theo cho hành khách lên tàu theo cách bên trên

 

Bạn cần tìm cách để tổng khoảng cách tất cả hành khách di chuyển là nhỏ nhất và viết ra..

Ex) Trong bảng bên dưới :

- Số lượng vị trí ngồi của tàu là : 10

- Cửa 1 : vị trí là 4, Số hành khác đang chờ lên tàu là 5

- Cửa 2 : vị trí là 6, Số hành khách đang chờ lên tàu là 2

- Cửa 3 : vị trí là 10, Số hành khách đang chờ lên tàu là 2

 

Trường hợp 1) Chúng ta mở các cửa theo thứ tự : Cửa 1 > Cửa 2 > Cửa 3

Khi cửa  1 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

Vị trí

 

G1

G1

G1

G1

G1

 

 

 

 

Khoảng cách

 

3

2

1

2

3

 

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  2 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

 

G1

G1

G1

G1

G1

G2

G2

 

 

Khoảng cách

 

3

2

1

2

3

2

3

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  3 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

 

G1

G1

G1

G1

G1

G2

G2

G3

G3

Khoảng cách

 

3

2

1

2

3

2

3

2

1

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Trong trường hợp này tổng khoảng cách hành khách di chuyển là : 3+2+1+2+3+2+3+2+1 = 19

 

Trường hợp 2) Chúng ta mở cửa theo thứ tự : Cửa 2 > Cửa 1 > Cửa 3

Khi mở cửa 2, hành khách đầu tiên sẽ chọn vị trí số 6, hành khách thứ 2 có thể chọn vị trí số 5 hoặc 7

 

 

5

6

7

Position

 

G2

G2

Khoảng cách

 

1

2

 

 

Cửa 2

 

 Hoặc

 

5

6

7

Position

G2

G2

 

Khoảng cách

2

1

 

 

 

Cửa 2

 

 

Trường hợp 2-1)

Khi cửa  2 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu (hành khách thứ 2 chọn vị trí số 5)

 

1

2

3

4

5

6

7

8

9

10

 

 

 

 

 

G2

G2

 

 

 

 

Khoảng cách

 

 

 

 

2

1

 

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  1 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G2

G2

G1

 

 

 

Khoảng cách

4

3

2

1

2

1

4

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  3 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G2

G2

G1

 

G3

G3

Khoảng cách

4

3

2

1

2

1

4

 

2

1

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Trong trường hợp này, tổng là : 4+3+2+1+2+1+4+2+1 = 20

 

Trường hợp 2-2)

Khi cửa  2 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu (hành khách thứ 2 chọn vị trí số 7)

 

1

2

3

4

5

6

7

8

9

10

 

 

 

 

 

 

G2

G2

 

 

 

Khoảng cách

 

 

 

 

 

1

2

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  1 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G1

G2

G1

 

 

 

Khoảng cách

4

3

2

1

2

1

2

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  3 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G1

G2

G1

 

G3

G3

Khoảng cách

4

3

2

1

2

1

2

 

2

1

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Trong trường hợp này, tổng là : 4+3+2+1+2+1+2+2+1 = 18

 

[Đầu vào]

- Dòng đầu tiên chứa số trường hợp thử nghiệm T (T <= 50)

- Mỗi trường hợp thử nghiệm:

          + Dòng đầu tiên chưa số ghế trên tàu N (10 <= N <= 60)

          + 3 dòng tiếp theo chưa thông tin của 3 cửa lên tàu :

                    > Vị trí cửa P ( 1 <= P <= N)

                    > Số lượng hành khách đang chờ ở cửa C ( 1 <= C <= 20 )

 

[Đầu ra]

Tổng di chuyển nhỏ nhất của tất cả các hành khách

Case #1

18

Case #2

25

Case #3

57

Case #4

86

Case #5

339








































//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.
Cho thông tin của 5 kiểu chạy của Hugo bao gồm số phút, số giây (số phút <= 6 và số giây <= 60) và số năng lượng tiêu tốn.
Hãy tính thời gian ngắn nhất để Hugo về đích mà không bị bệnh.

 

Input

Dòng đầu số test T (T<=50)

Mỗi test bao gồm 2 dòng

Dòng 1 chứa số năng lượng tối đa M <=60 và chiều dài quãng đường D<=40km
Dòng thứ 2 chứa thông tin của 5 kiểu chạy lần lượt là số phút, số giây, số năng lượng tiêu tốn

 

Output
In ra thời gian ngắn nhất để Hugo về đích mà không bị bệnh theo dạng số phút, số giây. Nếu không thể hãy in ra -1

 

Input

4

297 10

5 38 23 5 22 12 4 16 6 5 38 20 0 20 17

192 10

2 6 12 6 5 24 2 22 22 4 13 12 4 30 16

503 10

1 42 20 1 8 14 0 33 15 2 6 6 5 3 16

122 10

2 37 21 3 59 22 6 0 22 4 56 5 0 9 10

 

Output

Case #1

3 20

Case #2

21 0

Case #3

5 30

Case #4

1 30













































//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

T test case <=50

Dòng đầu tiên chưa 4 số Sx, Sy, Hx, Hy tương ứng là vị trí của công ty và nhà của Hugo trên hệ trục tọa độ Oxy

Dòng tiếp theo bao gồm số N và N cặp số liên tiếp tương ứng là tọa độ các điểm mà Hugo cần giao pizza.

N<=10

Cách tính khoảng cách giữa 2 điểm x1,y1 x2,y2    D = |x1-x2|+|y1-y2|

 

Đầu ra

In ra quãng đường ngắn nhất Hugo di chuyển từ công ty để giao bánh sau đó trở về nhà.

 

10

57 61 50 61

5 86 53 4 104 27 3 55 34 69 0

96 47 60 28

5 0 6 43 84 84 35 44 57 95 50

48 32 67 42

5 53 51 92 1 48 19 8 3 82 37

97 28 66 41

5 93 72 9 79 46 31 12 66 54 11

38 62 93 86

5 87 83 40 83 83 26 98 11 74 103

23 42 71 16

5 12 76 47 74 24 5 88 82 45 85

96 85 14 6

5 86 91 104 60 72 35 59 22 58 39

99 49 68 1

5 48 80 96 101 56 88 75 56 25 81

51 14 75 51

5 29 62 103 15 75 84 67 94 96 57

87 39 57 77

5 105 85 31 40 1 88 83 89 29 18

 

Case #1 393

Case #2 323

Case #3 267

Case #4 294

Case #5 281

Case #6 300

Case #7 219

Case #8 283

Case #9 295

Case #10 344