Ôn tập GĐ1: Đề 1
- Độ 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 | Đỉnh sóng | 25 | |
| 2 | Chuẩn hóa họ tên | 25 | |
| 3 | Cộng hai phân số | 25 | |
| 4 | Quân Hậu tấn công | 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. Đỉnh sóng
Một dãy sóng biển gồm n ngọn sóng, ngọn sóng thứ i có độ cao a[i]. Một ngọn sóng được gọi là đỉnh sóng nếu nó cao hơn hẳn các ngọn sóng kề bên. Ngọn đầu tiên chỉ có một ngọn kề bên (ngọn thứ hai), ngọn cuối cùng cũng chỉ có một ngọn kề bên (ngọn đứng ngay trước nó). Nếu n = 1 thì ngọn sóng duy nhất được coi là đỉnh sóng. Hãy đếm số đỉnh sóng và cho biết độ cao lớn nhất trong các đỉnh sóng đó.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 106). Dòng 2: n số nguyên a[i] (│a[i]│ ≤ 109). | |
|---|---|---|
| Đầu ra | Dòng 1: số lượng đỉnh sóng. Dòng 2: độ cao lớn nhất trong các đỉnh sóng, hoặc -1 nếu không có đỉnh sóng nào. | |
| 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 |
| 7 1 3 2 5 5 4 6 | 2 6 Giải thích: đỉnh sóng là hai ngọn có độ cao 3 và 6. Hai ngọn có độ cao 5 bằng nhau nên không ngọn nào cao hơn hẳn ngọn kề bên. | |
| 3 4 4 4 | 0 -1 Giải thích: không có ngọn nào cao hơn hẳn ngọn kề bên. | |
| 1 7 | 1 7 | |
Bài 2. Chuẩn hóa họ tên
Cô giáo nhận được danh sách họ tên do các bạn tự gõ nên rất lộn xộn: chữ hoa và chữ thường lẫn lộn, có dấu cách thừa ở đầu, ở cuối và giữa các từ. Hãy chuẩn hóa họ tên theo quy tắc: mỗi từ viết hoa chữ cái đầu và viết thường các chữ còn lại, các từ cách nhau đúng một dấu cách, không có dấu cách ở đầu và cuối. Đồng thời cho biết họ tên có bao nhiêu từ.
| Đầu vào | Một dòng duy nhất là họ tên chưa chuẩn hóa, chỉ gồm chữ cái không dấu (a–z, A–Z) và dấu cách, có ít nhất một chữ cái, độ dài không quá 105. | |
|---|---|---|
| Đầu ra | Dòng 1: họ tên sau khi chuẩn hóa. Dòng 2: số từ của họ tên. | |
| Giới hạn và chấm điểm | Độ dài dòng nhập không quá 105 ký tự. Chương trình cần chạy trong 1 giây. Gợi ý: dùng getline để đọc cả dòng có dấu cách. | |
| Test | Input | Output |
| nGUYEN van aN | Nguyen Van An 3 | |
| a | A 1 | |
Bài 3. Cộng hai phân số
Nam cần cộng hai phân số a/b và c/d rồi viết kết quả dưới dạng phân số tối giản p/q. Nam muốn nhờ em viết chương trình kiểm tra bài làm của mình.
| Đầu vào | Một dòng gồm bốn số nguyên dương a, b, c, d (1 ≤ a, b, c, d ≤ 109). | |
|---|---|---|
| Đầu ra | Hai số nguyên dương p và q cách nhau bởi dấu cách: tử số và mẫu số của phân số tối giản bằng a/b + c/d. | |
| Giới hạn và chấm điểm | Subtask 1 (10 điểm): a, b, c, d ≤ 104. Subtask 2 (15 điểm): a, b, c, d ≤ 109. | |
| Test | Input | Output |
| 1 2 1 3 | 5 6 Giải thích: 1/2 + 1/3 = 5/6. | |
| 1 6 1 3 | 1 2 Giải thích: 1/6 + 1/3 = 3/6 = 1/2. | |
| 999999937 999999929 999999929 999999937 | 1999999732000009010 999999866000004473 Chú ý: kết quả có thể rất lớn, vượt quá phạm vi của kiểu int. | |
Bài 4. Quân Hậu tấn công
Trên bàn cờ n × n chỉ có duy nhất một quân Hậu đặt ở ô nằm ở dòng r, cột c (dòng và cột đánh số từ 0). Quân Hậu có thể đi theo hàng ngang, cột dọc hoặc đường chéo, với số ô tùy ý (bàn cờ không có quân nào cản đường). Hãy đếm số ô mà quân Hậu có thể tấn công, không tính ô quân Hậu đang đứng.
| Đầu vào | Một dòng gồm ba số nguyên n, r, c (1 ≤ n ≤ 109; 0 ≤ r, c < n). | |
|---|---|---|
| Đầu ra | Số ô mà quân Hậu có thể tấn công. | |
| Giới hạn và chấm điểm | Subtask 1 (10 điểm): n ≤ 1000. Subtask 2 (15 điểm): n ≤ 109. | |
| Test | Input | Output |
| 8 0 0 | 21 Giải thích: Hậu ở góc trên bên trái tấn công 7 ô cùng hàng, 7 ô cùng cột và 7 ô trên đường chéo. | |
| 8 3 3 | 27 Giải thích: Hậu ở giữa bàn cờ tấn công 7 + 7 ô theo hàng, cột, và 7 + 6 ô theo hai đường chéo. | |
| 1000000000 0 0 | 2999999997 | |