Come da titolo… Ho provato una soluzione mia con alberi e quant’altro, ma al bellissimo 0/100 ho voluto provare una brute force (next_permutation sull’array di parole). E’ possibile che io ottenga “Wrong output: too many operations” provandole tutte?
Il bello è che in locale mi da il risultato giusto sia sul caso di esempio che su altri casi fatti da me.
Allego il mio codice
[code]#include
#include
#include
#include
#include
using namespace std;
vector strings;
string commands;
int first_difference(string s, string t)
{
int ret = 0;
for(int i = 0; i < min(s.size(), t.size()); i++)
{
if(s[i] != t[i])
break;
ret++;
}
return ret;
}
string count_commands(vector strings)
{
commands.clear();
int diff = 0;
for(int i = 0; i < strings.size(); i++)
{
commands.append(strings[i].substr(diff, strings[i].size() - diff));
commands += “P”;
if(i == strings.size() - 1)
break;
diff = first_difference(strings[i], strings[i + 1]);
for(int j = 0; j < (strings[i].size() - diff); j++)
commands += "-";
}
return commands;
}
int main()
{
int N;
scanf("%d", &N);
for(int i = 0; i < N; i++)
{
char buf[21];
scanf("%s", &buf);
string str(buf);
strings.push_back(str);
}
sort(strings.begin(), strings.end());
string best = count_commands(strings);
while(next_permutation(strings.begin(), strings.end()))
{
string maybe = count_commands(strings);
if(maybe.size() < best.size())
best = maybe;
}
commands = best;
printf("%d", commands.size());
for(int i = 0; i < commands.size(); i++)
printf("\n%c", commands[i]);
return 0;
}
[/code]
Dario
