BÀI TẬP Ở NHÀ

https://baitaponha.com

Tích riêng | Câu 4 Đề HSG tin 11 Nghệ An | Năm 2014 - 2015

Đây là câu 4 nên là một câu khó. Thoạt đầu đọc đề thì có vẻ rất dễ hiểu, nhưng khi xử lý code thì sẽ gặp nhiều khó khăn. Bởi theo định nghĩa tích riêng của một số là tích của số đó với các chữ số của nó. Và bài toán yêu cầu đếm các số có tích riêng thuộc khoảng [A; B] với 1 <= A, B <= 1018 , Như vậy A, B rất lớn. Một điều khó khăn nữa là: nếu a < b nhưng chúng ta sẽ không biết được TR(a) và TR(b) số nào lớn hơn. Ví dụ khi A = 20; B = 30 thì ta sẽ tìm được những số có tích riêng nằm trong khoảng [20; 30] là 5 và 12, có nghĩa trong khoảng này chỉ có 2 số cần tìm. Vậy công thức để máy tính tìm được 5 và 12 là gì, mời các bạn cùng tham khảo lời giải.
Tích riêng
 

Đề bài. (3 điểm) Tích riêng                                                                      

Tích_chữ số của một số nguyên dương là tích các chữ số thập phân của số đó.
Ví dụ: Tích_chữ số của số 2612 là 2.6.1.2 = 24.
Tích_riêng của một số là tích của số đó với Tích_chữ số của nó.
Ví dụ: Tích_riêng của số 2612 là 2612.24 = 62688.
Yêu cầu: Cho 2 số nguyên dương A và B. Hãy tính số các số nguyên dương có Tích_riêng của nó thuộc đoạn [A, B].
Dữ liệu vào từ file TICH.INP: Chỉ một dòng duy nhất chứa 2 số nguyên dương A và B cách nhau ít nhất một ký tự trống (1 < A < B < 1018).
Kết quả ghi ra file TICH.OUT: Chỉ chứa một số duy nhất là số tìm được.
Ví dụ:
TICH.INP TICH.OUT TICH.INP TICH.OUT TICH.INP TICH.OUT
20 30 2 145 192 4 2224222 2224222 1

Lưu ý: Có 50% số test của bài có A và B không vượt quá 1012.

Giải thích test thứ 2: Có 4 số  19, 24, 32 và 41 có Tích_riêng lần lượt là  171, 192, 192 và 164 thuộc đoạn [145, 192].

Lời giải:

Thoạt đầu đọc đề thì ta thấy cách tìm tích riêng của một số thì đơn giản là lấy tích các tích các chữ số của số nguyên rồi nhân với chính nó. Và sau đó ta có thể kiểm tra các tích riêng thuộc đoạn  [A; B]. Nếu thực hiện như vậy thì sẽ không thể full test bài này bởi dữ liệu cho là số rất lớn (1 < A < B < 1018). Tuy vậy tôi cũng xin trình bày code bằng Python để các bạn tham khảo. (Cách này không được điểm tối đa bởi các bạn có thể tham khảo bộ test dưới file đính kèm, sang test 3 đã là số có 8 chữ số): 
def tich_chu_so(n):
    res = 1
    while n > 0:
        res *= n % 10
        n //= 10
    return res

def tich_rieng(n):
    return n * tich_chu_so(n)

def tim_so(x,y):
    count = 0
    for i in range(1,y+1):
        if '0' in str(i):
            continue
        elif tich_rieng(i) >= x and tich_rieng(i) <= y:
            count += 1
    return count

if __name__ == "__main__":
    with open("TICH.INP", "r") as f:
        A, B = map(int, f.readline().split())

    with open("TICH.OUT", "w") as f:
        f.write(str(tim_so(A, B)))

Giải thích: Trong code trên hàm tim_so chỉ tìm các số có chữ số khác 0 và những số nhỏ hơn hoặc bằng b. Vì những số có chữ số là 0 thì tích riêng chắc chắn bằng 0, còn lại những số lớn hơn b thì tích riêng sẽ lớn hơn b.

Thuật toán đệ quy và code mẫu bằng Pascal.

program TICH_RIENG;
const   fi = 'TICH.inp';
        fo = 'TICH.out';
var
   memo : array[0..17,0..29,0..18,0..12,0..10] of int64;
   f : array[1..4] of longint = ( 2, 3, 5, 7 );
   k : array[1..4] of longint = ( 0, 0, 0, 0 );
   code : array[0..9,1..4] of longint = (
      ( 0, 0, 0, 0 ),
      ( 0, 0, 0, 0 ),
      ( 1, 0, 0, 0 ),
      ( 0, 1, 0, 0 ),
      ( 2, 0, 0, 0 ),
      ( 0, 0, 1, 0 ),
      ( 1, 1, 0, 0 ),
      ( 0, 0, 0, 1 ),
      ( 3, 0, 0, 0 ),
      ( 0, 2, 0, 0 )
   );
function rec( digits : longint; a, pot, lo, hi : int64 ) : int64;
var
   b : int64;
   memoize, ok : boolean;
   digit, i : longint;
begin
   b := a + pot-1;
   if (a > hi) or (b < lo) then begin
      rec := 0;
      exit;
   end;

   if digits = 18 then begin
      if (k[1] > 0) or (k[2] > 0) or (k[3] > 0) or (k[4] > 0) then rec := 0 else rec := 1;
      exit;
   end;

   if (a >= lo) and (b <= hi) then memoize := true else memoize := false;

   if memoize and (memo[digits,k[1],k[2],k[3],k[4]] >= 0) then begin
      rec := memo[digits][k[1]][k[2]][k[3]][k[4]];
      exit;
   end;

   pot := pot div 10;

   rec := 0;

   for digit := 0 to 9 do begin
      if (digit = 0) and (a <> 0) then continue;

      ok := true;
      for i := 1 to 4 do
         if code[digit,i] > k[i] then ok := false;
      if not ok then continue;

      for i := 1 to 4 do k[i] := k[i] - code[digit,i];
      rec := rec + rec( digits+1, a + digit*pot, pot, lo, hi );
      for i := 1 to 4 do k[i] := k[i] + code[digit,i];
   end;

   if memoize then memo[digits,k[1],k[2],k[3],k[4]] := rec;
end;

var
   lo, hi, rjesenje : int64;

function ceil( a, b : int64 ) : int64;
begin
   ceil := (a+b-1) div b;
end;

function floor( a, b : int64 ) : int64;
begin
   floor := a div b;
end;

procedure gen( limit, product : int64; factor : longint );
begin
   if (product > 1000000000) or (product*product > limit) then exit;

   if factor > 4 then begin;
      rjesenje := rjesenje + rec( 0, 0, 1000000000000000000, ceil(lo,product), floor(hi,product) );
   end else begin
      gen( limit, product, factor + 1 );
      inc( k[factor] );
      gen( limit, product*f[factor], factor );
      dec( k[factor] );
   end;
end;

   var dig, a, b, c, d : longint;
begin
   assign(input,fi);
   reset(input);
   assign(output,fo);
   rewrite(output);
   readln( lo, hi );

   for dig := 0 to 17 do
   for a := 0 to 29 do
   for b := 0 to 18 do
   for c := 0 to 12 do
   for d := 0 to 10 do
      memo[dig,a,b,c,d] := -1;

   gen( hi, 1, 1 );

   writeln( rjesenje );
end.

Biến

  • memo: Mảng 5 chiều lưu trữ kết quả của các giá trị đã tính trước đó.
  • f: Mảng các số nguyên tố 2, 3, 5 và 7.
  • k: Mảng theo dõi số lần mỗi số nguyên tố đã được sử dụng trong một số.
  • code: Mảng cho biết liệu một chữ số có chia hết cho bất kỳ số nguyên tố nào hay không.
  • lo: Giới hạn dưới của khoảng.
  • hi: Giới hạn trên của khoảng.
  • rjesenje: Số lượng tích riêng trong khoảng lo; hi.

Hàm

  • rec: Hàm đệ quy tính số lượng tích riêng trong khoảng [lo, hi].
  • ceil: Hàm trả về số nguyên nhỏ nhất lớn hơn hoặc bằng một số cho trước.
  • floor: Hàm trả về số nguyên lớn nhất nhỏ hơn hoặc bằng một số cho trước.
  • gen: Hàm tạo ra tất cả các tích riêng trong khoảng.
Đối với code pascal thì chạy full test. Hiện tại các test của đề thi có dưới file đinh kèm, các bạn tải về và chạy thử nhé.
 

Tác giả: admin

Bạn đã không sử dụng Site, Bấm vào đây để duy trì trạng thái đăng nhập. Thời gian chờ: 60 giây