Contest PreVNOI Ⅲ (NINH BÌNH 2013)

Trùm CUỐI 2019-12-17 13:52:37 2020-10-22 9:36:07

1. BEADS - Chuỗi ốc

Biển Đà Nẵng được nhiều du khách biết đến như một trong những điểm nghỉ ngơi lý tưởng và được tạp chí Forbes (Mỹ) bình chọn là một trong những bãi biển đẹp nhất thế giới. Các bãi tắm có độ dốc lớn, nước trong xanh thích hợp cho những du khách muốn thưởng thức các loại hình dịch vụ giải trí nghỉ dưỡng, câu cá, lướt ván, lặn ngắm san hô, du thuyền, ...

Trong một đợt đi du lịch ở Đà Nẵng, sáng sớm DONG3D thường đi dạo dọc bờ biển và nhặt những vỏ ốc rồi xâu chúng lại thành một chuỗi. Nguyên tắc tạo chuỗi ốc của DONG3D như sau: Ban đầu từ chuỗi rỗng, không có vỏ ốc; khi gặp một vỏ ốc mới, có thể lấy để xâu vào một trong hai đầu của chuỗi hoặc hoặc bỏ đi không lấy; cuối cùng nhận được một chuỗi vỏ ốc mà tính từ đầu chuỗi đến cuối chuỗi, các vỏ ốc có kích thước tăng dần và gồm càng nhiều vỏ ốc càng tốt.

Yêu cầu: Cho trước dãy 𝑎_1, 𝑎_2, … , 𝑎_𝑛 là kích thước của các vỏ ốc mà DONG3D lần lượt gặp khi đi dọc bờ biển, hãy tìm cách nhặt và xâu chuỗi để được chuỗi gồm nhiều vỏ ốc nhất.

Dữ liệu vào:

  • Dòng đầu chứa số nguyên dương 𝑛 ≤ 10^5
  • Dòng sau chứa n số nguyên dương 𝑎_1, 𝑎_2, … , 𝑎_𝑛\ (∀𝑖: 𝑎_𝑖 ≤ 10^9) cách nhau bởi dấu cách.

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là số lượng vỏ ốc trong chuỗi tạo được.

Ví dụ

Dữ liệu vào:
5 
4 4 5 3 1
Dữ liệu ra:
4 

Giới hạn:

  • 40\% số điểm ứng với các test có 𝑛 ≤ 20
  • 30\% số điểm ứng với các test có n thỏa mãn 20 ≤ 𝑛 ≤ 1000
  • 30\% số điểm ứng với các test có n thỏa mãn 1000 ≤ 𝑛 ≤ 10^5

2. QUEEN - Quân hậu

Mất ngủ vì không có đối thủ trong môn cờ vua, KHUELD quyết định chế tạo một robot để chơi cờ với mình. Một trong những việc đầu tiên là phải “dạy” robot biết quy tắc không chế bàn cờ của quân hậu. Xét bàn cờ vua hình chữ nhật kích thước 𝑚 × 𝑛 được chia làm lưới ô vuông đơn vị. Các hàng của bàn cờ được đánh số từ 1 tới m từ trên xuống và các cột của bàn cờ được đánh số từ 1 tới n từ trái qua phải, ô nằm trên giao của hàng i và cột j được gọi là ô (𝑖, 𝑗) Trên bàn cờ, tại một số ô có đặt vật cản. Quân hậu ở một ô có thể không chế một ô khác nếu đoạn thẳng nối tâm hai ô đó song song với một trong hai cạnh bàn cờ và đi qua đỉnh ô vuông có quân hậu đang đứng, đồng thời đoạn thẳng nối tâm hai ô không được chứa tâm bất kỳ ô nào chứa vật cản. Ta quy ước rằng quân hậu phải đặt vào ô không có vật cản và cũng khống chế luôn ô nó đang đứng.

Yêu cầu: Cho biết tình trạng bàn cờ, với mỗi ô (𝑖, 𝑗) không chứa vật cản, hãy “dạy” cho robot của KHUELD biết có bao nhiêu ô trên bàn cờ mà đặt hậu ở đó sẽ không chế được ô (𝑖, 𝑗)

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương 𝑚, 𝑛 ≤ 1000
  • m dòng tiếp theo, dòng thứ i chứa n ký tự liền nhau, ký tự thứ j là dấu . (chấm) nếu ô (𝑖, 𝑗) là ô trống, là dấu # nếu ô (𝑖, 𝑗) có đặt vật cản.

Dữ liệu ra:

  • Ghi ra m dòng, dòng i in ra n số nguyên, số nguyên thứ j là số ô trên bàn cờ mà khi đặt quân hậu vào ô đó có thể khống chế được ô (𝑖, 𝑗) .
    Các số trên một dòng được/phải ghi cách nhau bởi dấu cách.

Ví dụ:

Dữ liệu vào:
4 3
.#.
.#.
...
..#
Dữ liệu ra:
4 0 3 
5 0 5 
7 7 6 
7 5 0

3. JEWEL - Trang sức

Các thương nhân kinh doanh đồ trang sức tại các địa điểm dọc nước ta từ Bắc xuống Nam. Trong đó, các địa điểm buôn bán được đánh số từ 1 đến n dọc theo nước ta. Tùy thuộc vào nhu cầu mua mà giá của các đồ trang sức thay đổi theo từng ngày. Qua thống kê, người ta biết hiện có m loại đồ trang sức khác nhau được bán trong các ngày vừa qua, trong đó loại thứ i được biết với các thông tin như sau:

  • Ngày đầu tiên, đồ trang sức i được bán từ địa điểm 𝑠_𝑖
  • Ngày cuối cùng, đồ trang sức i sẽ được bán đến địa điểm 𝑒_𝑖\ (1 ≤ 𝑠_𝑖 ≤ 𝑒_𝑖 ≤ 𝑛)

Mỗi ngày thương nhân sẽ chuyển địa điểm bán sang địa điểm kế tiếp theo hướng xuống dưới phía Nam. Như vậy, các địa điểm bán đồ trang sức i sẽ là: 𝑠_𝑖, 𝑠_𝑖 + 1, … , 𝑒_𝑖 − 1, 𝑒_𝑖

  • Ngày đầu tại vị trí 𝑠_𝑖 , giá chào bán của nó là 𝑣_𝑖\ (1 ≤ 𝑣_𝑖 ≤ 10^9)
  • Mỗi ngày giá loại trang sức i sẽ cộng thêm một lượng là 𝑑_𝑖\ (|𝑑_𝑖| ≤ 10^9) . Tức là, giá tại địa điểm s_𝑖 𝑣_𝑖 , giá tại 𝑠_𝑖 + 1 𝑣_𝑖 + 𝑑_𝑖 ,…, giá tại 𝑒_𝑖 𝑣_𝑖 + (𝑒_𝑖 − 𝑠_𝑖) \times 𝑑_𝑖 .

KHUONGND là một nhà thống kê thị trường và anh ta muốn nhờ bạn cho biết giá đồ trang sức cao nhất được bán tại tất cả các địa điểm dựa vào thông tin của các đồ trang sức đã biết.

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương 𝑛, 𝑚 ≤ 2.10^5
  • m dòng tiếp theo, dòng thứ i chứa bốn số nguyên dương 𝑠_𝑖, 𝑒_𝑖, 𝑣_𝑖 𝑑_𝑖 lần lượt thể hiện thông tin của loại đồ trang sức lần lượt là vị trí bán ban đầu 𝑠_𝑖 , vị trí bán kết thúc 𝑒_𝑖 , giá chào bán ban đầu 𝑣_𝑖 và lượng giá bán thay đổi 𝑑_𝑖 theo mỗi ngày. Dữ liệu vào đảm bảo giá bán các loại đồ trang sức luôn dương. Các số trên một dòng của được ghi cách nhau bởi dấu cách

Dữ liệu ra:

  • Ghi ra n dòng, dòng thứ i ghi một số nguyên duy nhất là giá đồ trang sức đắt nhất bán tại vị trí i , nếu tại ví trí i không có đồ trang sức nào được bán thì dòng i ghi số 0

Ví dụ:

Dữ liệu vào:
6 4 
4 4 3 1 
1 2 5 1 
5 6 1 1 
6 6 1 1 5
Dữ liệu ra:
5
6
0
3
1
2

Giới hạn:

  • 30\% số điểm ứng với các test có 𝑛 × 𝑚 ≤ 5000^2