Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
 Аватар для anapshy
531 / 272 / 220
Регистрация: 14.11.2016
Сообщений: 1,052

Std::set проглатывает std::string{"b"}

28.09.2019, 18:11. Показов 1377. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Олимпиадное задание.
Задание
Мультиклавиатура — это обычная клавиатура с множеством выходов, каждый из которых можно подключить к одному персональному компьютеру.
Недавно в серверную одной очень большой и очень секретной конторы установили мультиклавиатуру. Последняя была подключена к N компьютерам. Таким образом, при нажатии клавиши, символ печатается сразу на всех машинах. Но вот незадача: кабели мультиклавиатуры оказались чрезвычайно хлипкими, и если отсоединить кабель от компьютера, то подключить его вновь не удастся.
Рабочий день уже в самом разгаре, и срочно требуется напечатать на каждом компьютере по заданной строке.
В конце набора на каждом компьютере должна быть набрана в точности заданная строка.
Определите, за какое минимальное количество нажатий клавиш мультиклавиатуры возможно напечатать все заданные строки на компьютерах.

Входные данные
В первой строке входного файла задано целое число T — количество тестов (1 ≤ T ≤ 100).
Далее следует T блоков.
В первой строке блока задано целое число N — количество компьютеров, к которым подключена мультиклавиатура (1 ≤ N ≤ 10^5).
В каждой i-ой из следующих строк задана непустая строка Si-я , которую требуется напечатать на i-ом компьютере.
Выходные данные
В выходной файл выведите T строк, в i-й строке — ответ на i-й тестовый пример.
Если напечатать заданные строки невозможно, ответом должно быть слово Impossible.
В противном случае требуется вывести одно целое число — минимальное количество нажатий клавиш мультиклавиатуры, с помощью которых можно напечатать заданные строки.
Пример input.txt файла
2
3
aba
abacaba
abca
2
hello
hell

Пример output.txt файла
Impossible
5

Реализовал код с использованием vector, и с использованием set.
КОД
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <cctype>

#define TEST

// Выбрать контейнер сдесь!!!
//#define SET
#define VECTOR

struct greater
{
greater(void) = default;
bool operator()(const std::string &lhs, const std::string &rhs)
{
return (lhs.size() > rhs.size());
}
};

int main()
{
std::fstream fin{ "input.txt", std::ios_base::in };
std::fstream fout{ "output.txt", std::ios_base::out
| std::ios_base::trunc };
std::size_t testNums{};

// Считываем кол-во тестов
fin >> testNums;

#ifdef TEST
std::cout << "All tests: " << testNums << std::endl;
#endif

// Идем по каждому из тестов
for (std::size_t i{}; i < testNums; ++i)
{
#ifdef TEST
std::cout << "\n________ Test #" << (i + 1) << " ________" << std::endl;
#endif
// Считываем кол-во строк
std::size_t strNums{};
fin >> strNums;

#ifdef TEST
std::cout << "All strings: " << strNums << std::endl << std::endl;
#endif

#ifdef SET
std::set<std::string, greater> data{}; // строки отсортированные по размеру (от больших к меньшим)
#endif
#ifdef VECTOR
std::vector<std::string> data{};
#endif
{
// Читаем строки и сохраняем в data
std::string str{};
for (std::size_t j{}; j < strNums; ++j)
{
fin >> str;

#ifdef TEST
std::cout << "["<< (j + 1) <<"] Readed string: '" << str << "'" << std::endl;
#endif

#ifdef SET
data.insert(std::move(str));
#endif
#ifdef VECTOR
data.emplace_back(std::move(str));
#endif
}
}

// Сортировка строк по размеру. От длинных к коротким.
#ifdef VECTOR
std::sort(data.begin(), data.end(), greater{});
#endif

#ifdef TEST
std::cout << std::endl;
std::cout << "\tData: " << std::endl;
for (auto &it : data)
{
std::cout << "> '" << it << "'" << std::endl;
}
std::cout << std::endl;
#endif

// Получаем первую самую длинную строку
auto itData = data.cbegin();
auto& sLongest = *itData++; // самая длинная строка
bool isEnter = true; // Ввод строк возможен?
// Идем по оставшимся строкам
while (itData != data.cend())
{

#ifdef TEST
std::cout << "> Comparsion '" << sLongest << "' & '" << *itData << "'" << std::endl;
#endif

// Сравниваем первую строки по символьно с длинной строкой sLongest
for (auto it = sLongest.cbegin(), it2 = itData->cbegin();
(it != sLongest.cend()) && (it2 != itData->cend());
++it, ++it2)
{
if (*it != *it2)
{ // Если символы не сошлись, значит все строки ввести не получится

#ifdef TEST
std::cout << "!!! isEnter = false !!!" << std::endl;
#endif
isEnter = false;
break;
}
}
if (!isEnter)
{
break;
}
++itData; // переход к следующей строке
}

if (!isEnter)
{ // Если строку ввести не возможно
fout << "Impossible" << std::endl;

#ifdef TEST
std::cout << "ANSWER: " << "Impossible" << std::endl << std::endl;
#endif

}
else
{ // Если строку ввести возможно
// !!! Количество символов в самой длинной строке и будет кол-вом минимальных нажатий !!!
fout << sLongest.size() << std::endl;

#ifdef TEST
std::cout << "ANSWER: " << sLongest.size() << std::endl << std::endl;;
#endif

}
}

#ifdef TEST
std::system("pause");
#endif
}

Сделал тестовый набор.
Тестовый набор (input.txt)
2
2
ab
aba
3
ab
a
b
Решением на данный набор является 3 Imposible.
НО, если использовать set, тогда во втором наборе теста читаются все строки, но почему-то set проглатывает b и её не обнаруживается в наборе и выдает output файл с ответами 3 2. Почему? С vector всё работает нормально.

Для смены контейнеров set на vector, vector на set юзайте дефайны после инклюдов.
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
28.09.2019, 18:11
Ответы с готовыми решениями:

ошибка error: cannot convert 'std::string {aka std::basic_string<char>}' to 'std::string* {aka std::basic_stri
на вод поступают 2 строки типа string. определить количество вхождений строки 2 в строку 1 ошибка error: cannot convert 'std::string {aka...

"range-base for" и проверка на последний элемент в std::set<std::string>
Добрый день. Голова совсем не варит. Как мне организовать простую проверку на послений элемент без введения счетчика а просто сравнивая...

STL std::set, std::pair, std::make_pair
Я не знаю как описать тему в двух словах, поэтому не обращайте внимание на название темы. Собственно перейдем к нашим баранам: есть...

2
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12937 / 6804 / 1821
Регистрация: 18.10.2014
Сообщений: 17,220
28.09.2019, 18:43
Лучший ответ Сообщение было отмечено anapshy как решение

Решение

Цитата Сообщение от anapshy Посмотреть сообщение
но почему-то set проглатывает b и её не обнаруживается
Так а чего же вы ожидали? Вы для std::set написали предикат greater который сравнивает только длины строк. Все строки одинаковой длины такой предикат считает одинаковыми. Разумеется, в ваш std::set теперь невозможно вставить больше одной строки каждой длины. Вставили "a". После этого "b" уже не вставится.
1
 Аватар для anapshy
531 / 272 / 220
Регистрация: 14.11.2016
Сообщений: 1,052
28.09.2019, 19:13  [ТС]
TheCalligrapher, благодарю
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
28.09.2019, 19:13
Помогаю со студенческими работами здесь

Поиск в std::vector < std::pair<UInt32, std::string> >
Подскажите пожалуйста, как осуществить поиск элемента в std::vector &lt; std::pair&lt;UInt32, std::string&gt; &gt; по ключу, а...

На основе исходного std::vector<std::string> содержащего числа, создать std::vector<int> с этими же числами
подскажите есть вот такая задача. Есть список . Создать второй список, в котором будут все эти же числа, но не в виде строк, а в виде...

std::string Зачем нужен std::string::compare, если есть перегруженный оператор ==?
Зачем нужен std::string::compare, если есть перегруженный оператор ==?

Запрошено преобразование от ‘const std::string*’ к нескалярному типу ‘std::string’
private: std::string firstName; }; std::string ClientData::getFirstName() const{ return firstName; } Дает в итоге...

Как удалить символ '—' из std::string, используя std::string::erase?
for(auto it = words.begin(); it!=words.end();) { if( *it == '—' ) { it = words.erase(it); ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Символьное дифференцирование
igorrr37 13.02.2026
/ * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru