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:

e-olymp 912. Количество предложений

20/12/2015 by Александр Коломеец

Постановка задачи

e-olymp 912. Количество предложений

Определить количество предложений в заданном фрагменте текста.

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

В единственной строке задан фрагмент текста на английском языке, количество символов в котором не превышает 250. Гарантируется, что в тексте отсутствуют тире, дефисы, цифры и числа.

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

Единственное число — количество предложений в фрагменте.

Алгоритм решения

Нужно заметить, что каждое предложение может заканчиваться точкой, восклицательным знаком или вопросительным знаком. Значит, если в тексте мы нашли какой-то из этих символов, то мы нашли и предложение. Но возникает проблема. Предложение может заканчиватся несколькими знаками препинания (к примеру, многоточием). Так как многоточие — это три поставленых рядом точки, то, если считать количество предложений как количество знаков препинания, которыми может заканчиваться предложение, мы, вероятнее всего, допустим ошибку. Это решается легким путем: при встрече таких знаков, идущих подряд, мы берем во внимание только один из них, игнорируя остальные. Таким образом мы можем подсчитать количество предложений.

Тесты

Входные данные	Выходные данные
Hello, World!	1
Those lips that Love’s own hand did make Breathed forth the sound that said ‘I hate,’ To me that languish’d for her sake: But when she saw my woeful state, Straight in her heart did mercy come, Chiding that tongue that ever sweet Was used in giving gentle doom, And taught it thus anew to greet: ‘I hate’ she alter’d with an end, That follow’d it as gentle day Doth follow night, who like a fiend From heaven to hell is flown away; ‘I hate’ from hate away she threw, And saved my life, saying — ‘not you.’	1
Winter…	1
Winter	0

Реализация

ideone: ссылка
Засчитаное решение: ссылка

#include <iostream>
using namespace std;

bool isNeededChar(char c) {
	switch(c) {
		case '.':
		case '!':
		case '?':
			return true;
		default:
			return false;
	}
}

int main() {
	int counter = 0;
	string text;
	getline(cin, text);
	for(int i = 1; i < text.length(); i++) {
		if(isNeededChar(text.at(i))) {
			if(!isNeededChar(text.at(i - 1))) {
				counter++;
			}
		}
	}
	cout << counter << endl;
	return 0;
}

#include <iostream>

using namespace std;

bool isNeededChar(char c) {

switch(c) {

case '.':

case '!':

case '?':

return true;

default:

return false;

}

int main() {

int counter = 0;

string text;

getline(cin, text);

for(int i = 1; i < text.length(); i++) {

if(isNeededChar(text.at(i))) {

if(!isNeededChar(text.at(i - 1))) {

counter++;

}

cout << counter << endl;

return 0;

}

Related Images:

e-olymp 329. Количество слов

30/11/2015 by Молоканов Юрий

Условие

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

Тестирование

№	Входные данные	Выходные данные
1	Hello, world!	2
2	War is Peace. Freedom is Slavery. Ignorance is Strength.	9
3	— «4», «8», <15>; (16), {23}, [42]!?	6
4	A flock of sparrows – some of them juveniles – alighted and sang.	11
5	A mean Earth solar day is approximately 24 hours, whereas a mean Martian ‘sol’ is 24 hours, 39 minutes, and 35.244 seconds.	22
6	Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.	19

Код

Реализация с помощью посимвольного считывания

#include <iostream>
using namespace std;

// Проверяет, принадлежит ли символ алфавиту
bool AllowedSign(char x) {
	return ((x >= '0' && x <= '9') || (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z'))?1:0;
}

int main() {
	char x;
	int count = 0;	// Счетчик слов в предложении
	bool wordBegin = true;	// Будет ли следующий считанный символ, принадлежащий алфавиту, началом нового слова
	while(EOF != (x = getchar())) { 
		if(AllowedSign(x) && wordBegin) {	// Если текущий символ принадлежит алфавиту и ожидается новое слово
			count++;
			wordBegin = false;	// Указываем, что последующие находимые символы алфавита не будут началом слова
		} else if(x == ' ')	// Если текущий символ - пробел
			wordBegin = true;	// Указываем для следующей итерации, что текущее слово "закончилось" и ожидается новое
	}
	cout << count;
	return 0;
}

#include <iostream>

using namespace std;

// Проверяет, принадлежит ли символ алфавиту

bool AllowedSign(char x) {

return ((x >= '0' && x <= '9') || (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z'))?1:0;

}

int main() {

char x;

int count = 0; // Счетчик слов в предложении

bool wordBegin = true; // Будет ли следующий считанный символ, принадлежащий алфавиту, началом нового слова

while(EOF != (x = getchar())) {

if(AllowedSign(x) && wordBegin) { // Если текущий символ принадлежит алфавиту и ожидается новое слово

count++;

wordBegin = false; // Указываем, что последующие находимые символы алфавита не будут началом слова

} else if(x == ' ') // Если текущий символ - пробел

wordBegin = true; // Указываем для следующей итерации, что текущее слово "закончилось" и ожидается новое

}

cout << count;

return 0;

}

Реализация с помощью строк c-string

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

// Проверяет, принадлежит ли символ алфавиту
bool AllowedSign(char x) {
	return ((x >= '0' && x <= '9') || (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z'))?1:0;
}

int main() {
	const int size = 500;
	int count = 0;	// Счетчик слов в предложении
	char word[size];
	while(cin >> word) {
		bool isWord = false;	// По умолчанию считаем, что считанная последовательность символов словом не является
		for(int i = 0; i < strlen(word) && !isWord; i++)	// Проверяем символы массива, пока не дойдем до его конца или не убедимся, что считанная последовательность ялвяется словом
			if(AllowedSign(word[i])) {	// Если текущий символ принадлежит алфавиту
				count++;
				isWord = true;	// Указываем, что последовательность является словом
			}
	}
	cout << count;
	return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

// Проверяет, принадлежит ли символ алфавиту

bool AllowedSign(char x) {

return ((x >= '0' && x <= '9') || (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z'))?1:0;

}

int main() {

const int size = 500;

int count = 0; // Счетчик слов в предложении

char word[size];

while(cin >> word) {

bool isWord = false; // По умолчанию считаем, что считанная последовательность символов словом не является

for(int i = 0; i < strlen(word) && !isWord; i++) // Проверяем символы массива, пока не дойдем до его конца или не убедимся, что считанная последовательность ялвяется словом

if(AllowedSign(word[i])) { // Если текущий символ принадлежит алфавиту

count++;

isWord = true; // Указываем, что последовательность является словом

}

cout << count;

return 0;

}

Решение

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

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

Теперь перейдем к практическому решению задачи.

Реализация с помощью посимвольного считывания

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

Для решения задачи этим методом воспользуемся функцией bool AllowedSign(char x), возвращающей значение true, если переданный ей символ принадлежит алфавиту неизвестного языка, и объявим логическую переменную wordBegin, определяющую, будет ли следующий считанный символ алфавита началом нового слова, и присвоим ей до начала выполнения цикла посимвольного считывания значение true. Сам цикл будет выполняться до тех пор, пока не будет прочитан весь входной поток:

bool wordBegin = true;
while(EOF != (x = getchar()))

1 2	bool wordBegin = true; while(EOF != (x = getchar()))

При этом на каждой его итерации будут возможны, в зависимости от текущего символа и значения переменной wordBegin, следующие два варианта действий. Если считанный символ принадлежит алфавиту и при этом ожидается новое слово ( wordBegin = true), инкрементируем счетчик слов count и присваиваем wordBegin значение false. С этого момента и до тех пор, пока не будет достигнут конец слова, все последующие считываемые символы алфавита не будут влиять на счетчик:

if(AllowedSign(x) && wordBegin) {
	count++;
	wordBegin = false;
}

if(AllowedSign(x) && wordBegin) {

count++;

wordBegin = false;

}

Если же считанный символ — пробел, присваиваем wordBegin значение true. Достигнут конец текущего слова, и теперь следующий алфавитный символ, если он встретится в потоке, приведет к инкрементированию счетчика слов, так как будет принадлежать уже другому слову:

else if(x == ' ')
	wordBegin = true;

1 2	else if(x == ' ') wordBegin = true;

Как видно, неалфавитные символы (знаки препинания) игнорируются и на подсчет слов никак не влияют. Наконец, после того, как будет прочитан весь входной поток, выводится значение счетчика слов count, что и есть ответом на поставленный вопрос задачи:

cout << count;

1	cout << count;

Реализация с помощью строк c-string

Как и в предыдущем варианте решения, воспользуемся функцией AllowedSign, определяющей принадлежность символа алфавиту, а также объявим переменную bool isWord, отвечающую за то, является ли проверяемая последовательность символов словом неизвестного языка. Тогда суть метода будет заключаться в считывании из входного потока последовательностей символов и проверке того, являются ли они словами. В основе метода лежит цикл, считывающий из входного потока «потенциальные слова» до тех пор, пока это возможно:

while(cin >> word)

1	while(cin >> word)

После считывания последовательности символов присваиваем переменной isWord значение false, изначально считая, что эта последовательность словом не является:

bool isWord = false;

1	bool isWord = false;

Затем поочередно проверяем символы последовательности до тех пор, пока isWord сохраняет значение false, или пока не дойдем до конца этой последовательности. Если в процессе проверки окажется, что очередной проверяемый символ принадлежит алфавиту, инкрементируем счетчик слов count и указываем, что последовательность является словом, переходя таким образом к проверке следующего «потенциального слова» в предложении, если таковые имеются:

for(int i = 0; i < strlen(word) && !isWord; i++)
	if(AllowedSign(word[i])) {
		count++;
		isWord = true;
	}

for(int i = 0; i < strlen(word) && !isWord; i++)

if(AllowedSign(word[i])) {

count++;

isWord = true;

}

Наконец, как и в первом случае, выводим количество найденных слов:

cout << count;

1	cout << count;

Ссылки

Условие задачи на E-Olymp;

Коды программ на Ideone.com: посимвольное считывание, строки c-string;

Подтверждение решения на E-Olymp.

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;
}