Skip to content

Instantly share code, notes, and snippets.

@cyclotimia
cyclotimia / MengerHypercube
Created March 29, 2016 08:25
Prrof that k-hypercube is k-connected using Menger theorem
/*
Докажите, что k-мерный гиперкуб k-связен с помощью теоремы Менгера.
k-мерным гиперкубом называется граф, в котором вершины — битовые строки длины k,
а рёбра проведены между теми парами вершин, которые отличаются ровно в одном бите.
На вход подаётся две различные битовых строки A и B длины k<100 через пробел.
Выведите k простых путей в k-мерном гиперкубе из A в B, не пересекающихся по
внутренним вершинам.
Формат вывода: один путь на строку; путь – последовательности битовых строк, разделённая пробелами.
@cyclotimia
cyclotimia / haskell test
Last active August 19, 2023 09:59
haskell Test
{--
Реализуйте функцию, задающую циклическое вращение списка.
rotate :: Int -> [a] -> [a]
rotate n xs = undefined
При положительном значении целочисленного аргумента вращение должно осуществляться влево, при отрицательном - вправо.
GHCi> rotate 2 "abcdefghik"
"cdefghikab"
GHCi> rotate (-2) "abcdefghik"
@cyclotimia
cyclotimia / addTwoElements
Last active June 25, 2020 17:00
Stepic Haskell course - Chapter 3. Lists
addTwoElements :: a -> a -> [a] -> [a]
addTwoElements x y z = x : y : z
@cyclotimia
cyclotimia / Tarjan algorithm - FindCutPoints
Last active March 29, 2016 08:23
finding cut points in a graph
/*
задача: https://stepic.org/lesson/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0-%D0%B4%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D1%85-%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2-12342/step/11?unit=6526
Найдите все точки сочленения в графе.
На вход программе подаётся описание графа, состоящее не более чем из 100000 строк.
Каждая строка описывает очередное ребро: содержит два номера вершин, которые данное ребро соединяет.
Номера разделены пробелом. Гарантируется, что ребра определяют связный граф, вершины которого
пронумерованы числами от 0 до некоторого n.
@cyclotimia
cyclotimia / maxFlow
Last active March 29, 2016 08:21
Ford Fulkerson algorithm - Finding maximum flow
/*
задача: https://stepic.org/lesson/12344/step/10
Найдите максимальный поток в сети.
Первая строка содержит два числа 2≤v≤50 и 0≤e≤1000 — число вершин и число рёбер сети.
Следующие ee строк описывают рёбра: каждая из них содержит три целых числа через пробел:
0≤ui<v, 0≤vi<v, 0<ci<50 — исходящую и входящую вершины для этого ребра, а так же его
пропускную способность.
class Pair<T, M> {
private final T first;
private final M second;
// конструктор
private Pair(T value1, M value2) {
this.first = value1;
this.second = value2;
}
#include <iostream>
using namespace std;
unsigned strlen(const char *str) {
const char *start = str;
while ('\0' != *str) {
++str;
}
int l = str - start;