SoP

Дополнительные задания для школы программирования HH
Язык: Python
Версия языка: 2.7
Задание 1 - find_nearest_points.py
Задание 2 - find_balance.py

Оба скрипта поддерживают стардартные потоки ввода-вывода

Пример вызова скрипта с перенаправлением в Windows:
python scrip-name.py < input-file.txt

Кто использует другие ОС, думаю сами разберутся с перенаправлением потоков )

Для ручного ввода данные необходимо ввести данные, далее нажать клавишу "Enter",
далее для Windows сочетание клавиш Ctrl+Z, для Unix Ctrl+D.

Далее для Windows
Протестировать работоспособность первого задания можно выполнив команду:
python find_nearest_points.py < points.txt

Протестировать работоспособность второго задания можно выполнив команду:
python find_balance.py < balance_test_1.txt

Задание №1 - Минимальное расстояние
Дан набор из N точек на плоскости (для простоты можно считать, что у всех точек целочисленные координаты). Найдите минимальное расстояние между двумя точками из этого набора.

Пример входных данных:
10 10
20 10
20 15

Пример выходных данных:
5

Решение:

1. Сортируем точки сначала по координате X, а при равных X по Y.
   
2. Рекурсивно делим все точки на две части, соотвественно каждую часть еще на две части и т.д.
   
3. Выбираем наименьшее из расстояний между точками в левой и правой частях.
   
4. Далее обрабатываем точки которые находились на границе деления.
   
5. Выбираем точки которые находятся от границы деления по X не дальше наименьшего
   расстояния, для каждой точки определяем точки которые находятся по X и Y не дальше наименьшего расстояния. Рассчитываем расстояния между точками и выбираем наименьшее.

Задание №2 - Баланс весов
Дана конечная последовательность натуральных чисел. Считая их массами имеющихся в наличии предметов, определить, можно ли все эти предметы положить на весы так, чтобы весы находились в равновесии. Вывести вариант расположения. Определить, можно ли из них отобрать какое-то количество предметов с суммарным весом 100 (вывести yes или no, в зависимости от результата).

Пример входных данных:
2 4 3 6 5

Пример выходных данных:
2 3 5 - 4 6
no

Решение:

1. Сортируем все числа по возрастанию
   
2. Проверяем что сумма всех чисел делится на 2 без остатка
   
3. Находим половину от всей суммы, эту половину мы и будем искать для левой и правой частей
   
4. Далее в цикле проходим по графу чисел (первая версия была реализована как рекурсия, но при колчестве чисел свыше 1000, приложение достигало максимума вложенности функций, версия с циклом сложнее и медленее но работает для большого количества чисел)
   

для чисел 2 3 4 5 6 7 8 9
Граф выглядит примерно следующим образом:
2 - 3 - 4 - 5 - 6 - 7 - 8 - 9
| - 4 - 5 - 6 - 7 - 8 - 9
| - 5 - 6 - 7 - 8 - 9
| - 6 - 7 - 8 - 9
| - 7 - 8 - 9
| - 8 - 9
| - 9

3 - 4 - 5 - 6 - 7 - 8 - 9
| - 5 - 6 - 7 - 8 - 9
| - 6 - 7 - 8 - 9
| - 7 - 8 - 9
| - 8 - 9
| - 9

и т.д.

То есть от числа 2 идут ребра ко всем числам больше 2-х, от числа 3 ко всем числам больше 3-х и т.д.

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