Stránka 1 z 1

revizory

PoslaťNapísal: Uto Jún 12, 2012 8:40 pm
od dzusik12
viete niekto riesit tuto ulohu ?
https://palma.strom.sk/SVK2012/A2/

Re: revizory

PoslaťNapísal: Uto Jún 12, 2012 10:21 pm
od Aries
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.

Re: revizory

PoslaťNapísal: Uto Jún 12, 2012 10:46 pm
od dzusik12
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.

Re: revizory

PoslaťNapísal: Uto Jún 12, 2012 11:23 pm
od Miro
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.

Re: revizory

PoslaťNapísal: Str Jún 13, 2012 1:14 am
od PainMaster
dzusik12 píše: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 :P (kod sa nachadza v spravnych rieseniach)
"Dufam, ze teraz ti to pomoze".. aj ked ja osobne som neprecital ani zadanie ulohy :P


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


pm. :twisted:

Re: revizory

PoslaťNapísal: Str Jún 13, 2012 7:32 am
od dzusik12
Vďaka za snahu :!: keby niekto zhrnul hlavnu myslienku veci, preco ten kod funguje a ako ? :roll:

Re: revizory

PoslaťNapísal: Str Jún 13, 2012 9:02 am
od johny
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.)

Re: revizory

PoslaťNapísal: Pia Jún 15, 2012 10:23 pm
od dzusik12
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?

Re: revizory

PoslaťNapísal: Sob Jún 16, 2012 9:07 am
od johny
dzusik12 píše: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.

dzusik12 píše: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.

Re: revizory

PoslaťNapísal: Sob Jún 16, 2012 6:30 pm
od dzusik12
ok, dakujem
:mrgreen: