Школа179: Разбор задачи E

https://server.179.ru/wiki     редакция: 20.08.2016 19:02:00
Информатика/Олимпиады/2008/Школьная/Разбор/E
Условия задачи пятого тура

Идея решения. В глобальной переменной Roman записана строка – римское число, в переменной Arabic – ее числовое значение. Первоналально оно равно нулю, в ходе разбора это значение будет увеличиваться. Переменная Position хранит количество уже успешно считанных и разобранных символов из переменной Roman.

Основная функция – это функция Read. Она получает два параметра: строку, соответствующую одной группе символов, которые считываются из переменной Roman и их числовое значение. Например, вызов Read("IX",9) – это попытка считать из переменной Roman последовательность символов "IX".

Считывание символов производится начиная с позиции Position. Считывание успешным, если строка Roman после пропуска первых Position символов совпадает с группой. Если считывание было успешным, то к значению Arabic прибавляется числовое значение группы (второй паараметр функции Read), а значение Position увеличивается на значение длины группы и функция Read возвращает true. Если считывание неуспешно, фунция Read возвращает false.

В функции main считывается значение Roman, далее осуществляется разбор строки. При этом используется особенность неполного вычисления логических выражений, например, при вызове Read("MMM", 3000) || Read("MM", 2000) || Read("M", 1000) сначала вызывается функция Read("MMM", 3000). Если она вернула true, то две другие функции не вызываются, а если вернула false, то вызывается Read("MM", 2000). В свою очередь, Read("M", 1000) вызывается только если два предыдущих вызова вернули false.

В функции main осуществляются последовательные попытки считать количество тысяч, сотен, десятков и единиц. Если после этого были считаны все символы, значит, запись римского числа корректна и выводится значение Arabic, иначе (остались несчитанные символы) запись некорректна и выводится 0.


#include<iostream>

using namespace std;

string Roman;
int Arabic;
int Position;

bool Read (string RomanDigit, int Value)
{
	if( Position+RomanDigit.length() > Roman.length() )
		return false;

	for(int i=0;i<RomanDigit.length();++i)
		if(Roman[Position+i]!=RomanDigit[i])
			return false;
	Position += RomanDigit.length();
	Arabic+=Value;
	return true;
}

int main()
{
	cin>>Roman;

	// Считываем количество тысяч
	Read("MMM", 3000) ||
	Read("MM",  2000) ||
	Read("M",   1000) ;

	// Считываем количество сотен
	Read("CM",   900) ||
	Read("DCCC", 800) ||
	Read("DCC",  700) ||
	Read("DC",   600) ||
	Read("D",    500) ||
	Read("CD",   400) ||
	Read("CCC",  300) ||
	Read("CC",   200) ||
	Read("C",    100) ;

	// Считываем количество десятков
	Read("XC",   90) ||
	Read("LXXX", 80) ||
	Read("LXX",  70) ||
	Read("LX",   60) ||
	Read("L",    50) ||
	Read("XL",   40) ||
	Read("XXX",  30) ||
	Read("XX",   20) ||
	Read("X",    10) ;

	// Считываем количество единиц
	Read("IX",   9) ||
	Read("VIII", 8) ||
	Read("VII",  7) ||
	Read("VI",   6) ||
	Read("V",    5) ||
	Read("IV",   4) ||
	Read("III",  3) ||
	Read("II",   2) ||
	Read("I",    1) ;

	if( Position==Roman.length())
		cout<<Arabic<<endl;
	else
		cout<<0<<endl;
	return 0;
}