Вопрос к программистам

Мне вот интересно, в состоянии ли находящиеся здесь программисты решить задания, предлагаемые школьникам на олимпиадах?

Вот, например, задача:

Задача. Суперкарго (30 баллов)
Ограничение по времени - 1 сек.

В далёком будущем всё достижимое космическое пространство разбито на кубы трёхмерной декартовой системой координат. В каждой точке пространства, в которой все 3 координаты являются целыми числами, находится космическая база. Торговый космический корабль должен пролететь по замкнутому маршруту, посетив заданные космические базы. Полёт между двумя базами А и В происходит по прямой, при этом посещаются все промежуточне базы, встретившиеся на отрезке АВю По заданному замкнутому маршкруту требуется определить число баз, которое посетит торговый корабль.

Входные данные
Во входном файле INPUT.TXT содержится описание маршрута, представляющего собой трёхмерную замкунутую ломаную. Первая строка содержит натуральное чило N (1<=n<=1000) - Число вершин ломаной.
Следующие n строк содержат по 3 целых числа a, b, c(1<=a,b,c<=10000) через пробел - координаты очередной посещаемой базы. Известно, что одна и та же база (точка) не повторяется в последовательности два раза подряд.

Выходные данные
В выходной файл OUTPUT.TXT нужно выдать количество точек с целыми координатами, находящиеся на заданной ломаной.

Пример INPUT.TXT
4
1 0 0
1 2 3
21 17 13
-9 5 -5

OUTPUT.TXT для примера
17

------
Решение - на любом компилируемом языке...

И, интересно, сколько Вам понадобится времени что бы решить одну такую задачу.

Ну в принципе вроде ничего сложного особо нет... Решаемо
Я думаю несколько часов...

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

Цитата ("Hungry_Hunter"):

Ну в принципе вроде ничего сложного особо нет... Решаемо
Я думаю несколько часов...

Вы уверены?
Задач на олимпиаде 6. Времени: 3 часа
Соответственно, логично можно предположить, что на решение задачи: 30 минут

Кашмар какой... На то это и олимпиада... Бедные детишки

Это при том, что учителя информатики, которые должны учить детей решать такие задачи - сами в вопросе некомпетентны

"Навскидку"
Выбираем 2 соседние точки ломанной (1 отрезок)
По 2-м точкам оотрезка получаем уравнение прямой.
Перебираем все целые X от одной точки до другой.
Подставляем в уравнение прямой, получаем Y и Z. Если они оба - целые - пишем координаты в массив. Если нужно - проходимся по массиву, ищем те же координаты. Если не находим - увеличиваем счетчик на 1.
Берем следующий отрезок.

Разумеется, алгоритм можно оптимизировать. Но работать должен.

(оптимизация)
Например можно решить уравнение прямой на предмет целых чисел и проверить их попадание в отрезок.

Вопрос: уравнение прямой для 3-мерной системы координат?

Или сначала составляется уравнение для x и y. Находится y, а потом составляется для y и z?

посилання
посилання

(x-x0)/k = (y-y0)/l = (z-z0)/m

А вот это человек, участвующий в олимпиаде, должен знать.

Цитата:

И, интересно, сколько Вам понадобится времени что бы решить одну такую задачу.

50$

Цитата ("Onym"):

"Навскидку"
Выбираем 2 соседние точки ломанной (1 отрезок)
По 2-м точкам оотрезка получаем уравнение прямой.
Перебираем все целые X от одной точки до другой.
Подставляем в уравнение прямой, получаем Y и Z. Если они оба - целые - пишем координаты в массив. Если нужно - проходимся по массиву, ищем те же координаты. Если не находим - увеличиваем счетчик на 1.
Берем следующий отрезок.

Разумеется, алгоритм можно оптимизировать. Но работать должен.

Наверняка, на тестах подберут такие длинные отрезки, что перебор по всем x не пройдёт по времени.

Вопрос в том, как по формуле прямой по двум точкам вычислить, сколько там целых точек.

Sir_Michael, вин

Цитата ("Onym"):

(x-x0)/k = (y-y0)/l = (z-z0)/m

А вот это человек, участвующий в олимпиаде, должен знать.

C учетом того, что олимпиады должны составляться по школьной программе (пусть и углубленной).
А трехмерную систему координат вообще в школе не изучают ни под каким видом.

Спасибо за статейки, конечно, но я всё равно не понял что за параметры k, l, m

В общем так.

По двум точкам пишем уравнение.

(x-x0)/k = (y-y0)/l = (z-z0)/m замечаем, что xo, y0, z0, k, l, m - все целые числа.

Решаем в целых числах уравнение (x-x0)/k = (y-y0)/l которое в итоге будет иметь вид ax + by + c = 0, причём a, b и c целые числа.
Такое уравнение решается по алгоритму евклида, получаем

x = a1 * t1 + b1
y = a2 * t1 + b2


Те, кто участвует в олимпиадах, специально готовятся и такие формулы, алгоритмы должны знать.


аналогично решаем второе уравнение, получаем

y = a3 * t2 + b3
z = a4 * t2 + b4

где a1, a2, a3, a4, b1, b2, b3, b4 - будут известные целые числа, t1 и t2 - целые числа из известного диапазона

а дальше элементарно вычисляется сколько таких троек чисел попадает в отрезок.

Цитата ("superkoder"):

Такое уравнение решается по алгоритму декарта

У меня за плечами нет 5 курсов ВУЗа =)) Как и у любого школьника.

Цитата ("Anexroid"):

У меня за плечами нет 5 курсов ВУЗа =)) Как и у любого школьника.

У меня есть, но такие формулы знал и до вуза.