Przeskocz do treści

Delta mi!

Wyspa i liczydło

Bartosz Łukasiewicz

o artykule ...

  • Publikacja w Delcie: luty 2019
  • Publikacja elektroniczna: 1 lutego 2019
  • Wersja do druku [application/pdf]: (299 KB)

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.

obrazek

Rys. 1

Rys. 1

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) i |(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) i (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.

Pozostał nam ostatni przypadek, kiedy | L nie jest wielokrotnością | P oraz |P nie jest wielokrotnością |L. Wtedy mnożymy |L przez |P oraz |P przez L i otrzymujemy dwie równe liczby. Wówczas odpowiedzią jest |3.

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