Ôn tập GĐ1: Đề 2
- Độ khó
- ★★★☆☆ Vừa
- Thời lượng
- Khoảng 120 phút
- Học trước
- Mảng 1 chiều, Vector, String (chuỗi ký tự), Ước, bội, ƯCLN, BCNN, Số nguyên tố và sàng, Mảng 2 chiều, Hàm tự tạo và đệ quy, Độ phức tạp (Big-O)
- 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 | Dọn hàng | 25 | |
| 2 | Giải nén chuỗi | 25 | |
| 3 | Tổng ước nguyên tố | 25 | |
| 4 | Xâu nhị phân có k số 1 | 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, số âm...).
- Ở những bài có nhiều mức 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 mức nhỏ.
- Chú ý kiểu dữ liệu: khi kết quả 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 và Bài 4 mỗi bài khoảng 35 phút.
Đề bài
Bài 1. Dọn hàng
Có n bạn nhỏ xếp thành một hàng, mỗi bạn cầm một tấm thẻ ghi một số nguyên. Nếu có nhiều bạn đứng liền nhau cầm các thẻ cùng số thì chỉ cần giữ lại một bạn trong số đó, các bạn còn lại rời khỏi hàng. Hãy in ra hàng sau khi đã dọn xong (thứ tự các bạn ở lại không thay đổi).
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 106). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Dòng 1: số bạn còn lại trong hàng. Dòng 2: các số ghi trên thẻ của các bạn còn lại, theo đúng thứ tự, cách nhau bởi dấu cách. | |
| Giới hạn và chấm điểm | Mọi test đều có 1 ≤ n ≤ 106. Chương trình cần chạy trong 1 giây. | |
| Test | Input | Output |
| 8 1 1 2 2 2 3 1 1 | 4 1 2 3 1 Giải thích: các cụm liền nhau (1 1), (2 2 2), (1 1) mỗi cụm chỉ giữ lại một bạn. | |
| 3 5 5 5 | 1 5 | |
| 4 1 2 1 2 | 4 1 2 1 2 Giải thích: không có hai bạn đứng liền nhau nào cầm thẻ giống nhau. | |
Bài 2. Giải nén chuỗi
Để tiết kiệm bộ nhớ, người ta nén một chuỗi bằng cách thay mỗi đoạn các ký tự giống nhau liên tiếp bằng ký tự đó kèm độ dài đoạn. Ví dụ aaabbc được nén thành a3b2c1. Hãy viết chương trình giải nén: từ chuỗi đã nén, khôi phục lại chuỗi ban đầu.
| Đầu vào | Một chuỗi s gồm các cặp (một chữ cái thường, một số nguyên dương) viết liền nhau. Độ dài của s không quá 1000, mỗi số nguyên dương không quá 1000 và có thể gồm nhiều chữ số. | |
|---|---|---|
| Đầu ra | Chuỗi sau khi giải nén. Độ dài chuỗi kết quả không quá 106. | |
| Giới hạn và chấm điểm | Chương trình cần chạy trong 1 giây. | |
| Test | Input | Output |
| a3b2c1 | aaabbc | |
| x12 | xxxxxxxxxxxx Giải thích: số 12 có hai chữ số, nghĩa là ký tự x lặp lại 12 lần. | |
| a1b10 | abbbbbbbbbb | |
Bài 3. Tổng ước nguyên tố
Cho số nguyên n. Hãy tính tổng của các ước nguyên tố khác nhau của n. Ví dụ n = 360 = 23 × 32 × 5 có ba ước nguyên tố khác nhau là 2, 3 và 5 nên tổng là 10.
| Đầu vào | Một số nguyên n (2 ≤ n ≤ 1012). | |
|---|---|---|
| Đầu ra | Tổng các ước nguyên tố khác nhau của n. | |
| Giới hạn và chấm điểm | Subtask 1 (10 điểm): n ≤ 106. Subtask 2 (15 điểm): n ≤ 1012. | |
| Test | Input | Output |
| 360 | 10 Giải thích: 360 = 23 × 32 × 5, tổng 2 + 3 + 5 = 10. | |
| 97 | 97 Giải thích: 97 là số nguyên tố nên ước nguyên tố duy nhất là chính nó. | |
| 600851475143 | 9238 Giải thích: 600851475143 = 71 × 839 × 1471 × 6857. | |
Bài 4. Xâu nhị phân có k số 1
Một xâu nhị phân là xâu chỉ gồm các ký tự 0 và 1. Hãy liệt kê tất cả các xâu nhị phân có độ dài n và có đúng k ký tự 1, theo thứ tự từ điển (từ nhỏ đến lớn), mỗi xâu trên một dòng. Gợi ý: xây dựng xâu từng ký tự, mỗi vị trí có hai lựa chọn là 0 hoặc 1, rồi gọi đệ quy cho vị trí tiếp theo.
| Đầu vào | Một dòng gồm hai số nguyên n, k (1 ≤ n ≤ 12; 0 ≤ k ≤ n). | |
|---|---|---|
| Đầu ra | Mỗi dòng là một xâu nhị phân độ dài n có đúng k ký tự 1, theo thứ tự từ điển. | |
| Giới hạn và chấm điểm | Chương trình cần chạy trong 1 giây. | |
| Test | Input | Output |
| 4 2 | 0011 0101 0110 1001 1010 1100 | |
| 3 0 | 000 | |
| 3 3 | 111 | |