Hỏi thuật toán 1 bài trong đề Tuyển sinh chuyên Tin (Pascal)

[pm2004 (Ẩn Danh)]

Bài 3 (Kho báu) (PTNK 2013-2014)
Bạn may mắn được một vị thần đưa vào kho báu bí ẩn gồm 9 căn phòng được xây dựng dưới dạng mê cung kích thước 3 x 3.
Mỗi căn phòng có một số hiệu là số nguyên dương trong phạm vi 1 đến 9.
Hai căn phòng khác nhau có số hiệu khác nhau. Ở một căn phòng bất kỳ, bạn có thể đi đến các căn phòng có chung cạnh.
Bạn tự chọn vị trí xuất phát từ một căn phòng bất kỳ trong kho báu và đi qua tất cả các căn phòng trong kho báu, mỗi căn phòng đi qua duy nhất một lần.
Vị thần sẽ viết liên tiếp số hiệu của các căn phòng khi bạn đi qua va tặng bạn số đồng tiền vàng đúng bằng giá trị của số có 9 chữ số tương ứng với đường đi của bạn.
Yêu cầu: Hãy xác định số lượng đồng tiền vàng nhiều nhất mà bạn có thể nhận được.

Dữ liệu vào: từ tập tin văn bản TREASURE.INP
• Dòng đầu tiên của dữ liệu vào chứa 1 số nguyên dương N (1⩽ N ⩽50)
• Tiếp theo là 3 N dòng lần lượt mô tả N bộ test. Bộ test thứ i trong số N bộ test được mô tả trên 3 dòng liên tiếp, mỗi dòng gồm 3 số tự nhiên.

Dữ liệu ra: ghi ra tập tin văn bản TREASURE.OUT gồm N dòng, dòng thứ i chứa một số nguyên dương gồm 9 chữ số là kết quả của bộ test thứ i (với 1 ⩽ i ⩽ N).

[SITUVN.gcd]

Vị trí xuất phát bao giờ cũng chọn số lớn nhất có thể, sau đó xét các số lớn tiếp theo quanh nó. Lưu ý là không đi vào ngõ cụt (bị bao quanh bởi các số đã đi).

Trùng với: Truy tìm kho báu loài rồng

[tntxtnt]

cái này chỉ là ma trận 3x3 thì cứ mò hết đường rồi hard code vào là được

giả sử ban đầu là
. . .
. . .
. . .
ta tìm được số lớn nhất ở giữa:
. . .
. 9 .
. . .
tiếp theo 1 trong 4 đường, đường nào lớn nhất thì đi
hướng nào cũng như nhau, xoay 90/180/270 độ là ra y hệt
chọn đi lên: (số 8 là ví dụ)
. 8 .
. 9 .
. . .
chọn tiếp đường lớn nhất trong 2 đường trái phải
nếu là trái, chỉ có 1 cách duy nhất duyệt hết 9 số là
7 8 1
6 9 2
5 4 3
nếu là phải, chỉ có 1 cách duy nhất duyệt hết 9 số là
1 8 7
2 9 6
3 4 5

làm tương tự với 4 góc, 4 cạnh thì hình như ko có đường đi quét hết 9 số.

ví dụ 1:

2 4 3
8 9 5
1 7 6
số lớn nhất ở giữa: tìm số lớn nhất trong 4 cạnh:
là cạnh trái (số 8), vậy quay A theo chiều kim đồng hồ 90 độ:
1 8 2
7 9 4
6 5 3
tìm tiếp số lớn nhất bên trái và bên phải số 8:
là bên phải (số 2)
vậy kết quả là 982435671

ví dụ 2:

3 5 1
4 7 6
9 8 2
số lớn nhất là 1 trong 4 góc: góc trái bên dưới:
xoay 90 độ theo kim đồng hồ để góc lớn nhất là góc trái bên trên
9 4 3
8 7 5
2 6 1
tìm số lớn nhất bên phải và bên dưới số 9:
là bên dưới (số 8)
chuyển vị (transpose) ma trận A để số lớn nhất là bên phải:
9 8 2
4 7 6
3 5 1
tìm số lớn nhất bên phải và bên dưới số 8:
là bên dưới (số 7).
vậy kết quả là 987435162

chỉ có 5 dạng thế này thì phải:

1 8 7
2 9 6
3 4 5

9 8 1
6 7 2
5 4 3

9 8 7
2 3 6
1 4 5

9 8 7
2 1 6
3 4 5

9 8 7
4 5 6
3 2 1

[MeigyokuThmn (明玉)]

Cái này không liên quan một tí nhưng, nếu bạn học cấp 3 mà nghe người ta kêu gọi thi chuyên tin học, thì nên nhớ đó không phải là tin học ngồi gõ lọc cọc, mà đó là toán-tin, cụ thể thì thiên nhiều về toán rời rạc (một môn mà phải đại học mới dạy/giảng). Ngày xưa mình cũng vào, và vỡ mộng.
Mình nghĩ những thớt kiểu này nên cho thêm tag math và algorithm, thậm chí đừng nên cho thêm những tag như pascal, delphi, C++, v.v.

[kisuluoibieng (Tên Gì Cũng Được)]

bài này trước đây đã từng hỏi rồi thì phải, cũng không biết phải bạn này hỏi hay không, nhưng trên những diễn đàn thế này là thảo luận, góp ý, xây dựng
những bài post thế này chẳng muốn trả lời chút nào, kiểu này thế nào ngày mình post 100 bài còn được, bạn đã suy nghĩ bài này bao lâu, đã nghĩ được gì thì post lên cho người ta đóng góp
miễn cưỡng thì bài này post ý kiến vài câu gợi ý có thể làm được, dụng tới cây, đồ thị hay gì đó khác nâng cao thì lấy gì mà hiểu, chả lẽ kêu người ta post code lên luôn cho copy về?

[pm2004 (Ẩn Danh)]

Dạ đây là lần đầu tiên em hỏi nên chắc cái bài đó không phải của em. Em cũng đâu cần code đâu anh, chỉ cần hướng dẫn cái hướng cái, vì em chưa có làm nhiều về lập trình cho lắm.

[kisuluoibieng (Tên Gì Cũng Được)]

cái chuyện code chỉ là bước sau cùng, cái cần phát triển chính là cái tư duy tính toán, cách sắp xếp các bước
muốn làm được bài thì phải giải tay bài đó trước, giải với 1 trường hợp cụ thể, giải với trường hợp tổng quát, rồi tình ra cái gọi là phương pháp giải
ít nhất mình cũng phải làm bằng tay theo một cách tổng quát nhất chứ không phải mắt nhìn vô mà ra kết quả
nếu như không có chút gì đưa lên đây gọi là chứng minh [bạn đã suy nghĩ, thử gì đó với bài này, dù là rất sơ khai cũng được] thì chẳng có gì để gợi ý cả

đọc bài này thì cách chuối nhất mà 5s sau khi đọc đề có thể nghĩ ra được, là list hết tất cả trường hợp => 9! (có cách không có thực), cải tiến chút nữa thì mỗi một ô chỉ có thể đi tới 1 2 3 hoặc 4 ô khác, suy ra cùng lắm là 4^9.

tất nhiên cách trên chỉ để đối khó khi đang ngồi thi mà thôi. còn cách tốt hơn thì theo như ước tính thì chỉ đếm hết đầu ngón tay mà thôi

[hungaya (Hung)]

Bài này chỉ sử dụng backtracking với max heap biễu diễn cho tập trạng thái tiếp theo mà thôi (giống cách của @SITUVN.gcd), nhưng do cái tag là #pascal nên mình lười code. :v

Bài này có 1 điểm thú vị, cho bất kì ma trận 3x3 nào, nếu sử dụng giải thuật backtracking như trên, thì luôn luôn tìm được dãy gồm 9 số. Nói một cách khác, không thể có một ma trận 3x3 mà không tìm được dãy 9 số thoả mãn đề bài.

Tổng quát hoá, có thể xem là Conjecture:
Cho ma trận NxN bất kì (N nguyên dương). Nếu sử dụng backtracking + max heap, có tồn tại hay không dãy gồm đủ N² phần tử.

Liệu có chứng minh (proof) cho trường hợp N = 3, hoặc N tổng quát không nhỉ?

[pm2004 (Ẩn Danh)]

em mới học lớp 9 nên chưa biết ma trận là cái gì hết.

[tntxtnt]

Có chứ, ma trận xoắn ốc là đủ n^2 đó, cần gì chứng minh =)

[tntxtnt]

chém gió vậy đc hem

#include <algorithm>
#include <array>
#include <iostream>

using Int9 = std::array<int, 9>;

template <int A, int B, int C, int D, int E, int F, int G, int H, int I>
Int9 copy9(const Int9& a)
{
    return {a[A], a[B], a[C], a[D], a[E], a[F], a[G], a[H], a[I]};
}

template <int A, int B, int C, int D, int E, int F, int G, int H, int I>
void swap_many(Int9& a)
{
    auto b = copy9<A, B, C, D, E, F, G, H, I>(a);
    std::copy(begin(b), end(b), begin(a));
}
void rot90(Int9& a)
{
    swap_many<6, 3, 0, 7, 4, 1, 8, 5, 2>(a);
}
void transpose(Int9& a)
{
    swap_many<0, 3, 6, 1, 4, 7, 2, 5, 8>(a);
}

template <int K>
int max_index(const Int9& a)
{
    return K;
}
template <int K, int M, int... Rest>
int max_index(const Int9& a)
{
    int N = max_index<M, Rest...>(a);
    return a[K] > a[N] ? K : N;
}

Int9 treasure(Int9& a)
{
    switch (max_index<0, 2, 4, 6, 8>(a))
    {
    case 2: rot90(a);
    case 8: rot90(a);
    case 6: rot90(a);
    case 0:
        if (a[3] > a[1]) transpose(a);
        if (a[4] > a[2]) return copy9<0, 1, 4, 3, 6, 7, 8, 5, 2>(a);
        if (a[4] > a[8]) return copy9<0, 1, 2, 5, 4, 3, 6, 7, 8>(a);
        return a[4] > a[6] ? copy9<0, 1, 2, 5, 8, 7, 4, 3, 6>(a)
                           : copy9<0, 1, 2, 5, 8, 7, 6, 3, 4>(a);
    case 4:
        switch (max_index<1, 3, 5, 7>(a))
        {
        case 5: rot90(a);
        case 7: rot90(a);
        case 3: rot90(a);
        }
        return a[2] > a[0] ? copy9<4, 1, 2, 5, 8, 7, 6, 3, 0>(a)
                           : copy9<4, 1, 0, 3, 6, 7, 8, 5, 2>(a);
    }
}

int main()
{
    int n;
    for (std::cin >> n; n--; std::cout << "\n")
    {
        Int9 a;
        for (int& x : a) std::cin >> x;
        for (int x : treasure(a)) std::cout << x;
    }
}

[pm2004 (Ẩn Danh)]

cám ơn anh tntxtnt nhưng em không cần code lắm với em mới biết chút xíu về c++ thôi.

[hungaya (Hung)]

Bài này có 1 điểm thú vị, cho bất kì ma trận 3x3 nào, nếu sử dụng giải thuật backtracking như trên, thì luôn luôn tìm được dãy gồm 9 số. Nói một cách khác, không thể có một ma trận 3x3 mà không tìm được dãy 9 số thoả mãn đề bài.

Phát biểu lộn rồi.
Giờ cho số 9 ở vị trí (0,1), (1,2), (2,1), (1,0) là không tìm ra được dãy 9 số, kể cả mọi trường hợp.

Ví dụ: số 9 ở (0,1)

. 9 .
. . .
. . .

Đi xuống dưới vị trí (1,1), đi qua trái kẹt ô (0,0), đi qua phải kẹt ô (0,2), đi xuống dưới thì ma trận chia thành 2 phần nên kẹt luôn.

. 9 .   . 9 .   . 9 .   . 9 .
. 8 .   7 8 .   . 8 7   . 8 .
. . .   . . .   . . .   . 7 .

Từ 9 đi sang trái (sang phải tương tự), rồi xuống dưới, được dãy 987.
Lúc này có 2 trường hợp, từ 7 xuống dưới và từ 7 sang phải.

8 9 .   8 9 .
7 . .   7 . .
. . .   . . .

Trường hợp 1: 7 đi xuống được thêm 65 (hình 1)

• Nếu từ 5 đi lên thì thêm được 43 (hình 2), kẹt 2 ô (0,2) và (2,2).
• Nếu từ 5 sang phải cũng thêm được 43 (hình 3), nhưng kẹt 2 ô (1,1) và (0,2).

    (1)                (2)               (3)
8 9 .   8 9 .  |  8 9 .   8 9 .  |  8 9 .   8 9 .
7 . .   7 . .  |  7 4 .   7 4 3  |  7 . .   7 . 3
6 . .   6 5 .  |  6 5 .   6 5 .  |  6 5 4   6 5 4

Trường hợp 2: 7 sang phải được thêm 6 (hình 4).

• Nếu từ 6 sang phải thì kẹt ô (0,2). (hình 5)
• Nếu từ 6 xuống dưới kẹt ô (2,0). (hình 6)

 (4)       (5)       (6)
8 9 .  |  8 9 .  |  8 9 .
7 6 .  |  7 6 5  |  7 6 .
. . .  |  . . .  |  . 5 .

---

Tự gạch mình cái vì cái tội không xem xét kĩ.

[tntxtnt]

số 9 nằm ở 4 cạnh thì đi tìm số 8 hay 7 6 5 v.v… ở 4 góc và ở giữa, đâu nhất thiết phải bắt đầu bằng số 9

tặng bạn số đồng tiền vàng đúng bằng giá trị của số có 9 chữ số tương ứng với đường đi của bạn.

ví dụ
3 9 4
6 1 8
5 7 2
thì đáp án sẽ là 572849361

---

cám ơn anh tntxtnt nhưng em không cần code lắm với em mới biết chút xíu về c++ thôi.

thì em chạy bằng tay giải thử đi. Ma trận 3x3 ngồi chạy tay cũng ra hết số trường hợp mà :V :V Giải tay được rồi thì áp dụng vào code thôi. Ma trận bé quá đi phang cái backtrack gì vô mất công :V

[rogp10]

Chu trình Hamilton có thể tìm được (NP-complete) nhưng big-O đều là cấp mũ.