Programozó versenyekDEIK Regionális Programozó Csapatverseny, egyetemi/főiskolai kategória, 2016. december 4.
2016. december 4. 10:10 –
2016. december 4. 15:10
|
Szabad súlyok
Egy jól szervezett súlytartó állvány.
Bath városa egy jegyzett olimpiai edzőhely, amely helyi, országos, de még nemzetközi csapatokat is vonz. Azonban még a legfinomabb tornaterem is áldozatául esik a legfőbb bűnnek: a rossz helyre visszarakott súlyzóknak.
Mindegyik súlyzópár teljes összevisszaságban hever a két állványon, néhányuk esetleg még meg is van osztva a két állványsor között. Kezdetben mindkét soron ugyanannyi súlyzó van, de mivel ez egy jól finanszírozott profi edzőterem, végtelen hely van mindkét sor mindkét végén további súlyzók tárolására.
Egy súlyzó mozgatását vagy ugyanazon soron egy szomszédos szabad helyre való görgetéssel oldhatjuk meg minimális erőfeszítéssel, vagy pedig felemelhetjük és áttehetjük bármelyik szabad helyre; ez utóbbi művelet a súllyal arányos erőt igényel. Minden súlyzópár két tagja ugyanolyan súlyú, és nincs két azonos súlyú súlyzópár.
Melyik az a legnehezebb súlyzó, amelyet fel kell tudnunk emelni ahhoz, hogy az egyforma súlyzókat egymás mellé helyezhessük? Vegyük észre, hogy az átrendezés után a két állványsoron eltérő számú súlyzó is lehet; ez teljesen rendben van.
A bemenet specifikációja
A bemenet a következő adatokat tartalmazza:
- egy sort, amelyben egy n egész szám, a súlyzópárok száma szerepel (1 ≤ n ≤ 106);
- két sort, amelyek mindegyikében n egész szám szerepel (w1, …, wn), ahol wi az adott sorban balról az i-edik súlyzó súlyát adja meg (1 ≤ wi ≤ 109 minden i-re).
A bemeneten minden súly pontosan kétszer fordul elő.
A kimenet specifikációja
A kimenetre a legnehezebb olyan súlyzó súlyát kell kiírni, amelyet fel kell emelnünk ahhoz, hogy minden súlyzót össze tudjunk párosítani úgy, hogy a lehető legkisebb maximális súlyt emeljük.
1. példa bemenet
52 1 8 2 89 9 4 1 4
Az 1. példa bemenethez tartozó kimenet
2
2. példa bemenet
87 7 15 15 2 2 4 45 5 3 3 9 9 1 1
A 2. példa bemenethez tartozó kimenet
0