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


Được gửi lên bởi:sieunhan
Ngày:2009-01-23
Thời gian chạy:0.210s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED
Nguồn bài:Croatia national contest 2008

hide comments
2016-09-12 09:30:24 Nguyễn Vĩnh Thịnh
=]] đọc đề tiếng Anh trải nghiệm cảm giác LOTR
2016-07-20 15:29:43
đọc kĩ đề là hiểu ak
bài này dễ đó chứ
2016-05-19 04:26:55 Nguyen Cuong
thanks PS đã giải thích kĩ :D
2015-09-12 13:06:32
tham khảo tại: http://nhatkynghiencuu.blogspot.com/2015/07/gondor-ma-gondor-spoj.html
2015-09-10 15:31:48
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/09/10/gondor-gondor/

Last edit: 2015-10-02 03:27:06
2015-07-22 05:46:31 Do Hong Huan
Nguyên buổi sáng cài heap=>NZEC, trưa cài ma trận kề AC.
2015-05-25 01:21:07 Stupid Dog

đề mình hiểu là vậy :

Có N cái tháp, tháp thứ j có tọa độ x[j], y[j], và trong tháp có s[j] cây cung. Tại thời điểm 0, tháp 1 được thắp sáng bằng lửa. Nội dung của bài này là tháp nào có lửa thì bắn cung lửa cho những tháp khác bằng s[j] cây cung của tháp đó. Mỗi tháp có danh sách ưu tiên của N-1 tháp khác, tức là duyệt từ đầu danh sách đến cuối danh sách, tháp nào chưa có lửa thì bắn cung lửa thắp sáng tháp đó trong phạm vi s[j] cây cung. Thời gian cung lửa đến được tháp kia là khoảng cách giữa hai tháp. Thời gian bắn s[j] cây cung liên tiếp là không đáng kể. Tìm thời điểm được thắp sáng của mỗi tháp (từ không có lửa thành có lửa).

2015-05-25 00:58:19 Stupid Dog

đọc bản tiếng anh thì có vẻ dễ hiểu hơn, bản tiếng việt gây nhiều hiểu lầm và thiếu nội dung, dịch chưa sát.

bản tiếng anh thay chữ 'or' thành chữ 'of' thì có vẻ đúng hơn



Last edit: 2015-05-25 01:11:05
2013-10-31 16:15:23 Chuyên Triết Tổng Hợp
clq nhưng hôm nay là halloween
2011-03-17 02:47:51 VOJ Team
Test 2:
Tại thời điểm 0, tháp 1 truyền tin đến tháp 5, 2
Tại thời điểm 1.4, tháp 5 nhận được tin. Lúc này tháp 2, 4 chưa nhận được tin --> tháp 5 truyền đến tháp 2 4
Tại thời điểm 2.0, tháp 2 nhận được tin (từ tháp 1). Lúc này tháp 4 chưa nhận được tin --> tháp 2 truyền đến tháp 4
Tại thời điểm 2.4, tháp 4 nhận được tin (từ tháp 5). Lúc này chỉ còn tháp 3 chưa nhận được tin --> tháp 4 truyền tin đến tháp 3.
Tại thời điểm 4.4, tháp 3 nhận được tin
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.