mọi người cùng thảo luận.
Cho trước n que diêm (n>=2), in ra số nhỏ nhất, lớn nhất mà nó có thể tạo thành.
YC: không được dư que diêm nào.
Số 0 k đứng ở đầu
Các số được xếp bởi diêm có dạng:
Thuật toán tìm số lớn nhất, nhỏ nhất có thể biểu diễn bằng n que diêm
1 Like
Số lớn nhất : Vã toàn 1. Dư que nào thì biến số 1 đầu tiên thành 7.
Số nhỏ nhất có 2 TH:
Tổng que <= 7 :
tra bảng.
Tổng que > 7:
Chia cho 7 để được n số 8.
Lấy số dư + 7 rồi tra bảng. Được bao nhiêu thì cộng thêm (n-1) số 8 phía sau.
6 Likes
Ưu tiên số lượng chữ số nên lấy số càng ít que càng tốt.
3 Likes
Bài này không đơn giản như thế đâu.
Gợi ý: Bạn thử với tất cả các n <= 35 xem đáp án ra sao đã.
Bài này từng ra trên codesignal rồi nhưng mình không có nhớ link 
3 Likes
Chuẩn luôn. Nếu lẻ thì chơi combo 7+1. Nếu chẵn thì cứ 1 mà vã.
2 Likes
Cái này k ổn nè.
Chỗ lấy số dư + 7 rồi tra bảng (khi đó số dư + 7 luôn > 7 => không thể tra bảng)
Còn tìm số lớn nhất ok rùi, thanks (y)
Ừ số nhỏ nhất không đơn giản 
Không phải vì không tra được bảng mà rất nhiều trường hợp.
Tôi viết anh em kiểm chứng nhé (viết tạm C++):
#include <string>
#include <string.h>
#include <iostream>
using namespace std;
void timSoLonNhat(int num){
int soMot = num / 2;
int soDu = num % 2;
char *buffer = new char[soMot];
memset(buffer,'1',static_cast<size_t>(soMot));
if(soDu) buffer[0]='7';
cout<<"So lon nhat : " << buffer << endl;
delete [] buffer;
}
void timSoNhoNhat(int num){
string bangDulieu[14] = { "-", "-", "1", "7", "4", "2", "6", "8", "10", "18", "22", "26", "28", "68" };
string res="";
if(num<7) {
res = bangDulieu[num];
if(res=="-"){
cout << "Khong tim duoc so nho nhat" <<endl;
return;
}
}
int soTam = num/7 -1;
int soDu = num % 7 + 7;
res = bangDulieu[soDu];
for(int i=0;i<soTam;i++) res+="8";
cout << "So nho nhat : " << res << endl;
}
int main(int argc, char *argv[]){
int soQueDiem = 123; //
timSoLonNhat(soQueDiem);
timSoNhoNhat(soQueDiem);
return 0;
}
1 Like
Tôi đang nghĩ như này:
Tổng diêm > 7:
Chia cho 7 để được n số 8.
Kiểm tra số dư:
Nếu số dư == 1 => kết quả = “10” & (n-1) số 8
else => Tra bảng. & n số 8
Bảng:
case 2: temp = 1; break;
case 3: temp = 7; break;
case 4: temp = 4; break;
case 5: temp = 2; break;
case 6: temp = 6; break;
Đã thử và ok! thanks mn!
mong mn góp ý! code java
package main;
public class MainClass {
public static void main(String[] args) {
xepSo(4);
xepSo(3);
xepSo(6);
xepSo(13);
xepSo(15);
}
private static void xepSo(int n) {
if (n > 1) {
System.out.println("So nho nhat - lon nhat duoc tao thanh tu " +n + " que diem là: "+ soNhoNhat(n) + " - " + soLonNhat(n));
}
else System.out.println("n phai >=2");
}
private static int soNhoNhat(int n) {
int soNhoNhat = 0;
int i = 0;
while (n>= 7) {
n = n - 7;
soNhoNhat = soNhoNhat*10 + 8;
i++;
}
switch (n) {
case 1: soNhoNhat = (soNhoNhat>10 ? soNhoNhat%10 : 0) + 1* (int)Math.pow(10, i);break;
case 2: soNhoNhat = soNhoNhat + 1* (int)Math.pow(10, i); break;
case 3: soNhoNhat = soNhoNhat + 7* (int)Math.pow(10, i); break;
case 4: soNhoNhat = soNhoNhat + 4* (int)Math.pow(10, i); break;
case 5: soNhoNhat = soNhoNhat + 2* (int)Math.pow(10, i); break;
case 6: soNhoNhat = soNhoNhat + 6* (int)Math.pow(10, i); break;
default: i = -1;
}
return soNhoNhat;
}
private static int soLonNhat(int n) {
int soLonNhat = 0;
int i = 0;
while (n>1) {
n = n-2;
soLonNhat = soLonNhat*10 + 1;
i++;
}
if(n == 1) {
soLonNhat = soLonNhat + 6 * (int)Math.pow(10, i-1);
}
return soLonNhat;
}
}
1 Like
Nếu có 10 que diêm có đúng không bạn ?
Có 10 que mình nghĩ số nhỏ nhất nó phải ra 22 mới đúng 
Bạn chưa tính đến trường hợp rút nhiều hơn 1 que từ số 8 và có thể sắp xếp lại khi rút n que từ số 8.
3 Likes
Hi Do Tran.
Theo mình thì thế này.
- Số chữ số và giá trị số là các yếu tố cần quan tâm.
Lớn nhất: Càng nhiều chữ số càng tốt và số càng lớn càng tốt.
Nhỏ nhất: Càng ít chữ số càng tốt và số càng nhỏ càng tốt. - Vậy chia 10 chứ số thành 6 nhóm: <số>:<số que>;
1:2; 7:3; 4:4; 2, 3, 5:5; 6, 9, 0:6; 8:7.
Và yêu cầu là không thừa que nào nên cần chú ý chẵn lẻ.
Áp dụng cho bài lớn nhất -> chọn các số thuộc nhóm có ít que nhất: 1:2 và 7:3.
Nhỏ nhất -> chọn nhóm có số que nhiều nhất trước. Với 10 que duyệt cho 8:7 sau đó dư 3 duyệt 7:3 rồi xắp xếp lại 78. Tiếp 40, 22. Dựa trên nhánh cận để tìm kiếm nhan.
1 Like
Số nhỏ nhất duyệt dfs trâu bò ra cái đáp án 
à dijkstra cũng đc
Mà với 1 tỷ que chắc chết :V
2 Likes
kết quả duyệt trâu :V
2 1
3 7
4 4
5 2
6 6
7 8
8 10
9 18
10 22
11 20
12 28
13 68
14 88
15 108
16 188
17 200
18 208
19 288
20 688
21 888
22 1088
23 1888
24 2008
25 2088
26 2888
27 6888
28 8888
29 10888
30 18888
31 20088
32 20888
33 28888
34 68888
35 88888
36 108888
37 188888
38 200888
39 208888
40 288888
41 688888
42 888888
43 1088888
44 1888888
45 2008888
46 2088888
47 2888888
48 6888888
49 8888888
50 10888888
51 18888888
52 20088888
53 20888888
54 28888888
55 68888888
56 88888888
57 108888888
58 188888888
59 200888888
60 208888888
61 288888888
62 688888888
63 888888888
64 1088888888
65 1888888888
66 2008888888
67 2088888888
68 2888888888
69 6888888888
70 8888888888
71 10888888888
72 18888888888
73 20088888888
74 20888888888
75 28888888888
76 68888888888
77 88888888888
78 108888888888
79 188888888888
80 200888888888
81 208888888888
82 288888888888
83 688888888888
84 888888888888
85 1088888888888
86 1888888888888
87 2008888888888
88 2088888888888
89 2888888888888
90 6888888888888
91 8888888888888
92 10888888888888
93 18888888888888
94 20088888888888
95 20888888888888
96 28888888888888
97 68888888888888
98 88888888888888
99 108888888888888
tìm quy luật thôi :V
4 Likes
có vẻ như quy luật là
888...
1888...
2888...
6888...
10888...
20888...
200888...
r = n % 7
(none) ứng với r=0
1 r=2
2 r=5
6 r=6
10 r=1??? 8=7+1
20 r=4??? 11=7+4
200 r=3??? 17=7*2+3
- 2 < n <= 17: truy mảng =]]
- n > 17: đặt q = n / 7, xét r = n % 7:
- r = 0: 888… (q số 8)
- r = 1: 10888… (q-1 số 8)
- r = 2: 1888… (q số 8)
- r = 3: 200888… (q-2 số 8)
- r = 4: 20888… (q-1 số 8)
- r = 5: 2888… (q số 8)
- r = 6: 6888… (q số 8)
C++ :V
std::string fast(int n) {
static std::string cache[] = {
"none", "none", "1", "7", "4", "2", "6", "8", "10",
"18", "22", "20", "28", "68", "88", "108", "188", "200",
};
if (n <= 17) return cache[n];
int q = n / 7;
switch (n % 7) {
case 0: return std::string(q, '8');
case 1: return "10" + std::string(q - 1, '8');
case 2: return "1" + std::string(q, '8');
case 3: return "200" + std::string(q - 2, '8');
case 4: return "20" + std::string(q - 1, '8');
case 5: return "2" + std::string(q, '8');
case 6: return "6" + std::string(q, '8');
}
}
test tới n=1000: https://rextester.com/EVGKQ2758
ko biết bước thêm/tạo số đúng ko :V
4 Likes
Nó chỉ loanh quanh mười mấy trường hợp rồi lặp lại thôi.
2 Likes
ờm, tham lam số 8 rồi xét 7 trường hợp số dư là đc :V
rút gọn cái cache còn 9 số thôi :V
std::string fast(int n) {
static std::string cc[] = {"1", "7", "4", "2", "6", "8", "10", "18", "22"};
if (n < 2) return "";
if (n < 11) return cc[n - 2];
switch (n % 7) {
case 0: return std::string(n / 7, '8');
case 1: return "10" + std::string(n / 7 - 1, '8');
case 2: return "1" + std::string(n / 7, '8');
case 3: return "200" + std::string(n / 7 - 2, '8');
case 4: return "20" + std::string(n / 7 - 1, '8');
case 5: return "2" + std::string(n / 7, '8');
case 6: return "6" + std::string(n / 7, '8');
}
}
edit: ko cần cache luôn :V
std::string fast(unsigned n) {
switch (n % 7) {
case 0: return std::string(n / 7, '8');
case 1: return n == 1 ? "" : "10" + std::string(n / 7 - 1, '8');
case 2: return "1" + std::string(n / 7, '8');
case 3:
return n > 14 ? "200" + std::string(n / 7 - 2, '8')
: n == 3 ? "7" : "22";
case 4: return n == 4 ? "4" : ("20" + std::string(n / 7 - 1, '8'));
case 5: return "2" + std::string(n / 7, '8');
case 6: return "6" + std::string(n / 7, '8');
}
}
4 Likes
thanks bạn, nhưng nó k ổn.
VD: 10 que diêm số nhỏ nhất là 22 không phải 78.
p/s: t bị cấm bình luận trong 3h, ai chỉ giùm nguyên nhân với.
do tài khoản mới thì bị cấm à? @@
xin lỗi vì tôi k học C++, có nhiều ký hiệu thấy lạ lạ, chưa hiểu hết được đoạn code làm gì
Nhưng nếu k nhầm bạn check lại trường hợp này với n = 10. KQ chưa đúng thì phải
mn nghĩ sao về cách giải:
Từ n diêm, tạo ra những cách chia cặp như thế nào. mà ưu tiên việc tốn diêm nhất (để số lần lấy diêm ít nhất) & số nhỏ nhất.
VD: 10 diêm sẽ có cách
C1: 7 diêm (số 8) & 3 diêm (số 7)
C2: 6 diêm (số 0) (6 diêm = số 0, 6, 9 => chọn số 0 vì 0 nhỏ nhất) & 4 diêm (số 4) (4 diêm = 2 diêm + 2 diêm => k xét trường hợp này vì ưu tiên chọn số lần lấy diêm ít)
C3: 5 & 5 diêm (số 2 & 2)
Dừng k giảm nữa vì giảm thì trùng C2 (4 diêm & 6 diêm)
Sau đó sắp xếp các số theo nhỏ đến lớn (số 0 không đứng đầu, nếu có đổi thành số 6)
C1: kết quả được số 78
C2: kq = 40
C3: kq = 22
So sánh các kết quả. Thấy cách 3 là kết quả nhỏ nhất
return 10 diêm có được số 22 là nhỏ nhất!
2 Likes
10 diêm là case 3 đó :V
case 3:
return n > 14 ? "200" + std::string(n / 7 - 2, '8')
: n == 3 ? "7" : "22";
chia 7 dư 3 có 3 trường hợp: 3, 10 và lớn hơn 14. 10 là trường hợp đặc biệt, return 22 nè.
học Java mà đọc code C++ ko hiểu là sao @_@ ko hiểu switch case à :V Có phải code cao siêu gì đâu… ?: cũng dễ đọc mà :V
edit: code Java đây, copy y hệt từ C++ sang chỉ thêm 1 hàm repeat thôi :V đọc ko hiểu là sao :V
import java.util.*;
import java.lang.*;
class Rextester
{
public static String repeat(int n, char c)
{
char[] s = new char[n];
Arrays.fill(s, c);
return new String(s);
}
public static String fast(int n)
{
switch (n % 7)
{
case 0: return repeat(n / 7, '8');
case 1: return n == 1 ? "" : "10" + repeat(n / 7 - 1, '8');
case 2: return "1" + repeat(n / 7, '8');
case 3:
return n > 14 ? "200" + repeat(n / 7 - 2, '8')
: n == 3 ? "7" : "22";
case 4: return n == 4 ? "4" : ("20" + repeat(n / 7 - 1, '8'));
case 5: return "2" + repeat(n / 7, '8');
case 6: return "6" + repeat(n / 7, '8');
}
return "";
}
public static void main(String args[])
{
for (int i = 2; i < 100; ++i)
System.out.println(i + " " + fast(i));
}
}
chạy thử: https://rextester.com/ZSQRK99012
output
2 1
3 7
4 4
5 2
6 6
7 8
8 10
9 18
10 22
11 20
12 28
13 68
14 88
15 108
16 188
17 200
18 208
19 288
20 688
21 888
22 1088
23 1888
24 2008
25 2088
26 2888
27 6888
28 8888
29 10888
30 18888
31 20088
32 20888
33 28888
34 68888
35 88888
36 108888
37 188888
38 200888
39 208888
40 288888
41 688888
42 888888
43 1088888
44 1888888
45 2008888
46 2088888
47 2888888
48 6888888
49 8888888
50 10888888
51 18888888
52 20088888
53 20888888
54 28888888
55 68888888
56 88888888
57 108888888
58 188888888
59 200888888
60 208888888
61 288888888
62 688888888
63 888888888
64 1088888888
65 1888888888
66 2008888888
67 2088888888
68 2888888888
69 6888888888
70 8888888888
71 10888888888
72 18888888888
73 20088888888
74 20888888888
75 28888888888
76 68888888888
77 88888888888
78 108888888888
79 188888888888
80 200888888888
81 208888888888
82 288888888888
83 688888888888
84 888888888888
85 1088888888888
86 1888888888888
87 2008888888888
88 2088888888888
89 2888888888888
90 6888888888888
91 8888888888888
92 10888888888888
93 18888888888888
94 20088888888888
95 20888888888888
96 28888888888888
97 68888888888888
98 88888888888888
99 108888888888888
5 Likes
switch case tôi đọc hiểu mà, nhưng hnay sr, tôi đọc k kỹ, bị nhầm case vẫn đang đinh ninh 10/7 dư 1 :)))
à, tôi tự học Java thôi. tôi k phải học cntt, đọc thấy bài này hay hay nên share để mn cùng thảo luận
thanks nha
3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?