Zadanie

Marcel má veľký sen. Jedného dňa by chcel byť skutočným vedcom v Slovenskej akadémii vied, tak ako jeho kamaráti Samko a Emko. Laboratórium vákuovej fyziky mu však zatiaľ dáva robiť iba podradné práce. Varí kolegom kávu, chodí po balíčky na poštu, seká uhorky, prípadne plní iné ich želania.

Jedného dňa ho Emko so Samkom poslali na nákup do Teska. Marcel si okrem nákupu kúpil aj dve veľké tašky, do ktorých chcel vkladať tovar. Kým predavač blokoval jeho nákup, Marcel rozmýšlal, ako tovar rozdeliť medzi tašky, aby ich hmotnosti boli čo najviac vyrovnané. Kedže v rade za ním je veľa ľudí, Marcel nechce zdržovať a ukladá tovar to tašiek jeden po druhom.

Po krátkom výpočte Marcel zistil, kedy má začať nákup ukladať do druhej tašky. Keď doniesol nákup svojim kolegom, spýtal sa ich, či aj oni vedia takúto úlohu vyriešiť. Pomôžte Samkovi a Emkovi vyriešiť tento problém.

Úloha

Marcel má dve tašky neobmedzenej veľkosti, do ktorých balí tovar v poradí, v akom mu ho predavač podáva. Postupuje pri tom tak, že niekoľko prvých predmetov vloží do prvej tašky a zvyšné predmety dá do druhej. Vašou úlohou je zistiť, koľko predmetov má dať do prvej tašky, aby bol rozdiel hmotností tašiek čo najmenší. Ak existuje viacero optimálnych riešení, potom vypíšte väčšie číslo (snažte sa teda dávať predmety do prvej tašky).

Formát vstupu

Na prvom riadku vstupu bude jedno kladné celé číslo \(n\) – počet predmetov v Marcelovom nákupe. Druhý riadok obsahuje postupnosť \(n\) kladných celých čísel oddelených medzerami – hmotnosti predmetov v poradí, v akom ich predavač podáva Marcelovi.

Pre jednotlivé testovacie sady platia nasledujúce obmedzenia:

číslo sady \(1\) \(2\) \(3\) \(4\)
\(n \leq\) \(1\,000\) \(5\,000\) \(100\,000\) \(100\,000\)
maximálna hmotnosť predmetu \(\leq\) \(1\,000\) \(5\,000\) \(10\,000\) \(10\,000\)

Formát výstupu

Na výstup vypíšte jeden riadok obashujúci jedno číslo – počet predmetov, ktoré má Marcel dať do prvej tašky.

Príklad

Input:

5
7 3 2 8 1

Output:

2

V prvej taške bude \(7+3=10\) a v druhej \(2+8+1=11\).

Input:

6
2 4 7 1 2 3

Output:

3

Nezáleží na tom, či dáme do prvej tašky prvé dva, alebo prvé tri predmety, rozdiel hmotností tašiek bude rovnaký. V prípade rovnosti máme však pridať predmet do prvej tašky, preto je odpoveď \(3\).

Našou úlohou bolo pomôcť Samkovi a Emkovi zistiť, koľko predmetov treba vložiť do prvej tašky. Ukážeme si najprv pomalšie riešenie, ktoré potom vylepšíme. Zadanie hovorí, že Marcel do určitého momentu dáva predmety iba do prvej tašky a od tohto momentu ich dáva iba do druhej. Prvý predmet, ktorý Marcel vloží do druhej tašky, budeme v ďalšej časti vzoráku nazývať zmrzlina.

Pomalšie riešenie

Vyskúšame všetky možnosti pre zmrzlinu. Pre každú možnosť vypočítame súčet hmotností predmetov, ktoré sú nablokované pred zmrzlinou a súčet hmotností zvyšných predmetov. Čím menší je rozdiel týchto čísel, tým lepšie sú tašky vyvážené. Kedže všetkých predmetov (možností pre zmrzlinu) je \(n\) a pri každej možnosti musíme sčítať \(n\) hmotností, výsledná časová zložitosť bude \(O(n^2)\), pamäťová je \(O(n)\).

n = int(input())
predmety = list(map(int, input().split())) # nacitame predmety do pola a skonvertujeme na int-y
best_index = 0 # (zatial) najlepsia volba zmrzliny
najlepsie_vyvazenie = sum(predmety) # ako velmi su tasky vyvazene pri (zatial) najlepsej volbe

for i in range(n + 1): # n + 1, lebo chceme overit pripad kedy su vsetky predmety v prvej taske
    prva, druha = sum(predmety[:i]), sum(predmety[i:]) # scitame hmotnosti predmetov v prvej a druhej taske
    vyvazenie = abs(prva - druha) # a spravime ich rozdiel
    if not vyvazenie > najlepsie_vyvazenie: # overime, ci sme nenasli lepsie vyvazenie
        najlepsie_vyvazenie = vyvazenie
        best_index = i

print(best_index)

Vzorové riešenie

Čo robíme navyše? Stačí si všimnúť dve veci:

  1. Najlepší výsledok dostaneme, ak bude hmotnosť prvej tašky najbližšie k polovici z celkovej hmotnosti všetkých predmetov.

  2. Nemusíme pre každú možnú pozíciu zmrzliny počítať hmotnosť prvej tašky samostatne. Rozdiel medzi taškou, ktorá obsahuje prvých \(x\) prvkov a taškou, ktorá obsahuje prvých \(x+1\) prvkov je len jeden predmet. Tiež si všimnime, že ak vieme hmotnosti oboch tašiek (nazvime tieto hmotnosti \(A\) a \(B\)) a hmotnosť predmetu \(p\), ktorý ideme dať z druhej do prvej tašky, tak hmotnosti týchto tašiek sa zmenia nasledovne: prvej taške stúpne hmotnosť na \(A + p\) a druhej klesne na \(B - p\).

Čo teda spravíme? Najprv si spočítame súčet hmotností všetkých predmetov. Na začiatku si predstavujeme, že všetky predmety sú v druhej taške. Potom postupne prechádzame cez všetky predmety zľava doprava a zisťujeme, či sa nám oplatí dať predmet z druhej tašky do prvej. Kým sa to oplatí, dávame predmety do prvej tašky až nastane situácia, že pridaním ďalšieho predmetu sa už nič nezlepší. Vtedy môžeme skončiť, lebo pridávaním ďalších predmetov do prvej tašky sa situácia vždy len zhorší. Výsledná časová zložitosť bude \(O(n)\), pamäťová ostáva \(O(n)\).

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, hmotnost_celkovo = 0; // pocet predmetov, celkovy sucet hmotnosti predmetov
  cin >> n; 
  vector<int> predmety(n);
  for (int i = 0; i < n; ++i) {
    cin >> predmety[i];
    hmotnost_celkovo += predmety[i];
  }

  int prva_taska = 0, i;
  for (i = 0; i < n; ++i) {
    // ekvivalentne napisane ako: prva_taska - (hmotnost_celkovo - prva_taska)
    int stare_vyvazenie = prva_taska * 2 - hmotnost_celkovo; 
    // podobna uvaha akurat pridame predmet do prvej tasky
    int nove_vyvazanie = (prva_taska + predmety[i]) * 2 - hmotnost_celkovo; 
    // ak sme pridanim predmetu do tasky nic nezlepsili, vypisme odpoved
    if (abs(nove_vyvazanie) > abs(stare_vyvazenie)) { 
      cout << i << endl;
      break;
    }
    prva_taska += predmety[i]; // pridajme predmet do prvej tasky
  }

  if (i == n) { // nezabudnut na pripad, ked su vsetky predmety v prvej taske
    cout << n << endl;
  }

  return 0;
}

Iný typ vzorového riešenia

Ukážeme si ešte jedno riešenie, založené na prefixových sumách.
Všimnime si, že v našom pomalšom riešení zbytočne sčitujeme hmotnosti predmetov pre každú voľbu zmrzliny. To, čo nás zaujíma, je súčet prvých \(x\) predmetov (pre \(x \leq n\)) a súčet hmotností zvyšných predmetov. Tieto súčty vieme získať v konštantnom čase použítím práve spomínaných prefixových súm. Výsledná časová zložitosť bude \(O(n)\), pamäťová ostáva \(O(n)\) rovnako ako v prvom vzorovom riešení.

n = int(input())
predmety = list(map(int, input().split())) # nacitame predmety do pola a skonvertujeme na int-y
best_index = 0 # (zatial) najlepsia volba zmrzliny
najlepsie_vyvazenie = sum(predmety) # ako velmi su tasky vyvazene pri (zatial) najlepsej volbe
prefixove_sumy = [0] # oplati sa nam spravit zarazka, lebo sucet prvych 0 predmetov je 0
for i in range(n): prefixove_sumy.append(predmety[i] + prefixove_sumy[i]) # spocitame prefixove sucty

def sucet(od, po):
    return prefixove_sumy[po] - prefixove_sumy[od] # kedze mame zarazku, tak pocitanie je jednoduche

for i in range(n + 1): # n + 1, lebo chceme overit pripad kedy su vsetky predmety v prvej taske
    prva, druha = sucet(0, i), sucet(i, n) # spravime sucet danych usekov v konstantnom case
    vyvazenie = abs(prva - druha) # potom spravime ich rozdiel
    if not vyvazenie > najlepsie_vyvazenie: # overime, ci sme nenasli lepsie vyvazenie
        najlepsie_vyvazenie = vyvazenie
        best_index = i

print(best_index) # vypiseme odpoved

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.