Ôn tập GĐ3: Đề 1
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 120 phút
- Học trước
- Ôn tổng hợp GĐ3
- Chủ đề
- mini contestôn tập
- Trạng thái
Họ và tên: ................................................
Thời gian làm bài 120 phút. Ngày làm bài: ........................
| Thông tin | Nội dung |
|---|---|
| Thời gian làm bài | 120 phút (tính cả thời gian kiểm tra lại bài) |
| Số bài và tổng điểm | 4 bài, mỗi bài 25 đ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 | Điểm đạt được |
|---|---|---|---|
| 1 | Cặp số may mắn | 25 | |
| 2 | Dãy ngoặc hỏng | 25 | |
| 3 | Phiếu giảm giá | 25 | |
| 4 | Mã khóa tủ | 25 | |
| Tổng điểm | 100 |
Lưu ý khi làm bài
Đọ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, chuỗi rỗng hoặc đã sạch...).
Ở 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ỏ.
Chọn công cụ theo giới hạn: set, map, stack, queue, priority_queue, sinh kế tiếp, quay lui. Chú ý kiểu dữ liệu: khi kết quả có thể vượt quá khoảng 2 tỷ thì dùng long long. Nhớ kiểm tra empty() và end() trước khi lấy phần tử.
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 20 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
Bài 1. Cặp số may mắn
Gấu Po có n chiếc thẻ, thẻ thứ i ghi số a[i]. Gấu Po gọi hai thẻ ở hai vị trí i < j là một cặp may mắn nếu tổng hai số trên thẻ bằng đúng K. Hãy đếm số cặp may mắn.
| Đầu vào | Dòng 1: hai số nguyên n, K (2 ≤ n ≤ 105; 1 ≤ K ≤ 2.109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cặp may mắn (có thể lớn hơn 2.109). | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n ≤ 2000. Nhóm 2 (15 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây. | |
| Test | Input | Output |
| 1 | 5 6 1 5 3 3 5 | 3 Giải thích: các cặp vị trí (1, 2), (1, 5) và (3, 4) đều có tổng bằng 6. |
| 2 | 4 10 1 2 3 4 | 0 Giải thích: không có cặp nào có tổng bằng 10. |
| 3 | 4 4 2 2 2 2 | 6 Giải thích: mọi cặp trong bốn vị trí đều có tổng 4, có 6 cặp. |
Bài 2. Dãy ngoặc hỏng
Thỏ viết một dãy chỉ gồm sáu loại dấu ngoặc: ( ), [ ] và { }. Thỏ muốn kiểm tra dãy có đúng không, tức là mỗi dấu đóng ghép được với dấu mở cùng loại đứng gần nhất chưa được ghép, và không còn dấu mở nào thừa. Nếu dãy sai, hãy chỉ ra vị trí lỗi theo quy tắc: duyệt từ trái sang phải, vị trí lỗi là vị trí đầu tiên của một dấu đóng không ghép được (không có dấu mở chờ hoặc dấu mở chờ không cùng loại). Nếu không có vị trí nào như vậy nhưng cuối dãy vẫn còn dấu mở chưa đóng thì vị trí lỗi là n + 1.
| Đầu vào | Một dòng duy nhất là xâu s gồm các ký tự ( ) [ ] { }, dài n ký tự (1 ≤ n ≤ 105). Vị trí đánh số từ 1. | |
|---|---|---|
| Đầu ra | In OK nếu dãy đúng, ngược lại in vị trí lỗi. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): xâu chỉ gồm hai ký tự ( và ). Nhóm 2 (15 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây. | |
| Test | Input | Output |
| 1 | ([]{}) | OK Giải thích: mọi dấu ngoặc đều ghép được. |
| 2 | ([)] | 3 Giải thích: dấu ) ở vị trí 3 gặp dấu mở [ đang chờ trên cùng nên không ghép được. |
| 3 | (( | 3 Giải thích: không có dấu đóng sai nhưng còn hai dấu mở chưa đóng, vị trí lỗi là n + 1 = 3. |
Bài 3. Phiếu giảm giá
Hổ đi mua n món đồ, món thứ i có giá a[i]. Hổ có k phiếu giảm giá. Mỗi phiếu dùng cho một món đồ và giảm giá món đó đi một nửa, làm tròn xuống (giá 7 thành 3; giá 1 thành 0). Một món có thể dùng nhiều phiếu, mỗi phiếu lại giảm một nửa giá hiện tại. Hổ dùng đúng k phiếu (phiếu dùng vào món giá 0 thì không thay đổi gì). Hỏi tổng số tiền Hổ phải trả nhỏ nhất là bao nhiêu?
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n, k ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng số tiền nhỏ nhất. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n, k ≤ 100. Nhóm 2 (15 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây. | |
| Test | Input | Output |
| 1 | 3 2 10 3 7 | 11 Giải thích: dùng một phiếu cho món 10 (còn 5) và một phiếu cho món 7 (còn 3), giá còn 5, 3, 3 và tổng là 11. |
| 2 | 2 5 1 1 | 0 Giải thích: chỉ hai phiếu đã đưa cả hai món về 0, ba phiếu còn lại không thay đổi gì, tổng là 0. |
| 3 | 1 3 100 | 12 Giải thích: giá 100 giảm thành 50, rồi 25, rồi 12. |
Bài 4. Mã khóa tủ
Tủ đồ của Gấu Po có khóa số gồm n chữ số (mỗi chữ số từ 0 đến 9, số 0 được đứng đầu). Gấu Po chọn mã khóa theo hai quy tắc: tổng các chữ số đúng bằng S, và hai chữ số đứng cạnh nhau không được giống nhau. Hỏi Gấu Po có bao nhiêu mã khóa để chọn?
| Đầu vào | Một dòng gồm hai số nguyên n, S (1 ≤ n ≤ 7; 0 ≤ S ≤ 63). | |
|---|---|---|
| Đầu ra | Số mã khóa thỏa mãn. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n ≤ 4. Nhóm 2 (15 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây. | |
| Test | Input | Output |
| 1 | 2 5 | 6 Giải thích: các mã thỏa mãn là 05, 14, 23, 32, 41, 50. |
| 2 | 3 3 | 7 Giải thích: các mã thỏa mãn là 012, 021, 030, 102, 120, 201, 210 (không có 003 hay 111 vì có hai chữ số cạnh nhau giống nhau). |
| 3 | 1 7 | 1 Giải thích: chỉ có mã 7. |