Minimalny iloczyn trzech liczb

Zadanie 3 z 10 · rozdział 24Trudność: 2 z 3listminmath

Treść zadania

Otrzymujesz listę liczb całkowitych. Znajdź najmniejszy możliwy iloczyn trzech elementów tej listy (trzech elementów o różnych indeksach; wartości mogą się powtarzać).

Jeśli lista ma mniej niż 3 elementy — wypisz iloczyn wszystkich jej elementów.

Dane wejściowe

  • 1. linia: n — długość listy
  • 2. linia: n liczb całkowitych oddzielonych spacjami

Dane wyjściowe

Jedna liczba całkowita — najmniejszy iloczyn.

Ograniczenia

  • 1 ≤ n ≤ 1000
  • elementy listy są z przedziału $[-1000, 1000]$

Uwagi

  • Uważaj na liczby ujemne: iloczyn dwóch ujemnych jest dodatni. Wystarczy porównać dwóch kandydatów: trzy najmniejsze liczby oraz najmniejszą liczbę razy dwie największe.
  • Sprawdzanie wszystkich trójek zajmuje czas $O(n^3)$ — przy $n = 1000$ to ponad $10^8$ trójek. Oczekiwane rozwiązanie działa w czasie $O(n \log n)$ (sortowanie) albo $O(n)$.

Przykład

Wejście
6
3 -1 -3 2 9 4
Wyjście
-108

Najmniejszy iloczyn daje trójka $-3 \cdot 9 \cdot 4 = -108$.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 24

Trudniejsze zadania na listach: przekształcenia w miejscu, sumy prefiksowe, kopiec i programowanie dynamiczne. Liczy się nie tylko poprawny wynik, ale też dobry algorytm — w testach są także długie listy, na których rozwiązanie „sprawdzające wszystkie możliwości” nie zdąży się wykonać.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”. Tekst podany w input("…") jest ignorowany przez sprawdzarkę.
  • Lista liczb jest podawana w dwóch liniach: w pierwszej jest liczba elementów n, w drugiej n liczb całkowitych oddzielonych spacjami (o ile zadanie nie mówi inaczej).
  • Listę wynikową wypisuj w jednej linii, a jej elementy oddzielaj pojedynczą spacją (o ile zadanie nie mówi inaczej).
  • Indeksy liczymy od 0.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
1
-7
Oczekiwane wyjście
-7

Test 2

Nie uruchomiono
Wejście
2
4 -5
Oczekiwane wyjście
-20

Test 3

Nie uruchomiono
Wejście
3
2 3 4
Oczekiwane wyjście
24

Test 4

Nie uruchomiono
Wejście
5
3 2 1 7 8
Oczekiwane wyjście
6

Test 5

Nie uruchomiono
Wejście
4
-1 -2 -3 -4
Oczekiwane wyjście
-24

Test 6

Nie uruchomiono
Wejście
6
1 20 2 -2 -4 -3
Oczekiwane wyjście
-160

Test 7

Nie uruchomiono
Wejście
5
0 5 3 0 2
Oczekiwane wyjście
0

Test 8

Nie uruchomiono
Wejście
4
-3 -2 1 5
Oczekiwane wyjście
-15

Test 9

Nie uruchomiono
Wejście
5
-2 -2 -2 1 1
Oczekiwane wyjście
-8

Test 10

Nie uruchomiono
Wejście
300
274 163 -399 -817 608 -169 -916 784 916 130 -11 696 919 -957 -764 -370 -450 -437 -782 276 491 -631 -721 -557 -785 -687 806 947 -471 188 -454 -381 242 -680 420 195 -108 -435 -770 -321 -48 798 -751 -678 298 -402 -598 447 -496 900 -220 -579 -286 -256 -766 -548 -834 349 774 -32 970 269 655 824 540 740 -773 -341 -394 563 31 351 733 -800 597 665 58 420 435 786 -614 922 347 -20 -540 -586 -577 -213 828 71 77 -724 -136 943 135 -862 -216 -892 535 877 -488 -999 -808 -874 -144 61 -558 960 -991 -811 -779 941 779 -351 -934 -495 -960 -949 -172 -572 -801 806 954 51 -981 -370 462 418 778 -81 850 841 956 375 -269 -542 243 -193 -470 747 689 324 474 569 -667 -398 -649 -797 999 614 94 -518 -30 -917 -869 -789 122 -378 -69 -386 -946 -19 849 546 -979 -25 -171 -802 327 -485 -285 -296 661 -759 101 -363 -349 114 371 518 320 472 547 388 -418 774 -632 291 259 304 -440 47 -909 -261 -599 -734 798 697 -341 -439 -458 454 -977 -882 -406 -921 -574 -178 -98 -572 -551 127 -843 712 -853 634 -417 -189 -758 576 806 -500 -60 -403 424 988 322 -929 -240 -814 595 -984 946 546 -476 -474 860 -388 717 -544 -501 -21 -56 867 407 388 56 -811 -218 199 -953 -185 -118 -698 -58 851 249 -90 400 -640 25 -272 -479 -428 366 247 837 242 741 87 23 779 -394 -357 722 716 107 805 356 280 -360 -507 208 912 -251 -677 -875 453 480 120 -149 397 379 498 9 -779 931 999 -154 77
Oczekiwane wyjście
-997002999
Uruchom z własnymi danymi