Trâu ăn cỏ

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
jumptozero
Dạng bài
Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

  • 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 5
Output 
3
Note

Đá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


  • 4
    longkold00    10:15 p.m. 11 Tháng 10, 2021 ← chỉnh sửa 2

    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


    • 1
      VoBaThongL921    6:08 p.m. 20 Tháng 10, 2021

      anh viết 9 ngày r em mới đọc:) cách làm gọn lẹ quá UwU


      • 2
        longkold00    8:19 p.m. 20 Tháng 10, 2021

        nay may quá e ạ, ko mất 30k r 🙂 4 hôm nữa thi nốt học phần 2

    2 bình luận nữa