banjalukaforum.com

Dobrodošli na banjalukaforum.com
Danas je 21 Jul 2025, 16:42

Sva vremena su u UTC [ DST ]




Započni novu temu Odgovori na temu  [ 164 Posta ]  Idi na stranicu Prethodni  1 ... 3, 4, 5, 6, 7, 8, 9  Sledeća
Autoru Poruka
PostPoslato: 11 Maj 2008, 17:43 
OffLine
Majstor
Majstor
Korisnikov avatar

Pridružio se: 28 Mar 2006, 11:25
Postovi: 898
Nesto nije uredu unese 10000 kao ulaz i ne mogu docekati, bas da vidim sta si sad zbrzio :D

EDIT: Jako sporo za ulaz 20 probija vremensko ogranicenja. Pogledaj moje resenje, nije zavisno od ulaza uvijek radi isto vremena i zauzima nesto manje od 8mb memorije.

Koliko sam vidio u tvom resenju ima funkcija koje se i ne koriste (int prost(long A)). Nemogu gledati malo na duze sta si radio temperatura me opet "uhvatila" odoh malo u krevet

Pozz

_________________
U raju je lijepo, ali u paklu je raja.


Vrh
 Profil  
 
PostPoslato: 11 Maj 2008, 18:46 
OffLine
Pripravnik
Pripravnik
Korisnikov avatar

Pridružio se: 23 Dec 2006, 20:47
Postovi: 101
Lokacija: BN
Za ulaz 20 radi veoma kratko. Za 10000 vjerovatno predugo, ali ovo "odokativna" metoda nije mjerodavna.

Uostalom, radili smo potpuno iste stvari, s tim sto sam ja (konj) pokusavao dodavati sve cifre [0,9], a ti samo 4 neparne. Prepravio sam i to, ali opet mi nije jasno zasto radi tako dugo za N=10000.

I taj overflow! I ja sam na isti nacin akumulirao vrijednosti u matricu: saberem u zagradi pa modujem prije dodjele. Stvarno ne znam sta mu je...

I ti svaki put racunas za brojeve sa svim duzinama pa za ispis "pokupis" vrijednosti samo za N. A ja racunam samo do N, sto bi trebalo biti brze...

Smijesno, zaista... :lol:

Ima li iko ideju o uzroku ovoga?

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
:)
Nikad ne zavrsim potpis do kr


Vrh
 Profil  
 
PostPoslato: 11 Maj 2008, 20:58 
OffLine
Majstor
Majstor
Korisnikov avatar

Pridružio se: 28 Mar 2006, 11:25
Postovi: 898
Vidim nekoliko propusta. Lose poslozene petlje i koristenje vektora te podkopavaju. To trebas popraviti

_________________
U raju je lijepo, ali u paklu je raja.


Vrh
 Profil  
 
PostPoslato: 12 Maj 2008, 11:28 
OffLine
Urednik
Urednik

Pridružio se: 26 Jun 2003, 21:50
Postovi: 2669
Vratio nam se Timus :) Nije ga bilo preko vikenda :)


Vrh
 Profil  
 
PostPoslato: 12 Maj 2008, 16:40 
OffLine
Pripravnik
Pripravnik
Korisnikov avatar

Pridružio se: 23 Dec 2006, 20:47
Postovi: 101
Lokacija: BN
Zadatak je bio OK, samo je u poslednjoj liniji bila greska.
Ja sam samo akumulirao rjesenje u promjenjuvu bez % CONST. Previd...

Poslao sam na timus.ru (sa prepravljenom predposlednjom linijom) i proslo je bez problema, ne znam zasto je Nemanji sporo radilo za N=20... Sve u svemu, super zadatak.

Nemanja, predlozi jos neki.

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
:)
Nikad ne zavrsim potpis do kr


Vrh
 Profil  
 
PostPoslato: 12 Maj 2008, 17:20 
OffLine
Majstor
Majstor
Korisnikov avatar

Pridružio se: 28 Mar 2006, 11:25
Postovi: 898
Jedan predlog, koristi u ovakim slucajevima koristi nizove i matrice a ne vektore.

Ne znam sto ja radilo sporo do duse ja sam kompajlirao sa VC++ 2008 Express

_________________
U raju je lijepo, ali u paklu je raja.


Vrh
 Profil  
 
PostPoslato: 15 Maj 2008, 23:19 
OffLine
Majstor
Majstor
Korisnikov avatar

Pridružio se: 28 Mar 2006, 11:25
Postovi: 898
E ljudi sta ocukujete za sutra (vec je sutra).

Ja se nadam da cu biti u prvi sest, ali ce to sve zavisiti po najvise koliko cu se napiti vecer prije.

_________________
U raju je lijepo, ali u paklu je raja.


Vrh
 Profil  
 
PostPoslato: 18 Maj 2008, 01:13 
OffLine
Majstor
Majstor
Korisnikov avatar

Pridružio se: 28 Mar 2006, 11:25
Postovi: 898
Proslo je drzavno takmicenje. Ja i peric smo se plasirali na IOI. Ja sam bio 4. a Igor 3. Cestitam.

Inace da mi je znati koji konj je pravio ovakve zadatke :D :D :D :D

_________________
U raju je lijepo, ali u paklu je raja.


Vrh
 Profil  
 
PostPoslato: 18 Maj 2008, 01:28 
OffLine
Pripravnik
Pripravnik
Korisnikov avatar

Pridružio se: 23 Dec 2006, 20:47
Postovi: 101
Lokacija: BN
Hvala, takodje.

Što se tiče zadataka, nisu bili nešto posebno.

1. Grafovi:
Treba naći broj različitih puteva u usmerenom težinskom grafu od čvora A do do čvora B, pri čemu se mora proći redom kroz ivice kapaciteta zadatih nizom elemenata.

2. Formula
Unosi se M različitih binarnih nizova nad kojima se mogu vršiti XOR operacije u cilju dobijanja traženog stringa. Ne mora se dobiti traženi string, ali se traži što bliži (onaj koji se razlikuje u što manjem broju znakova). Potrebno je ispisati broj istih bitova (daljinu najboljeg od traženog) i broj ulaznih stringova čijim se kombinovanjem dobila ta "daljina"...

3. Kiša
U bobu sa z-treninga, bio na YUOI. Zadatak se zove "jezero" ili tako nešto. Dat je neki niz stubova različite visine i treba izračunati koliko bi se vode zadržalo u takvoj konfiguraciji stubova kada bi poćela da pada kiša.

Na 2. zadatku imao sam sve bodove, na 1. sam radio DFS ali bez ikakve optimizacije pa je vjerovatno okinulo na vremenu. Tu sam imao 40 bodova. I ovaj treći... Ubjedljivo najlakši zadatak, uradio ga 5 puta, na z-treningu svi primjeri prošli daaaavno... U prevodu, ideju sam imao u malom prstu. Ne znam ni kako ni zašto, ali tu sam uzeo samo 30 bodova.

Da sam uradio ovaj treći kao na z-treningu, bio bih prvi sa 240 bodova a ovako imam samo 170.

Zadovoljan sam, sve u svemu. Sada se valja spremati za IOI 2008... Mmmmm... Egipat... 8)

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
:)
Nikad ne zavrsim potpis do kr


Vrh
 Profil  
 
PostPoslato: 18 Maj 2008, 01:32 
OffLine
Pripravnik
Pripravnik
Korisnikov avatar

Pridružio se: 23 Dec 2006, 20:47
Postovi: 101
Lokacija: BN
Posto mi samo jedan zadatak (formule) radi kako treba, ja ću ostaviti to rješenje, ako nekoga interesuje. Uskoro će, valjda, i na http://www.bhoi.net tekstovi zadataka sa rješenjima i zvaničnim test primjerima.

Kod:
#include <vector>
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("formula.in");
ofstream fout("formula.out");
unsigned long i,j,n,m;
vector<string> ins;
vector<unsigned long> in,dp,state,last;
string str;
unsigned long obj;

unsigned long F(unsigned long A,unsigned long B) {
     unsigned long ret(0),i;
     for (i=0;i<n;i++) {
           ret = ret + ((A&1) == (B&1));
           A = ( A >> 1 ); B = ( B >> 1 );
           }
     return ret;
     }
bool par(unsigned long A, unsigned long B) {
     return F(A,obj) > F(B,obj);
     }

int main() {
    fin >> m >> n;
    in.resize(m); dp.resize(m); state.resize(m); last.resize(m);
    fill(in.begin(),in.end(),0);
    fill(dp.begin(),dp.end(),0);
    fill(last.begin(),last.end(),0);
    fin >> str;
    for (i=0;i<n;i++) if (str[i]-'0') obj = obj | (1<<(n-i-1));
    for (i=0;i<m;i++) {
        fin >> str;
        for (j=0;j<n;j++)
            if (str[j]-'0') in[i] = in[i] | (1<<n-j-1);
        }
   
    sort(in.begin(),in.end(),par);
   
    dp[0] = F(in[0],obj);
    state[0] = in[0];
    last[0] = 1;
    for (i=1;i<m;i++) {
        last[i] = 1;
        state[i] = in[i];
        dp[i] = F(in[i],obj);
        for (j=0;j<i;j++)
            if (F( (state[j]^in[i]), obj) > dp[i]) {
                   state[i] = state[j]^in[i];
                   dp[i] = F( (state[j]^in[i]), obj);
                   last[i] = last[j] + 1;
                   }
        }
    unsigned long SI(0);
    for (i=1;i<m;i++) {
        if (dp[i] == dp[SI] && last[i] < last[SI]) SI = i;
        if (dp[i] > dp[SI]) SI = i;
        }
    fout << last[SI] << " " << dp[SI] << endl;
    //system("pause");
    return 0;
}


_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
:)
Nikad ne zavrsim potpis do kr


Vrh
 Profil  
 
PostPoslato: 18 Maj 2008, 02:52 
OffLine
Urednik
Urednik

Pridružio se: 26 Jun 2003, 21:50
Postovi: 2669
Nadam se da je bilo zanimljivo :)

Ti Nemanja pazi sta pises, znas ti dobro koji je konj pisao zadatke! ONAJ STO TI JE STARU TRSIO :D :D :D


Vrh
 Profil  
 
PostPoslato: 18 Maj 2008, 16:25 
OffLine
Urednik
Urednik

Pridružio se: 26 Jun 2003, 21:50
Postovi: 2669
Sto si koristio longove kad je N ograniceno na 16? Mogao si i short da stavis ;) Da smo dobro udesili time limit - pao bi ti zadatak zbog toga na barem 30% slucajeva, ovako, izvukao si se :)


Vrh
 Profil  
 
PostPoslato: 18 Maj 2008, 19:33 
OffLine
Pripravnik
Pripravnik
Korisnikov avatar

Pridružio se: 23 Dec 2006, 20:47
Postovi: 101
Lokacija: BN
Najteži (drugi) test primjer radio je 0.48 sekundi. Ne vjerujem da bi ograničenje bilo manje od 0.5 s... Zar ne?

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
:)
Nikad ne zavrsim potpis do kr


Vrh
 Profil  
 
PostPoslato: 18 Maj 2008, 21:26 
OffLine
Urednik
Urednik

Pridružio se: 26 Jun 2003, 21:50
Postovi: 2669
Pa to ti i ja kazem shabane! Ali da smo ga malo "ufercili", recimo, da je N moglo da bude 18...


Vrh
 Profil  
 
PostPoslato: 18 Maj 2008, 21:37 
OffLine
Pripravnik
Pripravnik
Korisnikov avatar

Pridružio se: 23 Dec 2006, 20:47
Postovi: 101
Lokacija: BN
A to u redu. Koje je onda pametnije rjesenje za ovaj zadatak?

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
:)
Nikad ne zavrsim potpis do kr


Vrh
 Profil  
 
PostPoslato: 18 Maj 2008, 21:48 
OffLine
Urednik
Urednik

Pridružio se: 26 Jun 2003, 21:50
Postovi: 2669
Uglavnom nije bilo neophodno da koristis long. A rijesenje ti je isto kao i moje, valjda ce Alvin okaciti materijale u skorije vrijeme. Nismo pretjerano mucili sa optimizacijom i mjerenjem vremena. Inace, da je N bilo 18 onda bi morao da koristis int sto je == long :) Jbg :D

Cestitam jos jednom, btw ako se tvojoj profanki ne ide u Egipat, zovite mene :) Have fun kako god :)))


Vrh
 Profil  
 
PostPoslato: 20 Maj 2008, 18:06 
OffLine
Majstor
Majstor
Korisnikov avatar

Pridružio se: 28 Mar 2006, 11:25
Postovi: 898
Evo ja sam malo bolje sad pa da napisem koju rec.

Prvo che ja se malo zezam(dobro mozda malo vise), a ti meni spominjes majku stvarno ruzno od tebe, al da ne idem u offtopic.

Sto se tice dana takmicenja sam je poceo katostrofalno. Ustao sam mamuran i bolestan. Do Sarajeva smo stajali dvadesetak puta zbog Ivanovica koome je citavo putovanje bila muka. Zatim krenuli ulicom koja je bila zatvorena pa nazad u guzvu, ali smo stigli na vrijeme.

I stizemo napokon na takmicenje, ja se napokon poceo dobro osjecati, uzeo da pojedem onu picu kad se ona oladila :angry4: . Poceli se zadatci raditi uocim odmah da je kisa stvarno lagan i pocnem ga raditi. A moje resenje stalno ispisuje nulu i gotovo. Izgubim tu 10-20 min dok ne vidim da mi resenja otprilike ovako: Ucitam podatke, ispisem rezultat, pa tek onda izracum ono sta treba biti rezultat. E tad sam poceo zaliti sto sam popio sinoc onoliko vina :) . Kad sam napokon uradio taj zadatak bacio sam se na zadatak formula. Pokusam, pa pokusam, pa pokusam, pa pokusam, pa pokusam, a ono nece, nece, nece i nece. Razmislim malo i pomislim ako sam uradio jedan 100% dovoljna ce biti ova dva da budu brutal force za dalje i bacim se ja na posao pisanja bf resenja. E tad me poce hvatati san. U svakom slucaju za formulu sam izgubio vise od 150 minuta. I napokon mi judge prihvati i ja pogledam na sat kad ono jos 47min. Pocnem citati obilazak kad ono kod ulaza M,N, K, L, A, B i jos svaceg, pa nikako popamtiti za sto je koje :) . I Uradim ga ja i nece. Tek onda vidim da se moraju svi novcici potrositi. Uradim ja ponovo a ono nece opet. I onda skontam da se novcici ne mogu "bacati" nego se moraju regularno potrositi. Uradim i to i judge mi prihvati resnje znam da je pisao 7 min 43 sec kad sam video da je prihvatio odmah izadjem. Kazem profi da ocekujem 4-5 mjesto. U sustini tako je bilo. Ja vec u svakom pogledu raspolozen da idem kuci (ne mogu vise stajati na nogama), kad ono pocese zalbe pa cekaj, pa onda dodjele diploma pa opet cekaj :( . I napokon smo krenuli kuci. E usput nam je palo na pamet da ja i jos dva profesora pjevamo dok Ivanovic spava. E to je trebalo vidjeti, od nas trojice se ne zna koje veci anti talent za pjevanje. Kuci sam stigao oko pola 2 navece umoran, sje*** do kraja, ali ne mogu zaspati temperatura i kasalj mi nedadese. :(. Tako da sam morao oko 3 otici u hitnu. I napokon kad sam iz hitne dosao kuci uspijem zaspati koji sat. I evo sad napokon sam koliko toliko dobar.

Sto se tice rezultata ja sam sasvim zadovoljan. Imam sad skora dva mjeseca vremena da ne moram nista raditi :) .

PS. Oni koji imate zadatke sa BHOI nek pogledaju zadatak obilazak, pa kako pise da treba ici datoteka za izlaz :) naravno ne moram reci da na takmicenju nisam skontao da je greska u kucanju pa sam pokusavao zadatak poslati sa takvim izlazom.

E sad posto sam se ja umorio kucajuci odoh malo slusati muziki da se odmorim.

Posto nisam citao sta sam napisao sigurno ima 1000+ gresaka u kucanju :)

_________________
U raju je lijepo, ali u paklu je raja.


Vrh
 Profil  
 
PostPoslato: 20 Maj 2008, 19:59 
OffLine
Urednik
Urednik

Pridružio se: 26 Jun 2003, 21:50
Postovi: 2669
Thrilling! :) Ziv ti nama bio i lijepo se ponasaj tamo u Egiptu :)


Vrh
 Profil  
 
PostPoslato: 21 Maj 2008, 06:10 
OffLine
Pripravnik
Pripravnik
Korisnikov avatar

Pridružio se: 23 Dec 2006, 20:47
Postovi: 101
Lokacija: BN
Uh, jbte, ti se pravo nap(at)io... :-? Pa zbog čega su taj kašalj i temperatura? Obična prehlada ili nešto ozbiljnije?

Aj' sve u svemu završilo se dobro. Čekaj, ti ne misliš vježbati dva mjeseca, koliko sam shvatio? Vježbaćeš mjesec pred olimpijadu?

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
:)
Nikad ne zavrsim potpis do kr


Vrh
 Profil  
 
PostPoslato: 21 Maj 2008, 11:12 
OffLine
Majstor
Majstor
Korisnikov avatar

Pridružio se: 28 Mar 2006, 11:25
Postovi: 898
Bio sam bolestan citavu sedmicu, samo nisam htjeo ici doktoru, jer je kod mene pravilo kad odem doktoru ostanem u bolnici :)

Sto se tice spremanja ne mislim se tako puno spremati, bar ne ispocetka, zadnji mjesec pred takmicenje ce biti bas, a do tad mozda samo ponesto prelistati

_________________
U raju je lijepo, ali u paklu je raja.


Vrh
 Profil  
 
Prikaži postove u poslednjih:  Poređaj po  
Započni novu temu Odgovori na temu  [ 164 Posta ]  Idi na stranicu Prethodni  1 ... 3, 4, 5, 6, 7, 8, 9  Sledeća

Sva vremena su u UTC [ DST ]


Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 2 gostiju


Ne možete postavljati nove teme u ovom forumu
Ne možete odgovarati na teme u ovom forumu
Ne možete monjati vaše postove u ovom forumu
Ne možete brisati vaše postove u ovom forumu
Ne možete slati prikačene fajlove u ovom forumu

Pronađi:
Idi na:  
Powered by phpBB® Forum Software © phpBB Group
Hosting BitLab
Prevod - www.CyberCom.rs