Ôn tập GĐ3: Đề 2
- Độ 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ửa sổ đủ màu | 25 | |
| 2 | Người cao hơn ở xa bao nhiêu | 25 | |
| 3 | Cặp gần nhau nhất | 25 | |
| 4 | Điểm cố định | 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ửa sổ đủ màu
Hổ treo n chiếc đèn lồng thành một hàng, chiếc thứ i có màu a[i]. Hổ có một khung kính che vừa k chiếc đèn liên tiếp và trượt từ trái sang phải qua mọi vị trí có thể (có n - k + 1 vị trí). Hổ thích những vị trí mà trong khung có đúng d màu khác nhau. Hãy đếm số vị trí của khung mà Hổ thích.
| Đầu vào | Dòng 1: ba số nguyên n, k, d (1 ≤ k ≤ n ≤ 105; 1 ≤ d ≤ k). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số vị trí của khung có đúng d màu khác nhau. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n ≤ 1000. 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 | 7 3 2 1 2 1 3 3 3 2 | 3 Giải thích: số màu của năm khung lần lượt là 2, 3, 2, 1, 2 nên có 3 khung có đúng 2 màu. |
| 2 | 4 4 1 5 5 5 5 | 1 Giải thích: chỉ có một khung và trong khung có đúng 1 màu. |
| 3 | 3 2 2 1 1 1 | 0 Giải thích: hai khung đều chỉ có 1 màu nên không có khung nào thỏa mãn. |
Bài 2. Người cao hơn ở xa bao nhiêu
Gấu Po cho n bạn đứng thành một hàng ngang, bạn thứ i cao a[i]. Mỗi bạn nhìn sang bên phải để tìm bạn đầu tiên cao hơn mình. Hãy cho biết với mỗi bạn, bạn cao hơn đó đứng cách mình bao nhiêu bước (hiệu số thứ tự). Nếu không có bạn nào cao hơn thì ghi 0.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | n số cách nhau một dấu cách, số thứ i là khoảng cách đến bạn đầu tiên bên phải cao hơn bạn i, hoặc 0 nếu không có. | |
| 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 | 6 4 5 2 25 7 8 | 1 2 1 0 1 0 Giải thích: bạn 1 (cao 4) có bạn cao hơn ở ngay sau (cách 1), bạn 2 (cao 5) gặp bạn cao 25 ở vị trí 4 (cách 2), bạn 4 (cao 25) và bạn 6 (cao 8) không có bạn cao hơn. |
| 2 | 3 3 2 1 | 0 0 0 Giải thích: dãy giảm dần nên không có bạn nào có người cao hơn bên phải. |
| 3 | 1 5 | 0 Giải thích: chỉ có một bạn. |
Bài 3. Cặp gần nhau nhất
Thỏ có n chiếc thẻ, thẻ thứ i ghi số a[i]. Thỏ muốn chọn hai thẻ ở hai vị trí khác nhau sao cho hiệu số hai số trên thẻ (số lớn trừ số nhỏ) là nhỏ nhất. Hãy cho biết hiệu số nhỏ nhất đó.
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Hiệu số nhỏ nhất giữa hai thẻ ở hai vị trí khác nhau. | |
| 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 | 4 10 3 8 20 | 2 Giải thích: cặp (10, 8) có hiệu là 2, nhỏ nhất. |
| 2 | 3 5 5 9 | 0 Giải thích: hai thẻ cùng ghi số 5 nên hiệu là 0. |
| 3 | 2 1 1000000000 | 999999999 Giải thích: chỉ có một cặp, hiệu là 999999999. |
Bài 4. Điểm cố định
Gấu Po xếp n thẻ bài đánh số từ 1 đến n thành một hàng. Thẻ ở vị trí i gọi là đứng đúng chỗ nếu số ghi trên thẻ đó bằng i. Hỏi có bao nhiêu cách xếp (hoán vị của 1, 2, ..., n) mà có đúng k thẻ đứng đúng chỗ?
| Đầu vào | Một dòng gồm hai số nguyên n, k (1 ≤ n ≤ 9; 0 ≤ k ≤ n). | |
|---|---|---|
| Đầu ra | Số cách xếp có đúng k thẻ đứng đúng chỗ. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n ≤ 6. 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 1 | 3 Giải thích: các cách xếp 1 3 2, 3 2 1 và 2 1 3 mỗi cách có đúng một thẻ đứng đúng chỗ. |
| 2 | 3 0 | 2 Giải thích: các cách xếp 2 3 1 và 3 1 2 không có thẻ nào đứng đúng chỗ. |
| 3 | 4 4 | 1 Giải thích: chỉ có cách xếp 1 2 3 4 có cả bốn thẻ đứng đúng chỗ. |