[Học thêm HSG9] Ngày 13/8/2024

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Đi thi 100 (p) 1.0s 256M
2 Kho báu bí ẩn 100 (p) 1.0s 256M
3 Dãy con tăng dài nhất 100 (p) 1.0s 1G

1. Đi thi

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bạn rất yêu thích và học giỏi môn Tin học, vì vậy năm nay bạn đã đăng ký tham dự kỳ thi HSG lớp 10 do nhà trường tổ chức. Vào buổi thi, sau khi nhận được đề thi, bạn thấy đề thi có \(n\) bài, bài thứ \(i\) có số điểm là \(d_i\). Sau khi phân tích kỹ các bài, bạn thấy với khả năng của mình thì thời gian để làm mỗi bài là như nhau và mình chỉ đủ thời gian làm \(k\) bài. Tuy nhiên quy định của ban tổ chức không cho phép thí sinh bỏ qua hai bài liền kề (nếu thí sinh bỏ qua bài thứ \(i\) và bài thứ \(i + 1\) thì tất cả các bài từ bài thứ \(i\) trở đi đều không được tính điểm). Tất nhiên với trí thông minh của mình thì bạn có thể lựa chọn các bài để làm sao cho đạt được số điểm tối đa. Hãy tính xem, số điểm tối đa bạn có thể đạt là bao nhiêu?

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương \(n\) và \(k\);
  • Dòng thứ hai chứa \(n\) số nguyên dương \(d_1, d_2, ..., d_n\).
  • Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra:

  • Một số nguyên duy nhất là số điểm tối đa bạn có thể đạt được.
Sample
Input 
5 2
7 3 3 9 10
Output 
12
Giải thích 
Bạn chọn làm các bài số 2 và số 4, số điểm đạt được là 3 + 9 = 12.

Giới hạn:

  • \(1 ≤ n, k ≤ 25; 1 ≤ d_1, d_2, ..., d_n ≤ 1000\).

2. Kho báu bí ẩn

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trung ở nhà chán quá nên Trung rủ các bạn mình đến nhà chơi trò chơi đi tìm kho báu. Một trong những chướng ngại vật mà các bạn của Trung cần vượt qua là phải tìm Mã hóa của số \(N (N <= 10^{8})\) (Không hiểu vì nó liên quan đến kho báu như thế nào nhưng Trung bảo bạn làm thế) cho trước theo quy tắc sau:

Với một số nguyên \(N\), xóa các chữ số từ con số này bằng mọi cách có thể, ta sẽ nhận được các con số mới. Một số cách xóa mà số mới thu được có giá trị bằng số cũ đó là khi ta xóa các chữ số 0 bên trái. Hãy tìm tổng của tất cả các con số thu được. Tổng này chính là mã hóa của \(N\).

Ví dụ: \(N = 109\)

  • Sau khi xóa chúng ta nhận được các số: \(109, 09, 19, 10, 9, 1, 0\).
  • Tổng các số thu được là: \(109 + 09 + 19 + 10 + 9 + 1 + 0 = 157\).
  • Vì vậy mã của \(109\) là \(157\).
Sample
Input 
109
Output 
157

3. Dãy con tăng dài nhất

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho một dãy số nguyên gồm \(n\) phần tử \(A_1,A_2,A_3,...,A_N\)
Biết rằng dãy con tăng đơn điệu là \(1\) dãy \(A_{i_1},A_{i_2},...,A_{i_k}\) thỏa mãn \(i_1 < i_2 < ... < i_k\) và \(A_{i_1}<A_{i_2}<A_{i_3}...<A_{i_k}\).Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương \(N(1 \leq N \leq 20)\) - số lượng phần tử của dãy \(A\).
  • Dòng thứ hai chứa \(N\) số nguyên dương - lần lượt là các phần tử của dãy \(A( 1 \leq A_i \leq 10^9)\).

Dữ liệu ra

  • Dòng thứ nhất chứa độ dài dãy con tìm được.
Sample
Input 
8
1 9 1 2 2 0 0 7
Output 
3