Задача A. Slicer ≡

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

Условие

В этой задаче нужно разработать шаблон Slicer, который разбивает содержимое контейнера на несколько страниц.

Пример, когда такое может пригодиться, — распределение списка приложений по экранам телефона. На вход функции поступает вектор приложений, и нам нужно разбить этот вектор по страницам фиксированного размера. Сделать это можно было бы таким кодом:

          

vector<vector<Application>> DistributeAmongScreens(const vector<Application>& apps) {
  vector<vector<Application>> result;
  for (const auto& page : Slice(apps, 20)) {
    result.push_back({page.begin(), page.end()});
  }
  // result[0] -- все приложения, которые попадают на первый экран
  // result[1] -- все приложения, которые попадают на второй экран
  // и т.д.
  return result;
}

          
      

Класс Slicer должен обладать следующими свойствами:

• он имеет один шаблонный параметр — тип итератора;
• конструктор класса Slicer принимает три параметра: пара итераторов begin и end, задающие полуинтервал [begin; end), который мы будем нарезать на страницы, и page_size — размер одной страницы;
• по объектам класса Slicer можно проитерироваться с помощью цикла range-based for;
• класс Slicer имеет метод size_t size() const, который возвращает количество страниц, на которые был разбит переданный контейнер;
• сами страницы должны так же поддерживать итерацию с помощью range-based for и иметь метод size_t size() const, возвращающий количество объектов в этой странице.

Кроме того разработайте шаблонную функцию Slice, которая принимает ссылку на контейнер и размер страницы, и возвращает объект класса Slicer<It>.

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

main.cpp

solution_template.h

---

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

---

Задача 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. Место для вашей задачи ≡

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

Условие

В виде Answer text отправьте сюда задачу, которую вы придумали.

---