Trâu ăn cỏ
Xem PDF-
Có \(n\) bãi cỏ được đánh số từ \(1\) đến \(n\) (từ trái sang phải). Và đám cỏ thứ \(i\) sẽ bị úa đi sau \(a_i\) ngày (cụ thể: ngày \(a_i\) cỏ vẫn chưa úa nhưng sang ngày \(a_{i+1}\) thì đã úa rồi).
-
Hôm nay nhân dịp xuân Tân Sửu \(2021\). \(Kaninho\) dắt trâu ra bãi cỏ đó và anh ấy đã giao cho trâu một nhiệm vụ như sau:
-
Nhiệm vụ của chú trâu phải đi từ bãi cỏ thứ nhất sang bãi cỏ thứ \(n\) trong nhiều ngày nhất có thể, biết rằng, trâu chỉ có thể đi từ trái sang phải và giả sử trâu đang ở bãi cỏ thứ \(i(1\le i<n-1)\) thì anh ấy có thể sang bãi cỏ \(i+1\) hoặc bãi có thứ \(i+2\) (tức là "bạn trâu" nhảy cóc), còn nếu trâu đang đứng ở bãi có thứ \(n-1\) thì anh ấy chỉ có thể sang bãi cỏ thứ \(n\) mà thôi. Và có một điều cần lưu ý đó là: Trâu không ăn cỏ úa, tức là nếu cỏ bị úa ở cánh đồng thứ nhất hoặc cánh đồng thứ \(n\) hoặc không tồn tại đường đi nào để đi từ cánh đồng \(1\) sang cánh đồng \(n\) thì xem như trâu chưa hoàn thành nhiệm vụ.
Yêu cầu: Cho một mảng gồm \(n\) phần tử \(a_i\) và xuất ra số ngày nhiều nhất trâu có thể hoàn thành nhiệm vụ.
Là một lập trình viên chuyên nghiệp, các bạn hãy giúp bạn trâu một tay nhé !
Input
-
Dòng thứ nhất chứa số nguyên \(n(1\le n\le 1000)\) - Thể hiện số lượng bãi cỏ.
-
Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n (1\le a_i\le 1000)\)
Output
- In ra đáp án cần tìm
Example
Test 1
Input
4
3 6 7 5Output
3Note
Đáp án của test ví dụ là \(3\) là vì \(3\) là số ngày lớn nhất mà trâu có thể đi từ bãi cỏ thứ \(1\) đến bãi có thứ \(4\). Và đường đi của trâu có thể đi được đó là : \(1\rightarrow 2\rightarrow 4\).
Bonus thêm một chút để các bạn hiểu đề đó là : Giả sử số ngày lớn nhất mà trâu có thể đi là \(4\) thì bãi cỏ đầu tiên sẽ bị úa, vì thế trâu sẽ không hoàn thành nhiệm vụ.
Bình luận
Sau khi tham khảo mình sẽ chia sẻ hướng làm bài ngắn gọn hơn sau: chỉ cần a[1], a[n], và không có bất cứ 2 bó cỏ liền nhau nào bị úa thì chắc chắn bò sẽ đi đc từ 1->n.
res=min(a[1],a[n]) sẽ là đáp án cần tìm. duyệt từ 1->n thì res=min(res,max(a[i],a[i+1])) :V
Mình hint một chút để các bạn có thể dễ hiểu đề hơn như sau:
Nhìn vào test ví dụ:
Sau 1 ngày, chúng ta nhận thấy rằng, chưa có bãi cỏ nào bị úa nên trâu sẽ dễ dàng đi từ bãi có \(1\) đến bãi cỏ \(n\). (Vậy chứng tỏ \(1\) có khả năng là đáp án của bài toán, nhưng chúng ta cùng xem tiếp nếu sau \(2\) ngày thì sao nhé ! - Vì bài toán yêu cầu chúng ta phải tìm số ngày lớn nhất mà trâu có thể đi)
Sau \(2\) ngày, chúng ta cũng nhận thấy rằng, vẫn chưa có bãi cỏ nào bị úa (Suy ra, \(2\) có khả năng là đáp án của bài toán và ta vẫn phải tiếp tục xét đến sau ngày thứ \(3\) thì mọi thứ như thế nào nhé ?)
Sau \(3\) ngày, chúng ta nhận thấy rằng, vẫn chưa có bãi cỏ nào bị úa , nên suy ra \(3\) có khả năng là đáp án của bài toán.
Tiếp theo, sau \(4\) ngày, ta nhận thấy rằng, bãi có \(1\) sẽ bị úa và trâu sẽ không thể hoàn thành nhiệm vụ
Vậy \(3\) là đáp án của bài toán.
cho em hỏi cái problem statement là sao ạ ?? Ví dụ test mẫu 3 6 7 5 là đi qua ô 3 7 5, tổng cộng 3 lần nhảy thì bé hơn ô nhỏ nhất trong tất cả những ô đã chọn hay sao ạ ? 🙂