GONDOR - mã: GONDOR - SPOJ

Link: http://vn.spoj.com/problems/GONDOR/

Vùng đất huyền thoại Gondor có một hệ thống truyền tin gồm các tháp canh để báo hiệu trong trường hợp khẩn cấp.

Khi mỗi tháp canh được báo hiệu, nhân viên truyền tin ở tháp đó sẽ ngay lập tức truyền thông tin đến tất cả các tháp chưa được nhận thông tin, và theo 1 thứ tự cho trước. Việc truyền tin xảy ra đồng thời (xem ví dụ 2: ngay khi tháp 1 nhận được tin, thông tin được truyền đến cả tháp 2 và 4 -> thời gian tháp 2 nhận được tin là 2). Tuy nhiên nhân viên truyền tin ở tháp i chỉ có thể truyền thông tin tới không quá s[i] tháp khác. Thời gian để truyền tin giữa 2 tháp bằng khoảng cách giữa 2 tháp đó. Tại thời điểm 0, thông tin bắt đầu được truyền từ tháp 1. Tính thời gian để mỗi tháp nhận được thông tin.

Input

Dòng đầu tiên: N (1<=N<=100) là số lượng tháp. Các tháp đánh số từ 1 đến N.

N dòng tiếp theo, dòng thứ i gồm:

+ Số nguyên X và Y (1<=X,Y<=1000) là tọa độ của tháp trong hệ toạ độ

+ Số nguyên S (1<=S<=100) là số tháp mà tháp đó có thể truyền tin đi

+ N-1 số nguyên phân biệt trong khoảng 1 đến N, là danh sách các tháp mà nhân viên ở tháp i được yêu cầu truyền tin. Nhân viên truyền tin ở tháp này sẽ phải lần lượt truyền thông tin đi theo thứ tự trong danh sách. Không có 2 số nào trùng nhau trong danh sách, và trong danh sách thứ i không chứa số i

Dữ liệu đảm bảo không có 2 tháp nào nhận được tin tại cùng 1 thời điểm.

Output

Gồm N dòng, mỗi dòng chứa một số thực. Dòng thứ i chứa thời gian mà tháp thứ i nhận được thông tin. Kết quả của bạn sẽ được tính là chính xác nếu kết quả sai khác không quá 0.01 so với đáp án.

Example

Input:

4

1 1 1 2 3 4

1 2 1 4 1 3

2 1 1 2 1 4

2 2 1 3 2 1

Output:

0.000000

1.000000

3.000000

2.000000

Input:

5

4 3 2 5 2 4 3

4 5 1 4 1 5 3

4 4 1 1 4 5 2

2 4 1 5 2 3 1

3 4 2 2 4 3 1

Output:

0.000000

2.000000

4.414214

2.414214

1.414214

HƯỚNG LÀM: GONDOR

ĐOẠN CHƯƠNG TRÌNH THAM KHẢO: GONDOR.PAS

Mảng A[u,v] (1<=v<=n-1) là danh sách ưu tiên của tháp canh thứ u

Continue Reading

QUÂN TƯỢNG (VOI06) - mã: QBBISHOP - SPOJ

Link: http://vn.spoj.com/problems/QBBISHOP/

================================================

Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải.

Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (r_i, c_i), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân

Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t). Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có 2 trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá 2 nước đi. Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy.

Yêu cầu: Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.

Input

Dòng đầu tiên chứa 6 số nguyên n, m, p, q, s, t.

Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Gồm 1 dòng duy nhất là số nước đi tìm được

Example

Input:

8 3 7 2 1 4

5 4

3 4

4 7

Output:

3

Hạn chế:

Trong tất cả các test: 1 ≤ n ≤ 200. Có 60% số lượng test với n ≤ 20.

Solution

Code

Continue Reading

ROBOT CỨU HỎA - mã: QBROBOT - SPOJ

Link: http://vn.spoj.com/problems/QBROBOT/
======================================

Trên một mạng lưới giao thông có n nút, các nút được đánh số từ 1 đến n và giữa hai nút bất kỳ có không quá một đường nối trực tiếp (đường nối trực tiếp là một đường hai chiều). Ta gọi đường đi từ nút s đến nút t là một dãy các nút và các đường nối trực tiếp có dạng:

s = u₁, e₁, u₂,..., u_i, e_i, u_i+1, ..., u_k-1, e_k-1, u_k = t,

trong đó u₁, u₂, …, u_k là các nút trong mạng lưới giao thông, e_i là đường nối trực tiếp giữa nút u_i và u_i+1(không có nút u_j nào xuất hiện nhiều hơn một lần trong dãy trên, j = 1, 2, …, k).

Biết rằng mạng lưới giao thông được xét luôn có ít nhất một đường đi từ nút 1 đến nút n.

Một robot chứa đầy bình với w đơn vị năng lượng, cần đi từ trạm cứu hoả đặt tại nút 1 đến nơi xảy ra hoả hoạn ở nút n, trong thời gian ít nhất có thể. Thời gian và chi phí năng lượng để robot đi trên đường nối trực tiếp từ nút i đến nút j tương ứng là t_ij và c_ij (1 ≤ i, j ≤ n). Robot chỉ có thể đi được trên đường nối trực tiếp từ nút i đến nút j nếu năng lượng còn lại trong bình chứa không ít hơn c_ij (1 ≤ i, j ≤ n). Nếu robot đi đến một nút có trạm tiếp năng lượng (một nút có thể có hoặc không có trạm tiếp năng lượng) thì nó tự động được nạp đầy năng lượng vào bình chứa với thời gian nạp coi như không đáng kể.

Yêu cầu: Hãy xác định giá trị w nhỏ nhất để robot đi được trên một đường đi từ nút 1 đến nút n trong thời gian ít nhất.

Input

Dòng đầu tiên chứa một số nguyên dương n (2 ≤ n ≤ 500);

Dòng thứ hai chứa n số, trong đó số thứ j bằng 1 hoặc 0 tương ứng ở nút j có hoặc không có trạm tiếp năng lượng (j = 1, 2, …, n);

Dòng thứ ba chứa số nguyên dương m (m ≤ 30000) là số đường nối trực tiếp có trong mạng lưới giao thông;

Dòng thứ k trong số m dòng tiếp theo chứa 4 số nguyên dương i, j, t_ij, c_ij (t_ij, c_ij ≤ 10000) mô tả đường nối trực tiếp từ nút i đến nút j, thời gian và chi phí năng lượng tương ứng.

Hai số liên tiếp trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách.

Output

Ghi ra số nguyên dương w tìm được.

Example

Input:

4

0 1 1 0

5

1 2 5 4

1 3 4 3

1 4 9 4

2 4 4 1

3 4 5 2

Output:

3

Code: QBROBOT
Solution: Robot Cứu Hỏa

Continue Reading

MẤT ĐIỆN - mã: PWRFAIL - SPOJ

Link: http://vn.spoj.com/problems/PWRFAIL/
===========================================

Một cơn bão đã phá hủy 1 số đường dây điện của nông trang! Nông dân John có một bản đồ tất cả N (2 <= N <= 1,000) cây cột điện, để thuận tiện ta đánh số các cột này từ 1->N, mỗi cột này được xác định trên mặt phẳng bởi 2 số nguyên x_i, y_i (-100,000 <= x_i <= 100000; -100,000 <= y_i <= 100,000).

Hiện đang có W (1 <= W <= 10,000) đường dây điện nối các cặp cột điện Pi và Pj (1 <= Pi <= N; 1 <= Pj <= N). John cần mang điện từ cột 1 tới cột N (thông qua các đường dây điện và các cột điện khác).

Cho tọa độ của N cột điện và danh sách những đường dây điện vẫn còn hoạt động. Hãy xác định độ dài nhỏ nhất của các đường dây điện cần thêm để sao cho điện từ cột 1 có thể truyền tới cột N. Biết rằng độ dài tối đa của 1 đường dây điện là 1 số thực M (0.0 < M <= 200,000.0).

Ví dụ, dưới đây là bên trái là bản đồ 9 cột điện và 3 dây nối vẫn còn hoạt động sau cơn bão. Trong ví dụ này, M = 2.0. Cách tốt nhất là ta thêm 2 đường dây điện nối 4-6 và 6-9.

      Sau cơn bão                   Phương án tối ưu

3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .

                                          /

2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .

                                        /

1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .

   |                               |

0  1 . . . . . . . . .          0  1 . . . . . . . . .

   0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9

Tổng độ dài là 1.414213562 + 1.414213562 = 2.828427124 .

DỮ LIỆU

• Dòng 1: Hai số nguyên cách nhau bởi dấu cách: N và W
• Dòng 2: Một số thực: M
• Dòng 3..N+2: Mỗi dòng gồm 2 số nguyên cách nhau bởi dấu cách: x_i và y_i
• Dòng N+3..N+2+W: 2 số nguyên cách nhau bởi dấu cách: Pi và Pj

KẾT QUẢ

• Dòng 1: Một số nguyên trên 1 dòng. Nếu không có phương án để cấp điện cho cột N từ cột 1 thì ghi ra -1. Ngược lại, ghi ra 1 số nguyên là tổng độ dài nhỏ nhất nhân với 1000.
• Chú ý không làm tròn, làm giảm tích thu được ở trên.

VÍ DỤ

Dữ liệu

9 3

2.0

0 0

0 1

1 1

2 1

2 2

3 2

3 3

4 1

4 3

1 2

2 3

3 4

Kết quả

2828

==========================================================

Hướng dẫn:

- Trước hết ta xây dựng ma trận kề, tức là tính độ dài dây điện từ cột i đến cột j (1<=i,j<=N) (tính dựa vào tọa độ)

==> độ dài vector AB(x,y) = SQRT(x*x+y*y)

nếu độ dài dây từ cột i tới cột j lớn hơn M thì ta bỏ, gán giá trị đó cho 1 giá trị cực lớn nào đó....

- Đối vời những đường dây còn hoạt động thì độ dài coi như bằng 0......

- Sử dụng Dijkstra tìm đường ngắn nhất từ 1->N......

- ghi kết quả: nhân kết quả cho 1000 và sử dụng hàm trunc để lấy phần nguyên (ức chế cái này, tại nó mà làm hoài không AC, đau khổ >.<)

Continue Reading

THAM QUAN THÀNH CỔ - mã: TTRIP - SPOJ

Link: http://vn.spoj.com/problems/TTRIP/
===================================

Trong kì thi IOI tại Thái Lan vừa qua, sau 2 ngày làm bài đầy căng thẳng, Tuệ cùng các thí sinh khác được đi tham quan Thành Cổ (Ancient City), 1 địa danh du lịch khá nổi tiếng nơi đây.Thành Cổ ngoài lối vào (được đánh số 1) và lối ra (được đánh số N), được chia ra làm N-2 khu vực khác nhau (được đánh số từ 2 đến N-1), mỗi khu vực được xây dựng theo 1 lối kiến trúc riêng vô cùng độc đáo. Giữa các khu vực này có thể có các lối đi, được biểu diễn bằng ma trận A.

Hành trình của Tuệ sẽ bắt đầu từ lối vào, tham quan các khu vực trong Thành Cổ và kết thúc ở lối ra. Là 1 người yêu thích chụp ảnh, Tuệ chắc chắn sẽ không bỏ qua 1 khu vực nào nếu cậu ta có thể đến được nó thông qua các con đường. Tại mỗi địa điểm, nếu còn ít nhất 1 khu vực Tuệ có thể đến được nhưng vẫn chưa đến tham quan, cậu ta sẽ chọn khu vực gần nhất so với vị trí hiện tại của cậu ta (có thể di chuyển qua các khu vực đã tham quan rồi hoặc lối vào, lối ra). Nếu có nhiều hơn 1 khu vực thỏa yêu cầu, Tuệ sẽ chọn khu vực có số thứ tự nhỏ nhất.

Hãy tính tổng độ dài đường đi trong chuyến tham quan của Tuệ. Luôn đảm bảo có ít nhất 1 cách để Tuệ di chuyển từ lối vào đến lối ra.

Input

Dòng 1: số nguyên N
Dòng 2...N+1: dòng thứ i+1 chứa N số nguyên A_i,1 A_i,2 ... A_i,n ; trong đó A_i,j > 0 nếu có lối đi và A_i,j = 0 nếu không có ( với mọi i khác j, luôn đảm bảo A_i,j = A_j,i và A_i,i = 0 )

Output

Tổng độ dài chuyến tham quan của Tuệ

Constraints

2 ≤ N ≤ 100
0 ≤ A ≤ 10⁶

Example

Input:
5
0 3 2 0 0
3 0 2 4 5
2 2 0 1 0
0 4 1 0 2
0 5 0 2 0

Output:

11

Giải thích:  Thứ tự các khu vực tham quan là 3, 4, 2. Hành trình cụ thể: 1 → 3 → 4 → 3 → 2 → 5.

==============================

Thuật giải:

- Floyd

- tham lam tìm đường đi

Continue Reading