Bài toán: Tìm nghiệm sử dụng Quay lui

c++

(Đạt Phạm) #1

Nếu chạy thử từng trường hợp 1 và kiểm tra thì sẽ phải thử 910 lần. Như vậy thời gian duyệt sẽ khá lớn. Có cách nào để giảm số lần thử đi không nhỉ?


(‏) #2

vì k <= 100 nên làm 1 cái mảng 100 phần tử chứa kết quả chạy sẵn rồi trả về answer[k-1] là xong :smiling_imp:


(Đạt Phạm) #3

NO :innocent::innocent:


(rogp10) #4

Không lớn đến thế :smiley: hãy suy nghĩ về bản chất đệ quy của bài toán :smiley:

spoil

nhánh cận đó


(Đạt Phạm) #5

Mình cũng nghĩ đến nhanh cận mà chưa làm được


(‏) #6

hơi dài nhưng chắc chạy đúng :smiling_face_with_three_hearts:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::vector<std::vector<std::string>> answer{
        {},
        {},
        {},
        {},
        {},
        {},
        {},
        {},
        {},
        {},
        {
            "1111111111",
        },
        {},
        {},
        {
            "1111111112",
        },
        {},
        {},
        {
            "1111111122",
        },
        {},
        {
            "1111111113",
        },
        {
            "1111111222",
        },
        {},
        {
            "1111111123",
        },
        {
            "1111112222",
        },
        {},
        {
            "1111111223",
        },
        {
            "1111111114",
            "1111122222",
        },
        {
            "1111111133",
        },
        {
            "1111112223",
        },
        {
            "1111111124",
            "1111222222",
        },
        {
            "1111111233",
        },
        {
            "1111122223",
        },
        {
            "1111111224",
            "1112222222",
        },
        {
            "1111112233",
        },
        {
            "1111111134",
            "1111222223",
        },
        {
            "1111111115",
            "1111111333",
            "1111112224",
            "1122222222",
        },
        {
            "1111122233",
        },
        {
            "1111111234",
            "1112222223",
        },
        {
            "1111111125",
            "1111112333",
            "1111122224",
            "1222222222",
        },
        {
            "1111222233",
        },
        {
            "1111112234",
            "1122222223",
        },
        {
            "1111111144",
            "1111111225",
            "1111122333",
            "1111222224",
            "2222222222",
        },
        {
            "1111111334",
            "1112222233",
        },
        {
            "1111111135",
            "1111113333",
            "1111122234",
            "1222222223",
        },
        {
            "1111111244",
            "1111112225",
            "1111222333",
            "1112222224",
        },
        {
            "1111112334",
            "1122222233",
        },
        {
            "1111111116",
            "1111111235",
            "1111123333",
            "1111222234",
            "2222222223",
        },
        {
            "1111112244",
            "1111122225",
            "1112222333",
            "1122222224",
        },
        {
            "1111122334",
            "1222222233",
        },
        {
            "1111111126",
            "1111111344",
            "1111112235",
            "1111223333",
            "1112222234",
        },
        {
            "1111111145",
            "1111113334",
            "1111122244",
            "1111222225",
            "1122222333",
            "1222222224",
        },
        {
            "1111111335",
            "1111133333",
            "1111222334",
            "2222222233",
        },
        {
            "1111111226",
            "1111112344",
            "1111122235",
            "1112223333",
            "1122222234",
        },
        {
            "1111111245",
            "1111123334",
            "1111222244",
            "1112222225",
            "1222222333",
            "2222222224",
        },
        {
            "1111111136",
            "1111112335",
            "1111233333",
            "1112222334",
        },
        {
            "1111112226",
            "1111122344",
            "1111222235",
            "1122223333",
            "1222222234",
        },
        {
            "1111111444",
            "1111112245",
            "1111223334",
            "1112222244",
            "1122222225",
            "2222222333",
        },
        {
            "1111111236",
            "1111113344",
            "1111122335",
            "1112233333",
            "1122222334",
        },
        {
            "1111111345",
            "1111122226",
            "1111133334",
            "1111222344",
            "1112222235",
            "1222223333",
            "2222222234",
        },
        {
            "1111111117",
            "1111111155",
            "1111112444",
            "1111113335",
            "1111122245",
            "1111333333",
            "1112223334",
            "1122222244",
            "1222222225",
        },
        {
            "1111112236",
            "1111123344",
            "1111222335",
            "1122233333",
            "1222222334",
        },
        {
            "1111111146",
            "1111112345",
            "1111222226",
            "1111233334",
            "1112222344",
            "1122222235",
            "2222223333",
        },
        {
            "1111111127",
            "1111111255",
            "1111111336",
            "1111122444",
            "1111123335",
            "1111222245",
            "1112333333",
            "1122223334",
            "1222222244",
            "2222222225",
        },
        {
            "1111122236",
            "1111223344",
            "1112222335",
            "1222233333",
            "2222222334",
        },
        {
            "1111111246",
            "1111113444",
            "1111122345",
            "1112222226",
            "1112233334",
            "1122222344",
            "1222222235",
        },
        {
            "1111111227",
            "1111111445",
            "1111112255",
            "1111112336",
            "1111133344",
            "1111222444",
            "1111223335",
            "1112222245",
            "1122333333",
            "1222223334",
            "2222222244",
        },
        {
            "1111113345",
            "1111222236",
            "1111333334",
            "1112223344",
            "1122222335",
            "2222233333",
        },
        {
            "1111111137",
            "1111111355",
            "1111112246",
            "1111123444",
            "1111133335",
            "1111222345",
            "1113333333",
            "1122222226",
            "1122233334",
            "1222222344",
            "2222222235",
        },
        {
            "1111112227",
            "1111112445",
            "1111122255",
            "1111122336",
            "1111233344",
            "1112222444",
            "1112223335",
            "1122222245",
            "1222333333",
            "2222223334",
        },
        {
            "1111111346",
            "1111123345",
            "1112222236",
            "1112333334",
            "1122223344",
            "1222222335",
        },
        {
            "1111111156",
            "1111111237",
            "1111112355",
            "1111113336",
            "1111122246",
            "1111223444",
            "1111233335",
            "1112222345",
            "1123333333",
            "1222222226",
            "1222233334",
            "2222222344",
        },
        {
            "1111114444",
            "1111122227",
            "1111122445",
            "1111222255",
            "1111222336",
            "1112233344",
            "1122222444",
            "1122223335",
            "1222222245",
            "2222333333",
        },
        {
            "1111112346",
            "1111133444",
            "1111223345",
            "1122222236",
            "1122333334",
            "1222223344",
            "2222222335",
        },
        {
            "1111111256",
            "1111112237",
            "1111113445",
            "1111122355",
            "1111123336",
            "1111222246",
            "1111333344",
            "1112223444",
            "1112233335",
            "1122222345",
            "1223333333",
            "2222222226",
            "2222233334",
        },
        {
            "1111111118",
            "1111111147",
            "1111111455",
            "1111124444",
            "1111133345",
            "1111222227",
            "1111222445",
            "1112222255",
            "1112222336",
            "1113333334",
            "1122233344",
            "1222222444",
            "1222223335",
            "2222222245",
        },
        {
            "1111111337",
            "1111113355",
            "1111122346",
            "1111233444",
            "1111333335",
            "1112223345",
            "1133333333",
            "1222222236",
            "1222333334",
            "2222223344",
        },
        {
            "1111111446",
            "1111112256",
            "1111122237",
            "1111123445",
            "1111222355",
            "1111223336",
            "1112222246",
            "1112333344",
            "1122223444",
            "1122233335",
            "1222222345",
            "2223333333",
        },
        {
            "1111111128",
            "1111111247",
            "1111112455",
            "1111113346",
            "1111224444",
            "1111233345",
            "1112222227",
            "1112222445",
            "1122222255",
            "1122222336",
            "1123333334",
            "1222233344",
            "2222222444",
            "2222223335",
        },
        {
            "1111111356",
            "1111112337",
            "1111123355",
            "1111133336",
            "1111222346",
            "1112233444",
            "1112333335",
            "1122223345",
            "1233333333",
            "2222222236",
            "2222333334",
        },
        {
            "1111112446",
            "1111122256",
            "1111134444",
            "1111222237",
            "1111223445",
            "1112222355",
            "1112223336",
            "1122222246",
            "1122333344",
            "1222223444",
            "1222233335",
            "2222222345",
        },
        {
            "1111111228",
            "1111112247",
            "1111114445",
            "1111122455",
            "1111123346",
            "1111333444",
            "1112224444",
            "1112233345",
            "1122222227",
            "1122222445",
            "1222222255",
            "1222222336",
            "1223333334",
            "2222233344",
        },
        {
            "1111111166",
            "1111112356",
            "1111122337",
            "1111133445",
            "1111223355",
            "1111233336",
            "1112222346",
            "1113333344",
            "1122233444",
            "1122333335",
            "1222223345",
            "2233333333",
        },
        {
            "1111111138",
            "1111111347",
            "1111113455",
            "1111122446",
            "1111222256",
            "1111234444",
            "1111333345",
            "1112222237",
            "1112223445",
            "1122222355",
            "1122223336",
            "1133333334",
            "1222222246",
            "1222333344",
            "2222223444",
            "2222233335",
        },
        {
            "1111111157", "1111111555", "1111112228", "1111113337",
            "1111122247", "1111124445", "1111133355", "1111222455",
            "1111223346", "1112333444", "1113333335", "1122224444",
            "1122233345", "1222222227", "1222222445", "1333333333",
            "2222222255", "2222222336", "2223333334",
        },
        {
            "1111111266",
            "1111113446",
            "1111122356",
            "1111222337",
            "1111233445",
            "1112223355",
            "1112233336",
            "1122222346",
            "1123333344",
            "1222233444",
            "1222333335",
            "2222223345",
        },
        {
            "1111111238",
            "1111111456",
            "1111112347",
            "1111123455",
            "1111133346",
            "1111222446",
            "1112222256",
            "1112234444",
            "1112333345",
            "1122222237",
            "1122223445",
            "1222222355",
            "1222223336",
            "1233333334",
            "2222222246",
            "2222333344",
        },
        {
            "1111111257", "1111112555", "1111113356", "1111122228",
            "1111123337", "1111144444", "1111222247", "1111224445",
            "1111233355", "1111333336", "1112222455", "1112223346",
            "1122333444", "1123333335", "1222224444", "1222233345",
            "2222222227", "2222222445", "2333333333",
        },
        {
            "1111112266",
            "1111123446",
            "1111222356",
            "1111334444",
            "1112222337",
            "1112233445",
            "1122223355",
            "1122233336",
            "1222222346",
            "1223333344",
            "2222233444",
            "2222333335",
        },
        {
            "1111112238",
            "1111112456",
            "1111122347",
            "1111134445",
            "1111223455",
            "1111233346",
            "1112222446",
            "1113333444",
            "1122222256",
            "1122234444",
            "1122333345",
            "1222222237",
            "1222223445",
            "2222222355",
            "2222223336",
            "2233333334",
        },
        {
            "1111111148", "1111111366", "1111111447", "1111112257",
            "1111114455", "1111122555", "1111123356", "1111222228",
            "1111223337", "1111244444", "1111333445", "1112222247",
            "1112224445", "1112233355", "1112333336", "1122222455",
            "1122223346", "1133333344", "1222333444", "1223333335",
            "2222224444", "2222233345",
        },
        {
            "1111111338",
            "1111113347",
            "1111122266",
            "1111133455",
            "1111223446",
            "1112222356",
            "1112334444",
            "1113333345",
            "1122222337",
            "1122233445",
            "1222223355",
            "1222233336",
            "1333333334",
            "2222222346",
            "2223333344",
        },
        {
            "1111111119", "1111111357", "1111113555", "1111114446",
            "1111122238", "1111122456", "1111133337", "1111222347",
            "1111234445", "1111333355", "1112223455", "1112233346",
            "1122222446", "1123333444", "1133333335", "1222222256",
            "1222234444", "1222333345", "2222222237", "2222223445",
            "3333333333",
        },
        {
            "1111111248", "1111112366", "1111112447", "1111122257",
            "1111124455", "1111133446", "1111222555", "1111223356",
            "1112222228", "1112223337", "1112244444", "1112333445",
            "1122222247", "1122224445", "1122233355", "1122333336",
            "1222222455", "1222223346", "1233333344", "2222333444",
            "2223333335",
        },
        {
            "1111112338",
            "1111113456",
            "1111123347",
            "1111222266",
            "1111233455",
            "1111333346",
            "1112223446",
            "1122222356",
            "1122334444",
            "1123333345",
            "1222222337",
            "1222233445",
            "2222223355",
            "2222233336",
            "2333333334",
        },
        {
            "1111111129", "1111111167", "1111111556", "1111112357",
            "1111123555", "1111124446", "1111133356", "1111222238",
            "1111222456", "1111233337", "1111344444", "1112222347",
            "1112234445", "1112333355", "1113333336", "1122223455",
            "1122233346", "1222222446", "1223333444", "1233333335",
            "2222222256", "2222234444", "2222333345",
        },
        {
            "1111112248", "1111122366", "1111122447", "1111144445",
            "1111222257", "1111224455", "1111233446", "1112222555",
            "1112223356", "1113334444", "1122222228", "1122223337",
            "1122244444", "1122333445", "1222222247", "1222224445",
            "1222233355", "1222333336", "2222222455", "2222223346",
            "2233333344",
        },
        {
            "1111111466",
            "1111122338",
            "1111123456",
            "1111223347",
            "1111334445",
            "1112222266",
            "1112233455",
            "1112333346",
            "1122223446",
            "1133333444",
            "1222222356",
            "1222334444",
            "1223333345",
            "2222222337",
            "2222233445",
        },
        {
            "1111111229", "1111111267", "1111111348", "1111112556",
            "1111113366", "1111113447", "1111122357", "1111134455",
            "1111223555", "1111224446", "1111233356", "1112222238",
            "1112222456", "1112233337", "1112344444", "1113333445",
            "1122222347", "1122234445", "1122333355", "1123333336",
            "1222223455", "1222233346", "1333333344", "2222222446",
            "2223333444", "2233333335",
        },
        {
            "1111111158", "1111111457", "1111113338", "1111114555",
            "1111122248", "1111133347", "1111222366", "1111222447",
            "1111244445", "1111333455", "1112222257", "1112224455",
            "1112233446", "1122222555", "1122223356", "1123334444",
            "1133333345", "1222222228", "1222223337", "1222244444",
            "1222333445", "2222222247", "2222224445", "2222233355",
            "2222333336", "3333333334",
        },
        {
            "1111111139", "1111112466", "1111113357", "1111133555",
            "1111134446", "1111222338", "1111223456", "1111333337",
            "1112223347", "1112334445", "1113333355", "1122222266",
            "1122233455", "1122333346", "1222223446", "1233333444",
            "1333333335", "2222222356", "2222334444", "2223333345",
        },
        {
            "1111112229", "1111112267", "1111112348", "1111114456",
            "1111122556", "1111123366", "1111123447", "1111222357",
            "1111234455", "1111333446", "1112223555", "1112224446",
            "1112233356", "1122222238", "1122222456", "1122233337",
            "1122344444", "1123333445", "1222222347", "1222234445",
            "1222333355", "1223333336", "2222223455", "2222233346",
            "2333333344",
        },
        {
            "1111111258", "1111112457", "1111123338", "1111124555",
            "1111133456", "1111222248", "1111233347", "1111444444",
            "1112222366", "1112222447", "1112244445", "1112333455",
            "1113333346", "1122222257", "1122224455", "1122233446",
            "1222222555", "1222223356", "1223334444", "1233333345",
            "2222222228", "2222223337", "2222244444", "2222333445",
        },

    };

    int k;
    std::cin >> k;
    if (answer[k].empty())
        std::cout << -1 << "\n";
    else
        for (auto& a : answer[k])
            do
            {
                for (char c : a)
                    std::cout << c << " ";
                std::cout << "\n";
            } while (std::next_permutation(begin(a), end(a)));
}

(Trần Hoàn) #7

Đề bài quy đổi thành
“Phân tích k thành tổng của 10 số chính phương từ 1 đến 100”

Chỉ có 10 số thành phần là 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

Với mỗi bộ kết quả thì tìm tất cả các hoán vị của nó.

2 cái này chắc trên mạng có sẵn code, có khi đọc lại hiểu :smile:


(HK boy) #8

Đề không nói là các số chính phương khác nhau mà anh.


(Sherly1001) #10

:sweat_smile:


(Đạt Phạm) #11

:rofl: Khá Ok nhưng nó không phải giải pháp mình muốn tìm


(Đạt Phạm) #12

Để mình thử và báo cáo kết quả nhé :grinning:


(Hung) #13

:pensive:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

void permutation(std::vector<int> x) {
    static std::unordered_map<int, int> square_roots {
        {1, 1}, {4, 2}, {9, 3}, {16, 4}, {25, 5},
        {36, 6}, {49, 7}, {64, 8}, {81, 9} };
    
    do {
        for (auto &n : x) std::cout << square_roots[n] << ' ';
        std::cout << '\n';
    } while (std::next_permutation(x.begin(), x.end()));
}

bool backtrack(std::vector<int> &x, const std::vector<int> &squares, const int &k, int sum, int start, int step) {
    bool has_solution = false;
    
    for (auto i = start; i < squares.size(); i++) {
        x[step] = squares[i];
        sum += squares[i];
        
        if (sum > k) break;
        
        if (step == x.size() - 1) {
            if (sum == k) {
                permutation(x);
                has_solution = true;
            }
            
            if (i < squares.size() - 1) {
                sum -= squares[i];
                continue;
            }
        } else {
            has_solution = backtrack(x, squares, k, sum, i, step + 1) || has_solution;
            sum -= squares[i];
        }
    }
    
    return has_solution;
}

void solve_equation(int k) {
    std::vector<int> x(10);
    std::vector<int> squares { 1, 4, 9, 16, 25, 36, 49, 64, 81 };
    if (!backtrack(x, squares, k, 0, 0, 0)) std::cout << -1;
}

int main() {
    int k; std::cin >> k;
    solve_equation(k);
}

:face_with_monocle: :face_with_monocle: :face_with_monocle:


(‏) #14

ngắn quá ko biết đúng ko :V :V :V

#include <algorithm>
#include <iostream>
#include <numeric>
struct SortedNumber {
    int a[10];
    bool next() { return i(9); }
    bool i(int d) {
        return d < 0 ? 0 : a[d] < 9 ? ++a[d] : i(d - 1) ? a[d] = a[d - 1] : 0;
    }
};
int main() {
    int k;
    std::cin >> k;
    int cnt = 0;
    for (SortedNumber p{1, 1, 1, 1, 1, 1, 1, 1, 1, 0}; p.next();)
        if (k == std::transform_reduce(p.a, p.a + 10, 0,
                                       [](int a, int b) { return a + b; },
                                       [](int n) { return n * n; })) {
            auto q = p;
            do {
                for (int c : q.a) std::cout << c << " ";
                std::cout << "\n";
                cnt++;
            } while (std::next_permutation(q.a, q.a + 10));
        }
    if (!cnt) std::cout << "-1\n";
}

(HK boy) #15

Code dp (làm màu đếm số nghiệm :rainbow:) nhưng có hàm trace (dùng backtrack :pensive:)

Mình đang tìm cách tối ưu hàm show_all_permutations vì không phải lúc nào 1 dãy nghiệm cũng sinh ra 10! hoán vị, hoặc là đề bài thực chất không có nhiều bộ nghiệm phân biệt đến thế (sợ time limit :pensive:).


(rogp10) #16

Cái này có phải quay lui đâu :smiley:


(HK boy) #17

Chơi xấu :penguin:

int cnt[10];
// cnt[i]: đếm số i trong dãy nghiệm
for (cnt[1] = 0; cnt[1] <= 10; cnt[1]++)
for (cnt[2] = 0; cnt[2] <= 10; cnt[2]++)
for (cnt[3] = 0; cnt[3] <= 10; cnt[3]++)
	for (cnt[4] = 0; cnt[4] <= 6; cnt[4]++)
		for (cnt[5] = 0; cnt[5] <= 4; cnt[5]++)
			for (cnt[6] = 0; cnt[6] <= 2; cnt[6]++)
				for (cnt[7] = 0; cnt[7] <= 1; cnt[7]++)
				for (cnt[8] = 0; cnt[8] <= 1; cnt[8]++)
				for (cnt[9] = 0; cnt[9] <= 1; cnt[9]++)
					if (sum(cnt[i] * i for i in [1..9]) == n) {
						backtrack_dựng_dãy_nghiệm_ahihi(cnt);
					}

Độ phức tạp O(11^3 * 7 * 5 * 3 * 2^3 + 10!) ≈ 4.7M, time limit là tại đề :penguin:


Cải tiến thêm 1 chút:

Trong các bộ nghiệm, không thể tồn tại khả năng 7^2 + 8^2, 8^2 + 9^2, 7^2 + 9^2 hay 7^2 + 8^2 + 9^2 (vì tổng của chúng đều vượt quá 100), do vậy chỉ có 4 khả năng xảy ra:

  • Dãy nghiệm không có 7, 8, 9.
  • Dãy nghiệm chỉ có 7.
  • Dãy nghiệm chỉ có 8.
  • Dãy nghiệm chỉ có 9.

Tạo 1 mảng flag789[4] = {0, 1, 2, 4} gồm các số có 3 bit, mỗi bit tượng trưng cho sự xuất hiện của các chữ số 7, 8, 9 (bit i <=> số i+7 xuất hiện). Hay đơn giản hơn, vẫn biểu diễn sự xuất hiện của 7, 8, 9 qua các số từ 0 -> 3 nhưng if else các khả năng :penguin:

Độ phức tạp giảm còn O(11^3 * 7 * 5 * 3 * 4 + 10!) ≈ 4.1M :v


(Đạt Phạm) #18
#include <bits/stdc++.h>
using namespace std;
ifstream fi ("GPT.INP");
ofstream fo ("GPT.OUT");

int sum = 0;
int dem = 0;

void InKQ (int x[], int k)
{
    if(sum == k)
    {
        dem++;
        for(int i=0; i<10; i++)
        {
            fo << x[i] << " ";
        }
        fo << endl;
    }
}

void Tim (int i, int x[], int k)
{
        for(int val=1; val<=9 ; val++)
        {
            x[i] = val;
            sum += val * val;
            if(i==9)
                InKQ(x,k);
            else if(sum < 100)
                Tim(i+1,x,k);
            sum -= val * val;
        }
}

int main()
{
    int k;
    fi >> k;
    if(k<10)
        fo << "-1";
    int x[10];
    Tim(0,x,k);
    if(dem == 0)
        fo << "-1";

    return 0;
}

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?