Siêu đối xứng (THTB Đà Nẵng 2022)

Xem PDF
Tác giả:
Small
Dạng bài
Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: dx.inp Output: dx.out

Một số nguyên dương được gọi là siêu đối xứng nếu tất cả các chữ số của nó giống nhau. Chẳng hạn số \(777\) hoặc \(4444\) là các số nguyên dương siêu đối xứng.

Nhập từ bàn phím một số nguyên dương \(x\). Hãy tìm và in ra màn hình số nguyên dương \(y\) nhỏ nhất sao cho tổng \(x + y\) là một số nguyên dương siêu đối xứng.

Input

  • Gồm 1 dòng duy nhất chứa số nguyên dương \(x\) \((1 \leq x \leq 10^{16})\).

Scoring

  • Subtask \(1\) (\(50\%\) số test): \(x \le 10^6\).
  • Subtask \(2\) (\(30\%\) số test): \(10^6 < x \le 10^9\).
  • Subtask \(3\) (\(20\%\) số test): \(10^9 \le x \le 10^{16}\).

Example

Test 1

Input 
45
Output 
10
Note

\(45 + 10 = 55\)

Bình luận


  • 9
    tula    7:05 p.m. 24 Tháng 7, 2022 ← chỉnh sửa 2

    SPOILER ALERT

    ** Yêu cầu:

    • Đề bài yêu cầu tìm y nhỏ nhất và y NGUYÊN DƯƠNG ( tức là y>0 ).
    • Sau khi đọc kĩ đề t có thể dễ dàng nhận thấy ta sẽ tìm số siêu đối xứng nhỏ nhất lớn hơn x.
    • Sau khi t tìm được số siêu đối xứng nhỏ nhất lớn hơn x thì t sẽ có đáp án là y-x.

    ** Thuật toán:

    • T có thể dễ dàng nhận thấy 1 số siêu đối xứng là 1 số có số chữ số lớn hơn 2 và các số giống nhau. Do đó t có thể dễ dàng tạo 1 mảng a đứa chứa tất cả các số siêu đối xứng cho đến 10e16 ( Thỏa mãn đề bài yêu cầu ).

    • Cách tạo: T có thể tạo theo cách tạo từng dãy siêu đối xứng 11,111,1111,11111,... cho đến khi số lượng số 1 là 16 lần.Cứ như vậy cho tới số 9.

    • Code tham khảo:

      for (int i=1;i<=9;i++)
      {
      long long o=i;
      for (long long j=1;j<=16;j++)
      {
      a[++k]=i+o*10;
      o=a[k];
      }
      }

    • Sau khi tạo xong mảng a chứa tất cả các số siêu đối xứng tới 1e16, t sẽ sort mảng a để tiếp tục chặt nhị phân tìm vị trí y nhỏ nhất lớn hơn x.

    • Code tham khảo:
      while (l<=r)
      {
      long long mid=(l+r)/2;
      if (a[mid]>n)
      {
      ans=a[mid];
      r=mid-1;
      }
      else
      {
      l=mid+1;
      }
      }
      return ans;
    • Sau khi thực hiện xong tất cả công việc trên, chúng ta chỉ đơn giản lấy số siêu đối xứng nhỏ nhất lớn hơn x ( tức là ans ) trừ cho x để có được đáp án cuối cùng.
      • 9 bình luận nữa