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

CÁC THÙNG NƯỚC - mã: IOIBIN - SPOJ

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

Có N thùng nước được đánh số từ 1 đến N, giữa 2 thùng bất kỳ đều có một ống nối có một van có thể khóa hoặc mở. Ở trạng thái ban đầu tất cả các van đều đóng.

Bạn được cho một số yêu cầu, trong đó mỗi yêu cầu có 2 dạng:

Dạng X Y 1 có ý nghĩa là bạn cần mở van nối giữa 2 thùng X và Y.

Dạng X Y 2 có ý nghĩa là bạn cần cho biết với trạng thái các van đang mở / khóa như hiện tại thì 2 thùng X và Y có thuộc cùng một nhóm bình thông nhau hay không? Hai thùng được coi là thuộc cùng một nhóm bình thông nhau nếu nước từ bình nàycó thể chảy đến được bình kia qua một số ống có van đang mở.

Input

Dòng đầu tiên ghi một số nguyên dương P là số yêu cầu.

Trong P dòng tiếp theo, mỗi dòng ghi ba số nguyên dương X, Y, Z với ý nghĩa có yêu cầu loại Z với 2 thùng X và Y.

Output

Với mỗi yêu cầu dạng X Y 2 (với Z = 2) bạn cần ghi ra số 0 hoặc 1 trên 1 dòng tùy thuộc 2 thùng X và Y không thuộc hoặc thuộc cùng một nhóm bình.

Example

Input:

9

1 2 2

1 2 1

3 7 2

2 3 1

1 3 2

2 4 2

1 4 1

3 4 2

1 7 2

Output:

0

0

1

0

1

0

Giới hạn

• 1 ≤ N ≤ 10000
• 1 ≤ P ≤ 50000

Solution: IOIBIN

Code: IOIBIN.PAS

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

MẠNG TRUYỀN THÔNG (VOI 2013) - mã: COMNET - SPOJ

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

   Tổng công ty Z gồm N công ty con, đánh số từ 1-N. Mỗi công ty con có một máy chủ. Để đảm bảo truyền tin giữa các công ty, Z thuê M đường truyền tin để kết nối N máy chủ thành một mạng máy tính của Tổng công ty. Không có 2 đường truyền nối cùng 1 cặp máy chủ. Đường truyền i nối máy chủ của 2 công ty u_i, v_i có chi phí là w_i. Mạng máy tính có tính thông suốt, nghĩa là từ một máy chủ có thể truyền tin đến một máy chủ bất kì khác bằng đường truyền trực tiếp hoặc qua nhiều đường trung gian.

    Một đường truyền gọi là không tiềm năng nếu như : một mặt, việc loại bỏ đường truyền này không làm mất tính thông suốt; mặt khác, nó phải có tính không tiềm năng, nghĩa là không thuộc bất cứ mạng con thông suốt gồm N máy chủ và N-1 đường truyền tin với tổng chi phí thuê bao nhỏ nhất nào của mạng máy tính.

    Trong thời gian tới, chi phí thuê bao của một số đường truyền tin thay đổi. Tổng công ty muốn xác định với chi phí mới thì đường truyền thứ k có là đường không tiềm năng hay không để xem xét chấm dựt việc thuê đường truyền này.

Input

• Dòng đầu là T – số testcase. T nhóm dòng, mỗi nhóm cho thông tin về một testcase.
• Dòng thứ nhất gồm 3 số nguyên dương N, M, Q (Q <= 30).
• Dòng thứ i trong M dòng tiếp theo chứa 3 số nguyên dương u_i, v_i, w_i (u_i ≠ v_i, w_i < 10⁹).
• Dòng thứ j trong Q dòng tiếp theo mô tả giả định thứ j:
• Số đầu tiên là chỉ số k_j của đường truyền tin cần xem xét
• Tiếp theo là s_j ( s_j <= 100) cho biết số lượng đường truyền có chi phí thuê mới
• Cuối cùng là s_j cặp số nguyên dương t_p, c_p cho biết đường truyền thứ t_p có chi phí thuê mới là c_p(c_p < 10⁹).

Output

• Gồm T nhóm dòng, mỗi nhóm gồm Q dòng. Mỗi dòng là câu trả lời cho giả định tương ứng trong input. Ghi YES nếu câu trả lời là khẳng định và NO trong trường hợp ngược lại.

Example

Input:

1

3 3 2

1 2 1

1 3 2

2 3 3

3 2 2 4 3 4

1 1 1 4

Output:

NO

YES

Giới hạn

- 30% số test đầu có 1 ≤ N ≤ 100;

- 30% số test tiếp theo có 1 ≤ N ≤ 10⁴ và 1 ≤ M ≤ 10⁵;

- 40% số test còn lại có 1 ≤ N ≤ 10⁵ và 1 ≤ M ≤ 10⁶.

Hướng làm: COMNET

Code tham khảo: COMNET.PAS

Continue Reading

ROBIN - mã: C11BC2 - SPOJ

LINK: http://vn.spoj.com/problems/C11BC2/

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

           Một ngày đẹp trời nọ, trên vương quốc của các Coders 2011, bỗng xuất hiện 1 lão phù thủy độc ác, lão phù thủy sirDat_LS đã có âm mưu thôn tính đất nước  của đức vua vodanh9x. Lão phù thủy này rất yêu con gái của đức vua là Rose và đã bắt Rose về nơi ở của lão ta.

            Đức vua vodanh9x liền tìm hiệp sĩ Robin và sẽ hứa gả con gái cho Robin nếu chàng cứu được công chúa Rose trở về. Lão phù thủy sirDat_LS độc ác với khuôn mặt rất ghê tởm khiến công chúa mỗi khi nhìn thấy hắn thì công chúa lại ngất đi.

            Và rồi, chàng Robin của chúng ta đã tìm được đến nơi ở của lão phù thủy. Nơi ở của lão là 1 mê cung có N phòng, và N phòng này liên thông với nhau và có đúng N-1 đường đi (coi mỗi đường đi là 1 cạnh).

            Nhưng khó khăn thay, lão phù thủy đã đánh số mỗi đường đi là 1 hoặc 2. Nếu chàng Robin muốn đến cứu công chúa, thì từ nơi xuất phát đến nơi có công chúa phải có ít nhất một đường đi được đánh số 2, nếu không chàng Robin sẽ chết.

            Yêu cầu: Cho m truy vấn (m <= 10^5) mỗi truy vấn có dạng (x,y), trong đó x là nơi xuất phát của Robin và y là nơi nhốt công chúa. Xác định đường đi ngắn nhất từ x đến y có cạnh co trọng số 2 hay không.

Input

-Dòng đầu là số nguyên N (N <= 10^4) - số đỉnh của đồ thị và M  – số truy vấn.

-Từ dòng 2 đến dòng N: dòng thứ i chứa 2 số nguyên dương  x (x < i) và k (k <= 2) nghĩa là có cạnh nối giữa i và x và được đánh số là k.
-M dòng sau: mỗi dòng chứa 2 số x và y (Biểu thị cho truy vấn (x,y)).

Output

Với mỗi truy vấn, xuất ra “YES” nếu tồn tại đường đi có ít nhất 1 cạnh có trọng số 2, ngược lại xuất ra “NO”.

Example

Input:
6 7
1 1
1 2
3 1
1 2
5 2
1 3
5 1
2 1
2 1
1 2
2 4
1 2
Output:
YES
YES
NO
NO
NO
YES
NO

===============================
Thuật:
- Hợp nhất đường đi đánh dấu số 1
- Với mỗi truy vấn, ta kiểm tra tính liên thông của hai đỉnh x và y, nếu có thì ghi NO ngược lại ghi YES
==============================
Code tham khảo: C11BC2.PAS

Continue Reading