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

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

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


0.326s 0.013s 47