Tuần 36

Thi tổng kết

Độ khó: ★★★★★ Khó
Thời lượng: Khoảng 150 phút
Học trước: Chữa đề và nhận dạng dạng bài
Chủ đề: thi tổng kết
Trạng thái

Họ và tên: ................................................

Thời gian làm bài 150 phút. Ngày làm bài: ........................

Thông tin	Nội dung
Thời gian làm bài	150 phút (tính cả thời gian kiểm tra lại bài)
Số bài và tổng điểm	5 bài, mỗi bài 20 điểm, tổng 100 điểm
Giới hạn mỗi test	Thời gian 1 giây, bộ nhớ 256 MB
Nhập, xuất dữ liệu	Đọc từ bàn phím (cin), in ra màn hình (cout)

Bài	Tên bài	Điểm tối đa
1	Đèn lồng đêm hội	20
2	Dải đèn màu	20
3	Ghép đống kẹo	20
4	Bữa tiệc của Gấu Po	20
5	Kho báu hang rồng	20
	Tổng điểm	100

Lưu ý khi làm bài

Đây là bài thi tổng kết cả khóa học nên đề trải rộng nhiều chủ đề. Em hãy đọc kỹ cả đề, đặc biệt là phần giới hạn, rồi làm bài dễ trước, bài khó sau. Em có thể làm các bài theo thứ tự tùy ý.

Chạy thử mọi ví dụ mẫu trước khi coi là xong một bài, và tự nghĩ thêm một vài test của riêng mình (n nhỏ nhất, các số bằng nhau, k lớn nhất...).

Ở những bài có nhiều nhóm chấm điểm, nếu chưa nghĩ ra cách làm nhanh, em vẫn nên làm cách đơn giản để lấy điểm của nhóm nhỏ.

Hãy tự chọn công cụ theo giới hạn dữ liệu: ước chung, hai con trỏ, cửa sổ trượt, priority_queue, quay lui, quy hoạch động. Chú ý kiểu dữ liệu: khi kết quả (hoặc một phép nhân, phép cộng ở giữa chừng) có thể vượt quá khoảng 2 tỷ thì dùng long long.

Dành khoảng 10 phút cuối để đọc lại code và kiểm tra các trường hợp đặc biệt. Gợi ý phân bổ thời gian: Bài 1 khoảng 15 phút, Bài 2 khoảng 25 phút, Bài 3 khoảng 30 phút, Bài 4 khoảng 35 phút, Bài 5 khoảng 35 phút.

Đề bài

Bài 1. Đèn lồng đêm hội

Đêm hội trăng rằm, Thỏ treo n chiếc đèn lồng thành một hàng. Cả n đèn cùng sáng lên vào giây số 0. Sau đó, đèn thứ i cứ đúng a[i] giây lại sáng một lần (sáng ở các giây a[i], 2·a[i], 3·a[i], ...). Hỏi sau ít nhất bao nhiêu giây (tính từ giây 0) thì cả n đèn lại cùng sáng một lần nữa?

Test	Input	Output
Đầu vào	Dòng 1: số nguyên n (1 ≤ n ≤ 20). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 10⁹). Dữ liệu đảm bảo đáp án không vượt quá 10¹⁸.
Đầu ra	Số giây ít nhất để cả n đèn lại cùng sáng.
Giới hạn và chấm điểm	Nhóm 1 (6 điểm): n ≤ 5 và a[i] ≤ 20. Nhóm 2 (6 điểm): đáp án không vượt quá 10⁹. Nhóm 3 (8 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây.
1	`3` `4 6 10`	60 Giải thích: đèn 1 sáng ở các giây 4, 8, 12, ...; đèn 2 sáng ở 6, 12, 18, ...; đèn 3 sáng ở 10, 20, 30, .... Giây nhỏ nhất cả ba cùng sáng là 60.
2	`1` `7`	7 Giải thích: chỉ có một đèn nên nó sáng lại ở giây 7.
3	`2` `1000000000 999999999`	999999999000000000 Giải thích: hai số này nguyên tố cùng nhau nên đáp án bằng tích của chúng, lớn hơn rất nhiều so với 2 tỷ.

Bài 2. Dải đèn màu

Hổ có một dải đèn gồm n bóng xếp thành hàng, mỗi bóng có một màu được ghi bằng một chữ cái thường (từ a đến z), dải đèn được mô tả bằng xâu s. Hổ muốn cắt lấy một đoạn gồm các bóng liên tiếp sao cho đoạn đó có không quá k màu khác nhau. Hỏi đoạn dài nhất Hổ cắt được có bao nhiêu bóng đèn?

Test	Input	Output
Đầu vào	Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 10⁵; 1 ≤ k ≤ 26). Dòng 2: xâu s gồm n chữ cái thường.
Đầu ra	Độ dài lớn nhất của một đoạn liên tiếp có không quá k màu khác nhau.
Giới hạn và chấm điểm	Nhóm 1 (8 điểm): n ≤ 2000. Nhóm 2 (12 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây.
1	`7 2` `abcbbbd`	5 Giải thích: đoạn "bcbbb" (vị trí 2 đến 6) chỉ có hai màu b và c. Đoạn dài 6 nào cũng có ít nhất ba màu.
2	`4 1` `aaaa`	4 Giải thích: cả dải chỉ có một màu a nên lấy hết 4 bóng.
3	`3 1` `abc`	1 Giải thích: mỗi đoạn dài hơn 1 bóng đều có từ hai màu trở lên.

Bài 3. Ghép đống kẹo

Gấu Po có n đống kẹo, đống thứ i có a[i] viên. Mỗi lần, Gấu Po chọn hai đống bất kỳ và dồn chúng thành một đống mới; việc dồn này tốn công bằng tổng số viên kẹo của hai đống vừa dồn. Gấu Po làm liên tục cho đến khi chỉ còn lại một đống. Hỏi tổng công nhỏ nhất Gấu Po phải bỏ ra là bao nhiêu?

Test	Input	Output
Đầu vào	Dòng 1: số nguyên n (1 ≤ n ≤ 10⁵). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 10⁹).
Đầu ra	Tổng công nhỏ nhất (bằng 0 nếu ngay từ đầu chỉ có một đống).
Giới hạn và chấm điểm	Nhóm 1 (8 điểm): n ≤ 1000 và a[i] ≤ 1000. Nhóm 2 (12 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây.
1	`4` `1 2 3 4`	19 Giải thích: dồn đống 1 và 2 (công 3) được các đống 3, 3, 4; dồn hai đống 3 (công 6) được các đống 6, 4; dồn nốt (công 10). Tổng công là 3 + 6 + 10 = 19.
2	`1` `5`	0 Giải thích: chỉ có một đống nên không cần dồn.
3	`3` `1000000000 1000000000 1000000000`	5000000000 Giải thích: dồn hai đống đầu tốn 2 tỷ, rồi dồn đống 2 tỷ với đống còn lại tốn 3 tỷ, tổng 5 tỷ (vượt quá int).

Bài 4. Bữa tiệc của Gấu Po

Gấu Po tổ chức bữa tiệc sinh nhật và có n người bạn, đánh số từ 1 đến n. Bàn tiệc chỉ đủ chỗ cho đúng k bạn. Tuy nhiên có m cặp bạn không ưa nhau, hai bạn trong một cặp như vậy không được ngồi cùng bàn. Hỏi Gấu Po có bao nhiêu cách chọn đúng k bạn đến dự tiệc? (Hai cách chọn khác nhau nếu có ít nhất một bạn có mặt ở cách này mà không có mặt ở cách kia.)

Test	Input	Output
Đầu vào	Dòng 1: ba số nguyên n, k, m (1 ≤ k ≤ n ≤ 20; 0 ≤ m ≤ n·(n − 1)/2). m dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v (1 ≤ u < v ≤ n) cho biết bạn u và bạn v không ưa nhau. Các cặp là khác nhau.
Đầu ra	Số cách chọn thỏa mãn.
Giới hạn và chấm điểm	Nhóm 1 (8 điểm): n ≤ 10. Nhóm 2 (12 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây.
1	`4 2 2` `1 2` `3 4`	4 Giải thích: các cách chọn được là {1, 3}, {1, 4}, {2, 3}, {2, 4}. Hai cách {1, 2} và {3, 4} bị loại.
2	`3 3 1` `1 2`	0 Giải thích: phải mời cả ba bạn nhưng bạn 1 và bạn 2 không ưa nhau.
3	`5 2 0`	10 Giải thích: không ai ghét ai nên mọi cách chọn 2 trong 5 bạn đều được, có 10 cách.

Bài 5. Kho báu hang rồng

Hổ khám phá hang rồng và tìm thấy n món báu vật. Món thứ i nặng w[i] ki-lô-gam và có giá trị v[i] đồng. Chiếc túi của Hổ chỉ mang được tối đa W ki-lô-gam, và mỗi món báu chỉ có một cái. Hỏi tổng giá trị lớn nhất mà Hổ mang ra khỏi hang là bao nhiêu?

Test	Input	Output
Đầu vào	Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 100; 1 ≤ W ≤ 10⁴). n dòng tiếp theo, dòng thứ i gồm hai số nguyên w[i], v[i] (1 ≤ w[i] ≤ 10⁴; 1 ≤ v[i] ≤ 10⁹).
Đầu ra	Tổng giá trị lớn nhất có thể mang đi.
Giới hạn và chấm điểm	Nhóm 1 (6 điểm): n ≤ 15. Nhóm 2 (6 điểm): n ≤ 100, W ≤ 1000 và v[i] ≤ 1000. Nhóm 3 (8 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây.
1	`3 5` `2 3` `3 4` `4 5`	7 Giải thích: chọn món 1 và món 2 (nặng 2 + 3 = 5, giá trị 3 + 4 = 7). Món 3 một mình chỉ được 5.
2	`2 1` `2 100` `3 200`	0 Giải thích: cả hai món đều nặng hơn sức chở 1 ki-lô-gam nên Hổ không mang được gì.
3	`3 10000` `3000 1000000000` `3000 1000000000` `3000 1000000000`	3000000000 Giải thích: cả ba món nặng tổng 9000 ≤ 10000 nên mang hết, giá trị 3 tỷ (vượt quá int).

Ghi chú cá nhân (lưu trên trình duyệt này)