trang chủ / đề bài / icpc24_mt_d

Chia kẹo

Đề bài

Mô tả

Anh là học sinh lớp bốn với ước mơ được thi ICPC World Finals. Hôm nay Anh học phép chia, và để việc học thử thách hơn, Anh muốn đổi mọi số sang các hệ cơ số khác nhau trước khi thực hiện phép chia.

Anh có n viên kẹo xếp thành một vòng tròn, viên thứ i có độ ngon là số nguyên dương a[i], và một cơ số nguyên dương m. Để việc ăn kẹo vui hơn, Anh chơi một trò chơi. Anh đổi mỗi số a[i] sang hệ cơ số m, được biểu diễn b[i] (b[i] và a[i] là cùng một số, chỉ khác cách viết). Trò chơi diễn ra như sau:

  • Anh chọn và ăn một viên kẹo i trong vòng tròn.
  • Sau khi ăn, Anh xác định hai viên kẹo kề với nó, gọi là j và k, có biểu diễn cơ số m là b[j] và b[k].
  • Anh tính tổng hai phân số b[j]b[k]+b[k]b[j], viết tổng này dưới dạng số thập phân trong hệ cơ số m và đếm số chữ số ở phần sau dấu phẩy (gồm các chữ số không tuần hoàn và các chữ số của một chu kỳ tuần hoàn). Ví dụ trong hệ cơ số 10: 514+145=3,1(571428), Anh viết 1 chữ số không tuần hoàn và 6 chữ số tuần hoàn, tổng cộng 7 chữ số; 32=1,5 có 1 chữ số; 51=5 có 0 chữ số. Trong hệ cơ số 2: 45+54=4120=(10,00(0011))2 có 2+4=6 chữ số.
  • Sau khi tính xong và ăn viên kẹo i, Anh xếp hai viên kẹo j và k (vốn kề với i) kề nhau, giữ nguyên vòng tròn. Mỗi bước số viên kẹo giảm đi một.
  • Anh lặp lại quá trình ăn kẹo cho đến khi chỉ còn hai viên.
  • Với hai viên kẹo cuối cùng, Anh cũng tính tổng phân số như trên cho hai viên đó và đếm số chữ số ở phần sau dấu phẩy, rồi ăn nốt hai viên và kết thúc trò chơi.

Trò chơi lúc đầu thì vui, nhưng Anh nhanh chóng thấy mệt vì phải viết quá nhiều chữ số, nên Anh muốn ăn hết số kẹo mà viết ít chữ số nhất. Hãy giúp Anh xác định tổng số chữ số nhỏ nhất cần viết trong suốt quá trình ăn hết n viên kẹo.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và m (2≤n≤80, 2≤m≤106).
  • Dòng tiếp theo chứa n số nguyên a1,a2,…,an (1≤ai≤106), theo thứ tự trên vòng tròn.

Dữ liệu ra

In ra một số nguyên: tổng số chữ số nhỏ nhất Anh cần viết.

Ràng buộc

  • 2≤n≤80
  • 2≤m≤106
  • 1≤ai≤106

Ví dụ

Input Output Giải thích
4 10
1 5 7 3
4 Ăn viên thứ 3 (độ ngon 7): 53+35=3,2(6), viết 2 chữ số. Còn 1,5,3; ăn viên độ ngon 3: 51+15=5,2, viết 1 chữ số. Còn 1,5: viết thêm 1 chữ số. Tổng 4.
2 10
14 5
7 145+514=3,1(571428).
5 2
4 7 5 11 6
17 Trong hệ cơ số 2: ăn viên độ ngon 7 (4120, 6 chữ số), rồi viên 11 (6130, 5 chữ số), rồi viên 5 (136, 3 chữ số), hai viên cuối 4 và 6 (3 chữ số). Tổng 17.
5 104
654074 236092 654237 254045 253310
4605392

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