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

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

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

Откуда они известны то будут?

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

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

Стереометрию отменили?? 0_о Куда катится образование...

Решение Onym проходит. Только нет смысла хранить найденные координаты, посколку вопрос только в их количестве.
На счёт скорости: 1001 отрезок максимум, 10000 переборов на каждый максимум (на самом деле 9998), итого 10 010 000 итераций максимум. Должно укладываться.

Учитывая, что задача 30 баллов из обычных 100, то это самая сложная задача олимпиады, остальные проще. Значит школьник может потратить на неё до часа.

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

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

Аналогично.

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

Откуда они известны то будут?

Уравнение вида Ax + By + C = 0 в целых числах имеет алгоритм решения.

Вариантов только 2. Либо решений в целых числах нет совсем, либо, решений бесконечно много и все они имеют вид

x= a1 * t1 + b1
y = a2 * t1 + b2 , где a1, a2, b1, b2 - известные коэффициенты, а t1 - любое целое число.

но так-как у нас всё-таки ограниченные отрезки, то t1 становится ограниченным тоже.

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

Стереометрию отменили?? 0_о Куда катится образование...

Нет, но данная тема проходится в конце 11 класса. Задача с олимпиады для 10 класса.

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

задача 30 баллов из обычных 100

На олимпиаде сумма была 150 баллов.
Да, это одна из 2 задач, которая оценивалась в 30 баллов.

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

Только нет смысла хранить найденные координаты, посколку вопрос только в их количестве.

Смысл хранить координаты есть в случае, если требуется вычислить количество _станций_, а не количество _визитов на станции_
То есть, если ломаная где-то пересекает сама себя, причем в точке с целыми координатами, то одна станция будет посчитана 2 и более раз. Вот от этих случаев и нужен массив.

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

Нет, но данная тема проходится в конце 11 класса. Задача с олимпиады для 10 класса.

Вообще, да. Формулы прямой в пространстве по двум точкам в школе проходят. Вопрос в каком классе.

А вот решение уравнений вида Ax + By + C = 0 в школе когда я учился не проходили.
Это относится к теме "делимость", а её не проходят.

Но при решении олимпиадных задач знание темы делимость очень помогает.

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

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

Только нет смысла хранить найденные координаты, посколку вопрос только в их количестве.

Смысл хранить координаты есть в случае, если требуется вычислить количество _станций_, а не количество _визитов на станции_
То есть, если ломаная где-то пересекает сама себя, причем в точке с целыми координатами, то одна станция будет посчитана 2 и более раз. Вот от этих случаев и нужен массив.

Согласен. Но с проверкой массива посещённых вершин в лимит времени, пожалуй, не уложиться. Для школьной олимпиады это уже перебор, поэтому, вероятно, трактуется как "количество посещений".

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

На олимпиаде сумма была 150 баллов.
Да, это одна из 2 задач, которая оценивалась в 30 баллов.

Как правило, количество задач больше, чем можно решить за имеющееся время. Это чтоб никто не успел заскучать

Спорно))
Эта задача - с городского тура.
На региональном туре - сумма 200 баллов. Темы исключительно: Комбинаторика и Динамическое программирование
При этом люди набирали по 180-190 баллов

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

Но с проверкой массива посещённых вершин в лимит времени, пожалуй, не уложиться.

Если массив 3-мерный, первое измерение = X, второе Y, третье Z, при нахождении точки в значение пишется TRUE, по умолчанию FALSE, то все сводится к простой проверке значения массива.

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

Если массив 3-мерный, первое измерение = X, второе Y, третье Z, при нахождении точки в значение пишется TRUE, по умолчанию FALSE, то все сводится к простой проверке значения массива.

Массив такого размера не влезет ни в какую выделенную память. И не пройдёт по времени.

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

вероятно, трактуется как "количество посещений"

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

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

Если понимать дословно, то все-таки Базы а не посещения.

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

Если понимать дословно, то все-таки Базы а не посещения.

Да, кстати. Если ломаная себя пересекает, то возможно посещение одной базы несколько раз.
Тогда надо ещё выделить точки пересечения отрезков, чтобы их 2 раза не считать.

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

Массив такого размера не влезет ни в какую выделенную память. И не пройдёт по времени.

Да, пожалуй.
Значит все-таки двухмерный с 1000 "строк", в первом "столбце" - признак для сортировки, во втором - значения координат в виде Record.

Добавил:
Прошу прощения, 1000 - мало, т. к. это только максимальное количество вершин. А надо - станции.

Судя по входным данным - число баз может быть до 10000*10000*10000...

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

Судя по входным данным - число баз может быть до 10000*10000*10000...

Не может.
Максимальное количество вершин = 1000. Значит количество отрезков 998. Даже если все они будут проходить вдоль осей координат, больше чем 1000*10000 станций не получится.

А, ну да =)

Детская задача. минут на 20-40 работы

Тут дольше обвязку писать, чем сам алгоритм решения.

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