Düzensizlikten Çıkış (Platin)#10390

Düzensizlikten Çıkış (Platin)

1 saniye

128 megabayt

Çok zor

Çiftlik dışındaki uzun vadeli kariyer fırsatlarını göz önünde bulundurarak, inek Bessie çeşitli çevrimiçi kodlama sitelerinde algoritmalar öğrenmeye başladı. En sevdiği iki algoritma "kabarcık sıralaması (bubble sort)" ve "hızlı sıralama (quicksort)", ama ne yazık ki Bessie bu ikisini kolayca karıştırıyor ve sonunda ikisinin oldukça tuhaf bir melezini uyguluyor!

$A$ dizisinin $i$ ve $i + 1$ i + 1 elemanları arasındaki konuma, eğer $A_{0}, \dots, A_{i}$ A_0, \ldots, A_i'nin maksimumu $A_{i + 1}, \dots, A_{n - 1}$ A_{i+1}, \ldots, A_{n-1}'in minimumundan büyük değilse, bir bölüm noktası (partition point) diyelim. Bessie, hızlı sıralamanın diziyi bir bölüm noktasına sahip olacak şekilde yeniden düzenlediğini ve ardından iki parçayı $A_{0}, \dots, A_{i}$ A_0, \ldots, A_i ve $A_{i + 1}, \dots, A_{n - 1}$ A_{i+1}, \ldots, A_{n-1} olarak özyinelemeli şekilde sıraladığını hatırlıyor. Ancak, bir dizinin tüm bölüm noktalarının doğrusal zamanda bulunabileceğini doğru bir şekilde not etmesine rağmen, hızlı bir şekilde bir bölüm noktası oluşturmak için dizinin nasıl yeniden düzenlenmesi gerektiğini unutmuş! Sıralama tarihindeki en kötü algoritmik hata olabilecek şekilde, bu işlem için kabarcık sıralamasını kullanma gibi talihsiz bir karar veriyor.

İşte Bessie'nin $A$ dizisini sıralamak için uyguladığı kodun taslağı. İlk olarak, kabarcık sıralamasının bir geçişini gerçekleştiren basit bir fonksiyon yazıyor:

bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}

Hızlı(ımsı) sıralama fonksiyonunun özyinelemeli kodu şu şekilde yapılandırılmıştır:

quickish_sort (A) {
   if length(A) = 1, return
   do { // Main loop
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A)
   divide A at all partition points; recursively quickish_sort each piece
}

Bessie, kodunun ne kadar hızlı çalışacağını merak ediyor. Basitlik adına, ana döngünün her bir yinelemesinin doğrusal zaman aldığını varsayıyor, bu yüzden algoritmanın yaptığı toplam işi takip etmek için döngü içinde $w or k_co u n t er$ work\_counter global değişkenini buna göre artırıyor.

Verilen giriş dizisi için, dizi $q u i c k i s h_sor t$ quickish\_sort tarafından sıralandıktan sonra $w or k_co u n t er$ work\_counter'ın son değerini tahmin edin.

Giriş

İlk satır bir tamsayı $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) içerir. Sonraki $n$ satırın her biri dizinin bir elemanını içerir: $A_{0}, \dots, A_{n - 1}$ A_0, \ldots, A_{n-1} — $0$ ile $1 0^{9}$ 10^9 arasında bir tamsayı. Elemanlar mutlaka farklı olmak zorunda değildir.

Çıktı

Tek bir tamsayı yazdırın — $w or k_co u n t er$ work\_counter'ın son değeri.

Örnekler

Örnek 1

Not

Bu örnekte, $20234987$ 20\ 2\ 3\ 4\ 9\ 8\ 7 dizisiyle başlıyoruz. Kabarcık sıralamasının bir geçişinden sonra (ki bu $w or k_co u n t er$ work\_counter'a $7$ ekler), $2 ∣ 3 ∣ 4 ∣ 987 ∣ 20$ 2 \mid 3 \mid 4 \mid 9\ 8\ 7 \mid 20 elde ederiz; burada $∣$ bir bölüm noktasını belirtir. Bu nedenle, problem özyinelemeli alt problemlere bölünür: $2$ , $3$ , $4$ ve $20$ 'yi sıralamak (her biri sıfır iş gerektirir) ve $987$ 'yi sıralamak. $987$ alt problemi için, ana döngünün bir yinelemesi ( $3$ birim iş) $87 ∣ 9$ 8\ 7 \mid 9 verir, ardından $87$ üzerinde son bir geçiş ( $2$ birim iş) sıralamayı tamamlar. Toplamda, $w or k_co u n t er$ work\_counter $7 + 3 + 2 = 12$ 7 + 3 + 2 = 12'ye eşittir.