Lowest Hash
Национална Олимпиада по Информатика 2019, Контрола 1
Time Limit: 2s, Memory Limit: 128MiB
Наскоро Ели, Крис и Станчо научиха следния алгоритъм за хеширане на стринг S с дължина N, съставен от главни букви на английската азбука:
S[i] дава ASCII кода на i-тата буква от стринга. Буквата 'A' е с ASCII код 65, докато 'Z' - с код 90. Стойността на променливата hash след края на цикъла се нарича "хеш" на стринга.
Всеки от тримата има по един любим стринг с дължина N: този на Ели е A, този на Крис е B, а този на Станчо е C. Сега те са решили да съставят стринг S със същата дължина, който на всяка от позициите си съдържа една от буквите на съответната позиция в някой от техните стрингове. С други думи, за позиция i, S[i] = A[i] или S[i] = B[i] или S[i] = C[i].
Ели, Крис и Станчо искат да намерят стринга S с най-малък хеш. Можете ли да им помогнете, като го намерите вместо тях?
long long hash = 0;
for (int i = 0; i < N; i++) {
hash = (hash * 127 + S[i]) % 1000000000000037;
}
S[i] дава ASCII кода на i-тата буква от стринга. Буквата 'A' е с ASCII код 65, докато 'Z' - с код 90. Стойността на променливата hash след края на цикъла се нарича "хеш" на стринга.
Всеки от тримата има по един любим стринг с дължина N: този на Ели е A, този на Крис е B, а този на Станчо е C. Сега те са решили да съставят стринг S със същата дължина, който на всяка от позициите си съдържа една от буквите на съответната позиция в някой от техните стрингове. С други думи, за позиция i, S[i] = A[i] или S[i] = B[i] или S[i] = C[i].
Ели, Крис и Станчо искат да намерят стринга S с най-малък хеш. Можете ли да им помогнете, като го намерите вместо тях?
Вход
На първия ред на стандартния вход ще бъде зададено цялото число N - дължината на всеки от стринговете. На всеки от следващите три реда ще бъде зададен по един стринг с дължина N, съставен от главни букви от английската азбука - съответно стринговете на Ели (А), Крис (B), и Станчо (C).
Изход
На единствен ред на стандартния изход изведете едно цяло число - минималния възможен хеш, който може да има стринг S, образуван по описания по-горе начин.
Ограничения
- 1 ≤ N ≤ 28
Примерен Вход | Примерен Изход |
---|---|
14 ELEONORAEKIFLA KRISSIMASTRING STANCHOPIEVODA | 545601337476 |
Примерни стрингове, които могат да съставят, са STISNIMASTRONG (с хеш 816860215893321) или пък ETENNHRPEEIOLA (с хеш 881156714759922) или дори KRISSIMASTRING (с хеш 515697493951910), но този с най-малък такъв е KTESNOOPEEIFDA (с хеш 545601337476).