REINVENT

Nguồn: Mr Kiên

Zăhărel và Sica cần thay đổi tinh thần. Trong giai đoạn đầu, họ di chuyển đến trung tâm thành phố. Trung tâm thành phố có N ngôi nhà (Đánh số từ 1 đến N), được kết nối với nhau bởi M con đường hai chiều có chiều dài bằng nhau. Do Không có nhiều tiền nên họ chỉ có thể di chuyển trong một khu vực có x ngôi nhà. Là hai người bạn thân, họ muốn di chuyển đến 2 ngôi nhà riêng biệt nhưng càng gần nhau càng tốt. Hãy giúp họ xác định khoảng cách tối thiểu giữa hai ngôi nhà bất kỳ trong X ngôi nhà.

Dữ liệu vào: Từ tệp văn bản REINVENT.INP

+ Dòng đầu tiên ghi 3 số nguyên N, M và X. M dòng thiếp theo, mỗi dòng ghi 2 số nguyên phân biệt thể hiện một con đường hai chiều nối 2 ngôi nhà.

+ Dòng cuối cùng ghi X số nguyên phân biệt thể hiện các ngôi nhà trong khu vực được lựa chọn.

Dữ liệu ra: Ghi vào tệp văn bản REINVENT.OUT

+ Khoảng cách tối thiểu giữa hai ngôi nhà riêng biệt trong khu vực được chọn

Giới hạn:

+ 1≤N, M≤10⁵

+ 2≤X≤N

+ Trong 30% tổng số test có N ≤ 1024

+ Khoảng cách giữa hai ngôi nhà được đo bằng số lượng tối thiểu các con đường trên tuyến đường nối hai ngôi nhà.

+ Giữa bất kỳ 2 ngôi nhà đề có ít nhất một tuyến đường hai chiều

+ Có ít nhất hai ngôi nhà trong khu phố được chọn

Ví dụ:

REINVENT.INP	REINVENT.OUT
5 6 2 1 2 2 3 2 4 3 4 1 4 3 5 1 5	3

Test - code  - solution

QUÂN HẬU

Xét bàn cờ tổng quát kích thước kx k, các hàng của bàn cờ được đánh số từ 1 tới k từ trên xuống dưới và các cột của bàn cờ được đánh số từ 1 tới k  từ trái qua phải. Ô nằm trên giao của hàng i và cột j được gọi là ô (i, j). Từ bàn cờ ban đầu gồm các ô trống, người ta đặt đúng n quân hậu vào n ô hoàn toàn phân biệt trên bàn cờ.

Ta nói một quân hậu ở ô (x, y) khống chế được ô trống (x^’, y^’) nếu đoạn thẳng nối tâm hai ô đó song song với một trong hai cạnh bàn cờ hoặc song song với một trong hai đường chéo của bàn cờ, đồng thời đoạn thẳng nối tâm của hai ô (x, y) và (x’ , y^’) không đi qua tâm của bất kỳ ô nào chứa quân hậu khác.

Như ví dụ trên, quân hậu ở ô (4, 4) có thể khống chế được 16 ô trống đánh dấu “ü” trong hình.

Yêu cầu: Cho biết kích thước bàn cờ và vị trí n quân hậu, hãy đếm số ô trống bị quân hậu khống chế.

Dữ liệu: Vào từ file văn bản QUEENS.INP

·            Dòng 1 chứa hai số nguyên dương k≤10⁹, n≤10⁵

·            n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương lần lượt là chỉ số hàng và chỉ số cột của quân hậu thứ i

Kết quả: Ghi ra file văn bản QUEENS.OUT n dòng, dòng thứ i ghi số ô trống bị quân hậu thứ i khống chế.

Ví dụ:

QUEENS.INP	QUEENS.OUT
8 7 1 1 1 7 3 4 4 4 4 7 6 2 7 7	14 11 20 16 16 19 15

Test - Code - Đề (word)

BẢO VỆ NÔNG TRANG

Nguồn: http://vn.spoj.com/problems/NKGUARD/
Solution:

Ý tưởng giải thuật: Ta sẽ làm 2 bước:

Bước 1: Với mỗi đỉnh [i,j] chưa thăm, ta dfs đánh dấu các đỉnh có chiều cao < a[i,j], ta sẽ đảm bảo rằng từ đỉnh có chiều cao a[u,v] nào đó, thủ tục dfs1 sẽ đánh dấu những đỉnh có chiều cao ≤ a[u,v] lận cận;

Như vậy chỉ có các đỉnh có chiều cao “đỉnh” còn lại;

Bước 2: Dfs để tìm các nhóm đỉnh, thực chất Dfs lần này là để đếm số lượng thành phần liên thông

Chương trình tham khảo:

CONNECT

Nguồn: Mr Kiên

Cho một đồ thị vô hương gồm N đỉnh và M cạnh, có Q truy vấn, mỗi truy vấn có dạng x, y. Yêu cầu kiểm tra xem x và y có cũng thuộc một thành phần liên thông hay không (từ x có thể đi tới y thông qua một số cạnh hay không).

Dữ liệu vào: Từ tệp văn bản CONNECT.INP

+ Dòng đầu tiên chứa ba số nguyên dương N, M, Q lần lượt là số đỉnh, số cạnh và số lượng truy vấn (1≤N, M≤10⁵_, Q≤10⁶+1 )

+ M dòng tiếp theo, mỗi dòng gồm hai số nguyên dương x, y, chỉ một cạnh nối hai đỉnh x và y.

+ Q dòng tiếp theo, mỗi dòng là một truy vấn có dạng x y.

Dữ liệu ra: Ghi vào tệp văn bản CONNECT.OUT

Với mỗi truy vấn dạng x y, in ra “YES” nếu x và y là hai đỉnh cùng thuộc một thành phần liên thông, in ra “NO” trong trường hợp ngược lại.

CONNECT.INP	CONNECT.OUT
3 1 3 1 2 2 1 1 3 3 2	YES NO NO

BFS2

Nguồn: Mr Kiên

Cho một đơn đồ thị liên thông gồm N đỉnh và N-1 cạnh. Mỗi cạnh có độ dài bằng 1. Ta nói đây là một cây không trọng số.

Đường kính của cây là khoảng cách giữa hai đỉnh xa nhau nhất. Tâm của cây là đỉnh mà có khoảng cách từ nó tới nút xa nó nhất là nhỏ nhất. Một cây có thể có nhiều tâm.

Hãy tìm đường kính của cây và các tâm của cây.

Dữ liệu vào: Từ tệp văn bản BFS2.INP

+ Dòng đầu tiên chứa số nguyên dương N (1≤N≤10⁵)

+ N-1 dòng tiếp theo, mỗi dòng gồm hai số nguyên dương x và y chỉ một cạnh nối giữa hai đỉnh x và y trên cây.

Dữ liệu ra: Ghi vào tệp văn bản BFS2.OUT

+ Dòng đầu tiên, in ra đường kính của cây.

+ Dòng thứ hai, in ra số lượng tâm của cây.

+ Dòng thứ ba, in ra các đỉnh là tâm của cây theo thứ tự tăng dần. Các số cách nhau bởi 1 dấu cách.

Ví dụ:

BFS2.INP	BFS2.OUT
5 1 2 2 3 3 4 2 5	4 2 2 3

BFS1

Nguồn: Mr Kiên

Cho đồ thị vô hướng gồm N đỉnh và M cạnh, độ dài của mỗi cạnh bằng 1. Tìm độ dài đường đi ngắn nhất từ đỉnh 1 đến cách đỉnh còn lại của đồ thị.

Dữ liệu vào: Từ tệp văn bản BFS1.INP

+ Dòng đầu tiên gồm hai số nguyên dương N và M (1≤N, M≤10⁵)

+ M dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương x và y, chỉ 1 cạnh nối giữa hai đỉnh x và y

Dữ liệu ra: ghi vào tệp văn bản BFS1.OUT

+ In ra N dòng, dòng thứ i là độ dài đường đi ngắn nhất từ đỉnh 1 đến đỉnh i.

+ Nếu không thể đi từ 1 đến i, in ra -1

Ví dụ:

BFS1.INP	BFS1.OUT
5 4 1 2 2 3 2 4 3 4	0 1 2 2 -1

ACM

Nguồn: PREVOI

SuperCodes là đội trưởng huyền thoại của trường XYZ đã nhiều lần vô địch cuộc thi lập trình viên vũ trụ ACM Universe Final. Theo thể thức cuộc thi, mỗi đội tham dự có đúng 3 thành viên và được giao duy nhất một máy tính chính vì vậy việc điều phối công việc vô cùng quan trọng. Trong đội SuperCodes – đội trưởng là PHUONGHD - người nắm giữ vai trò quan trọng đó.

Đề thi ACM năm nay gồm có 2N bài được đánh số từ 1 đến 2N. Bằng kỹ thuật thiết kế thuật toán siêu việt, chỉ vài giây sau khi đọc đề PHUONGHD đã có lời giải cho 2N bài toán. Vấn đề còn lại là phân công 2 người lập trình bởi PHUONGHD không quen với ngôn ngữ lập trình mới vừa được đưa vào sử dụng tại cuộc thi.

 Do rất hiểu 2 thành viên Tí và Tèo trong đội, PHUONGHD biết rằng nếu giao bài thứ i cho Tí thì mất a_i giây, cũng bài đó nếu giao cho tèo sẽ mấy b_i giây để hoàn thành (1≤i≤2N). Nhiệm vụ của bạn làm giúp PHUONGHD phân công cho 2 thành viên, mỗi người làm đúng N bài sao cho tổng thời gian lập trình cả 2N bài là ít nhất.

Dữ liệu vào: Từ tệp văn bản ACM.INP

+ Dòng 1 chứa số nguyên dương N (N≤4.10⁵)

+ 2N dòng tiếp theo, dòng thứ i chứa 2 số nguyên dương a_i, b_i (a_i, b_i≤100) cách nhau bởi dấu cách.

Dữ liệu ra: ghi vào tệp văn bản ACM.OUT một số nguyên duy nhất là thời gian lập trình cả 2N bài theo phương án phân công tìm được.

Chú ý:

40% số điểm tương ứng với test có N≤1000

30% số điểm tương ứng với test có 10⁴ ≤N≤ 10⁵

30% số điểm tương ứng với test có 3.10⁵≤N≤ 4.10⁵

Ví dụ
ACM.INP	ACM.OUT
2 2 1 3 2 5 3 1 2	8