trang chủ / đề bài / icpcwf06_d

Số lưỡng phân

Đề bài

Mô tả

Ban giám đốc công ty nơi bạn làm việc muốn gửi cho nhau các thông điệp được mã hoá. Thay vì dùng phần mềm mã hoá có sẵn như PGP, họ giao cho bộ phận IT tự giải quyết việc mã hoá. Bộ phận IT chọn một cách làm cần các khoá số nguyên "công khai" và "bí mật". Ý tưởng là ai cũng thấy khoá công khai của bạn, nhưng chỉ bạn biết khoá bí mật của mình.

Người bạn thân nhất của bạn trong công ty là một người tuyệt vời nhưng là một lập trình viên không mấy tuyệt vời. Anh ấy đã tạo ra một cơ chế khoá công khai, bí mật như sau. Khoá công khai có thể là một số nguyên dương bất kỳ. Khoá bí mật tương ứng là số lưỡng phân nhỏ nhất lớn hơn khoá công khai và là bội của khoá công khai.

Một số lưỡng phân là một số nguyên dương có đúng 2 chữ số thập phân khác nhau s và t sao cho s≠0 và mọi lần xuất hiện của s đều đứng trước mọi lần xuất hiện của t. Ví dụ 44444411 là số lưỡng phân (s là 4 và t là 1), các số 41, 10000000 và 5555556 cũng vậy. Tuy nhiên, cả 4444114 lẫn 44444 đều không phải số lưỡng phân.

Để ý rằng số lưỡng phân lớn 88888888888800000 có thể mô tả gọn là 12 chữ số 8 theo sau bởi 5 chữ số 0. Mọi số lưỡng phân đều có thể biểu diễn bằng bốn số m s n t: s và t là chữ số đứng đầu và chữ số đứng cuối như trên, m là số lần chữ số s xuất hiện trong số lưỡng phân, và n là số lần chữ số t xuất hiện.

Vấn đề của cơ chế này là tính khoá bí mật từ khoá công khai không quá khó. Bạn cần thuyết phục người bạn rằng cơ chế của anh ấy không an toàn trước khi anh ấy mất việc vì quyết định tồi này! Hãy viết chương trình nhận vào các khoá công khai và in ra khoá bí mật tương ứng.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Mỗi bộ test nằm trên một dòng riêng, gồm một khoá công khai duy nhất là số nguyên trong khoảng từ 1 đến 99999.

Sau bộ test cuối cùng là một dòng chứa số 0.

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm khoá công khai, một dấu hai chấm, rồi 4 số nguyên m s n t như mô tả ở trên (định dạng như ví dụ).

Ràng buộc

  • Mỗi khoá công khai là số nguyên từ 1 đến 99999.
  • Mỗi file có từ 1 đến 100 khoá công khai (không tính dòng 0 cuối cùng).

Ví dụ

Input Output Giải thích
125
17502
2005
0
125: 1 5 2 0
17502: 4 7 4 8
2005: 3 2 3 5
Khoá bí mật lần lượt là 500=4·125, 77778888=4444·17502 và 222555=111·2005.
10
1
41
99999
0
10: 1 2 1 0
1: 1 1 1 0
41: 1 8 1 2
99999: 5 9 1 0
Ví dụ tự thêm. 10 là số lưỡng phân nhưng khoá bí mật phải lớn hơn hẳn khoá công khai, nên đáp án là 20. Với khoá 1, đáp án là 10 (số 1 đến 9 chỉ có một chữ số khác nhau). Khoá 41 cho 82, khoá 99999 cho 999990.

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