Đánh số phiên bản ứng dụng
Đề bài
Mô tả
Với sự phát triển của AI, việc viết mã giờ đây nhanh hơn bao giờ hết. Nhiều công ty "nghiện AI" ước tính số dòng mã họ viết ra trong năm 2026 sẽ gấp ít nhất 20 lần năm 2025. Nhiều mã hơn nghĩa là nhiều bản phát hành hơn, và việc đánh số phiên bản ứng dụng sẽ trở nên phức tạp hơn nhiều. Để chuẩn bị cho tương lai đó, bạn đang xây dựng một hệ thống đánh số phiên bản mới.
Một phiên bản là một dãy gồm một hoặc nhiều số nguyên không âm, gọi là các thành phần, ngăn cách nhau bởi dấu chấm. Ví dụ, 1.2.3, 2.1 và 10 là các phiên bản. Mỗi thành phần phải được viết ở hệ thập phân và không có chữ số ở đầu. Nói riêng, 0 là một thành phần hợp lệ, nhưng 02 thì không, nên 1.02.3 không phải là một phiên bản hợp lệ.
Khác với các phiên bản con người dùng ngày nay, thường có không quá bốn thành phần, phiên bản trong hệ thống của bạn có thể có hàng trăm nghìn thành phần. Điều này hiển nhiên không phải vấn đề với một hệ thống mà đối tượng sử dụng là các AI agent.
Hai phiên bản được so sánh theo từng thành phần, từ trái sang phải:
- Tại vị trí đầu tiên mà thành phần của hai phiên bản khác nhau, phiên bản có thành phần nhỏ hơn (so sánh như số nguyên) là phiên bản nhỏ hơn. Ví dụ, , và .
- Nếu không có vị trí như vậy, tức là một phiên bản là tiền tố của phiên bản kia, thì phiên bản có ít thành phần hơn là phiên bản nhỏ hơn. Ví dụ, và .
Thật không may, khi kiểm thử hệ thống, bạn phát hiện hai phiên bản đã bị mất hết dấu chấm. Cụ thể hơn, bạn có hai xâu chữ số và . Bạn cần chèn dấu chấm vào và vào để khôi phục chúng thành các phiên bản và . Có thể chèn dấu chấm vào giữa hai chữ số kề nhau bất kỳ, và giữa mỗi cặp chữ số kề nhau chèn nhiều nhất một dấu chấm. Không chèn dấu chấm nào cũng được. Các chữ số không được thay đổi, xóa hay đổi thứ tự.
Hãy đếm số cách chèn dấu chấm sao cho cả và đều là phiên bản hợp lệ và . Hai cách được coi là khác nhau nếu cặp thu được khác nhau. Vì đáp án có thể rất lớn, hãy in ra phần dư của nó khi chia cho .
Dữ liệu vào
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu.
Mỗi bộ dữ liệu gồm một dòng chứa hai xâu và (), cách nhau bởi một dấu cách. Cả hai xâu chỉ gồm các chữ số từ 0 đến 9.
Dữ liệu đảm bảo tổng qua tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra số cách chèn dấu chấm, lấy phần dư khi chia cho .
Ràng buộc
- .
- ; , chỉ gồm các chữ số từ 0 đến 9.
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 12 13 102 11 0 00 |
3 3 1 |
Bộ thứ nhất: có thể là 12 hoặc 1.2, có thể là 13 hoặc 1.3. Có cách thỏa mãn : , và . Bộ thứ hai: có thể là 102, 10.2 hoặc 1.0.2 (không thể là 1.02 vì có chữ số ở đầu), có thể là 11 hoặc 1.1. Có cách: , và . Bộ thứ ba: cách hợp lệ duy nhất là , , và quả thật . |
| 2 10 101 5 5 |
5 0 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: , . Các cặp thỏa mãn: , , , , . Bộ thứ hai: hai phiên bản luôn bằng nhau. |
Bình luận