Para o danej sumie — szybko

Zadanie 14 z 15 · rozdział 17Trudność: 2 z 3dict2-sumzłożoność

Treść zadania

Wczytaj listę n liczb całkowitych oraz liczbę x. Znajdź indeksy i, j (gdzie $i < j$) takie, że lista[i] + lista[j] == x.

Jeśli takich par jest kilka, wybierz tę o najmniejszym i, a przy równym i — o najmniejszym j. Jeśli nie ma żadnej — wypisz -1 -1.

To samo zadanie rozwiązywaliśmy w rozdziale o listach (ZAD-16), ale tym razem lista może mieć nawet $2 \cdot 10^5$ elementów, więc sprawdzanie wszystkich par dwiema pętlami (około $2 \cdot 10^{10}$ porównań) jest zbyt wolne. Użyj słownika, który pozwala w jednym kroku sprawdzić, czy i gdzie w liście wystąpiła potrzebna wartość.

Dane wejściowe

  • 1. linia: liczba elementów n
  • 2. linia: n liczb całkowitych oddzielonych spacjami
  • 3. linia: liczba całkowita x

Dane wyjściowe

Jedna linia: dwie liczby i j oddzielone spacją albo -1 -1.

Ograniczenia

  • $2 \le n \le 2 \cdot 10^5$
  • $-10^9 \le$ lista[i], x $\le 10^9$

Uwagi

  • Para składa się z dwóch różnych pozycji w liście — elementu nie można dodać do samego siebie, ale dwie równe liczby na różnych pozycjach już tak.
  • Wskazówka: przechodź po liście indeksem j i trzymaj słownik wartość → indeks jej pierwszego wystąpienia dla elementów przed j. Wtedy najmniejsze i do pary z j to slownik[x - lista[j]] (o ile taki klucz istnieje). Spośród znalezionych par zapamiętaj tę o najmniejszym i.
  • Uważaj: pierwsza znaleziona w ten sposób para ma najmniejsze j, a niekoniecznie najmniejsze i (patrz przykład).

Przykład

Wejście
4
3 1 4 2
5
Wyjście
0 3

Sumę $5$ dają pary indeksów $(0, 3)$: $3 + 2$ oraz $(1, 2)$: $1 + 4$. Para $(1, 2)$ kończy się wcześniej, ale wybieramy $(0, 3)$, bo ma mniejsze i.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 17

Zadania w tym rozdziale ćwiczą pracę ze słownikami (dict): tworzenie, dodawanie i usuwanie par, zliczanie wystąpień oraz grupowanie danych według klucza.
Każde zadanie (oraz każdy podpunkt) jest osobnym, niezależnym programem: czyta standardowe wejście (stdin) i wypisuje wynik na standardowe wyjście (stdout).

Konwencje wspólne:

  • Dane wczytuj dokładnie w kolejności podanej w sekcji Wejście; jeśli w jednej linii jest kilka wartości — rozbij ją po spacjach.
  • Jeśli wynikiem jest słownik, wypisz go tak, jak robi to print(slownik) w Pythonie: {klucz: wartość, klucz: wartość} — pary oddzielone przecinkiem i spacją, po dwukropku spacja, klucze i wartości napisowe w apostrofach (np. {'ala': 2, 'ma': 1}), liczby bez apostrofów (np. {1: 1, 2: 4}), pusty słownik to {}.
  • Kolejność par w wypisanym słowniku to kolejność, w jakiej klucze były do niego dodawane (tak zachowuje się słownik w Pythonie).
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”.

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
4
2 7 11 15
9
Oczekiwane wyjście
0 1

Test 2

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

Test 3

Nie uruchomiono
Wejście
3
2 2 2
4
Oczekiwane wyjście
0 1

Test 4

Nie uruchomiono
Wejście
3
5 1 9
10
Oczekiwane wyjście
1 2

Test 5

Nie uruchomiono
Wejście
4
-3 7 0 3
0
Oczekiwane wyjście
0 3

Test 6

Nie uruchomiono
Wejście
3
1000000000 -1000000000 5
0
Oczekiwane wyjście
0 1

Test 7

Nie uruchomiono
Wejście
6
1 4 2 6 3 2
4
Oczekiwane wyjście
0 4

Test 8

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

Test 9

Nie uruchomiono
Wejście
400
1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97 100 103 106 109 112 115 118 121 124 127 130 133 136 139 142 145 148 151 154 157 160 163 166 169 172 175 178 181 184 187 190 193 196 199 202 205 208 211 214 217 220 223 226 229 232 235 238 241 244 247 250 253 256 259 262 265 268 271 274 277 280 283 286 289 292 295 298 301 304 307 310 313 316 319 322 325 328 331 334 337 340 343 346 349 352 355 358 361 364 367 370 373 376 379 382 385 388 391 394 397 400 403 406 409 412 415 418 421 424 427 430 433 436 439 442 445 448 451 454 457 460 463 466 469 472 475 478 481 484 487 490 493 496 499 502 505 508 511 514 517 520 523 526 529 532 535 538 541 544 547 550 553 556 559 562 565 568 571 574 577 580 583 586 589 592 595 598 601 604 607 610 613 616 619 622 625 628 631 634 637 640 643 646 649 652 655 658 661 664 667 670 673 676 679 682 685 688 691 694 697 700 703 706 709 712 715 718 721 724 727 730 733 736 739 742 745 748 751 754 757 760 763 766 769 772 775 778 781 784 787 790 793 796 799 802 805 808 811 814 817 820 823 826 829 832 835 838 841 844 847 850 853 856 859 862 865 868 871 874 877 880 883 886 889 892 895 898 901 904 907 910 913 916 919 922 925 928 931 934 937 940 943 946 949 952 955 958 961 964 967 970 973 976 979 982 985 988 991 994 997 1000 1003 1006 1009 1012 1015 1018 1021 1024 1027 1030 1033 1036 1039 1042 1045 1048 1051 1054 1057 1060 1063 1066 1069 1072 1075 1078 1081 1084 1087 1090 1093 1096 1099 1102 1105 1108 1111 1114 1117 1120 1123 1126 1129 1132 1135 1138 1141 1144 1147 1150 1153 1156 1159 1162 1165 1168 1171 1174 1177 1180 1183 1186 1189 1192 1195 1198
2393
Oczekiwane wyjście
398 399
Uruchom z własnymi danymi