Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
277 / 249 / 209
Регистрация: 14.11.2016
Сообщений: 946
1

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

28.09.2019, 18:11. Просмотров 924. Ответов 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.09.2019, 18:11
Ответы с готовыми решениями:

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

Error c2440 "невозможно преобразовать "std::string" в "std::string *" "
class file { public: string file_name; ... } int main() { file File, *r; r...

отсутствует оператор "<<" соответствующий этим операндам (std::ostream << const std::string)
В 20 строке подсвечиваются красным знаки &lt;&lt;. Пишет, что &quot;отсутствует оператор &quot;&lt;&lt;&quot; соответствующий...

Ошибка: отсутствует оператор ">>"; типы операндов: std::istream >> std::string
Привет всем! Кто-нибудь объясните пожалуйста, что не так, что от меня компилятор требует?

2
С чаем беда...
Эксперт CЭксперт С++
7860 / 3790 / 1040
Регистрация: 18.10.2014
Сообщений: 8,050
28.09.2019, 18:43 2
Лучший ответ Сообщение было отмечено anapshy как решение

Решение

Цитата Сообщение от anapshy Посмотреть сообщение
но почему-то set проглатывает b и её не обнаруживается
Так а чего же вы ожидали? Вы для std::set написали предикат greater который сравнивает только длины строк. Все строки одинаковой длины такой предикат считает одинаковыми. Разумеется, в ваш std::set теперь невозможно вставить больше одной строки каждой длины. Вставили "a". После этого "b" уже не вставится.
1
277 / 249 / 209
Регистрация: 14.11.2016
Сообщений: 946
28.09.2019, 19:13  [ТС] 3
TheCalligrapher, благодарю
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.09.2019, 19:13

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

Функция isspace и тип string: Не существует подходящей функции преобразования из "std::string" в "int"
Добрый день! Я только начинаю изучать язык c++ по книге &quot;Язык программирования С++. Базовый курс...

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

Ошибка "не найден оператор, принимающий правый операнд типа "const std::string" "
Привет. Подчеркивает Name. Как можно обратиться к public string из класса наследника? 1) Класс...

Error C2679: бинарный "<<": не найден оператор, принимающий правый операнд типа "std::string" (или приемлемое
эмулятор работы банкомата Например #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.