e-olymp 1099. Говорящий Галчонок

27/03/2019 by Николай Козиний

Задача взята с сайта e-olymp

Задача

«Ура-a-a! Заработало!» – радостно воскликнул Матроскин, услышав первую произнесенную Галчонком фразу.

Э.Успенский «Трое из Простоквашино»

Как Вам всем известно, Галчонок из мультфильма «Трое из Простоквашино» при стуке в дверь всегда спрашивал: «Кто там?». Статистика, как и вся математика, наука точная и она утверждает, что Галчонок мог запоминать как отдельные слова, так и целые предложения, только в том случае, если слово было произнесено не менее $n$ раз, а предложение – не менее чем $m$ раз $\left(n\leqslant m\right)$.

Ваша задача по заданному тексту определить количество слов и предложений, которые точно запомнил Галчонок.

Входные данные

В первой строке находится два натуральных числа $n$ и $m$ $\left(n , m \leqslant 100 \right)$. Во второй строке находится сам текст. Текст написан грамматически верно.

Выходные данные

Два числа через пробел: сначала количество запомненных слов $s$, а потом количество запомненных предложений $p$.

Тесты

N,M	ТЕКСТ	ВЫХОДНЫЕ ДАННЫЕ
2,4	Blessed are the peacemakers, for they will be called children of God.	0 0
2,3	Kto tam? It is Pechkin. Kto tam? My name is Fedor. Kto tam? Pechkin!	4 1
1,1	Hey you! out there on the road Always doing what you’re told Can you help me Hey you! out there beyond the wall Breaking bottles in the hall Can you help me Hey you! don’t tell me there’s no hope at all Together we stand, divided we fall	33 3
2,2	Yes! No. Yes Yes! No Yes no no. No yes No No.	2 1
1,1	Workers of the world, unite!	5 1

Решение

#include <iostream>
#include <map>
using namespace std;
int main() {
    map <string,int> s;
    map <string,int> w;
    int n, m, a = 0,b = 0;
    cin >> n >> m;
    string word, sent;
    while(cin >> word){
        if(word.back() == ',')word.pop_back();
        sent = sent + word;
        if(word.back() == '.' or word.back() == '?' or word.back() == '!'){
            word.pop_back();
            sent.pop_back();
            if((++s[sent]) == m)a++;
            sent = "";
        }
        if((++w[word]) == n)b++;
    }
    cout << b << ' ' << a;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

map <string,int> s;

map <string,int> w;

int n, m, a = 0,b = 0;

cin >> n >> m;

string word, sent;

while(cin >> word){

if(word.back() == ',')word.pop_back();

sent = sent + word;

if(word.back() == '.' or word.back() == '?' or word.back() == '!'){

word.pop_back();

sent.pop_back();

if((++s[sent]) == m)a++;

sent = "";

}

if((++w[word]) == n)b++;

}

cout << b << ' ' << a;

}

Для решения данной задачи найдем все слова и все предложения в тексте. Слова будем считать одинаковыми, если они совпадают без знаков препинания в нижнем регистре они совпадают. Одинаковыми предложениями, соответственно, будем считать предложения, что совпадают без пробелов и знаков препинания. Увеличивая значения ассоциативных массивов, соответствующих предложению или слову на 1, увеличим на 1 значение b, если слова совпали больше чем $n$ раз и значение a, если предложения совпали больше чем $m$ раз.

Код задачи на ideone

Засчитанное решение на e-olymp

Related Images:

Анаграммы

26/11/2018 by Иван Киреев

Анаграммы

Игорю стало интересно какое количество перестановок букв его фамилии существует. Для этого он выписал на листке бумаге все буквы своей фамилии по алфавиту и начал создавать новые перестановки этих букву в лексикографическом порядке, записывая их на листок.

После того как он закончил выписывать все перестановки Игорь устал и пошел учиться. Он взял словарь и начал учить новые слова. Через некоторое время Игорь заметил что некоторые из слов в словаре совпадают с записанными им перестановками на листке и задался вопросом, — а какие можно получить слова переставляя буквы из других в словаре.

Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.

Подумав несколько ночей у него получилось написать программу которая находит слово анаграмму в словаре к другому — данному. Но перед ним встал новый вопрос, — а какое слово имеет наибольшее количество анаграмм в заданном словаре.

Его программа работала слишком долго, поэтому он попросил вас написать новую которая справилась бы с этой задачей.

Входные данные

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

Выходные данные

Вывести все слова что имеют максимальное количество анаграмм в нем.

Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка first.

Тесты

№

Ввод

Вывод

2500 слов английского языка

trace react crate

dear dare read

post stop spot

Код

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define DIFFERENCE ('A' - 'a') // разность регистров
using namespace std;
bool IsBigAlpha(char a) {
	return (a >= 'A' && a <= 'Z');
}
bool IsSmalAlpha(char a) {
	return (a >= 'a' && a <= 'z');
}
string edit(const string &str) { // приводим всё к нижнему регистру и  убираем лишние символы
	string rez = "";
	for(char a : str) {
		if (IsBigAlpha(a)) a -= DIFERENSE;
		if (IsSmalAlpha(a)) rez += a;
	}
	return rez;
}
bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке
	return a.second < b.second;
}
int main() {
	vector <pair<string, string>> words; // словарь
	string str;
	while (getline(cin, str, '\n')) {
		pair<string, string> word; // слово
		word.first = str;
		word.second = edit(str);
		sort(word.second.begin(), word.second.end()); // сортируем буквы в слове
		words.push_back(word);
	}
	sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам
	vector <int> indeces; // массив индексов
	int Count = 0, MaxCount = 0, n = words.size();
	for (int i = 1; i < n; i++) {
		if (words[i-1].second == words[i].second) Count++; 
		else {
			if (Count > MaxCount) { 
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(i-1);
			} else if (Count == MaxCount) indeces.push_back(i-1);
			Count = 0;
		}
	}
	if (Count > MaxCount) {  // обрабатываем последний найденный набор анаграмм
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(n-1);
	} else if (Count == MaxCount) indeces.push_back(n-1);
	bool first = 1;
	for (int index : indeces) { // выводим
		if (!first) cout << endl << "---------------" << endl;
		else first = 0;
		for (int i = 0; i <= MaxCount; i++) {
			if (i != 0) cout << endl;
			cout << words[index - i].first;
		}
	}
	return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

#define DIFFERENCE ('A' - 'a') // разность регистров

using namespace std;

bool IsBigAlpha(char a) {

return (a >= 'A' && a <= 'Z');

}

bool IsSmalAlpha(char a) {

return (a >= 'a' && a <= 'z');

}

string edit(const string &str) { // приводим всё к нижнему регистру и убираем лишние символы

string rez = "";

for(char a : str) {

if (IsBigAlpha(a)) a -= DIFERENSE;

if (IsSmalAlpha(a)) rez += a;

}

return rez;

}

bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке

return a.second < b.second;

}

int main() {

vector <pair<string, string>> words; // словарь

string str;

while (getline(cin, str, '\n')) {

pair<string, string> word; // слово

word.first = str;

word.second = edit(str);

sort(word.second.begin(), word.second.end()); // сортируем буквы в слове

words.push_back(word);

}

sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам

vector <int> indeces; // массив индексов

int Count = 0, MaxCount = 0, n = words.size();

for (int i = 1; i < n; i++) {

if (words[i-1].second == words[i].second) Count++;

else {

if (Count > MaxCount) {

MaxCount = Count;

indeces.clear();

indeces.push_back(i-1);

} else if (Count == MaxCount) indeces.push_back(i-1);

Count = 0;

}

if (Count > MaxCount) { // обрабатываем последний найденный набор анаграмм

MaxCount = Count;

indeces.clear();

indeces.push_back(n-1);

} else if (Count == MaxCount) indeces.push_back(n-1);

bool first = 1;

for (int index : indeces) { // выводим

if (!first) cout << endl << "---------------" << endl;

else first = 0;

for (int i = 0; i <= MaxCount; i++) {

if (i != 0) cout << endl;

cout << words[index - i].first;

}

return 0;

}

Код на ideone

Related Images:

e-olymp 1080. Анаграмматическое расстояние

21/12/2015 by Антон Локтев

Условия задачи

Два слова называются анаграмматически одинаковыми, если из букв одного слова можно получить другое слово. Например, occurs является анаграммой для слова succor; и наоборот, dear не является анаграммой слова dared (так как буква d встречается дважды в dared, и только один раз в dear). Наиболее известной английской анаграммой являются слова dog и god.

Анаграмматическим расстоянием двух слов называется минимальное количество букв, которые нужно удалить, чтобы в результате два слова стали анаграмматически одинаковыми. Например, для слов sleep и leap, нужно удалить как минимум три буквы — две из sleep и одну из leap — чтобы остались анаграмматически одинаковые слова (в указанном случае lep). А для слов dog и cat, в которых нет одинаковых букв, анаграмматическое расстояние равно [latex]6[/latex], так как нужно удалить все буквы (любое слово, в том числе и пустая строка, являются анаграммой само к себе).

Ваша задача найти анаграмматическое расстояние для заданных двух слов.

Входные данные

В первой строке задано положительное целое число [latex]N[/latex] (не превышающее [latex]60000[/latex]), указывающее количество тестовых примеров. Каждый тестовый пример состоит из двух слов, возможно пустых, каждое из которых записано в отдельной строке (всего [latex]2N[/latex]последующих строк).

Все слова, имеющие не нулевую длину, сформированы из строчных букв английского алфавита (abcdefghijklmnopqrstuvwxyz). Самым длинным словом является pneumonoultramicroscopicsilicovolcanoconiosis.

Выходные данные

Для каждого примера входных данных вывести в отдельной строке номер тестового случая и анаграмматическое расстояние, отформатированные так, как показано в примере выходных данных.

Ссылка на задачу находится здесь.

Тесты

№	Входные данные	Выходные данные
1	4 crocus succor dares seared empty smell lemon	Case #1: 0 Case #2: 1 Case #3: 5 Case #4: 4
2	1	Case #1: 0
3	5 lol lolipop primate mathematics kangaroo kilimanjaro sister sisters android andromeda	Case #1: 4 Case #2: 8 Case #3: 7 Case #4: 1 Case #5: 4

Код (cstring)

#include <cstring>
#include <iostream>
using namespace std;

const short maxSize = 46;

int main() {
	int n, matchingLetters;
	cin >> n;
	cin.ignore();
	char *word_1 = new char[maxSize]; 
	char *word_2 = new char[maxSize];
	for (int i = 0; i < n; i++) {
		 matchingLetters = 0;
		 cin.getline(word_1, maxSize);
		 cin.getline(word_2, maxSize);
		 for (int j = 0; j < strlen(word_1); j++) {
		 	  for (int k = 0; k < strlen(word_2); k++)  {
		 	  	   if (word_1[j] == word_2[k]) {
		 	  	   	   word_2[k] = '#';
		 	  	       matchingLetters++;
		 	  	       break;
		 	  	   }
		 	  }
		 }
		 cout << "Case #" << i + 1 << ":  " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;
	}
	return 0;
}

#include <cstring>

#include <iostream>

using namespace std;

const short maxSize = 46;

int main() {

int n, matchingLetters;

cin >> n;

cin.ignore();

char *word_1 = new char[maxSize];

char *word_2 = new char[maxSize];

for (int i = 0; i < n; i++) {

matchingLetters = 0;

cin.getline(word_1, maxSize);

cin.getline(word_2, maxSize);

for (int j = 0; j < strlen(word_1); j++) {

for (int k = 0; k < strlen(word_2); k++) {

if (word_1[j] == word_2[k]) {

word_2[k] = '#';

matchingLetters++;

break;

}

cout << "Case #" << i + 1 << ": " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;

}

return 0;

}

Код на ideone можно найти здесь.

Ход решения

Наша задача состоит в определении количества символов в двух строках, которые необходимо удалить для того, чтобы слова считались анаграммами. Используем после ввода числа примеров [latex]n[/latex] функцию cin.ignore(), для игнорирования перехода на новую строку, а затем считываем по парам слова. Последовательно проходим все буквы слова в первой строке с помощью цикла for. Если находим эту букву в слове второй строки, увеличиваем счётчик совпадающих букв. Совпадающую букву во второй строке заменяем на символ #, дабы избежать повторных проверок одной и той же буквы в случае её неоднократного появления в первой строке. Общее количество букв в двух строках равняется сумме длин первой и второй строк. Таким образом, чтобы получить анаграмматическое расстояние необходимо вывести:

strlen(word_1) + strlen(word_2) - 2 * matchingLetters

26	strlen(word_1) + strlen(word_2) - 2 * matchingLetters

Умножение matchingLetters на [latex]2[/latex] возникает вследствие того, что (по факту) нужно зачёркивать символы в двух строках.

Стоит отметить, что в задаче не требуется реализовывать поиск символа самостоятельно. Можно воспользоваться уже встроенной функцией для работы со строками strchr(), которая вернёт нам указатель на искомый символ. Если символ не будет найден, функция вернёт NULL. Тогда наш код приобретает следующий вид:

#include <cstring>
#include <iostream>
using namespace std;

const short maxSize = 46;

int main() {
	int n, matchingLetters;
	cin >> n;
	cin.ignore();
	char *word_1 = new char[maxSize]; 
	char *word_2 = new char[maxSize];
	for (int i = 0; i < n; i++) {
		 matchingLetters = 0;
		 cin.getline(word_1, maxSize);
		 cin.getline(word_2, maxSize);
		 for (int j = 0; j < strlen(word_1); j++) {
		 	  if (strchr(word_2, word_1[j])) {
		 	  	   *strchr(word_2, word_1[j]) = '#';
		 	  	   matchingLetters++;
		 	  }
		 }
		 cout << "Case #" << i + 1 << ":  " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;
	}
	return 0;
}

#include <cstring>

#include <iostream>

using namespace std;

const short maxSize = 46;

int main() {

int n, matchingLetters;

cin >> n;

cin.ignore();

char *word_1 = new char[maxSize];

char *word_2 = new char[maxSize];

for (int i = 0; i < n; i++) {

matchingLetters = 0;

cin.getline(word_1, maxSize);

cin.getline(word_2, maxSize);

for (int j = 0; j < strlen(word_1); j++) {

if (strchr(word_2, word_1[j])) {

*strchr(word_2, word_1[j]) = '#';

matchingLetters++;

}

cout << "Case #" << i + 1 << ": " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;

}

return 0;

}

Код на ideone можно найти здесь.

Код (string)

#include <string>
#include <iostream>
using namespace std;

int main() {
	int n, matchingLetters;
	cin >> n;
	cin.ignore();
	string word_1, word_2;
	for (int i = 0; i < n; i++) {
		 matchingLetters = 0;
		 getline(cin, word_1);
		 getline(cin, word_2);
		 for (int j = 0; j < word_1.size(); j++) {
		 	  if (word_2.find(word_1[j]) != string::npos) {
		 	  	  word_2[word_2.find(word_1[j])] = '#';
		 	  	  matchingLetters++;
		 	  }
		 }
		 cout << "Case #" << i + 1 << ":  " << word_1.size() + word_2.size() - 2 * matchingLetters << endl;
	}
	return 0;
}

#include <string>

#include <iostream>

using namespace std;

int main() {

int n, matchingLetters;

cin >> n;

cin.ignore();

string word_1, word_2;

for (int i = 0; i < n; i++) {

matchingLetters = 0;

getline(cin, word_1);

getline(cin, word_2);

for (int j = 0; j < word_1.size(); j++) {

if (word_2.find(word_1[j]) != string::npos) {

word_2[word_2.find(word_1[j])] = '#';

matchingLetters++;

}

cout << "Case #" << i + 1 << ": " << word_1.size() + word_2.size() - 2 * matchingLetters << endl;

}

return 0;

}

В случае решения данной задачи с помощью класса string используем функцию find() для поиска заданного символа в строке.

Код на ideone можно найти здесь.

Ссылка на засчитанное решение.

Related Images:

e-olymp 332. Детская железная дорога

28/11/2015 by Таран Таня

Витэк не прекращает своих игр с кубиками. А тут еще папа подарил ему детскую железную дорогу. Витэк расставляет какое-то количество кубиков по одному на вагончик и перед тем как закончить игру, решает перестроить состав таким образом, чтобы получившееся слово было лексикографически наименьшим из всех возможных, но так как он уже наигрался, поэтому может только один раз отцепить какое-то количество кубиков и паровозиком перевезти их в хвост своего состава.

Какое слово получится у Витэка?

Входные данные

Первая и единственная строка содержит исходное слово. Кубики у Витэка только из заглавных букв латинского алфавита и их количество не превышает [latex]500000[/latex].

Выходные данные

Слово, которое образовал Витэк.

Задача взята с сайта e-olymp.

Тесты

Входные данные	Выходные данные
CBABC	ABCCB
XXXXX	XXXXX
ABEABFABBABC	ABBABCABEABF
RATOBCQATOBC	ATOBCQATOBCR
OROOXOOSTO	OOROOXOOST
LBDEAFAARDEABBAF	AARDEABBAFLBDEAF

Алгоритм

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

Так как мы работаем над упорядоченным алфавитом, то для получения наименьшего лексикографического слова следует из всех возможных для нас перестановок выбрать то слово, которое будет стоять первым при их упорядочивании в лексикографическом порядке.

Нетрудно догадаться, что для этого следует найти наименьший символ в данной строке по номеру вхождения в данный алфавит (в дальнейшем будем называть его минимальным символом) и выполнить сдвиг так, чтобы он оказался в начале. Но следует учесть, что минимальный символ может встречаться в данном слове не один раз, тогда следует построить алгоритм поиска наименьшей подстроки для сдвига.

Так как мы имеем право выбирать подслово только начиная от некоторого символа и до конца строки, то нам следует сравнить все подстроки начинающиеся с вхождения минимального символа и заканчивающиеся в конце слова.

Рассмотрим на произвольно выбранном примере:

LBDEAFAARDEABBAF

Тогда следует сравнить такие подслова:

AFAARDEABBAF
AARDEABBAF
ARDEABBAF
ABBAF
AF

Найти среди них минимальное лексикографическое и передвинуть его в начало слова.

Реализуем описанный выше алгоритм на практике с некоторыми особенностями.

Прочитаем слово.
Найдем минимальный символ в данном слове.
Создадим вектор для хранения индексов вхождения минимального символа (indicesOfMinSymbol) и будем добавлять в него значение только в том случае, если текущий символ является минимальным, а предыдущий нет. (Обратившись к предоставленному примеру, можно заметить, что не имеет смысла отдельно проводить сравнение подслов AARDEABBAF и ARDEABBAF, так как первое из них явно «выгоднее». Также мы сможем упростить ситуацию и избавиться от большого количества лишних проверок, когда на вход поступает слово состоящее из всех одинаковых символов (например, XXXXX), в котором не нужно выполнять ни единого сравнения и как-либо изменять слово).
Объявим индекс начала текущего наименьшего лексикографического подслова (indexOfMinLexicSubstr) и для каждого значения из заполненного ранее вектора будем сравнивать от иднекса начала текущего наименьшего лексикографического подслова столько символов, сколько осталось до конца строки от текущего индекса вхождения минимального символа, с подстрокой, начинающейся с этого индекса и заканчивающейся в конце слова, с помощью функции compare. (Рассмотрим произвольные подслова из заданного примера: AFAARDEABBAF и AARDEABBAF. Тогда исходя из пункта 4 следует сравнить подслова AFААRDEABB и AARDEABBAF. Мы имеем полное право выполнить такое упрощение, так как отсутствие следующего символа меньше, чем наличие любого другого символа, и если будет выбрано первое подслово, то второе подслово, стоящее справа от него, автоматически также будет сдвинуто в начало.
Однако существует немаловажное исключение при построении такого алгоритма. Его удобно рассмотреть на каком-либо конкретном случае, например, OROOXOOSTO. Когда мы дойдем до сравнения подслов OOSTO (на данный момент будет являться минимальным) и О, исходя из выше описанного алгоритма, мы получим равенство подстрок и не изменим индекс начала минимальной строки, тогда ложно будет построена как наименьшая лексикографическая строка из данной OOSTOOROOX. Исправить эту проблему можно дополнительной проверкой того, что выйдет при сдвиге второй (более короткой) подстроки в начало заданного слова. То есть для данного примера, можно заметить, что подслово OROO лексикографически меньше чем OSTO (сравниваем такое же количество символов в начале строки, сколько оставалось до конца у текущей наименьшей лексикографической подстроки).
Примечание: следует отметить, что даже без выполнения второй проверки алгоритм проходил все тесты к данной задаче на сайте e-olymp, что может говорить лишь о неполноте тестов.).
И только в том случае, если функция compare в пункте 4 вернула значение больше чем [latex]0[/latex], то есть правое подслово меньше, или же меньше подслово получаемое при сдвиге правой строки в сравнении с текущим наименьшим лексикографическим, тогда изменяем значение индекса минимального лексикографического подслова на текущий индекс вхождения минимального символа.
После прохождения всего вектора, выполняем сдвиг найденного минимального лексикографического подслова в начало, благодаря встроенной функции rotate, и выполняем вывод полученного слова.

Код программы:

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	string word;
	cin >> word;
	char minSymbol = word[0]; 
	vector <int> indicesOfMinSymbol; // Вектор для хранения индексов вхождения "минимального" символа
	for (int i = 1; i < word.size(); i++) {
		 if (word[i] < minSymbol) {
		     minSymbol = word[i];
		 }
	} // Поиск "минимального" символа в данном слове
	for (int i = 0; i < word.size(); i++) {
		 if (word[i] == minSymbol && word[i - 1] != minSymbol) {
		     indicesOfMinSymbol.push_back(i);
		 } // Добавляем индекс, если текущий является "минимальным", а предыдущий таковым не был
	} // Заполняем вектор индексами вхождения "минимального" символа
	int indexOfMinLexicSubstr = indicesOfMinSymbol[0]; // Индекс начала текущего минимального лексикографического подслова
	for (int i = 1; i < indicesOfMinSymbol.size(); i++) {
		 if (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) > 0
		 	 || (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) == 0
		 	     &&  word.compare(0, indicesOfMinSymbol[i] - indexOfMinLexicSubstr, word, indexOfMinLexicSubstr + word.size() - indicesOfMinSymbol[i], string::npos) < 0)) {
			 indexOfMinLexicSubstr = indicesOfMinSymbol[i]; 
		 } // Сравниваем текущее минимальное подслово и подслово начинающееся со следующего вхождения "минимального" символа, если они равны, то следует проверить, что выйдет, благодаря задействованию символов из начала строки
    } // Поиск наименьшего лексикографического подслова
	rotate(word.begin(), word.begin() + indexOfMinLexicSubstr, word.end()); // Cдвигаем наименьшее лексикографическое подслово в начало
	cout << word;
	return 0;
}

#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

string word;

cin >> word;

char minSymbol = word[0];

vector <int> indicesOfMinSymbol; // Вектор для хранения индексов вхождения "минимального" символа

for (int i = 1; i < word.size(); i++) {

if (word[i] < minSymbol) {

minSymbol = word[i];

}

} // Поиск "минимального" символа в данном слове

for (int i = 0; i < word.size(); i++) {

if (word[i] == minSymbol && word[i - 1] != minSymbol) {

indicesOfMinSymbol.push_back(i);

} // Добавляем индекс, если текущий является "минимальным", а предыдущий таковым не был

} // Заполняем вектор индексами вхождения "минимального" символа

int indexOfMinLexicSubstr = indicesOfMinSymbol[0]; // Индекс начала текущего минимального лексикографического подслова

for (int i = 1; i < indicesOfMinSymbol.size(); i++) {

if (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) > 0

|| (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) == 0

&& word.compare(0, indicesOfMinSymbol[i] - indexOfMinLexicSubstr, word, indexOfMinLexicSubstr + word.size() - indicesOfMinSymbol[i], string::npos) < 0)) {

indexOfMinLexicSubstr = indicesOfMinSymbol[i];

} // Сравниваем текущее минимальное подслово и подслово начинающееся со следующего вхождения "минимального" символа, если они равны, то следует проверить, что выйдет, благодаря задействованию символов из начала строки

} // Поиск наименьшего лексикографического подслова

rotate(word.begin(), word.begin() + indexOfMinLexicSubstr, word.end()); // Cдвигаем наименьшее лексикографическое подслово в начало

cout << word;

return 0;

}

Код программы

Засчитанное решение

Related Images:

e-olymp 330. Слово-чемпион

19/11/2015 by Таран Таня

Задано некоторое предложение на неизвестном языке. Назовем слово в нем чемпионом, если оно является палиндромом и количество букв в нем максимально. Буквами алфавита в неизвестном языке являются буквы латинского алфавита и арабские цифры. Гарантируется, что других символов, кроме пробелов и знаков препинания в предложении нет.

Задача взята с сайта e-olymp.

Входные данные

Предложение на неизвестном языке.

Выходные данные

Номер слова-чемпиона.

Тесты

Предложение	Номер слова-чемпиона
Oo, it aaa is not bb.	3
Tummut, suuruu 18!	1
Qrtew asd x, pol 123 xcv.	3
Antaa, qor — aapapaa for Saippuakivikauppias kappak!	6
A b C d E f G h	1
NoPalindrome	0
123321 oro 1234554321?	3

Примечание : в ходе решения задачи выяснилось, что, если в предложении присутствуют несколько палиндромов одинаковой длины, следует вывести первый из встретившихся.

Алгоритм

В данной задаче требуется найти в заданном предложении палиндром максимальной длины. Так как нам нужно проводить анализ отдельных слов, то считывать будем по одному слову пока предложение не закончится, при этом храня порядковый номер текущего слова. Однако, следует учесть следующее:

Слово-палиндром может содержать в себе буквы различного регистра, что может помешать при проверке на палиндромность. Во избежание ошибки переведем все слово, например, в нижний регистр с помощью соответствующей функции.
В предложении встречаются знаки препинания, поэтому если последний символ в слове не является буквой латинского алфавита или цифрой (проверку для удобства чтения вынесем в отдельную функцию), заменим его на нуль-символ, чтобы в дальнейшем его не учитывать.

После проведенных операций найдем длину текущего слова и, если она превышает максимальную длину ранее найденного слова-чемпиона, проверим, является ли текущее слово палиндромом. Осуществим это с помощью рекурсивной функции, сравнивающей соответствующие символы в данной строке по индексам. Функция работает до тех пор, пока начальный и конечный индекс не сравняются или поменяются местами (изначально первый индекс (start) равен нулю, а конечный (end) меньше длины строки на единицу), или же соответствующие символы окажутся разными. Если данное слово оказалось палиндромом, храним его порядковый номер в предложении.
Как только предложение завершено, выводим индекс найденного слова-чемпиона, или индекс первого из них, если таковых было несколько.

Код программы:

#include <iostream>
#include <cstring>
using namespace std;

const int registerShift = 'A' - 'a'; // Сдвиг от верхнего регистра к нижнему по таблице ASCII

// Функция, для определения, является ли текущий символ "буквой" в контексте данной задачи
bool IsAllowedSymbol(char symbol) {
	return ((symbol >= '1' && symbol <= '9') || (symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z')) ? true : false;
}

// Функция, для определения, является ли текущее слово палиндромом
bool IsPalindrom(char *word, int begin, int end) {
	return (end <= begin) ? true : (word[begin] != word[end]) ? false : IsPalindrom(word, ++begin, --end);
}

// Функция, которая переводит все слово в нижний регистр
void ToLowerCase(char *word) {
	 for (int i = 0; i < strlen(word); i++) {
	 	  if (word[i] >= 'A' && word[i] <= 'Z')
	 	      word[i] -= registerShift;
	 }
}

int main() {
	char word[1001];
	int wordSize, maxSize = 0, indexOfPalindrom = 0;
    for (int i = 1; cin >> word; i++) {
    	 ToLowerCase(word); // Перевод слова в нижний регистр 
    	 if (!IsAllowedSymbol(word[strlen(word) - 1]))
    	     word[strlen(word) - 1] = '\0'; // Не учитывать последний символ слова, если это не "буква" (т. е. знак препинания)
    	 wordSize = strlen(word);
    	 if (wordSize > maxSize) {
	         if (IsPalindrom(word, 0, wordSize - 1)) {
	         	 maxSize = wordSize;
	             indexOfPalindrom = i;	    
	         } // Храним новый максимум и индекс текущего наибольшего палиндрома, если он был найден
	     }
    } // Чтение по словам до конца предложения
	cout << indexOfPalindrom;
    return 0;
}