Neçə kəsişmə nöqtəsi var?#1539

Neçə kəsişmə nöqtəsi var?

1 saniyə
128 meqabayt
Orta

İki sıra var. Yuxarı sırada nöqtə, aşağı sırada isə nöqtə yerləşir. Yuxarı sıradakı hər bir nöqtə aşağı sıradakı hər bir nöqtə ilə bir xətt parçası ilə birləşdirilib. Nöqtələr elə düzülüb ki, parçaların yaratdığı daxili kəsişmə nöqtələrinin sayı maksimum olsun. Bunun üçün heç bir üç xətt parçası bir nöqtədə kəsişməməlidir. Sıraların üzərində yerləşən kəsişmə nöqtələri nəzərə alınmır; həmin nöqtələrdə istənilən sayda parça kəsişə bilər. və verildikdə, iki sıra arasında maksimum kəsişmə nöqtələrinin sayını P(a, b) tapın. Məsələn, a = 2 və b = 3 olduqda, şəkildə göstərildiyi kimi, P(2, 3) = 3-dür.

prb1539

Giriş

Hər sətirdə iki natural ədəd (0 < a \leq 20000) və (0 < b \leq 20000) verilir. Son sətirdə isə iki sıfır verilir və bu sətir işlənməməlidir. Testlərin sayı -dən çox deyil.

Çıxış

Hər test üçün, onun sıra nömrəsini və P(a, b) qiymətini ayrı-ayrı sətirlərdə verin.Nəticə 64-bit işarəli tam ədəd tipinə sığır.

Nümunələr

Nümunə 1

Loading
Loading