Problem
Yeni bir oyun oynarken (bazı bowling ve bilardo melezleri), 1'den N'ye kadar numaralandırılmış N top kullanılır. Oyunun başında, bu toplar sayısal sırayla bir sıra halinde dizilmelidir. Oyun sırasında sıralamaları değişebilir.
Bir sonraki oyun başlamadan önce topları düzenlemek için aşağıdaki cihaz kullanılır. Bu cihaz, topların üzerinde hareket ederek "emebilen" bir kafadan oluşur. ve "tükürmek" balonlar. Bu cihaz hakkında daha iyi bir fikir edinmek için, topları emebilen, doğru yere hareket edebilen ve orada ters yönde üfleyen, topları "tüküren" bir elektrikli süpürge hayal edin.
Bir balon emildiğinde, emilen balonun sağındaki tüm balonlar sola kaydırılır. "Tükürmek" top herhangi iki topun arasında olabilir (ve ayrıca ilk toptan önce veya sonuncudan sonra), sonra tüküren top bu topların arasına sokulur ve sokulan topun sağındaki tüm toplar sağa kaydırılır. .
Cihaza aynı anda birden fazla top emilebilir ve top tükürürken önce son emilen top, ardından sondan bir önceki top tükürülür ve bu böyle devam eder. (yani cihaz bir yığın prensibine göre çalışır). Toplar birer birer tükürülür, yani. geri kalanını cihazın içinde bırakarak yalnızca bir top tükürebilirsiniz (bu durumda, topları aynı veya başka bir yere "tükürmeye" veya yeni topları emmeye devam edebilirsiniz).
Açıklanan işlemler arasında enerji açısından en yoğun olanı top emme işlemidir, bu nedenle bu tür işlemlerin sayısını en aza indirmek istiyoruz.
Bilyaların ilk yerleşimi verildiğinde, topları sayısal sırayla düzenlemek için gereken minimum emme sayısını belirleyecek bir program yazın.
Giriş
Giriş dosyasında önce N sayısı verilir — top sayısı (1≤N≤1000). Daha sonra, topların numaralarını mevcut konumlarında soldan sağa sırayla veren N adet sayı vardır (her bir sayı — 1'den N'ye ve sayıların her biri dizide tam olarak bir kez geçer).
Çıktı
Tek bir sayı çıktısı — topları numara sırasına göre düzenlemek için gerekli olacak minimum top emme işlemi sayısı.
Örnek testler hakkında yorumlar
1.Örneğin 2 numaralı balonu emip 1. ve 3. balon arasına tükürebilirsiniz.
2.>Böyle bir şey yapabilirsiniz. Önce
1 numaralı balonu em, ardından – 2 numaralı top. Sonra başlangıca geçiyoruz ve 4. toptan önce topu tükürüyoruz (bu 2 numaralı top olacak). Ardından, 3 numaralı balonu içine çekin ve 2 ve 4 numaralı balonların arasına tükürün. Ardından başa gidin ve 1 numaralı balonu orada tükürün. Ancak, bu örnekteki balonların tek olası sıralaması bu değildir.
| Giriş |
Çıktı |
|
3
2 1 3
|
1 |
|
4
4 3 2 1
|
3 |
Takım Olimpiyatı, Moskova Takım Olimpiyatı, 9-11. Sınıflar, 2007, A Ligi, Problem F