nImam problema s ovim zadatkom.
1. Dali u ulazu imam velika i mala slova jer tako napravim maleni overhead sa tolower().
Moja solucija:
Ulazne rijeci tretiram kao unikatne skupove slova, po kojima napravim hash tabelu (ht) za odredjeno slovo.
pr.
1 - maja -> maj
2 - taric -> taric
3 - katarina -> katrin
ht['a'] = { 1, 2, 3 };
ht['k'] = { 3 };
ht['t'] = { 2, 3 };
I onda rekurzivno prolazim kroz slova zadate rijeci za provjeru i provjeravam sve moguce solucije.
Ovo je sporo. Svaka pomoc bi bila dobrodosla.
Hvala.
Imas samo mala slova, ali u zadatku pise da nije bitna velicina.
Zadatak moze da se uradi grafovski. Ne znam koliko si upoznat sa grafovskom teorijom!?
razmislit cu malo, pa ako nista bolje ne smislim evo me nazad
poz
Ne znam stvarno, pomagaj.
Ja jesam uradio DFS, ali nije dovoljno brz.
Evo koda.
int c[1000+1] = {0}; // dali je rijec 'i' vec upotrebljena
vector<int> h[256]; // govori za svako slovo 'i' gdje ga ima za naci u rijeci na c[]
char str[100+1]; // privremeni string za trenutnu rijec
bool rek_on_str( int x )
{
char chr = tolower( str[x] ); // slovo koje se trazi
for( int i = 0; i < h[chr].size(); ++i )
{
if( !c[ h[chr][i] ] ) // dali je rijec 'i' slobodna
{
if( str[x+1] == '\0' ) // dali se radi o zadnjem slovu
return true;
else
{
c[ h[chr][i] ] = 1;
bool ret = rek_on_str( x + 1 );
c[ h[chr][i] ] = 0;
if( ret )
return true;
};
};
};
return false; // ako ne postoji ni jeno rijesenje
};
int main( void )
{
int n;
scanf( "%d", &n );
for( int i = 0; i < n; ++i )
{
set<unsigned char> m; // rijec sa unikatnim slovima
char tstr[16];
scanf( "%s", tstr );
for( int j = 0; tstr[j] != '\0'; ++j )
m.insert( (unsigned char)tolower( tstr[j] ) );
for( typeof( m.begin() ) it = m.begin(); it != m.end(); ++it )
h[*it].push_back( i );
};
int k;
scanf( "%d", &k );
list<string> sol; // rijesenje
for( int i = 0; i < k; ++i )
{
scanf( "%s", str );
if( rek_on_str( 0 ) )
sol.push_back( string( str ) );
};
sol.sort( less<string>() );
printf( "%d\n", sol.size() );
for( typeof( sol.begin() ) it = sol.begin(); it != sol.end(); ++it )
printf( "%s\n", (*it).c_str() );
//system( "pause" );
return 0;
}
Nisam se udubljivao u kod, iako nisam gledao ovaj na forumu - mogu da vidim tvoj koji si postovao i nemoj slati kod ovako. Jedna je stvar sto neko ko nije uradio ne treba da gleda u tvoj kod (iako nije u potpunosti tacan) vec da razmislja o ideji, a druga sto svako ko je uradio taj zad moze da vidi tvoj kod...
Ideja koju sam ja koristi je matching. Jedna rec - jedan matching. Da li je pomoglo :)???
Ako ti Slobina jedna rech ne pomogne, pogledaj na topcoderu tutorial o network flowu, i pri dnu druge strane imash slichan zadatak ...
Network flow i matching su jedine oblasti graf torije koje jos nisam prosao.
Hvala, informirati cu se.
Jel mogu da dobijem test-primere: 5,12,14,17?
Posto ja ne mogu da postavim na share, onda ili posalji meni ili Rajku mejl pa ces dobiti (a moze valjda i dimitru). Moj mejl je boba5555@gmail.com...
Hehe, treba da se napravi jedan podforum:
"Treba mi test primer ..."
:)
:)
Nema na cemu... Pitacu admina pa mozda mogu da stavim na share, pa ce onda biti svima lakse :)
jeli moze netko da mi posalje kod ako nije problem na imacek@gmail.com da usporedim.
Moj kod je rekurzivni matching i pada na memoriji.
Ja sam ovaj zadatak uradio tako sto za svaku rec proveravam slovo po slovo
za svako od imena devojaka ali prolaze samo 1,2 i poslednjih 4 primera.
Nije mi jasno gde gresim.
Dali mozda imena devojaka mogu da se mesaju ili treba traziti reci u datom redosledu?
I gde da nadjem dobar tutorial za matching posto nemam poima sta je to
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2
to je sve jedan tutorial..samo iz 2 dela....
