Informatyczny kącik olimpijski

Wyspa i liczydło

Tym razem omówimy dwa zadania: Wyspę z IX OIG oraz Liczydło z XII OIG.

Zadanie (Wyspa). Dany jest prostokąt o bokach równoległych do osi układu współrzędnych, którego lewy-dolny róg ma współrzędne $(0,0),$ zaś prawy-górny róg ma współrzędne $(N, M).$ Dla podanego $P ∈ N (P ⩽ NM 2-)$ chcemy znaleźć taki czworokąt wypukły o polu $|P,$ którego wierzchołki mają współrzędne całkowite oraz należą do prostokąta.

Przypadek: $N$
Rozważmy najpierw przypadek, kiedy $|N P .$ Wtedy możemy zbudować prostokąt, którego wierzchołkami są: $P (0,0),(N, 0),(N, N )$ i $P (0, N ).$ Przykład dla: $N = 7,M = 5,P = 14.$ [Rys. 1]

Przypadek: $N$
Ten przypadek przeanalizujemy w trzech krokach:

(1)

Jeśli

P < N,

wtedy możemy zbudować prostokąt, którego wierzchołkami są:

(0,0),(P,0),(P ,1)

|(0,1).

Przykład dla:

N = 7,M = 5,P = 5.

[Rys. 2]

(2)

Jeśli

N < P < 2N,

wtedy możemy zbudować trapez, którego wierzchołkami są:

(0,0),(N,0),(P − N, 2)

(0,2).

Przykład dla:

N = 7,M = 5,P = 10.

[Rys. 3]

(3)

Został nam do rozpatrzenia przypadek, kiedy

2N < P .

Niech:

$|P = N ⌊P⌋ c N$ (największa wielokrotność $|N$ nie większa niż $P$ ),
$|H = 2PNc$ (wysokość trójkąta o podstawie $N,$ który ma pole $P c$ ),
$|R = P− Pc.$ Wówczas możemy zbudować czworokąt, którego wierzchołkami są: $|(0,0), (N,0),(N, 2)$ i $(N −R, H).$ Przykład dla: $|N = 7,M = 5,P = 16.$ Wtedy $Pc = 14,H = 4$ oraz $|R = 2.$ [Rys. 4]

Powyższe rozważania pokrywają wszystkie przypadki. Dla każdego z nich udało nam się wskazać czworokąt wypukły o polu $P .$

Zadanie (Liczydło). Dane są dwie liczby całkowite $|L$ i $P .$ W każdym kroku możemy wykonać jedną z dwóch operacji: 1) dodać dowolnie wybraną liczbę całkowitą do $L$ oraz do $|P$ (jednocześnie); 2) przemnożyć L lub P przez dowolnie wybraną niezerową liczbę całkowitą. Ile minimalnie operacji należy wykonać, aby obie liczby stały się równe zero?

Zauważmy najpierw, że tylko dla $L = 0$ i $P = 0$ odpowiedzią jest $|0.$ Podobnie, tylko dla $L = P,$ gdzie $L /= 0,$ odpowiedzią jest $1$ - wystarczy do obu liczb dodać $|− L.$

W pozostałych przypadkach odpowiedź będzie większa od $1.$ Zauważmy, że operacja typu $2)$ nie pozwala wyzerować niezerowej liczby, więc ostatnia operacja będzie typu $1)$ i zostanie zastosowana do dwóch równych liczb. Jak zatem wyrównać dwie liczby w minimalnej liczbie ruchów?

Rozważmy przypadek, kiedy jedna z liczb jest wielokrotnością drugiej (bez straty ogólności załóżmy, że $|L$ jest wielokrotnością $|P$ ):

jeśli $L /= 0,$ wtedy $P$ mnożymy przez $L P .$ Całkowita liczba operacji wynosi $2,$
jeśli $L = 0,$ wtedy do obu liczb dodajemy $P$ i tę o mniejszej wartości bezwzględnej mnożymy przez $2.$ Całkowita liczba operacji wynosi $3.$

Prosty dowód, że w każdym z powyższych przypadków korzystamy z minimalnej liczby operacji, pozostawiamy Czytelnikowi.