revizory

viete niekto riesit tuto ulohu ?
https://palma.strom.sk/SVK2012/A2/

Pozrel(a) si sa uz na existujuce riesenia? Ak ano a nechapes ich, kludne sa spytaj comu konkretne, a skusim(e) s tym pomoct. Nejake rady myslim boli aj popri zadani poslednej ulohy z PAZ, mohlo by to tiez pomoct.

tak ako ked sa vyznas s tohto
public class source {

void solve() throws Exception {

int p = nextInt();
next: while (p-->0) {
int k = nextInt(), n = nextInt();
int[] v = new int[n];
for (int i=0; i<n; ++i) v[i] = nextInt();

out: for (int i=1; i<=200*100; ++i) {
int sec = 1;
int curr = 0;
for (int j=0; j<v.length; ++j) {
curr+=v[j];
if (curr>i) {
sec++;
if (sec>k) continue out;
curr=v[j];
if (curr>i) continue out;
}
}
if (sec<=k) {
System.out.println(i); continue next;
}
}
}

}
ta diky pekne ale s toho nevydumem o com to je a to este jedno s troch rieseni ostatne su v ccku a tomu uz vobec nebudem rozumiet, a keby to bola taka trivialna uloha predpokladam ze by nemala 3 uspesnych riesitelov zo vsetkych sutaziacich a ze by ju niekto na tu domacu zriesil. ked tomu rozumies, prosimta vysvetli mi to.

Popravde johnyho riesenie v Ccku je ovela zrozumitelnejsie ako tuto kolegove v Jave, takze netreba sa zlaknut ze to je iny jazyk
V tom kratkom kuse javackeho kodu som videl tolko pre mna novych veci. Z toho Cckoveho je zase pekne viditelny pristup riesenia.

viete niekto riesit tuto ulohu ?
https://palma.strom.sk/SVK2012/A2/

povodne som uvazoval nad lahkym trollingom typu "co vas na tej skole ucia", ale potom som sa rozhodol pre drastickejsi krok a to prepisat johnyho kod do javy, aby bol pre teba zrozumitelny (kod sa nachadza v spravnych rieseniach)
"Dufam, ze teraz ti to pomoze".. aj ked ja osobne som neprecital ani zadanie ulohy


PS: dufam, ze som nikomu nesposobil ujmu svojim plagiatorstvom..


pm.

Vďaka za snahu keby niekto zhrnul hlavnu myslienku veci, preco ten kod funguje a ako ?

Označme P maximálny počet ľudí, ktorých môže obslúžiť jeden sprievodca.

Ak by ti niekto povedal číslo P, vieš z toho zrátať, koľko sprievodcov potrebuješ? (V mojom kóde je to funkcia "pocet".)

Našou úlohou je teraz nájsť maximálne P také, aby pocet(P) <= K (zo vstupu). Ja som na to použil binárne vyhľadávanie, Maťo tuším trochu inú metódu.

(Treba si ešte uvedomiť, že to funguje vďaka tomu, že funkcia "pocet" je monotónna.)

dakujem za vysvetlenie, uz tomu rozumiem, a predsa co sa stane ak zisti ze mas mat menej ludi na revizora ako vagon ma ludi, kde si to osetril v tvojom kode? a preco si pouzil binarne vyhladavanie ? nestacilo to lienearne prebehnut?

co sa stane ak zisti ze mas mat menej ludi na revizora ako vagon ma ludi, kde si to osetril v tvojom kode?

Funkcia "pocet" pracuje s celými vozňami naraz, teda buď pridá revízorovi celý vozeň alebo mu nepridá nič a začne nového revízora.

a preco si pouzil binarne vyhladavanie ? nestacilo to lienearne prebehnut?

Asi by to nezbehlo v časovom limite. Interval, ktorý treba prejsť, je od 1 do celkového počtu cestujúcich (ak je len jeden revízor), teda v najhoršom prípade 200000, a čas na overenie jednej hodnoty je O(N). Teda celkovo v najhoršom prípade 100 testovacích sád * 200000 * 1000 = 20 miliárd operácií. Rozumný odhad je, že súčasné procesory spracujú za sekundu asi 100 miliónov operácií.

Ale ak tam nie je takýto maximálny vstup, tak možno by to aj zbehlo -- skús.

ok, dakujem