Задача 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.


Problem B. Finite Field (Easy version)

Input file:Standard input   Time limit:5 sec
Output file:Standard output   Memory limit:512 Mb

Statement

You are to create .cpp file with implementation of num.h

Constructor of Num should store value modulo modulo. By default, modulo is equal to 0. In that case modulo operation should not be applied to value.

Copy constructor should only copy value value. modulo must be set to zero in copy constructor.

Materials

main.cpp

task.xml

num.h


Задача C. 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.


Problem D. Set

Input file:Standard input   Time limit:1 sec
Output file:Standard output   Memory limit:512 Mb

Statement

You are to implement class Set in which the basic operations on sets are implemented:

Set Union(const Set&) const,

Set Intersection(const Set&) const,

Set Difference(const Set&) const,

Set SymmetricDifference(const Set&) const.

It is also necessary to implement a constructor Set(const std::vector&) and functions for adding, removing and checking the presence of an element in the set:

void Add(int64_t),

void Remove(int64_t), bool Contains(int64_t) const.

Also, implement the method std::vector Data() const that will be used to access the elements of the set.

The class is supposed to be used to store integers of type int64_t. For storing items you should use std::vector with the appropriate template parameter

Materials

main.cpp

task.xml

Output format

The file with the solution must contain only the implementation of the described class, without a main


Problem E. Finite Field (Hard version)

Input file:Standard input   Time limit:5 sec
Output file:Standard output   Memory limit:512 Mb

Statement

You are to create .cpp file with implementation of num.h

Materials

main.cpp

task.xml

num.h


Задача F. 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. FixedAllocator

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

Выделять память можно только с помощью данного объекта

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

main.cpp

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

Файл с решением должен содержать только реализацию класса FixedAllocator


Задача B. Smart Pointer

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

Условие

Вам необходимо реализовать класс SmartPointer, интерфейс которого находится в файле SmartPointer.hpp, а также реализовать вспомогательный класс Core.

Ограничение

При реализации класса SmartPointer нельзя добавлять новые поля.

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

main.cpp

SmartPointer.hpp

task.xml

Test_SmartPointer.hpp

Test.hpp


Задача 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.


Задача E. 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.


Задача A. 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


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

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

Условие

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

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

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

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

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

main.cpp

task.xml


Задача C. 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


Задача D. 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


Задача E. 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


Задача 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

1.438s 0.020s 191