Xếp số bằng que diêm 1 - LCOJ: Luyện Code Online Judge

XEPSO1 - Xếp số bằng que diêm 1

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Xét cách biểu diễn số bởi các que diêm:

Với một số lượng que diêm cho trước, hãy xác định số nhỏ nhất và số lớn nhất mà bạn có thể biểu diễn được.

Bạn không được để thừa que diêm nào.
Số được biểu diễn không bắt đầu bởi chữ số ~0~.

Input

Dòng đầu ghi số nguyên dương ~T~ là số bộ test;
~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ là số que diêm.

Giới hạn:

~1≤T≤38,2≤n≤39~

Output

Với mỗi số ~n~ là số que diêm, in ra trên một dòng hai số nguyên dương là số nhỏ nhất và số lớn nhất mà ~n~ que diêm biểu diễn được, mỗi số cách nhau bởi một khoảng trắng.

Sample

Input #1

Output #1

7 7
2 71
10 1111

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

mducc đã bình luận lúc 3, Tháng 6, 2026, 3:16 ← chỉnh sửa →

hint

minDp[i] = string nhỏ nhất dùng i que diêm.
maxDp[i] = string lớn nhất dùng i que diêm.
Khởi tạo: minDp[2]="1", minDp[3]="7", minDp[4]="4", minDp[5]="2", minDp[6]="6", minDp[7]="8".
Với mỗi i từ 8 đến n:
Duyệt từng chữ số d (0..9), lấy pre = i - que[d].
Nếu pre >= 2:
cur = minDp[pre] + to_string(d)
So sánh với minDp[i] (ngắn hơn thì lấy, bằng độ dài thì so sánh xâu)
Làm tương tự với maxDp[i] nhưng so sánh ngược lại.

code tham khảo (c++)

#include <bits/stdc++.h>
using namespace std;
int que[] = {6,2,5,5,4,5,6,3,7,6};
string mn[40], mx[40];
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for (int i=0; i < 40; i++) mn[i] = string(20,'9'), mx[i] = "";
    mn[2]="1"; mn[3]="7"; mn[4]="4"; mn[5]="2"; mn[6]="6"; mn[7]="8";
    mx[2]="1"; mx[3]="7"; mx[4]="11"; mx[5]="71"; mx[6]="111"; mx[7]="711";
    for (int i=8; i<=39; i++) {
        for (int d=0; d<=9; d++) {
            int pre = i - que[d];
            if (pre < 2) continue;
            string cur = mn[pre] + char(d+'0');
            if (cur.length() < mn[i].length() || (cur.length() == mn[i].length() && cur < mn[i]))
                mn[i] = cur;
            string cur2 = mx[pre] + char(d+'0');
            if (cur2.length() > mx[i].length() || (cur2.length() == mx[i].length() && cur2 > mx[i]))
                mx[i] = cur2;
        }
    }
    int t; cin>>t;
    while(t--) {
        int n; cin>>n;
        cout << mn[n] << " " << mx[n] << "\n";
    }
    return 0;
}

include <bits/stdc++.h>

using namespace std;

int match[10] = {6,2,5,5,4,5,6,3,7,6};

string maxNumber(int n){ string res; if(n % 2) { res += '7'; n -= 3; } res += string(n/2, '1'); return res; }

// DP tìm số chữ số tối thiểu int minDigits[100]; int main() { ios::syncwithstdio(false); cin.tie(nullptr);

for(int i=0;i<=100;i++) minDigits[i] = 1e9;
minDigits[0] = 0;
for(int i=1;i<=100;i++){
    for(int d=0;d<=9;d++){
        if(i >= match[d]) minDigits[i] = min(minDigits[i], minDigits[i-match[d]] + 1);
    }
}

int t; cin >> t;
while(t--){
    int n; cin >> n;
    // Số lớn nhất
    string largest = maxNumber(n);

    // Số nhỏ nhất
    string smallest;
    int rem = n;
    while(rem > 0){
        for(int d=0; d<=9; d++){
            if(smallest.empty() && d==0) continue; // chữ số đầu không 0
            if(rem >= match[d] && minDigits[rem-match[d]] == minDigits[rem]-1){
                smallest += char('0'+d);
                rem -= match[d];
                break;
            }
        }
    }

    cout << smallest << " " << largest << "\n";
}

}

1

nguyendangkhoinguyen đã bình luận lúc 10, Tháng 7, 2025, 1:16

link bn dua bi block

0

kekuda01 đã bình luận lúc 12, Tháng 1, 2025, 13:50

cho vong lap tu 0 den max so dau tien chuyen doi thanh n que diem la min con max la 111...1 neu n chia het cho 2 con neu khong chia het cho 2 thi max la 7111...1

1

dainghiajustiin đã bình luận lúc 29, Tháng 2, 2024, 10:17 ← chỉnh sửa →

code tham khảo nếu quá bí nhé các bạn :vv

https://github.com/dainghiajustiin/LCOJ/blob/main/XEPSO1

0

Yorickur đã bình luận lúc 13, Tháng 1, 2024, 11:05

Dạ ai có ý tưởng không ạ cho em xin với ạ em code nhưng AC được từ 1 đến 5 thôi, còn sai 6 7, time out 8 9. em biết mình time out do dùng quay lui để giải nhưng em không biết mình sai ở test 6 7 là sai ở đâu.

0

2009_giangkhanh đã bình luận lúc 19, Tháng 9, 2023, 14:47

cho e xin ý tưởng với ạ