Tìm k lớn nhất
Xem PDF
Điểm:
250
Thời gian:
0.1s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho \(n\) số nguyên dương \(c_1,c_2,...,c_n\) và số nguyên dương \(X\). Tìm số nguyên \(k\) không âm lớn nhất sao cho tồn tại \(k\) chỉ số \(i_1,i_2,...,i_k\) thỏa mãn:
-
\(1\le i_1<i_2<...<i_k\le n\)
-
\(\sum\limits_{j=1}^{k}c_{i_j}(n-i_j+1)\le X\)
Input
-
Dòng thứ nhất chứa \(2\) số nguyên \(n,k(1\le n\le 100;1\le X\le 10000)\).
-
Dòng thứ hai chứa \(n\) số nguyên: \(c_1,c_2,...,c_n (1\le c_i\le 300\ \forall 1\le i\le n)\)
Output
- In ra số \(k\) lớn nhất cần tìm
Example
Test 1
Input
3 4
1 2 1Output
2Note
Giải thích: Ở ví dụ này ta chọn tìm được \(k=2\) là lớn nhất thỏa mãn yêu cầu bài toán , 2 chỉ số đó là \(i_1=1;i_2=3\).
Bình luận
bài này nên tăng giới hạn của n
Mình nghĩ bài này các bạn biết cách làm QHD là được rồi, việc tăng giới hạn ở bài này mình thấy cũng không cần thiết !