Zen Course Guide

Ôn tập cụ thể

Câu 1

Trong một lớp học có n sinh viên (giả sử được đánh số từ 1 tới n). Mỗi sinh viên đều được cấp một tài khoản nên có thể sử dụng tài khoản này để đăng nhập hệ thống email của Google để gửi email cho nhau.

Giả sử không có ai tự gửi email cho chính mình và người A có thể gửi cho người B và nhiều email khác

Hãy tìm người đã nhận nhiều email nhất.

💡 GIẢI THÍCH

Cho ví dụ sau:

3
0 1 0
1 0 1 
1 2 0

Đầu vào: Có nghĩa là có 3 sinh viên.

  • 0 1 0: SV1 gửi cho SV2 1 email

  • 1 0 1: SV2 gửi cho SV1, SV3 1 email

  • 1 2 0: SV3 gửi 1 email cho SV1 và gửi 2 email cho SV2

Đầu ra:

In ra màn hình người đã nhận nhiều email nhất dạng sau: x has received y email(s).

InputResult
3
0 1 0
1 0 1
1 2 0		2 has received 3 email(s).
7
0 0 0 0 0 1 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0		3 has received 2 email(s)
4
0 2 0 0
0 0 1 1
1 1 0 0
1 0 0 0		2 has received 3 email(s)

Phân tích

Đây là 1 đơn đồ thị có hướng và không có khuyên

🚨 CHÚ Ý

Các bạn có thể làm dễ dàng bằng cách đặt biến mảng, nhưng lập trình là chúng ta phải hiểu luôn cả vấn đề sâu của nó nhé

💡 MẸO

Công việc của ta ngay lúc này chính là chuyển ma trận bằng hàm như sau:

int n;
scanf("%d",&n);
for(int i = 1; i <= n; i++){
    for (int j = 1; j <= n; j++){
        int x; 
        scanf("%d",&x);
        if(x != 0)
            add_edgeDirection(&G,i,j,x);
    }
}
Ma trậnĐồ thị
0 1 0
1 0 1
1 2 0		1 2 1
2 1 1
2 3 1
3 1 1
3 2 2

==> Nhìn lên hình và ta cũng có thể đón nhanh được, số 2 nhận 3 email và là nút nhận nhiều nhất.

Tham khảo hàm sau:

int received(Graph G,int x){
    int sum = 0;
    for(int i = 1; i <= G.n; i++){
        if(G.A[i][x] > 0){
            sum += G.A[i][x];
        }
    }
    return sum;
}

Lời giảiopen in new window

Câu 2

Công ty ABC có một dự án gồm n công việc (giả sử được đánh số từ 1 tới n). Một công việc thứ j có thể phụ thuộc vào công việc khác, công việc thứ i. Khi đó, công việc thứ i hoàn thành thì mới thực hiện được công việc thứ j.

Hãy viết chương trình in ra màn hình số lượng công việc phụ thuộc của một công việc x nào đó.

💡 GIẢI THÍCH

Đầu vào:

  1. Dòng đầu tiên chứa 2 số, tương ứng với số lượng công việc và số lượng mối quan hệ giữa các công việc

  2. Các dòng tiếp theo, mỗi dùng chứa u, v nói rằng: công việc v phụ thuộc công việc u

  3. Dòng cuối sẽ chứa công việc x cần tìm số công việc phụ thuộc

InputResult
3 2
1 2
2 3
2		2:1
3 2
1 2
2 3
1		1:0
5 7
1 4
1 2
1 3
1 5
2 3
3 5
4 5
2		2:1
5 7
1 4
1 2
1 3
1 5
2 3
3 5
4 5
5		5:3

Phân tích

💡 MẸO

Nhìn sơ qua không khác gì bài 1, chúng ta hoàn toàn có thể sử dụng lại:

Ví dụ mô hình 3 và 4:

ở nút số 2 có 1 phụ thuộc ==> 2:1

ở nút số 5 có 3 phụ thuộc ==> 5:3

Lời giảiopen in new window

Câu 3

Trang trại vừa nhập về n con gà mới và đang chuẩn bị phân bổ vào 2 chuồng gà trống. Tuy nhiên, một số con gà lại không thích ở chung với nhau. Nếu thả chúng vào chung một chuồng thì chúng sẽ mổ nhau.

Hãy viết chương trình xem có thể phân chia các con gà vào 2 chuồng gà không, và mỗi chuồng gà có bao nhiêu con.

💡 GIẢI THÍCH

Đầu vào:

  1. Dòng đầu tiên chứa 2 số tương ứng với số con gà và cặp gà không thích nhau

  2. Các dòng tiếp theo, mỗi dòng chứa gà a và b sẽ cắn nhau theo chung một chuồng

Đầu ra:

  1. x là số con gà trong chuồng A

  2. y là số con gà trong chuồng B

InputResult
5 5
1 3
2 3
2 4
3 5
4 5		3 2
5 4
1 4
5 2
3 2
1 2		3 2
3 3
1 2
2 3
3 1		-1 -1

⚠️ LƯU Ý

Nếu không thể phân chia thì in ra -1 -1

Phân tích

Đầu tiên chúng ta cần xác định bằng cách lấy một ví dụ không quá dễ cũng không quá khó để vẽ ra một mô hình:

Mình sẽ lấy ví dụ 1:

==> Nhìn sơ ta cũng biến đáp án là:

Chuồng AChuồng B
1
2
5		3
4

💡 MẸO

Vậy thì mình thử sử dụng BFS để duyệt tuần tự: 1 3 2 5 4

  • B1: Tạo ra 2 danh sách A và B

  • B2: bỏ số 1 vào danh sách A

  • B3: Duyệt từ số tiếp theo tới cuối

  • B4: Ví dụ là 3, sẽ kiểm tra các đỉnh kề của 3 có nằm trong danh sách A không ?

    1. Nếu vừa có trong A và B thì in ra -1 -1 và kết thúc

    2. Nếu có trong danh sách A thì hãy thêm vào danh sách B

    3. nếu không có trong danh sách A thì hãy thêm vào danh sách A

  • B5: Số phần tử trong 2 danh sách A và B là kết quả

Lời giảiopen in new window

Câu 4

Quốc gia Peaceful và Savage đang chiến tranh. Quân đội của Peaceful tại thành phố 1 cần phải vận chuyển vũ khí qua thành phố n cần được bảo vệ. Các tuyến đường đi qua thành phố phải đi qua những tuyến đường trung gian, hơn nữa mỗi tuyến đường đều có trọng tải tối đa khác nhau.

Hãy viết chương trình kiểm tra sau đó vận chuyển vũ khí từ thành phố 1 sang thành phố n có phù hợp hay không

💡 GIẢI THÍCH

Đầu vào:

  • Dòng dòng đầu tiên chứa n thành phố và m tuyến đường

  • m dòng tiếp theo là danh sách các tuyến đường gồm : u, v, x, y, cho biết tuyến đường từ u đến v, trọng tải cho phép là x và trọng tải thực tế là y

Đầu ra:

  • Nếu trọng lượng thực tế vận chuyển đường hợp lý và không bị mất hàng thì in good plan

  • Nếu trọng lượng thực tế vận chuyển đường không hợp lý hoặc bị mất hàng thì in bad plan

VÍ DỤ:

InputOutput
7 10
1 2 9 3
1 3 4 4
1 4 8 2
2 3 4 1
2 6 3 3
3 7 7 4
4 5 5 2
5 3 3 0
5 7 2 2
6 7 6 3		bad plan
7 10
1 2 9 5
1 3 4 4
1 4 8 2
2 3 4 0
2 6 3 3
3 7 7 4
4 5 5 2
5 3 3 0
5 7 2 2
6 7 6 3		bad plan
7 10
1 2 9 3
1 3 4 4
1 4 8 2
2 3 0 4
2 6 3 3
3 7 7 4
4 5 5 2
5 3 3 0
5 7 2 2
6 7 6 3		bad plan
7 10
1 2 9 3
1 3 4 4
1 4 8 2
2 3 4 0
2 6 3 3
3 7 7 4
4 5 5 2
5 3 3 0
5 7 2 2
6 7 6 3		good plan

Phân tích

Chúng ta sẽ lấy ví dụ đúng và sai (cụ thể là ví dụ là 1 và 4)

Mô hình 1Mô hình 4

⚠️ LƯU Ý

Hãy nhìn mô hình 1 ở nút số 2 : vào 3 nhưng lại ra 3+1 = 4 ==> Sai (check các trường hợp còn lại)

Ở mô hình 4 tổng vào và tổng ra đều là 2+4+3 và các nút còn lại cũng luồng ra và luồng vào như sau

💡 MẸO

  • B1: Nhập cung nhưng kiểm tra trọng tải

    Nếu sai thì in ra bad plan và return 0

  • B2: Kiểm tra luồng vào của nút n và luồng ra của nút 1

    Nếu không bằng nhau thì in ra bad plan và return 0

  • B3: Kiểm tra luồng vào và ra của các nút còn lại

    Nếu có nút nào luồng vào và ra không bằng nhau thì in ra bad plan và return 0

  • B4: In ra good plan khi các trường hợp trên sai

Lời giảiopen in new window

Câu 5

John là lập trình viên sống tại San Francisco. Hiện tại trong nhóm phát triển phần mềm với 2 công ty A và B. Vì lý do đặc biệt nên hàng tháng John phải đi qua lại công ty A và B.

Biết rằng tại nơi John sống có thể đi đến công ty A và B thông qua hệ thống các chuyến bay như sau:

STTChuyến bayGiá vé
1San Francisco <=> Detroit$329
2San Francisco <=> New York$359
3San Francisco <=> Denver$279
4San Francisco <=> Los Angeles$69
5Denver <=> Los Angeles$209
6Denver <=> Detroit$129
7Denver <=> New York$279
8Los Angeles <=> New York$379
9Los Angeles <=> Detroit$349
10Detroit <=> New York$89

Ví dụ vé số 1 là từ San Francisco tới Detroit và Detroit tới Francisco đề có giá vé là $329

Để đơn giản ta sẽ đánh các thành phố theo số sau:

San FranciscoDetroitNew YorkLos AngelesDenver
12345

Thông thường thì chuyến bay của John sẽ đến gặp công ty A và B diễn ra trong 3 ngày:

  • Ngày 1: Đi từ nhà (San Francisco) tới công ty A (Denver)

  • Ngày 2: Đi từ công ty A (Denver) tới công ty B (New York)

  • Ngày 3: Đi từ công ty B (New York) về nhà (San Francisco)

Viết chương trình giúp John chọn chuyến bay sau cho chi phí phải trả là thấp nhất

💡 GIẢI THÍCH

Đầu vào:

  • Dòng đầu tiên chứa số thành phố và số chuyến bay giữa 2 thành phố

  • Các Dòng tiếp theo chứa 3 số u,v,w: chuyến bay từ u tới v có giá w

  • Dòng cuối chứa x và y là hai thành phố và John muốn tìm đường đi công tác với số tiền thấp nhất

InputResult
5 10
1 2 329
1 3 359
1 5 279
1 4 69
5 4 209
5 2 129
5 3 279
4 3 379
4 2 349
2 3 89
1 5		278
1 4 5
5 10
1 2 329
1 3 359
1 5 279
1 4 69
5 4 209
5 2 129
5 3 279
4 3 379
4 2 349
2 3 89
5 3		218
5 2 3

Phân tích

Từ ví dụ trên ta sẽ có mô hình như sau:

Từ đây chúng ta có thể nhìn đơn giản rằng :

  • Con đường đi từ 1 tới 5 là : 1-4-5 và có giá trị là 278

  • Con đường đi từ 5 tới 3 là : 5-2-3 và có giá trị là 218

💡 MẸO

Sử dụng giải thuật Dijstra để tìm ra đường đi ngắn nhất

Lời giảiopen in new window

Câu 6

Một người nông dân trồng thanh long cần lắp đèn chiếu sáng vào ban đêm đã cắm n cọc lắp đèn chiếu sáng (được đánh số từ 1 tới n) và bác đã kéo dây điện từ nhà của bác tới cọc số 1.

Trên mỗi cọc này, từ một bóng đèn sẽ nối dây điện cho tất cả bóng đèn ở những cọc còn lại. Nếu một cọc được cấp điện thì tất cả các cọc khác nối với nó cũng được cấp điện, các điểm nối phải nằm trên cọc nào đó (không nằm ở lưng chừng giữa 2 cọc).

Bác nông dân đã thấy có m cặp cọc có thể được nối với nhau và đã ghi lại chiều dài dây điện cần thiết để nối (mỗi dây kết nối có giá tiền khác nhau).

Hãy viết chương trình giúp nông dân tính số tiền tối thiểu cần để mua dậy điện thắp sáng mảnh vườn thanh long.

💡 GIẢI THÍCH

Đầu vào:

  • Dòng đầu tiên chứa số cọc lắp đèn và số cặp cọc có thể nối với nhau bằng dây điện

  • Các dòng tiếp theo mỗi dòng sẽ chứa 4 số u, v, x, y nói rằng : cọc u với cọc v, cần mua x mét dây mỗi mét có giá y nghìn VND/m

Đầu ra:

  • In ra màn hình số tiền thấp nhất để mua đèn thắp sáng cả vườn thanh long

⚠️ Nếu bài toán không có lời giải hãy in ra: "KHONG CO LOI GIAI"

InputResult
7 10
1 3 5 2
1 2 2 3
1 4 7 2
3 2 2 2
3 5 8 1
2 4 1 3
2 6 9 4
4 7 10 2
5 6 6 5
6 7 15 2		71
7 7
1 3 5 4
1 2 2 2
1 4 7 2
3 2 2 5
2 4 1 4
2 6 9 5
5 7 8 6		KHONG CO LOI GIAI
5 8
1 2 7 2
1 3 10 3
2 3 8 2
2 4 2 3
2 5 9 2
3 4 6 3
3 5 15 2
4 5 7 3		54

Phân tích

Đầu tiên về phần nhập giá trị: 2 thông số x và y thực chất ta có thể gộp lại bằng phép nhân như sau:

Ban đầuGộp lạiMô hình
1 3 5 2
1 2 2 3
1 4 7 2
3 2 2 2
3 5 8 1
2 4 1 3
2 6 9 4
4 7 10 2
5 6 6 5
6 7 15 2		1 3 10
1 2 6
1 4 14
3 2 4
3 5 8
2 4 3
2 6 36
4 7 20
5 6 30
6 7 30
1 3 5 4
1 2 2 2
1 4 7 2
3 2 2 5
2 4 1 4
2 6 9 5
5 7 8 6		1 3 20
1 2 4
1 4 14
3 2 10
2 4 4
2 6 45
5 7 48
1 2 7 2
1 3 10 3
2 3 8 2
2 4 2 3
2 5 9 2
3 4 6 3
3 5 15 2
4 5 7 3
1 2 14
1 3 13
2 3 16
2 4 6
2 5 18
3 4 18
3 5 30
4 5 21

🚨 CHÚ Ý

Bạn hãy chú ý mô hình số 2, nhánh 5-7 nó nằm ngoài chứng tỏ nó không liên thông, nên chúng ta không có lời giải

CÁC BƯỚC LÀM

  • Bước 1: Nhập vào đồ thị có trọng số

    Sử dụng đồ thị danh sách cung

    int n,m;
scanf("%d%d",&n,&m);
initGraph(&G, n);
for(int i = 0; i < m; i++){
    int x,y,a,b;
    scanf("%d%d%d%d",&x,&y,&a,&b);
    int z = a * b;
    addEdge(&G,x,y,z);
}

  • Bước 2: Sử dụng hàm tính cây khung nhỏ nhất kruskal để tìm ra giá trị cây khung nhỏ nhất có trọng số

  • Bước 3: Kiểm tra đồ thị có liên thông không ? tham khảo

    1. Nếu có: in ra kết quả

    2. Nếu không: in KHONG CO LOI GIAI

Lời giảiopen in new window

Cập nhật lúc :
Tác giả: Zenfection, Zenfection