Матч 247, Произношение (Speller)

Дивизион 2, Уровень 3

Имеется строка, которая содержит целое число от 1 до 99 словами. Грамматика, описывающая число, имеет вид:

<NUMBER> ::= <ONES> | <TEEN> | <TENS> | <TENS>-<ONES>

<ONES> ::= one | two | three | four | five | six | seven | eight | nine

<TEEN> ::= ten | eleven | twelve | thirteen | fourteen | fifteen |

sixteen | seventeen | eighteen | nineteen

<TENS> ::= twenty | thirty | forty | fifty | sixty | seventy | eighty | ninety

В задаче необходимо найти число, написание которого является ближайшим к тому, что записано во входной строке. Расстоянием между строк называется минимальное количество букв, которое следует изменить, чтобы получить из одной строки другую. Сравнение букв происходит с учетом регистра. Расстояние между словами разной длины равно бесконечности.

Класс: Speller

Метод: int value(String number)

Ограничения: строка number содержит от 1 до 20 символов, каждый из символов строки является кодом от 33 до 126 включительно.

Вход. Строка number, содержащая чсло от 1 до 99, записанное словами.

Выход. Целое число, которое является «ближайшим» по написанию к слову, записанному с строке number. Если существует несколько чисел, ближайших по написанию к number, вернуть -1.

Пример входа

number

Forty-two

FORTY-TWO

Eighteen

Fi

Пример выхода

42

-1

18

-1

РЕШЕНИЕ

обработка текста

Занесем в вектор строк v имена числительные, соответствующие числам от 1 до 99. Для заданной строки number ищем строку в массиве v, находящуюся на наименьшем расстоянии от нее. Или то же самое, что ищется строка в v, имеющая максимум общих букв с number. Если таких строк существует несколько (имеет место неоднозначность решения), то выводится -1. Иначе выводится значение переменной p, которая содержит искомый ответ.

Функция cmpr(string a, string b) возвращает -1 , если строки a и b имеют разную длину (расстояние между строками разной длины равно бесконечности). Иначе возвращаемое значение равно числу букв, находящихся на одинаковых позицияк.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

using namespace std;

class Speller

{

public:

int cmpr(string a, string b)

{

int i, res;

if (a.size() != b.size()) return -1;

for(i = res = 0; i < a.size(); i++) res += (a[i] == b[i]);

return res;

}

int value(string number)

{

vector<string> v(100);

int max = -1, p= -1, i, j;

string digits[] = {"one","two","three","four","five","six","seven",

"eight","nine"};

string teens[] = {"ten","eleven","twelve","thirteen","fourteen","fifteen",

"sixteen","seventeen","eighteen","nineteen"};

string tens[] = {"twenty","thirty","forty","fifty","sixty","seventy",

"eighty","ninety"};

for(i = 0; i < 9; i++) v[i+1] = digits[i];

for(i = 0; i < 10; i++) v[i+10] = teens[i];

for(i = 20; i < 100; i++)

if (i % 10 == 0) v[i] = tens[i / 10 - 2];

else v[i] = tens[i / 10 - 2] + "-" + v[i % 10];

for(i = 1; i < v.size(); i++)

{

j = cmpr(v[i],number);

if (j > max) {max = j; p = i;} else

if (j == max) p = -1;

}

return p;

}

};