D#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
using namespace std;
int a[1000005];
int b[1000005];
int main()
{
a[0]=(0);
b[0]=(0);
int n,x=0,y=0,i,j,MAX=0,tmp=0;
string s;
cin >> n;
for(i = 1; i <= n; i )
{
scanf("%s %d", &s, &tmp);
if( s == "Gore")
y = 1;
if( s == "Dole")
y -= 1;
if( s == "Levo")
x -= 1;
if( s == "Desno")
x = 1;
a[i]=x;
b[i]=y;
}
int time = 0;
for( i = 0; i <= n; i )
{
for( j = 0; j <= n; j )
{
if((a[i] == a[j]) && (b[i] == b[j]))
time ;
}
if(time > MAX)
MAX = time;
time = 0;
}
cout<<MAX<<endl;
return 0;
}
Treba mi efikasniji algoritam koji mi nazalost ne pada na pamet, ja sam isao i pamtio mjesata i onda isao redom i brojao koliko je na kojem bio. Javi mi u svakom primjeru Time limit exeded . Kako bi se moglo ubrzati, ili Na koji nacin treba razmisljati..
razmišljaš u dobrome smjeru, ali tle na svim primjerima ne znači stvarno tle, nego uglavnom to bude mle, memory limit exceeded, ako pogledaš na ograničenja zadatka vidiš da je memory limit 7MB, a ti imaš 2*10^6 intova, sto je vise od 7 MB, tocnije oko 7.5 :), dakle to je previše, i najbolje bi bilo da izbaciš jedan array tako da ti ostane 10^6 intova, sto bi prepolovilo zauzetu memoriju, ako trebas jos hintova reci, ali ovo bi trebaol biti dovoljno da rjesis zadatak
Hmm, uocio sam da nije zbog vremena nego zbog memorije. To sto ti kazes da sklonim jedan niz bi bilo dobro, ali neznam kako da poredim koordinate sa jednim nizom , jer u mom primjeru jedan za "x" i jedan za "y". Kako bi se to poredenje sprovelo za jedanim nzom??
Prilicno sam nov u programiranju, i neznam za hashing i to sto tome pripada. Nisam nista korisno mogao naci na webu o tome, pa ako ti nije tesko bio bi ti zahvalan da mi pojasnis ili dadnes koji link gdje ima objasnjeno o tome.
hashing je postupak kod kojeg nekom stringu, nizu brojeva, svejedno cemu, dajes neku "jedinstvenu" vrijednost, za to ti je potrebna hash funkcija, koja prima parametre i vraca neku prema parametrima definiranu vrijednost, tako recimo ti trebas 2 koordinate predstavit jednim brojem, tako da to bude jedinstveno, npr.
f( x, y ) = x * 1000003 y;
tu ćeš za svaki par tocaka dobiti drugu vrijednost zato jer y koordinata ne moze preci 1000000, samo je problem sto to moze preci vrijednost int-a, ali evo mogu ti reci da je kod meni prosao systest sa takvom funkcijom. mogao bi koristiti
f( x, y ) = x * 10000 y, to staje u int, ali moze se desiti da neke tocke sa razlictim koordinatama imaju iste vrijednosti, pa to nije 100 % točno, mozes koristiti i modanje da izbjegnes velike brojeve, ali to su već detalji koji ovise o tipu podataka koji se hashira i sličnim stvarima...
funkcije u gornjem postu su trebale biti
x * 1000003 plus y
x * 1000 plus y
nesto mi ne priznaje znak plus
Mozda sam malo naporan ali me ovaj zadatak stavrno nervira. Uradio sam tako ali mi samo prvi kaze da je ok a ostalo wrong. Neznam gdje sad gresim jer ipak provjeravao sam kod. Ako ti vidis gdje gresim reci mi pls.
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int a[1000100];
int main()
{
a[0]=0;
int n,x=0,y=0,i,j,MAX=0;
string s;
cin >> n;
for(i = 1; i <= n; i )
{
cin>>s;
if( s == "Gore")
y = 1;
if( s == "Dole")
y -= 1;
if( s == "Levo")
x -= 1;
if( s == "Desno")
x = 1;
a[i]=(x * 1000003) y;
}
int time = 1;
sort(&a[0],&a[n 1]);
for( i = 0; i <= n-1; i )
{
if(a[i] == a[i 1])
time ;
else if( a[i] != a[i 1] )
{
i ;
time = 1;
}
if(time > MAX)
MAX = time;
}
cout<<MAX<<endl;
return 0;
}
ne vidim dobro kod, jer mi ne prkiazuje dobro neke znakove, pa ga posalji na mail, ivan.katanic@gmail.com
hm, nisam nista nasao, probaj ponovo napisati sve, i kad gledas gdje si bio najvise puta, gledaj uvijek je li ti to mjesto isto kao i prethodno, a ne kako si ti radio gdje gledas sljedeće, iako i to treba raditi, ali ovako je manje kompliciranja
