Три задачи по программированию

1. Бесконечная ж/д с 2 паровозами с парашютами.
2. Запрограммировать лифт.
3. Отсортировать большой файл в бесконечной файловой системе.

Ниже есть продолжение.

Условия задач.

1. Бесконечная ж/д с 2 паровозами с парашютами. Дана прямая ветка ж/д неограниченной длинны, без петель. На неё в не заданный заранее местах садятся с парашютом два паровоза. После приземления, они отстёгивают парашют и он остаётся лежать в точке приземления. Требуется написать программу, две идентичных копии которой будут бежать в этих 2 паровозах. Цель программы, найти другой паровоз. При этом между паровозами на расстоянии нет никакой связи. Чтобы ещё больше усложнить задачу, задан очень ограниченный язык имеющий

moveLeft - поехать влево
moveRight - поехать враво

if(isOtherParachuteFound){
...
{ else {
...
}

- это единственный доступный оператор ветвления (if)


Более того, ваша программа должна быть внутри

while(!meet){
_PUT_YOU_CODE_HERE_
}

Пока паровозы не столкнулись, сделать что-то. Вместо что-то должна быть ваша программа.

Подчеркну: Переменных никаких нет, if-ов нет, кроме одного, приведенного выше, циклов - тоже нет.

2. Запрограммировать лифт. Дан лифт в многоэтажном доме. Пронумеруем этажи 0 (вход),1,2,...,n. На каждом этаже есть кнопки вверх и вниз. В самом лифте есть кнопки с указанием номера этажа. Если человек, хочет поехать вверх он нажимает, на кнопку вверх, если он хочет поехать вниз-вниз. Лифт должен развести всех людей, которые пользуются лифтом, совершая как можно меньше изменений в движении (каждое изменение, вместо того, чтобы ехать вверх-едем вниз, вместо того, чтобы ехать вверх-едем вниз, приводит к большой трате электроэнергии, а мы хотим её сэкономить). Опишите структуру данных, которую вы будете при этом использовать.


3. Отсортировать большой файл в бесконечной файловой системе. У вас есть очень большой файл, размером a (к примеру a=2 Gb) содержащих, к примеру, целые числа разделённые между собой с помощью \n. Весь файл целиком не помещается у вас в оперативной памяти, размером порядка b (скажем, у вас всего b~10 Mb памяти). При этом a/b не является O(1). Но у вас есть неограниченная в размерах файловая система, вам разрешается свободно писать и читать в неё, создавать сколько угодно новых файлов, менять уже существующие и т.п. Нужно отсортировать этот файл. Это может быть как существующий файл, так и новый, где все числа отсортированы в порядке возрастания.

Подсказки к решению задач, находятся тут.