| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб |
Необходимо реализовать класс PrimeNumberGenerator — генератор
простых чисел.
У класса должен быть конструктор,
принимающий (int start), и функция int GetNextPrime(),
возвращающая ближайшее справа от start-а простое число (включая start).
Функция GetNextPrime должна изменять состояние объекта — при повторном
ее вызове нужно возвращать уже следующее простое число.
class PrimeNumberGenerator {
public:
explicit PrimeNumberGenerator(int start);
int GetNextPrime();
};
Файл с решением должен содержать только реализацию описанного
класса, без функции main.
| Входной файл: | Стандартный вход | Ограничение времени: | 5 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб |
Вам необходимо написать .cpp файл с реализацией хедера num.h
В конструкторе Num необходимо сохранять значение value по модулю modulo!
По умолчанию modulo равно нулю, в таком случае value
сохраняется без взятия по модулю.
В конструкторе копирования требуется скопировать
только значение value, при этом modulo задается равным нулю.
| Входной файл: | Стандартный вход | Ограничение времени: | 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.
| Входной файл: | Стандартный вход | Ограничение времени: | 5 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб |
Вам необходимо написать .cpp файл с реализацией хедера num.h
| Входной файл: | Стандартный вход | Ограничение времени: | 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.
| Входной файл: | Стандартный вход | Ограничение времени: | 2 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 128 Мб |
Конструктор класса PageAllocator принимает размер блока в байтах
Функция Allocate выделяет блок размера, заданного в конструкторе
Данный класс реализовывать не нужно
class PageAllocator {
public:
explicit PageAllocator(std::uint64_t page_size);
void* Allocate();
};
Необходимо реализовать класс FixedAllocator, у которого должны быть:
Конструктор принимающий page_size — размер блока в элементах типа Tp
Функция Allocate возвращающая указатель на следующую свободную память
Если свободной памяти нет функция Allocate получает ее через объект page_allocator_
Функция Deallocate добавляющая указатель обратно в пул свободной памяти
Функция InnerAllocator возвращающая неизменяемую ссылку на объект page_allocator_
template<typename Tp>
class FixedAllocator {
PageAllocator page_allocator_;
public:
explicit FixedAllocator(std::uint64_t page_size);
Tp* Allocate();
void Deallocate(Tp* p);
const PageAllocator& InnerAllocator() const noexcept;
};
Таким образом вы должны выделять минимально возможное кол-во блоков памяти (кол-во вывозов Allocate у объекта page_allocator_)
Выделять память можно только с помощью данного объекта
Файл с решением должен содержать только реализацию класса FixedAllocator
| Входной файл: | Стандартный вход | Ограничение времени: | 25 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб |
Вам необходимо реализовать класс SmartPointer, интерфейс которого находится в файле SmartPointer.hpp,
а также реализовать вспомогательный класс Core.
При реализации класса SmartPointer нельзя добавлять новые поля.
| Входной файл: | Стандартный вход | Ограничение времени: | 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 Мб |
Необходимо реализовать класс 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 Мб |
Вам необходимо написать функцию initialize_vector(value, dim1, dim2, ...), принимающую значение и размерности, и возвращающую вектор заданных размерностей, заполненный этим значением.
Пример использования такой функции может быть следующим:
vector<vector<vector<int>>> v = initialize_vector(-1, 100, 50, 30)
Для реализации требуется использовать variadic templates
| Входной файл: | Стандартный вход | Ограничение времени: | 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 Мб |
Реализовать шаблонный класс визитора со следующим интерфейсом для использования в алгоритме поиска в ширину в неориентированном графе.
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 Мб |
Вам необходимо написать метафункцию
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 Мб |
Вам необходимо написать преобразование 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(???);
};