| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб |
Необходимо реализовать класс PrimeNumberGenerator — генератор
простых чисел.
У класса должен быть конструктор,
принимающий (int start), и функция int GetNextPrime(),
возвращающая ближайшее справа от start-а простое число (включая start).
Функция GetNextPrime должна изменять состояние объекта — при повторном
ее вызове нужно возвращать уже следующее простое число.
class PrimeNumberGenerator {
public:
explicit PrimeNumberGenerator(int start);
int GetNextPrime();
};
Файл с решением должен содержать только реализацию описанного
класса, без функции main.
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб |
Реализовать класс Date со следующими методами:
Конструктор Date(int year, int month, int day)
Метод bool IsLeap() const, возвращающий true в случае, если год является високосным и false в противном случае.
Метод std::string ToString() const, возвращающий строковое представление даты в формате dd.mm.yyyy.
Метод Date DaysLater(int days) const, возвращающий дату, которая наступит спустя days дней от текущей.
Метод int DaysLeft(const Date& date) const, возвращающий разницу между указанной и текущей датой (в днях).
Файл с решением должен содержать только реализацию описанного класса, без функции main.
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб |
Необходимо реализовать Set — класс,
в котором реализованы основные операции над множествами:
Set Union(const Set&) const,
Set Intersection(const Set&) const,
Set Difference(const Set&) const,
Set SymmetricDifference(const Set&) const.
Также необходимо
реализовать конструктор Set(const std::vector и функции добавления, удаления и проверки
наличия элемента во множестве:
void Add(int64_t),
void Remove(int64_t), bool Contains(int64_t) const.
Для доступа ко всем элементам множества реализовать функцию std::vector.
Предполагается, что класс будет использован для хранения целых чисел типа int64_t. Для хранения элементов
следует использовать std::vector с соответствующим параметром шаблона.
Файл с решением должен содержать только реализацию описанного класса, без функции main.
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб |
Требуется реализовать класс BufferedReader со следующим интерфейсом:
class BufferedReader {
public:
explicit BufferedReader(PackageStream* stream);
int32_t Read(char* output_buffer, int32_t buffer_len);
};
В конструктор BufferedReader передается указатель на объект класса PackageStream (см. описание ниже), с помощью которого будут считываться пакеты некоторой длины.
Метод int32_t Read(char* output_buffer, int32_t buffer_len) записывает по указателю output_buffer пакет длины не более buffer_len и возвращает реальный размер записанного пакета (это число может быть меньше, чем заданная длина, если строка закончилась раньше).
Интерфейс класса PackageStream:
class PackageStream {
public:
PackageStream(std::string source, int32_t package_len);
int32_t PackageLen() const;
int32_t ReadPackage(char* output_package);
};
В конструктор PackageStream передается строка source, из которой впоследствии побайтово будут считываться пакеты длины package_len и, собственно, длина пакетов package_len.
Метод int32_t PackageLen() возвращает длину пакета (package_len), который считывает метод ReadPackage.
Метод int32_t ReadPackage(char* output_package) записывает по указателю output_package пакет длины не более package_len и возвращает реальный размер записанного пакета.
Файл с решением должен содержать только реализацию описанного класса, без функции main.
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4000 Мб |
Необходимо реализовать класс GameDatabase cо следующим интерфейсом:
class GameDatabase
{
public:
GameDatabase() = default;
/// вставляет в базу объект с именем [name] и позицией [x, y]
/// если объект с таким id в базе уже есть, заменяет его новым
void Insert(ObjectId id, string name, size_t x, size_t y)
/// удаляет элемент по id
/// если такого элемента нет, ничего не делает
void Remove(ObjectId id);
/// возвращает вектор объектов c именем [name]
/// сортировка по убыванию id
vector<GameObject> DataByName(string name) const;
/// возвращает вектор объектов, находящихся в позиции [x, y]
/// сортировка по убыванию id
vector<GameObject> DataByPosition(size_t x, size_t y) const;
/// возвращает вектор всех объектов из базы
/// сортировка по убыванию id
vector<GameObject> Data() const;
};
Код для GameObject и ObjectId указан ниже.
using ObjectId = unsigned long long int;
struct GameObject
{
ObjectId id;
string name;
size_t x;
size_t y;
};
Рекомендуется использовать структуры данных: std::unordered_map, std::map, std::set
Отдельная сортировка не потребуется если использовать компаратор для упорядоченных контейнеров (std::set, std::map)
Пример организации данных с компаратором:
bool operator>(const GameObject& a, const GameObject& b) {
return a.id > b.id;
}
template<class Tp, template<class> class Compare>
class DereferenceCompare {
Compare<Tp> comp;
public:
bool operator()(const Tp* const a, const Tp* const b) const {
return comp(*a, *b);
}
};
/// быстрый доступ по id
std::map<ObjectId, GameObject, std::greater<ObjectId>>
/// быстрый доступ по позиции
std::map<std::pair<size_t, size_t>, std::set<GameObject*, DereferenceCompare<GameObject, std::greater>>>
/// быстрый доступ по имени
std::unordered_map<string, std::set<GameObject*, DereferenceCompare<GameObject, std::greater>>>
Файл с решением должен содержать только реализацию класса GameDatabase без функции main.
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4000 Мб |
Аллокатор — это класс, который инкапсулирует управление памятью.
Известная проблема аллокации для связных списков состоит в том, что при интенсивных операциях вставки и удаления может возникнуть эффект фрагментации системной памяти. Чтобы снизить влияние этого эффекта, предлагается запрашивать у операционной системы память на группу объектов и оперировать полученным буфером, что также снижает количество системных вызовов.
Необходимо реализовать класс FixedAllocator, который будет использовать необходимое количество непрерывных буферов как пул памяти для элементов списка. Размер страницы (размер одного непрерывного буфера), как и размер объектов, передается аллокатору как параметр конструктора.
Определение класса должно содержать следующие методы:
FixedAllocator(size_t chunk_size, size_t page_size) — конструктор, принимающий размер страницы памяти и размер одного объекта;
void* Allocate() — возвращает указатель на свободный участок
памяти для одного элемента размера chunk_size;
void Deallocate(void*) — возвращает в пул память, занимаемую элементом.
Список использует метод Allocate, когда необходимо получить
память для одного элемента, и Deallocate, когда память нужно
освободить.
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4096 Мб |
Реализуйте паттерн проектирования "Фабрика".
Фабрика может создавать произвольных потомков базового класса. В нашем случае
базовым классом будет Object, а сама фабрика — классом Factory.
Определение класса Object должно быть в точности таким:
class Object {
public:
virtual std::string ToString() const = 0;
virtual ~Object() {}
};
Метод ToString является абстрактным. Это означает, что все потомки
Object обязаны перегрузить этот метод.
Ваша фабрика должна уметь понимать, потомка какого типа от неё хотят получить в данный момент. Это означает, что у каждого потомка должен быть некоторый идентификатор. В этом задании будем использовать строковые идентификаторы.
Фабрика поддерживает всего две операции. Одна из них:
Object* Create(const std::string& class_id) — этот метод
класса Factory
получает на вход идентификатор класса, создает экземпляр этого класса
и возвращает указатель на созданный экземпляр.
Сразу после конструирования ваша фабрика должна уметь создавать потомков с
идентификаторами "apple!", "list" и "yet another identifier". В этом задании
все потомки Object при вызове ToString должны
возвращать свои идентификаторы.
Например, код
Factory factory;
Object* apple_instance_ptr = factory.Create("apple!");
cout << apple_instance_ptr->ToString() << endl;
должен печатать "apple!".
Чтобы не было скучно, ваша фабрика должна поддерживать создание любых потомков
Object. Для этого существует операция регистрации:
void Register(const std::string& class_id, Object*(*instance_creator)()) —
этот метод связывает идентификатор класса class_id
с порождающей функцией instance_creator.
Параметр instance_creator — это указатель на функцию, которая
возвращает указатель на наследника Object.
Пример использования:
Factory factory;
factory.Register("smth", new_smth);
Object* smth_instance_ptr = factory.Create("smth");
cout << smth_instance_ptr->ToString() << endl;
Где new_smth это функция, объявленная как Object* new_smth();
Файл с решением должен содержать только реализацию классов Factory и Object и вспомогательных классов, если необходимы.
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4000 Мб |
Вам заданны классы узлов синтаксического дерева программы, необходимые для описания объявления класса, методов класса и полей класса.
class ClassDeclarationNode;
class VarDeclarationNode;
class MethodDeclarationNode;
class BaseNode;
class BaseVisitor {
public:
virtual void Visit(const BaseNode* node) = 0;
virtual void Visit(const ClassDeclarationNode* node) = 0;
virtual void Visit(const VarDeclarationNode* node) = 0;
virtual void Visit(const MethodDeclarationNode* node) = 0;
};
class BaseNode {
public:
virtual void Visit(BaseVisitor* visitor) const = 0;
};
class ClassDeclarationNode: public BaseNode {
public:
const std::string& ClassName() const;
const std::vector<BaseNode*>& PublicFields() const;
const std::vector<BaseNode*>& ProtectedFields() const;
const std::vector<BaseNode*>& PrivateFields() const;
void Visit(BaseVisitor* visitor) const override {
visitor->Visit(this);
}
};
class VarDeclarationNode: public BaseNode {
public:
const std::string& VarName() const;
const std::string& TypeName() const;
void Visit(BaseVisitor* visitor) const override {
visitor->Visit(this);
}
};
class MethodDeclarationNode: public BaseNode {
public:
const std::string& MethodName() const;
const std::string& ReturnTypeName() const;
const std::vector<BaseNode*>& Arguments() const;
void Visit(BaseVisitor* visitor) const override {
visitor->Visit(this);
}
};
Требуется реализовать класс FormatVisitor, который будет позволять получать отформатированное представление программы в виде строки,
в соответствии с синтаксисом языка C++ и Google Style Guide.
class FormatVisitor: public BaseVisitor {
public:
void Visit(const BaseNode* node) override {
node->Visit(this);
}
void Visit(const ClassDeclarationNode* node) override;
void Visit(const VarDeclarationNode* node) override;
void Visit(const MethodDeclarationNode* node) override;
const std::vector<std::string>& GetFormattedCode() const;
};
Файл с решением должен содержать только реализацию описанного класса, без функции main.
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4000 Мб |
Вам необходимо написать метафункцию
is_customly_convertible<A, B>
, которая проверяет, существует ли специализация структуры Convert для типов A и B.
Интерфейс функции должен соответствовать аналогичным функциям из модуля type_traits, например is_same
Специализация структуры Convert может выглядеть следующим образом:
template < >
struct Convert<int, float> {
float operator()(const int& a) {
return a;
}
};
Также необходимо реализовать 2 структуры: NoTriviallyConstructible — структуру без дефолтного конструктора и NoCopyConstructible — структуру без конструктора копирования. (Это единственные требования к структурам, все остальное — неважно)
Для вышеописанных структур требуется добавить специализацию функтора Convert: для (NoTriviallyConstructible, int) и (NoCopyConstructible, NoTriviallyConstructible) и реализовать ей оператор () произвольным образом.
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4000 Мб |
Реализовать шаблонный класс визитора со следующим интерфейсом для использования в алгоритме поиска в ширину в неориентированном графе.
template<Vertex>
class BfsVisitor {
public:
void ExamineVertex(const Vertex& vertex);
void DiscoverVertex(const Vertex& vertex);
size_t DistanceTo(const Vertex& target) const;
Vertex Parent(const Vertex& vertex) const;
}
Объект данного класса будет использован функцией обхода графа в ширину, аналогичной данной. Метод ExamineVertex
будет вызван в момент извлечения вершины из очереди, метод DiscoverVertex будет вызван в момент добавления вершины в очередь.
После обхода графа визитор должен хранить кратчайшие расстояния от начальной
вершины до всех остальных. Для получения расстояния до вершины будет использован метод DistanceTo.
Также, в процессе обхода в ширину визитор должен построить соответствующее такому обходу остовное дерево графа.
Метод Parent будет использован для получения предка каждой вершины в таком графе. Родителем корневой вершины является она сама.
Экземпляр визитора передается в функцию по значению, и для эффективного копирования
его размер должен быть не больше размера shared_ptr.
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4000 Мб |
Написать функцию
Iterator Find<T, Iterator>(const T& value, Iterator first, Iterator last),
которая принимает элемент и итераторы на отсортированную коллекцию и возвращает итератор на требуемый элемент (в случае отсутствия такого элемента, функция должна вернуть last).
В зависимости от типа итератора, данная функция должна использовать бинарный или линейный поиск (Бинарный поиск, если итератор является Random Access).
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4000 Мб |
Необходимо реализовать функцию MergeAssociative, которая принимает 2 ассоциативных контейнера и добавляет содержимое второго к первому
Возвращает false если операцию можно выполнить (см. далее), иначе возвращает true
template<class C1, class C2>
bool MergeAssociative(C1* c1, const C2& c2)
С контейнерами имеющимися в стандартной библиотеке C++ можно ознакомиться здесь
Операцию можно выполнить если верны 3 условия:
1) Оба типа являются ассоциативными контейнерами
2) Их типы элементов совпадают, не учитывая cv qualifiers
3) Первый контейнер является мультиконтейнером или оба ими не являются
Мультиконтейнерами в данном случае названы следующие: multiset, unordered_multiset, multimap, unordered_multimap
Примеры пар типов, для которых операцию выполнить можно:
multiset<int> + set<int>
map<int, int> + unordered_map<int, int>
multimap<int, const int> + unordered_map<int, volatile int>
Для которых нельзя:
set<int> + multiset<int>
set<int> + set<double>
int + double
Файл с решением должен содержать функцию MergeAssociative
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4000 Мб |
Вам необходимо написать функцию initialize_vector(value, dim1, dim2, ...), принимающую значение и размерности, и возвращающую вектор заданных размерностей, заполненный этим значением.
Пример использования такой функции может быть следующим:
vector<vector<vector<int>>> v = initialize_vector(-1, 100, 50, 30)
Для реализации требуется использовать variadic templates
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4000 Мб |
Вам необходимо написать преобразование TupleToVector и обратное для него VectorToTuple
Типы на выходе должны быть без cv qualifiers и ссылок
tuple<vector<T1>, vector<T2>, vector<T3>, ...> ==> vector<tuple<T1, T2, T3, ...>>
vector<tuple<T1, T2, T3, ...>> ==> tuple<vector<T1>, vector<T2>, vector<T3>, ...>
tuple<vector<int>, vector<double>, vector<char>> tpl;
const tuple<const vector<int>, const vector<double>, vector<char>> tpl2;
vector<tuple<int, double, char>> vec;
const vector<tuple<const int, double, const char>> vec2;
static_assert(std::is_same_v<decltype(VectorToTuple(vec)), decltype(tpl)>);
static_assert(std::is_same_v<decltype(TupleToVector(tpl)), decltype(vec)>);
static_assert(std::is_same_v<decltype(VectorToTuple(vec2)), decltype(tpl)>);
static_assert(std::is_same_v<decltype(TupleToVector(tpl2)), decltype(vec)>);
vector<int> v1, v2, v3;
static_assert(std::is_same_v<decltype(TupleToVector(tuple<const vector<int>&, const vector<int>&, const vector<int>&>{v1, v2, v3})),
vector<tuple<int, int, int>>>);
Если возможно, функции должны возвращать 'удобные' типы вместо std::tuple, а так же принимать их в кач-ве параметра
В частности tuple размера 2 должен быть преобразован в pair, а размера 1 в тип первого элемента
tuple<vector<int>, vector<double>> tpl;
vector<pair<int, double>> vec = TupleToVector(tpl); // tuple<vector<int>, vector<double>> -> vector<tuple<int, double>> -> vector<pair<int, double>>
vector<tuple<int, double>> vec2;
pair<vector<int>, vector<double>> tpl2 = VectorToTuple(vec2) // vector<tuple<int, double>> -> tuple<vector<int>, vector<double>> -> pair<vector<int>, vector<double>>
// *******************
tuple<vector<int>> tpl;
vector<int> vec = TupleToVector(tpl); // tuple<vector<int>> -> vector<tuple<int>> -> vector<int>
vector<tuple<int>> vec2;
vector<int> tpl2 = VectorToTuple(vec2) // vector<tuple<int>> -> tuple<vector<int>> -> vector<int>
// *******************
vector<int> vec;
vec = VectorToTuple(vec);
vec = TupleToVector(vec);
// *******************
vector<pair<int, char>> vp;
pair<vector<int>, vector<char>> pv = VectorToTuple(vp);
vp = TupleToVector(pv);
Файл с решением должен содержать функции из условия
| Входной файл: | input.txt | Ограничение времени: | 60 сек | |
| Выходной файл: | output.txt | Ограничение памяти: | 4000 Мб |
Необходимо реализовать функцию CaesarEncrypt обрабатывающую шифром Цезаря (правый сдвиг на 3) входную строку
в несколько потоков
Гарантируется, что строка будет состоять только из маленьких латинских букв в кодировке ASCII
void CaesarEncrypt(std::string* s);
Функция должна отрабатывать быстрее (по системному времени), чем следующая:
void CaesarEncryptOneThread(std::string* s)
{
for (char& c : *s)
c = 'a' + (c + 3 - 'a') % 26;
}
Файл с решением должен содержать функцию CaesarEncrypt
| Входной файл: | Стандартный вход | Ограничение времени: | 15 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4000 Мб |
Вам дан класс с основными функциями для реализации матриц со следующим интерфейсом.
class DenseMat {
public:
DenseMat(int32_t rows = 0, int32_t cols = 0);
DenseMat(int32_t rows, int32_t cols, const std::vector<int32_t>& data);
int32_t Rows() const;
int32_t Cols() const;
const int32_t& operator()(int row, int col) const;
int32_t& operator()(int row, int col);
bool operator==(const DenseMat& other) const;
bool operator!=(const DenseMat& other) const;
};
Требуется реализовать функцию DenseMat MatMulParal(const DenseMat& a, const DenseMat& b, int thread_count); , которая выдает результат умножения матрицы a на матрицу b.
Функция должна использовать алгоритм параллельного умножения матриц, используя thread_count потоков.
При перемножении матриц вычисление каждого i, j-го элемента матрицы-результата не зависит от порядка вычисления остальных элементов,
поэтому вы можете вычислять отдельные части матрицы-результата независимо в разных потоках без синхронизации между ними.
Тестирующая система будет проверять, что:
| Входной файл: | Стандартный вход | Ограничение времени: | 5 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 4000 Мб |
Вам необходимо реализовать thread-safe очередь со следующими методами:
template <typename T>
class Queue {
public:
T Pop();
size_t Size();
template <typename U>
void Push(???);
template <typename ... U>
void Emplace(???);
};