Матч 404, Чтение книг (ReadingBooks)

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

Каждая книга состоит из трех частей: вступление (“introduction”), основная часть (“story”) и наставление (“edification”). Когда читатель заканчивает прочтение какой-либо части, он заносит ее название в список. Из книги можно читать любое количество частей (даже 0) и в любом порядке. Но одну и туже часть из одной книги читать нельзя. Возвращаться к прочитанным книгам нельзя.

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

Класс: ReadingBooks

Метод: int countBooks(vector<string> readParts)

Ограничения: readParts содержит от 1 до 50 элементов, readParts[i] содержит “introduction”, “story” или “edification”.

Вход. Список прочитанных частей книг readParts.

Выход. Наибольшее количество книг, в которых могли быть прочитаны все три части.

Пример входа

readParts

{"introduction", "story", "introduction", "edification"}

{"introduction", "story", "edification", "introduction", "story", "edification"}

{"introduction", "story", "introduction", "edification", "story",

"story", "edification", "edification", "edification", "introduction",

"introduction", "edification", "story", "introduction", "story",

"edification", "edification", "story", "introduction", "edification",

"story", "story", "edification", "introduction", "story"}

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

1

2

5

РЕШЕНИЕ

перебор

Главы readParts[i], readParts[i + 1] и readParts[i + 2] могут принадлежать одной книге, если они попарно разные. Просматриваем список частей прочитанных книг слева направо. Если очередные три стоящие рядом части с номерами i, i + 1 и i + 2 разные, то увеличиваем результат res на 1. После чего продолжаем процесс просмотра частей, начиная с i + 3 - ей.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

class ReadingBooks

{

public:

int countBooks(vector<string> readParts)

{

int i, res;

if(readParts.size() < 3) return 0;

for(res = i = 0; i < readParts.size() - 2; i++)

if ((readParts[i] != readParts[i+1]) &&

(readParts[i+1] != readParts[i+2]) &&

(readParts[i+2] != readParts[i])) res++, i += 2;

return res;

}

};