İnteraktiv
Alex_KPR: — ...Dekart ağacları, FFT və digər mövzularla məşğul olmaq, kod yazmaq və səhvləri düzəltmək yorucu və olduqca darıxdırıcı bir işə çevrilir...
Kunyavsky: — Kiçik bir məsələyə toxunmaq istəyirəm. Dekart ağacı və FFT yazılış baxımından eyni sırada nə edirlər?
Alex_KPR: — Bu, çox yazmaq lazım olan və səhv etməyə açıq olan ilk şeydir
Kunyavsky: — Dedim ki: kiçik məsələlərə toxunuram. Məncə, yan-yana qoyulmuş məsələlərdən biri yazılış baxımından müqayisə olunmaz dərəcədə asandır
homo_sapiens: — Tamamilə razıyam, Furye ağacdan iki, bəlkə də üç dəfə daha sürətli yazılır (amma onu adətən əllə və ayaqla itələmək lazımdır)
Kunyavsky: — Mən əksini nəzərdə tuturdum. Hər halda çox spesifik mövzudur.
homo_sapiens: — Görünür, həqiqətən də zövq və rəng məsələsidir...
Sadə olanı öyrənməyin vaxtı gəldi.
Sizə N tam ədəddən ibarət iki ardıcıllıq {x_i} və {y_i} verilir.
Əgər FFT sizə daha çox maraqlıdırsa, təsəvvür edin ki, bunlar iki çoxhədlinin əmsallarıdır:
P(z)·Q(z) çoxhədlinin əmsallarını tapın.
Əgər Dekart ağacları sizə daha çox maraqlıdırsa, təsəvvür edin ki, {x_i} — açarlar, {y_i} — prioritetlərdir. Bütün N elementlərini (x_i, y_i) ardıcıl olaraq daxil edərək Dekart ağacı qurun. Hər bir daxil etmədən sonra alınan ağacın hündürlüyünü çıxarın. Ağacın hündürlüyü — istənilən zirvədən kökə qədər olan ən uzun yoldakı kənarların sayıdır.
FFT-ni seçənlər üçün xatırladaq ki, Dekart ağacı — zirvələrdəki açarlara görə ikili axtarış ağacıdır (x_i). Eyni zamanda zirvələrdəki prioritetlərə görə yığındır (y_i). Yəni, ağacın hər bir zirvəsi üçün sol alt ağacdakı bütün zirvələrin açarları həmin zirvənin açarlarından kiçikdir, sağ alt ağacdakı bütün zirvələrin açarları isə böyükdür. Həmçinin, həmin zirvənin prioriteti onun oğullarının prioritetindən böyükdür.
Nəyi seçməyinizdən asılı olmayaraq, müəllif bu məsələdə hazır kod istifadə etməməyinizi xahiş edir.
Giriş verilənləri
Birinci sətirdə N ədədi. İkinci sətirdə N fərqli tam ədəd — {x_i}. Üçüncü sətirdə N fərqli tam ədəd — ardıcıllıq {y_i}.
Çıxış verilənləri
Əgər FFT-ni seçmisinizsə, 2N-1 tam ədəd çıxarın — nəticə çoxhədlinin əmsalları. Əgər Dekart ağacı, N tam ədəd çıxarın — hər bir zirvənin daxil edilməsindən sonra ağacın hündürlüyü.
Ümumiyyətlə, hər ikisini də çıxara bilərsiniz, amma o zaman hər iki nəticə düzgünlüyə görə yoxlanacaq.
Məhdudiyyətlər
1 ≤ N ≤ 50000
1 ≤ x_i ≤ 50000
1 ≤ y_i ≤ 50000
Ağacın hündürlüyünün 50-dən çox olmayacağı təmin edilir.