K-th số nguyên cực lớn theo thứ tự

Bối cảnh

Một kho dữ liệu lưu n số nguyên có thể dài đến hàng nghìn chữ số. Các token có thể có dấu +/- và leading zero, ví dụ +00012, 12, 00012 đều biểu diễn cùng giá trị. Hệ thống cần chuẩn hóa tất cả số, sắp xếp tăng dần theo giá trị số học rồi trả phần tử thứ k (1-based). Đồng thời in số lượng giá trị phân biệt sau canonicalization.

Không thể dùng long long. Comparator số nguyên dạng string phải xử lý dấu, độ dài magnitude và lexicographic: mọi số âm nhỏ hơn số không âm; với hai số dương, magnitude dài hơn lớn hơn; với hai số âm, magnitude dài hơn lại nhỏ hơn. Sau sort, vì canonical string của cùng giá trị giống hệt nhau, có thể đếm distinct bằng so sánh các phần tử kề.

Bài Advanced kết hợp kỹ năng string pipeline của B21 với comparator/sort từ Module 05 và yêu cầu comparator strict.

Comparator nên được kiểm tra bằng các cặp dễ sai: -100 với -9, +0005 với 5, -0 với 0, và hai số dương cùng độ dài. Nếu một cặp bị so ngược, std::sort có thể cho ranking sai dù nhiều test nhỏ vẫn qua. Canonical hóa trước comparator giúp giảm rất nhiều nhánh đặc biệt.

Yêu cầu

1. Đọc n k và n token số nguyên.
2. Canonical hóa mỗi token.
3. Sort tăng theo giá trị số học bằng comparator string.
4. In phần tử thứ k và số giá trị distinct.
5. Không chuyển toàn số sang kiểu built-in.

Yêu cầu tổ chức code

Không dùng big integer library.

Online Judge chấm output. Giảng viên có thể review source code để kiểm tra việc sử dụng đúng pointer/lifetime/string pipeline theo phạm vi buổi học.

Input

Dòng 1 n k; sau đó n token.

Output

Dòng 1: giá trị thứ k canonical. Dòng 2: số distinct.

Ràng buộc

1≤k≤n≤5000, mỗi token dài ≤2000; input hợp lệ.

Ví dụ 1

Input

6 3
+00012 12 -5 0003 -0005 100

Output

3
4

Giải thích

Canonicalization biến +00012 và 12 thành cùng 12, 0003 thành 3, còn -0005 thành -5. Sau comparator signed, dãy tăng là -5, -5, 3, 12, 12, 100. Phần tử thứ 3 là 3. Khi đếm block canonical kề nhau có bốn giá trị distinct: -5, 3, 12, 100.

Ví dụ 2

Input

5 1
0 -0 +000 1 -1

Output

-1
3

Giải thích

0, -0 và +000 đều canonical về đúng chuỗi 0, vì zero không được giữ dấu âm. Cùng với 1 và -1, thứ tự số học là -1,0,0,0,1. k=1 nên kết quả thứ nhất là -1. Có ba block giá trị khác nhau là -1, 0 và 1, nên distinct count bằng 3.

Thông tin học tập

• Module: M06
• Buổi: B21
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: big integer string, canonicalization, signed comparator, std::sort, duplicate counting
• Giới hạn kiến thức: B01-B21
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100