Số Tiến Đạt

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Tác giả:

PhanDinhKhoi

Dạng bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Một số tự nhiên được cho là Số Tiến Đạt nếu nó chỉ chứa các số \(0\) và số \(9\).

Input

\(t(t \le 10^4)\) - số test
Mỗi test \(1\) số nguyên dương \(n(n \le 500)\)

Output

In ra số Tiến Đạt nhỏ nhất chia hết cho \(n\) (đáp án đảm bảo có nhiều nhất \(13\) chữ số).

Example

Test 1

Input

Output

90
9009
9

Bình luận

hint

dùng quay lui để vét cạn rồi tìm giá trị

thuật toán

theo đề ta có, số tiến đạt chỉ có nhiều nhất 13 chữ số và chỉ có 2 giá trị là 0 và 9
vậy số phép tính tối đa là \(2^{13}\)=8192
sau đó duyệt từ đầu tới cuối để tìm giá trị thỏa mãn chia hết cho n
độ phức tạp của thuật toán là: O(t*8192)
với t tối đa là 10^4 thì vừa đẹp

code C++

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> a;
void ham(ll i,ll t)
{
    if(i>13)
    {
        if(t==0) return;
        a.push_back(t);
        return;
    }
    ham(i+1,t*10);
    ham(i+1,t*10+9);
    return ;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ham(1,0);
    sort(a.begin(),a.end());
    ll t;
    cin>>t;
    ll n;
    while(t>0)
    {
        t--;
        cin>>n;
        for(ll i=0;i<a.size();i++)
        {
            if(a[i]%n==0)
            {
                cout<<a[i]<<endl;
                break;
            }
        }
    }
}

0

lehongduc 8:39 a.m. 22 Tháng 8, 2024

tại sao cout full 0 ko mã nhỉ :))

0

thanphong 9:09 a.m. 25 Tháng 2, 2022

tại sao tui k ăn đc test thứ 4 nhỉ

còn 1 trường hợp nào nữa sao

tui dùng sinh số mak chỉ ăn đc 4/5 cái buồn ghê

-3

donhatnam 7:14 a.m. 18 Tháng 9, 2020

Hình ảnh nhạt ghê

3

tuanha2 5:21 p.m. 15 Tháng 9, 2020

Đạt rùi 0 9 thì chúng ta sẽ có đạt 09 vậy thui đừng nghĩ sâu xa hay là đọc ngược nha

2 phản hồi

-1

donhatnam 9:18 a.m. 14 Tháng 9, 2020

Hình ảnh trên có nghĩa là gì vậy

1 phản hồi