Задача A. PrimeNumberGenerator

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Необходимо реализовать класс PrimeNumberGenerator — генератор простых чисел.

У класса должен быть конструктор, принимающий (int start), и функция int GetNextPrime(), возвращающая ближайшее справа от start-а простое число (включая start).

Функция GetNextPrime должна изменять состояние объекта — при повторном ее вызове нужно возвращать уже следующее простое число.

      
         
class PrimeNumberGenerator {
  public:
    explicit PrimeNumberGenerator(int start);
    int GetNextPrime();
};
      
  

Материалы задачи

main.cpp

task.xml

Формат выходных данных

Файл с решением должен содержать только реализацию описанного класса, без функции main.


Задача B. Date

Входной файл:Стандартный вход   Ограничение времени: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.cpp

task.xml

Формат выходных данных

Файл с решением должен содержать только реализацию описанного класса, без функции main.


Задача C. Set

Входной файл:Стандартный вход   Ограничение времени: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 Data() const.

Предполагается, что класс будет использован для хранения целых чисел типа int64_t. Для хранения элементов следует использовать std::vector с соответствующим параметром шаблона.

Материалы задачи

main.cpp

task.xml

Формат выходных данных

Файл с решением должен содержать только реализацию описанного класса, без функции main.


Задача D. BufferedReader

Входной файл:Стандартный вход   Ограничение времени: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.cpp

task.xml

01.in

02.in

03.in

04.in

01.out

02.out

03.out

04.out

Формат выходных данных

Файл с решением должен содержать только реализацию описанного класса, без функции main.


Задача A. GameDatabase

Входной файл:Стандартный вход   Ограничение времени: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>>>
          
      

Материалы задачи

main.cpp

1.in

2.in

3.in

4.in

5.in

6.in

7.in

1.ans

2.ans

3.ans

4.ans

5.ans

6.ans

7.ans

Формат выходных данных

Файл с решением должен содержать только реализацию класса GameDatabase без функции main.


Задача B. Аллокатор для связного списка

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:4000 Мб

Условие

Аллокатор — это класс, который инкапсулирует управление памятью.

Известная проблема аллокации для связных списков состоит в том, что при интенсивных операциях вставки и удаления может возникнуть эффект фрагментации системной памяти. Чтобы снизить влияние этого эффекта, предлагается запрашивать у операционной системы память на группу объектов и оперировать полученным буфером, что также снижает количество системных вызовов.

Необходимо реализовать класс FixedAllocator, который будет использовать необходимое количество непрерывных буферов как пул памяти для элементов списка. Размер страницы (размер одного непрерывного буфера), как и размер объектов, передается аллокатору как параметр конструктора.

Определение класса должно содержать следующие методы:

FixedAllocator(size_t chunk_size, size_t page_size) — конструктор, принимающий размер страницы памяти и размер одного объекта;

void* Allocate() — возвращает указатель на свободный участок памяти для одного элемента размера chunk_size;

void Deallocate(void*) — возвращает в пул память, занимаемую элементом.

Список использует метод Allocate, когда необходимо получить память для одного элемента, и Deallocate, когда память нужно освободить.


Задача C. Фабрика

Входной файл:Стандартный вход   Ограничение времени: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 и вспомогательных классов, если необходимы.

Материалы задачи

main.cpp

task.xml


Задача D. Code format visitor

Входной файл:Стандартный вход   Ограничение времени: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.cpp

task.xml

Формат входных данных

Формат выходных данных

Файл с решением должен содержать только реализацию описанного класса, без функции main.


Задача A. Is convertable

Входной файл:Стандартный вход   Ограничение времени: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) и реализовать ей оператор () произвольным образом.

Материалы задачи

main.cpp

task.xml


Задача B. Graph visitor

Входной файл:Стандартный вход   Ограничение времени: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.

Материалы задачи

main.cpp

task.xml


Задача C. Binary/linear search

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:4000 Мб

Условие

Написать функцию

Iterator Find<T, Iterator>(const T& value, Iterator first, Iterator last),

которая принимает элемент и итераторы на отсортированную коллекцию и возвращает итератор на требуемый элемент (в случае отсутствия такого элемента, функция должна вернуть last).

В зависимости от типа итератора, данная функция должна использовать бинарный или линейный поиск (Бинарный поиск, если итератор является Random Access).

Материалы задачи

main.cpp

task.xml


Задача D. Merge

Входной файл:Стандартный вход   Ограничение времени: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

 

Материалы задачи

main.cpp

task.xml

Формат выходных данных

Файл с решением должен содержать функцию MergeAssociative


Задача E. Initialize vector

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:4000 Мб

Условие

Вам необходимо написать функцию initialize_vector(value, dim1, dim2, ...), принимающую значение и размерности, и возвращающую вектор заданных размерностей, заполненный этим значением.

Пример использования такой функции может быть следующим:

          
vector<vector<vector<int>>> v = initialize_vector(-1, 100, 50, 30)
          
      

Для реализации требуется использовать variadic templates

Материалы задачи

main.cpp

task.xml


Задача F. V2T + T2V

Входной файл:Стандартный вход   Ограничение времени: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);
        
    

Материалы задачи

main.cpp

task.xml

Формат выходных данных

Файл с решением должен содержать функции из условия


Задача A. Шифр Цезаря

Входной файл: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;
            }
        
    

Материалы задачи

main.cpp task.xml gen.cpp sol.cpp

Формат выходного файла

Файл с решением должен содержать функцию CaesarEncrypt


Задача B. Параллельное перемножение матриц

Входной файл:Стандартный вход   Ограничение времени: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-го элемента матрицы-результата не зависит от порядка вычисления остальных элементов, поэтому вы можете вычислять отдельные части матрицы-результата независимо в разных потоках без синхронизации между ними.

Тестирующая система будет проверять, что:

Материалы задачи

main.cpp task.xml

Задача C. Queue

Входной файл:Стандартный вход   Ограничение времени: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(???);
        };
    

Очередь должна уметь работать с объектами без конструктора копирования.

Материалы задачи

main.cpp task.xml

0.328s 0.006s 155