revizory

Moderátor: FeroG

<<

dzusik12

Príspevky: 55

Registrovaný: Str Sep 21, 2011 12:13 pm

Poslať Uto Jún 12, 2012 8:40 pm

revizory

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

Aries

Príspevky: 379

Registrovaný: Pia Jan 30, 2009 1:26 pm

Bydlisko: 127.0.0.1

Poslať Uto Jún 12, 2012 10:21 pm

Re: revizory

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.
Vasnivy pestovatel binarnych stromov a opravar Turingovych strojov na polovicny uvazok.
"Problem citatov najdenych na internete je taky, ze si nikdy nemozete byt isti ich autenticitou" Abraham Lincoln
<<

dzusik12

Príspevky: 55

Registrovaný: Str Sep 21, 2011 12:13 pm

Poslať Uto Jún 12, 2012 10:46 pm

Re: revizory

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.
<<

Miro

Príspevky: 20

Registrovaný: Sob Okt 23, 2010 10:48 am

Poslať Uto Jún 12, 2012 11:23 pm

Re: revizory

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.
<<

PainMaster

Príspevky: 689

Registrovaný: Uto Okt 06, 2009 12:50 pm

Bydlisko: 3.Kanal,4.Chodba

Poslať Str Jún 13, 2012 1:14 am

Re: revizory

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:
We weren't born to follow
You gotta stand up for what you believe!

Ps: Za gramatiku ma neopravovat! Dakujem!
<<

dzusik12

Príspevky: 55

Registrovaný: Str Sep 21, 2011 12:13 pm

Poslať Str Jún 13, 2012 7:32 am

Re: revizory

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

johny

Príspevky: 132

Registrovaný: Pia Feb 22, 2008 6:37 pm

Bydlisko: Košice

Poslať Str Jún 13, 2012 9:02 am

Re: revizory

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.)
E-mail/Jabber: jan[zavináč]jergus.eu
<<

dzusik12

Príspevky: 55

Registrovaný: Str Sep 21, 2011 12:13 pm

Poslať Pia Jún 15, 2012 10:23 pm

Re: revizory

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?
<<

johny

Príspevky: 132

Registrovaný: Pia Feb 22, 2008 6:37 pm

Bydlisko: Košice

Poslať Sob Jún 16, 2012 9:07 am

Re: revizory

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.
E-mail/Jabber: jan[zavináč]jergus.eu
<<

dzusik12

Príspevky: 55

Registrovaný: Str Sep 21, 2011 12:13 pm

Poslať Sob Jún 16, 2012 6:30 pm

Re: revizory

ok, dakujem
:mrgreen:

Späť na PAZ1b

Kto je on-line

Užívatelia prezerajúci fórum: Žiadny registrovaný užívateľ nie je prítomný a 1 hosť

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software.
Slovenský preklad.