Studious Student
You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string.
Input
As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.
Output
Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.
Constraints
1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10
[php]
<?php
$file = file('input.txt');
$i=0;
$quanti = $file[$i++];
while( $i<=$quanti )
{
$row = preg_split('/[\s]+/', $file[$i]);
$m = $row[0];
// elimino il primo elemento
array_shift($row);
// elimino l'ultimo elemento se vuoto
if( empty($row[$m]) ) unset($row[$m]);
// ordino alfabeticamente
$row = merge_sort($row);
$res[] = trim(implode('', $row));
$i++;
}
file_put_contents('output.txt', implode("\n",$res));
function merge_sort(&$arrayToSort)
{
if (sizeof($arrayToSort) <= 1)
return $arrayToSort;
// split our input array into two halves
// left...
$leftFrag = array_slice($arrayToSort, 0, (int)(count($arrayToSort)/2));
// right...
$rightFrag = array_slice($arrayToSort, (int)(count($arrayToSort)/2));
// RECURSION
// split the two halves into their respective halves...
$leftFrag = merge_sort($leftFrag);
$rightFrag = merge_sort($rightFrag);
$returnArray = merge($leftFrag, $rightFrag);
return $returnArray;
}
function merge(&$lF, &$rF)
{
$result = array();
// while both arrays have something in them
while (count($lF)>0 && count($rF)>0)
{
$ret = compare($lF[0], $rF[0]);
if($ret)
{
array_push($result, array_shift($lF));
}
else
{
array_push($result, array_shift($rF));
}
}
// did not see this in the pseudo code,
// but it became necessary as one of the arrays
// can become empty before the other
array_splice($result, count($result), 0, $lF);
array_splice($result, count($result), 0, $rF);
return $result;
}
/**
* @return bool true se la seconda stringa è >= della prima
*/
function compare($str1, $str2)
{
$len1 = strlen($str1);
$len2 = strlen($str2);
// controllo se la prima parte della stringa più lunga è uguale alla stringa più corta
if( $len1>=$len2 )
{
return check($str1, $str2, $len1, $len2);
}
else
{
return !check($str2, $str1, $len2, $len1);
}
}
/**
* @param $str1 parola lunga
* @param $str2 parola corta
* @param $len1
* @param $len2
* @return bool true se la seconda stringa è >= della prima
*/
function check($str1, $str2, $len1, $len2)
{
if($str1==$str2) return true;
$pos = strpos($str1, $str2);
if($pos!==false && $pos==0)
{
// devo eliminare tutte le occorrenze di str2 da str1 (solo se presenti ad inizio stringa)
$regex = "/^($str2)+/";
$str3 = preg_replace($regex, '', $str1);
$len3 = strlen($str3);
if( $len3>$len2 )
{
return check($str3, $str2, $len3, $len2);
}
elseif( $len3<$len2 )
{
return !check($str2, $str3, $len2, $len3);
}
else
{
if( strcasecmp($str3, $str2) <= 0 )
{
return true;
}
else
{
return false;
}
}
}
// se la prima parte non coincide
if( strcasecmp($str1, $str2) <= 0 )
{
return true;
}
else
{
return false;
}
}
[/php]