BOI 2012 - Ngày 2

Các đường phố của thành phố RightAngleles tạo thành một lưới ô vuông vô hạn. Hai đường bất kỳ hoặc song song hoặc vuông góc với nhau, và khoảng cách giữa hai đường song song gần nhau nhất bằng một đơn vị. Các đường chạy theo hướng tây–đông được gọi là đường ngang, đánh số bằng các số nguyên liên tiếp theo chiều từ nam lên bắc. Các đường chạy theo hướng nam–bắc được gọi là đường dọc, đánh số tương tự theo chiều từ tây sang đông.

Mỗi người dân sống trong một ngôi nhà có cửa ra vào tại một giao điểm của một đường ngang và một đường dọc. Nhiều người có thể sống trong cùng một ngôi nhà.

Thị trưởng muốn tăng sự ủng hộ của người dân bằng cách tổ chức bắn pháo hoa tại giao điểm của đường ngang chính, mang số \(0\), với một đường dọc nào đó. Vị trí nhà của tất cả những người muốn đến xem đã được biết trước. Pháo hoa có thể được quan sát dọc theo hai đường đi qua nơi bắn. Để bảo đảm an toàn, người xem phải đứng cách nơi bắn ít nhất \(S\) đơn vị.

Như vậy, nếu chọn đường dọc \(V\), mỗi người phải đi dọc các đường phố tới một giao điểm nằm trên đường ngang \(0\) hoặc đường dọc \(V\), cách giao điểm \((0,V)\) ít nhất \(S\) đơn vị. Chẳng hạn, khi \(S=2\), người xem có thể đứng tại mọi giao điểm trên đường ngang \(0\), trừ các giao điểm với đường dọc \(V-1,V,V+1\); tương tự, trên đường dọc \(V\) phải loại các giao điểm với đường ngang \(-1,0,1\).

Mức độ hài lòng của người dân phụ thuộc nhiều vào tổng quãng đường họ phải đi để xem pháo hoa. Hãy chọn vị trí bắn sao cho tổng quãng đường này nhỏ nhất và tính giá trị nhỏ nhất đó.

Dữ liệu vào

Dòng đầu chứa hai số nguyên dương \(N,S\), lần lượt là số người dân muốn xem pháo hoa và khoảng cách an toàn. Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(H_i,V_i\), là số hiệu đường ngang và đường dọc tại giao điểm có cửa nhà của người thứ \(i\).

Dữ liệu ra

In ra đúng một số nguyên: tổng quãng đường nhỏ nhất mà tất cả người dân phải đi để xem pháo hoa.

Ràng buộc

• \(1 \le N \le 10^5\).
• \(1 \le S \le 10^6\).
• \(-10^9 \le H_i,V_i \le 10^9\).

Phân nhóm

• Các bộ test có \(0 \le V_i \le 5000\) với mọi \(i\) chiếm \(20\) điểm.
• Các bộ test có \(N \le 5000\) chiếm tổng cộng \(40\) điểm.
• Toàn bộ các bộ test chiếm \(100\) điểm.

Ví dụ

7 2
3 -2
0 8
-4 8
-1 4
-2 13
-4 8
1 5

9

Linas thích chơi một nhạc cụ mà không ai biết tên. Nhạc cụ có \(S\) lỗ, và Linas có thể chơi \(N\) nốt khác nhau, đánh số từ \(1\) đến \(N\), bằng cách bịt mỗi lỗ theo một trong mười cách, đánh số từ \(0\) đến \(9\).

Mỗi nốt ứng với đúng một cách bịt tất cả các lỗ, được mô tả bằng một xâu chữ số. Nếu bịt theo một cấu hình không tương ứng với nốt nào, nhạc cụ phát ra âm thanh rất khó chịu. Vì thế, Linas thà chơi sai nốt còn hơn dùng một cấu hình không hợp lệ.

Linas tham gia một ban nhạc thường chơi những giai điệu phức tạp với tốc độ rất nhanh. Cậu đã viết một giai điệu, là một dãy số hiệu các nốt, và muốn chơi cùng ban nhạc. Tuy nhiên, Linas chỉ chơi được hai nốt liên tiếp nếu khi chuyển sang nốt thứ hai, cậu phải thay đổi cách bịt không quá \(G\) lỗ so với nốt thứ nhất. Do đó, đôi khi cậu phải chơi một nốt khác với nốt trong giai điệu ban đầu. Mỗi vị trí chơi sai như vậy được tính là một lỗi.

Cho giai điệu ban đầu, hãy tìm một giai điệu đã sửa mà Linas chơi được với số lỗi ít nhất.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(N,S,G\): số nốt có thể chơi, số lỗ và giới hạn số lỗ có thể thay đổi giữa hai nốt liên tiếp.

Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu gồm \(S\) chữ số, không có dấu cách. Chữ số thứ \(j\) của xâu thứ \(i\) cho biết cách bịt lỗ thứ \(j\) để chơi nốt \(i\). Không có hai nốt nào có cùng một cách bịt các lỗ.

Dòng tiếp theo chứa số nguyên \(L\), độ dài giai điệu. Dòng cuối chứa \(L\) số nguyên trong đoạn từ \(1\) đến \(N\), là các nốt của giai điệu theo thứ tự.

Dữ liệu ra

Dòng đầu chứa một số nguyên không âm: số lỗi nhỏ nhất. Dòng thứ hai chứa \(L\) số nguyên, là một giai điệu Linas chơi được và đạt số lỗi đó. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• \(1 \le N \le 100\).
• \(0 \le G < S \le 100\).
• \(1 \le L \le 10^5\).

Phân nhóm

• Các bộ test có \(L \le 100\) chiếm tổng cộng \(40\) điểm.
• Các bộ test có \(L \le 5000\) chiếm tổng cộng \(65\) điểm, bao gồm các bộ test ở mục trên.
• Toàn bộ các bộ test chiếm \(100\) điểm.

Ví dụ

5 4 2
1111
2101
2000
0100
0000
7
1 5 4 5 3 2 1

1
1 2 4 5 3 2 1

Những người lớn tuổi vẫn nhớ trò chơi nổi tiếng TETRIS do Alexey Pajitnov sáng tạo. Trong trò chơi đó, những mảnh ghép gồm bốn ô vuông rơi xuống; người chơi xoay và xếp chúng vào một khung chữ nhật để tạo ra nhiều hàng đầy nhất có thể. Mỗi hàng không còn ô trống sẽ biến mất, nhường chỗ cho các mảnh tiếp theo.

Hãy xét một phiên bản đơn giản hơn, gọi là Tiny TETRIS, hay Tiny. Trò chơi chỉ có chín loại mảnh, mỗi mảnh gồm từ một đến ba ô vuông:

Các số trong hình là số hiệu dùng để chỉ từng loại mảnh. Khung chơi có chiều rộng \(9\) và chiều cao \(9\) ô. Các mảnh không được xoay, và cũng không được dịch sang trái hoặc phải sau khi bắt đầu rơi. Với mỗi mảnh, người chơi chỉ chọn số hiệu cột, từ \(1\) đến \(9\), mà ô ngoài cùng bên trái của mảnh, được đánh dấu bằng dấu \(\times\), sẽ rơi vào.

Mỗi ván gồm một dãy hữu hạn \(N\) mảnh. Mục tiêu là thả được nhiều mảnh nhất vào khung mà không vượt quá mép trên và không thực hiện nước đi không hợp lệ. Kết quả của ván chơi là số mảnh đã thả thành công.

Bộ đếm ban đầu bằng \(0\). Trò chơi diễn ra như sau:

1. Người chơi chọn cột cho ô ngoài cùng bên trái của mảnh hiện tại.
2. Nếu cột được chọn hợp lệ, mảnh rơi thẳng xuống cho tới khi gặp chướng ngại vật. Nếu không, ván chơi kết thúc. Chẳng hạn, cột \(8\) luôn không hợp lệ với mảnh loại \(5\) vì mảnh sẽ vượt ra ngoài khung bên phải.
3. Nếu toàn bộ các ô của mảnh nằm trong khung \(9\times9\), bộ đếm tăng thêm \(1\). Nếu không, ván chơi kết thúc.
4. Kiểm tra các hàng ngang đã được lấp đầy. Mọi hàng đầy biến mất, và các hàng phía trên dồn xuống mà không thay đổi cách sắp xếp các ô trong từng hàng.
5. Nếu vẫn còn mảnh, quay lại bước \(1\). Nếu đã hết mảnh, ván chơi kết thúc.

Kết quả của ván chơi là giá trị bộ đếm khi ván kết thúc.

Dữ liệu vào

Đây là bài chỉ nộp kết quả, với dữ liệu vào công khai. Có đúng năm tệp dữ liệu: tiny.i1, tiny.i2, tiny.i3, tiny.i4 và tiny.i5.

Trong mỗi tệp, dòng đầu chứa số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên từ \(1\) đến \(9\), là số hiệu một mảnh. Các mảnh được liệt kê theo đúng thứ tự phải thả; mảnh thứ \(i\) nằm trên dòng \(i+1\).

Dữ liệu ra

Nộp một tệp ZIP chứa đúng năm tệp tiny.o1, tiny.o2, tiny.o3, tiny.o4 và tiny.o5 ngay ở thư mục gốc của ZIP. Tệp tiny.ok chứa kết quả cho tiny.ik, với \(k\) từ \(1\) đến \(5\).

Mỗi tệp kết quả có nhiều nhất \(N\) dòng. Dòng thứ \(i\) chứa đúng một số hiệu cột từ \(1\) đến \(9\), cho biết cột thả mảnh thứ \(i\). Có thể nộp một tiền tố của dãy nước đi; nếu không ghi nước đi nào thì tệp tương ứng rỗng. Không ghi số lượng nước đi ở đầu tệp. Khi một nước đi làm ván chơi kết thúc, chỉ những mảnh đã được thả thành công trước đó được tính.

Ràng buộc

• Mỗi mảnh thuộc một trong chín loại trong hình.
• Năm tệp lần lượt có \(N=1000,5000,20\,000,50\,000,100\,000\) mảnh.
• Với mỗi tệp, bảo đảm tồn tại một dãy cột giúp thả thành công toàn bộ \(N\) mảnh.

Phân nhóm

• tiny.i1: tối đa \(20\) điểm.
• tiny.i2: tối đa \(20\) điểm.
• tiny.i3: tối đa \(20\) điểm.
• tiny.i4: tối đa \(20\) điểm.
• tiny.i5: tối đa \(20\) điểm.

Gọi \(K\) là số mảnh thả thành công. Trong kỳ thi gốc, điểm cuối cùng của mỗi tệp được tính theo công thức

rồi làm tròn đến hai chữ số sau dấu thập phân. Trong thời gian thi, thí sinh được thông báo \(K\) và mức điểm bảo đảm, với giả thiết có người thả được đủ \(N\) mảnh. Sau kỳ thi, điểm được tính lại theo kết quả tốt nhất thực tế nên có thể tăng lên.

Ở bài luyện tập này, điểm được cố định theo đúng mức điểm bảo đảm đó:

Ví dụ

20
5
4
1
6
7
6
4
4
7
9
5
5
6
8
3
4
3
7
4
2

1
2
2
4
8
8
7
4
8
6
1
1
4
8
3
7
7