trang chủ / đề bài / icpc23_mn_k

Tam giác đá

Đề bài

Mô tả

Trong một phòng triển lãm nghệ thuật cổ điển, Leo Da Vi tạo tác phẩm từ n cột đá liên tiếp có chiều cao lần lượt là a1,a2,…,an. Ông muốn tạo ra một tác phẩm điêu khắc hình tam giác cân, nhưng hiện tại mỗi cột đá lại có một chiều cao khác nhau.

Leo quyết định đục bớt từng cột đá, luôn đục từ đỉnh xuống dưới của mỗi cột, sao cho cuối cùng chỉ còn lại một tam giác cân bằng đá. Ông chỉ có thể đục bớt trên từng cột đá chứ không thể chuyển đá sang cột khác.

Một tam giác đá có chiều cao h gồm 2h−1 cột liên tiếp với chiều cao lần lượt là 1,2,…,h−1,h,h−1,…,2,1. Ví dụ, các tam giác có chiều cao 1, 2, 3 lần lượt là các dãy cột 1; 1,2,1; 1,2,3,2,1. Các cột không thuộc tam giác bị đục bỏ hoàn toàn.

Cho dãy chiều cao của các cột đá, hãy giúp Leo xác định chiều cao lớn nhất mà tam giác cân có thể đạt được.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n (1≤n≤50000) là số cột đá.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤n) là chiều cao của các cột đá.

Dữ liệu ra

In ra một số nguyên H là chiều cao lớn nhất mà tam giác có thể đạt được.

Ràng buộc

  • 1≤n≤50000
  • 1≤ai≤n

Ví dụ

Input Output Giải thích
16
5 6 5 8 9 10 5 8 9 5 7 9 9 9 6 3
6 Tam giác có đỉnh ở cột thứ 6 dùng các cột 1 đến 11 với chiều cao 1,2,3,4,5,6,5,4,3,2,1, đều không vượt quá chiều cao ban đầu 5,6,5,8,9,10,5,8,9,5,7.
8
5 1 1 1 1 1 1 3
1 Không có ba cột liên tiếp nào có cột giữa cao ít nhất 2, nên chỉ tạo được tam giác chiều cao 1.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0