trang chủ / đề bài / icpc26_nat_a

Đá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ố 0 ở đầ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ụ, 1.2.3<1.2.4, 1.9<1.10 và 1.3<2.1.
  • 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ụ, 1.3<1.3.1 và 1.3<1.3.0.

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ố A và B. Bạn cần chèn dấu chấm vào A và vào B để khôi phục chúng thành các phiên bản VA và VB. 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ả VA và VB đều là phiên bản hợp lệ và VA<VB. Hai cách được coi là khác nhau nếu cặp (VA,VB) 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 109+7.

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 τ (1≤τ≤5·105). 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 A và B (1≤|A|,|B|≤5·105), 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 |A|+|B| qua tất cả các bộ dữ liệu không vượt quá 106.

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 109+7.

Ràng buộc

  • 1≤τ≤5·105.
  • 1≤|A|,|B|≤5·105; A, B chỉ gồm các chữ số từ 0 đến 9.
  • Tổng |A|+|B| qua tất cả các bộ dữ liệu không vượt quá 106.

Ví dụ

Input Output Giải thích
3
12 13
102 11
0 00
3
3
1
Bộ thứ nhất: VA có thể là 12 hoặc 1.2, VB có thể là 13 hoặc 1.3. Có 3 cách thỏa mãn VA<VB: 12<13, 1.2<13 và 1.2<1.3. Bộ thứ hai: VA có thể là 102, 10.2 hoặc 1.0.2 (không thể là 1.02 vì có chữ số 0 ở đầu), VB có thể là 11 hoặc 1.1. Có 3 cách: 10.2<11, 1.0.2<11 và 1.0.2<1.1. Bộ thứ ba: cách hợp lệ duy nhất là VA=0, VB=0.0, và quả thật 0<0.0.
2
10 101
5 5
5
0
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: VA∈{10,1.0}, VB∈{101,10.1,1.0.1}. Các cặp thỏa mãn: 10<101, 10<10.1, 1.0<101, 1.0<10.1, 1.0<1.0.1. Bộ thứ hai: hai phiên bản luôn bằng nhau.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0