e-olymp
Yarışlar

IOI 2019 Azerbaijan Team Selection Contest (Day1 + Day2)

Binaların Dağıdılması

Bakı şəhərində sıradan çıxmış binalar var. Bu binaların yerində yeni binalar tikiləcək. Bunun üçün mövcud binaların sökülməsi lazımdır.

Barış sıradan çıxmış binaların dağıdılması üzrə mütəxəssisdir. Onun belə binaları dağıdan super robotu var.

Şəhərdə n sayda yan-yana yerləşən bina var. Bu binaları dağıtmaq üçün Barış öz super robotunu işə saldı.

Binaların hər biri üst-üstə qoyulmuş müəyyən sayda blokdan ibarətdir. Robot bu binaların hamısını dağıtmalıdır. Bir gedişdə robot bütün daxili olmayan blokları dağıdır. Buna əsasən robotun bütün binaları neçə gedişə dağıdacağını tapın.

Bütün 4 tərəfində (sol, sağ, aşağı, yuxarı) dağılmamış blok və ya yer olan bloklar daxili bloklar sayılır (Müəyyənlik üçün şəklə baxın).

Giriş verilənləri

İlk sətirdə bir tam ədəd n (1n105) - ardıcıl binaların sayı, ikinci sətirdə isə boşluqla ayrılmış n sayda tam ədəd h1, h2, ... , hn (1hi109) - binaların hündürlükləri verilir.

Çıxış verilənləri

Çıxışa bir tam ədəd – bütün binaları dağıtmaq üçün lazım olan gedişlərin sayını verin.

Aşağıdakı şəkildə birinci nümunə üçün 3 mərhələ göstərilmişdir.

img.jpg

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
6
2 1 4 6 2 2

Çıxış verilənləri #1
3
Giriş verilənləri #2
7
3 3 3 1 3 3 3

Çıxış verilənləri #2
2
Müəllif Rashad Mammadov
Mənbə İOİ 2019 Azərbaycan komandasına seçim turu