Koniec kola: 17. máj 2021 23:59
1 deň
Počet bodov:
Popis:  12b
Program:  8b

Krtko a Hodobox - posledné piliere KSP - pracujú na novom ksp. Každý má list svojich úloh, ktoré má pripraviť, aby mohla ďalšia séria prebehnúť. Avšak, internet je beznádejne zaťažený Netflixami, online vyučovaním, Zoom callmi s mačiatkami… čo značne sťažuje komunikáciu. Čo sťažuje – internet im beznádejne padol, a nevyzerá, že by chcel znovu nabehnúť. Nuž - čo už, séria aj tak musí byť, offline či online.

Na poslednom stretku pred padnutím internetu si Krtko a Hodobox rozdelili úlohy. Avšak, po pokuse začať pracovať zistili, že rozdelenie úloh je nerovnomerné. Za veľmi obmedzenej komunikácie1 si dokázali sprostredkovať, že by si mali nejakú úlohu vymeniť.

Problém je, že internet nefunguje, tak si musia poslať úlohu poštou. Listy sú ale drahé, takže si môžu vymeniť presne dve úlohy2 (Hodobox pošle jednu svoju úlohu Krtkovi a neopak).

Pre každú úlohu vedia koľko práce na ňu bude treba. Ktoré dve úlohy by si mali vymeniť?

Úloha

Každý z nich má spraviť \(N\) úloh (\(N \leq 10^5\)). Hodoboxova \(m\)-ta úloha zaberie \(h_m\) minút času. Krtkova \(m\)-tá úloha zaberie zase \(k_m\) minút času.

Ktorú úlohu by si mali vymeniť, aby strávili čo najvyrovnanejší čas prácou na úlohách?

Formát vstupu

Na prvom riadku je číslo \(N\).

Na ďalšom riadku je \(N\) čísel \(h_1\), …, \(h_N\).

Na poslednom riadku je \(N\) čísel \(k_1\), …, \(k_N\).

Všetky časy sú od \(1\) do \(10^9\) vrátane.

Formát výstupu

Ak by nemali vymeniť žiadnu úlohu, vypíšte \(-1\).

Inak vypíšte dva čísla \(1 \leq i, j \leq N\) - naznačujúce, že Krtko má pripraviť Hodoboxovu úlohu číslo \(i\), a Hodobox Krtkovu úlohu číslo \(j\).

Ak existuje viac optimálnych riešení, vypíšte také, že \(i\) je najmenšie možné. Ak je viac riešení s rovnakým \(i\) vypíšte také, že \(j\) je najmenšie možné. V prípade že jedno z optimálnych riešení zahŕňa nemenenie úlohy, vypíšte to.

Obmedzenia

Úloha má osem sád.

V prvých štyroch platí, že \(N \leq 1000\).

Vo zvyšných \(N \leq 10^5\)

Navyše, v sade \(1\), \(2\), \(5\) a \(6\) sú časy Krtkových a Hodoboxových úloh usporiadané od najmenej časovo náročnej, po najviac.

Príklad

Input:

5
1 4 2 5 3
7 10 5 8 9

Output:

1 2

Pôvodné rozdelenie úloh dáva oveľa viac (o \(24\) minút) práce Krtkovi ako Hodoboxovi. Najlepšie je, aby si Hodobox zobral Krtkovu najťažšiu úlohu, a Krtko Hodoboxovu najľahšiu. Následne bude Krtko mať len o \(6\) minút viac práce než Hodobox

Input:

6
2 4 10 17 99 123
1 7 17 17 101 112 

Output:

-1

Pôvodné rozdelenie úloh je už vyrovnané. Netreba meniť.

Input:

4
2 7 2 7
3 4 4 3

Output:

2 2

Najlepšie je vymeniť Hodoboxovu úlohu zaberajúcu \(7\) minút času za Krtkovu úlohu zaberajúcu \(4\) minúty času. Existuje tu viacero riešení, ale to s najmenšími indexami je vymeniť si úlohy na druhej pozícii.


  1. poštové holuby↩︎

  2. ani jeden z nich si nepamätá zadania úloh toho druhého↩︎

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.