Siêu đối xứng (THTB Đà Nẵng 2022)
Xem PDF
Đ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
45Output
10Note
\(45 + 10 = 55\)
Bình luận
Sao file output của em bị lỗi vậy, theo test là phải ra kết quả mà sao cái test nào file output của em cũng ra 222222222222224, em có thử test ở ngoài thì đúng nhưng sao đưa lên máy lại sai?
Các số có 1 chữ số có được gọi là số siêu đối xứng ko :v
sao output bị lỗi nhỉ
đáp án ko cout ra dc
Em nham
Cho em hỏi sao em bị lỗi EOFError vậy?
*Đã biết lỗi
mn 1 ngày tốt lành
cái này đâu cần binary search bro =/?
giả sử anh nhập vào một số có n chũ số
=> Anh sẽ liệt kê tất cả các số đối xứng có n chữ số
ví dụ: 123
111
222 kết quả sẽ là: 222-123=99 => in ra 99
333
444
555
666
777
888
999
ví dụ: 99
11
22
33
44
55
66
77
88
99
111 kết quả sẽ là 111-99=12
SPOILER ALERT
** Yêu cầu:
** Thuật toán:
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.
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;
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.