Kỳ thi Học sinh giỏi Quốc gia 2018 - Ngày 2

VOI 18 Bài 4 - Phần thưởng

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 7

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Đọc đề gốc tại đây

Vinh là người thắng cuộc trong một cuộc thi "Tìm hiểu kiến thức vũ trụ" và được nhận các phần thưởng do công ty AZ tài trợ. Trên mỗi ô của một lưới kích thước ~n \times n~ ô vuông có cạnh độ dài đơn vị, Ban tổ chức xếp một món quà. Các dòng của bảng được đánh số từ ~1~ đến ~n~, từ trên xuống dưới và các cột của bảng được đánh số từ ~1~ đến ~n~, từ trái qua phải. Ô nằm trên giao của dòng ~i~ và cột ~j~ được gọi là ô ~(i, j)~ và món quà trên ô đó có giá trị là ~a_{ij}~ ~(1 \le i, j \le n)~.

Ban tổ chức cho phép Vinh chọn một trong ~k~ phương án nhận phần thưởng. Phần thưởng trong phương án thứ ~s~ ~(s = 1, 2, \dots, k)~ được xác định như sau: Vinh được nhận các món quà trên các ô của lưới thuộc một trong ~p~ hình vuông kích thước ~r \times r~, trong đó hình thứ ~h~ xác định bởi ô góc trên trái có tọa độ ~(x_{sh}, y_{sh})~, ~h = 1, 2, \dots, p~. Chú ý là các hình vuông này nằm trọn vẹn trong lưới và có thể có các hình vuông là giao nhau.

Yêu cầu: Hãy giúp Vinh chọn phương án nhận phần thưởng với tổng giá trị của các món quà nhận được là lớn nhất.

Input

Dòng thứ nhất chứa bốn số nguyên dương ~n~, ~k~, ~r~, ~p~;
Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ~n~ số nguyên dương, số thứ ~j~ là ~a_{ij}~ ~(a_{ij} \le 10^6)~, ~(i =1, 2, \ldots, n~; ~j = 1, 2, \ldots, n)~;
Dòng thứ ~s~ trong số ~k~ dòng tiếp theo chứa ~2 \times p~ số nguyên dương ~x_{s1}, y_{s1}, x_{s2}, y_{s2}, \ldots, x_{sp}, y_{sp}~ xác định ~p~ hình vuông trong phương án thứ ~s~ ~(s = 1, 2, \ldots, k)~.

Output

Ghi ra một số nguyên duy nhất là giá trị lớn nhất của tổng giá trị các món quà mà Vinh có thể nhận được.

Giới hạn

Có ~25\%~ số test ứng với ~25\%~ số điểm của bài có ~n \le 50~; ~k \le 50~; ~p \le 5~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có ~n \le 500~; ~k \le 10^5~; ~p = 2~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có ~n \le 500~; ~k \le 10^5~; ~p = 3~;
~25\%~ số test còn lại ứng với ~25\%~ số điểm của bài có ~n \le 500~; ~k \le 10^5~; ~p \le 5~;

Sample Input

4 2 2 3
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 2 2 3 3
1 1 1 3 3 1

Sample Output

Note

Giải thích:

Các hình vẽ dưới đây mô tả 2 phương án giải thưởng trong ví dụ và tổng giá trị của giải thưởng trong mỗi phương án:

VOI 18 Bài 5 - Người đặc biệt

Nộp bài

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 7

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Đọc đề gốc tại đây

Trong trường học mà Sơn đang theo học có ~N~ học sinh. Cũng giống như ở các trường học khác, trong trường của Sơn có người là đặc biệt có người thì không. Một học sinh muốn trở thành người đặc biệt cần giao tiếp với những học sinh đã là người đặc biệt. Sơn muốn xác định ai trong số các học sinh trong trường sẽ là người đặc biệt thông qua bảng thống kê về các lần trao đổi tin nhắn trên mạng xã hội. Chúng ta không cần quan tâm đến việc Sơn đã làm thế nào để có được bảng thống kê này. Vì bảng thống kê là quá lớn nên Sơn cần đến sự trợ giúp của máy tính. Theo qui tắc, nếu một học sinh chưa là đặc biệt mà trao đổi tin nhắn với ít ra là ~K~ người đã là đặc biệt, mỗi người ít nhất một lần, thì học sinh đó sẽ trở thành người đặc biệt. Tiếc là do hạn chế của hệ thống thu thập thông tin nên Sơn chỉ ghi nhận được các tin nhắn đã được trao đổi giữa hai người mà không biết chính xác chúng được thực hiện ở các thời điểm nào.

Yêu cầu: Biết danh sách những người đặc biệt lúc ban đầu (tức là trước khi tin nhắn đầu tiên trong bảng thống kê được thực hiện), hãy giúp Sơn xác định xem nhiều nhất có thể có bao nhiêu học sinh trở thành người đặc biệt và cụ thể đó là những người nào sau khi tất cả các tin nhắn trong bảng thống kê được thực hiện.

Input

Dòng đầu tiên chứa ~4~ số nguyên được ghi cách nhau bởi dấu cách ~N~, ~K~, ~S~, ~M~ tương ứng là số lượng học sinh trong trường, số lượng người đặc biệt ít nhất mà một học sinh cần trao đổi tin nhắn với họ để trở thành người đặc biệt, số lượng người đặc biệt lúc ban đầu, số lượng tin nhắn trong bảng thống kê mà Sơn sở hữu;
Dòng thứ hai chứa tên của ~S~ người đặc biệt trong trường trước khi tin nhắn đầu tiên trong bảng thống kê được gửi đi, trong đó tên của mỗi người là dãy gồm không quá ~10~ chữ cái la tinh in thường, hai tên liên tiếp được ghi cách nhau bởi một dấu cách;
Mỗi dòng trong số ~M~ dòng cuối ghi nhận thông tin về một tin nhắn trao đổi giữa hai học sinh bao gồm hai tên của hai học sinh được ghi phân cách nhau bởi một dấu cách. Tên của các học sinh là dãy gồm không quá ~10~ chữ cái la tinh in thường. Lưu ý là thứ tự các tin nhắn được liệt kê không phải là theo trình tự thời gian mà chúng được gửi đi.

Chú ý:

Việc trao đổi tin nhắn là hai chiều, nghĩa là nếu ~A~ trao đổi tin nhắn với ~B~ thì cũng có nghĩa là ~B~ đã trao đổi tin nhắn với ~A~;
Dữ liệu đảm bảo không có hai học sinh nào trùng tên và trong bảng thống kê không có tin nhắn giữa một người với chính mình.

Output

Dòng đầu tiên ghi tổng số người đặc biệt;
Dòng thứ hai ghi tên của các người đặc biệt trong trường sau khi tất cả các tin nhắn trao đổi trong bảng thống kê được thực hiện với giả thiết là trình tự thời gian mà chúng được thực hiện là trình tự được liệt kê sao cho có nhiều người trở thành đặc biệt nhất. Tên của các người đặc biệt cần được liệt kê theo thứ tự từ điển tăng dần, hai tên liên tiếp được ghi cách nhau bởi một dấu cách.

Giới hạn

Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~K = 1~; ~S \le N \le 100~; ~1 \le M \le 1\,000~;
Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~1 \le K \le S \le N \le 1\,000~; ~1 \le M \le 10\,000~;
~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~1 \le K \le S \le N \le 10\,000~; ~1 \le M \le 100\,000~.

Sample Input 1

3 1 1 1
cuoi
son cuoi

Sample Output 1

2
cuoi son

Sample Input 2

9 2 3 6
san son rong
cuoi phuong
son anh
son cuoi
cuoi san
son phuong
san phan

Sample Output 2

5
cuoi phuong rong san son

Note

Giải thích:

Trong ví dụ thứ hai: Sau khi trao đổi tin nhắn với son và san, cuoi trở thành người đặc biệt.

Tiếp đến trong bảng thống kê cả son và cuoi đều trao đổi tin nhắn với phuong, nên phuong cũng trở thành người đặc biệt. Lưu ý rằng: nếu như coi rằng cuoi trao đổi tin nhắn với phuong trước khi trở thành người đặc biệt (tức là trình tự thời gian thực hiện các tin nhắn là trình tự liệt kê trong dữ liệu) thì phuong sẽ không trở thành người đặc biệt được. Nhưng theo giả thiết đầu bài ta có thể xếp lại trình tự thực hiện các tin nhắn sao cho có được nhiều người đặc biệt nhất, nên tin nhắn này có thể coi là được thực hiện sau khi cuoi đã trở thành người đặc biệt.

Trong ví dụ này có hai học sinh trong trường không trao đổi tin nhắn với bất cứ ai, vì thế tên của họ không xuất hiện trong bảng thống kê.

VOI 18 Bài 6 - Dãy xấp xỉ tăng

Nộp bài

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 6

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Đọc đề gốc tại đây

Vinh rất thích các bài toán liên quan đến dãy số. Vừa qua thầy dạy giải tích đã giao cho Vinh giải quyết bài toán sau đây:

Cho dãy số nguyên ~A = \, <a_1, a_2, \ldots, a_N>~, cần xây dựng dãy số nguyên ~B = \, <b_1, b_2, \ldots, b_N>~ thỏa mãn các điều kiện sau:

Dãy ~B~ là đơn điệu tăng, nghĩa là ~b_1 < b_2 < \ldots < b_N~;
Độ chênh lệch ~d(A, B)~ giữa hai dãy ~A~ và ~B~ được tính theo công thức: ~d(A, B) = |a_1 - b_1| + |a_2 - b_2| + ... + |a_N - b_N|~ là nhỏ nhất.

Dãy ~B~ thỏa mãn các điều kiện nêu trên được gọi là dãy đơn điệu tăng xấp xỉ tốt nhất dãy số ~A~.

Yêu cầu: Hãy giúp Vinh tìm dãy số ~B~ thỏa mãn các yêu cầu đặt ra.

Input

Dòng đầu tiên chứa số nguyên dương ~N~;
Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~, hai số liên tiếp được ghi cách nhau bởi dấu cách, là các số hạng của dãy số ~A~ đã cho.

Output

Dòng đầu tiên chứa một số nguyên là độ chênh lệch giữa dãy số tìm được với dãy đã cho;
Dòng thứ hai chứa ~N~ số nguyên ~b_1, b_2, \ldots, b_N~, hai số liên tiếp được ghi cách nhau bởi dấu cách, là các số hạng của dãy tìm được. Nếu có nhiều dãy cùng thỏa mãn các điều kiện đặt ra, hãy đưa ra một dãy tùy ý trong số chúng.

Giới hạn

Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N = 3~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~;
Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 300~; ~0 \le a_k \le 300, k = 1, 2, \ldots, N~;
Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 300~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~;
Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 3\,000~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~;
Có ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \le 300\,000~; ~0 \le a_k \le 10^9, k = 1, 2, \ldots, N~.

Đối với mỗi test, ~50\%~ số điểm của test dành cho việc đưa ra giá trị độ chênh lệch nhỏ nhất và ~50\%~ số điểm còn lại dành cho việc đưa ra dãy đơn điệu tăng xấp xỉ tốt nhất dãy đã cho.

Sample Input

7
1 5 1 7 3 1 3

Sample Output

17
-1 0 1 2 3 4 5