Вопрос: Новое сообщение без темы

Добавлено: 07.01.04 14:58

Автор вопроса:  Диман | Web-сайт: www.dimon1int.narod.ru | ICQ: 224590251

Областная олимпиада школьников по программированию     (г. Челябинск, 4 января 2004 года, ЮУрГУ)   Личное первенство 1. "Простые" числа (5 баллов)  Дан набор различных натуральных чисел. Будем называть число "простым для заданного набора", если число не делится ни на одно из чисел набора, кроие самого себя.  Во входном файле в первой строке содержится целое число N(1<=N<=100) - количество чисел в наборе. Во второй строке файла содержатся N различных целых чисел от 1 до 1000000, разделенных пробелами.  В выходной файл вывести "простые для заданного набора числа", разделяя числа одним пробелом. Числа выводятся в том порядке, в котором они шли во входном файле.  __________________________________________________ |Входной файл INPUT.TXT   |Выходной файл OUTPUT.TXT | |--------------------------------|----------------------------------| |6                                              |5 3 8                                           | |10 5 3 15 6 8                           |                                                   | |________________________|__________________________| 2. Дождь (20 баллов)  Капля дождя падает вертикально вниз с большой высоты на землю. На пути у капти могут встретится препятствия, которые изменяют её путь к земле.  Будем рассматривать двумерный вариант(на плоскости) этой задачи. Пусть препятствия - это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз,пока не упадёт вертикально вниз с меньшего по высоте конца отрезка. Напишите программу, которая по координате Х0 точки появления капли над землей вычисляет координату Х соприкосновения капли с землёй(Y=0).  Во входном файле в первой строке содержатся два целых числа через пробел - координата Х0 точки появления капли(0<X0<10000) и количество отрезков-препятстви N(0<=N<=100). Далее следует N строк, каждая из которых содержит четыре разделённые пробелами числа x1, y1, x2, y2 - координаты левого и правого концов отрезка-препятствия(все числа целые и находятся в диапазоне от 0 до 10000, x1<x2, y1!=y2). Отрезки не пересекаются и не соприкасаются.  В выходной файл вывести одно целое число -  координату соприкосновения точки с землёй.  ___________________________________________________ |Входной файл INPUT.TXT   |Выходной файл OUTPUT.TXT | |--------------------------------|----------------------------------| |30 4                                         |18                                              | |25 35 40 30                             |                                                  | |1 32 20 30                               |                                                  | |33 22 50 29                             |                                                  | |18 10 33 19                             |                                                  | |________________________|_________________________| 3. Шпионы (25 баллов)  Разветвлённая шпионская сеть охватывает много городов в нескольких странах. Для передачи сообщений между собой шпионы используют почту, курьеров, газетные объявления и т.д. Для каждой пары шпионских групп известно, возможно или нет передать сообщение непосредственно от одной группы другой, и время, которое потребуется на передачу сообщения. Шпионская сеть построена таким образом, что всегда существует способ передать прямо или через другие группы сообщение между двумя любыми группами. Одной из шпионских групп стала известна важная информация, которую необходимо распространить как можно скорее среди всех других групп. Напишите программу, которая вычисляет минимальное время для распространения информации во всей шпионской сети и определяет план такого распространения.  Во выходном файле в первой строке содержатся два целых числа N и K, где N(1<=N<=100) - количество шпионских групп, а K(1<=K<=N) - номер шпионс Ответить

Ответы

Всего ответов: 3

Номер ответа: 1 Автор ответа:  Sharp Лидер форума ICQ: 216865379  Вопросов: 106 Ответов: 9979	Web-сайт: sharpc.livejournal.com  Профиль | Цитата | #1	Добавлено: 07.01.04 15:09
	Первую задачу смешно обсуждать, вторая элементарная, третья, видимо, на плохоразветвляющееся дерево, тут надо подумать, что удобнее для решения. Думаю, эти задачи по силе большинству. Ответить

Номер ответа: 2 Автор ответа:  Диман ICQ: 224590251  Вопросов: 29 Ответов: 64	Web-сайт: www.dimon1int.narod.ru  Профиль | Цитата | #2	Добавлено: 08.01.04 00:50
	Sharp, если ты такой умный, то реши задачу 2. Первая задача элементарная, согласен. Она-то и была рассчитана на всех. Во второй задаче, если ты решил решать по принципу наименьшей координаты Y у отрезков, то ты глубоко ошибаешься. Могут быть отрезки, расположенные ниже, но так, что капля на них упасть не может. Я решал на С++ следующим способом: объявил переменные под текущие координаты точки. Вначале ищу отрезок, содержащий X0 точки и имеющий наибольшую координату Y. Потом присваиваю текущим координатам точки координаты нижнего конца найденного отрезка. Затем ищу отрезок, расположенный под точкой и опять же имеющий такую координату X0. Цикл повторяется, пока под точкой не будет найдено отрезков. Тогда выводится в файл. За эту задачу я получил 17 баллов из 20. Каким способом решишь её ТЫ? Там ещё рисунок прилагается, могу кинуть. Третья задача нормальная, просто не влезла. Там я решал с помощью волнового алгоритма. Ещё были 4 и 5 задачи, щас кину все. P.S. Напиши решения, интересно будет посмотреть. Ответить

Номер ответа: 3 Автор ответа:  Sharp Лидер форума ICQ: 216865379  Вопросов: 106 Ответов: 9979	Web-сайт: sharpc.livejournal.com  Профиль | Цитата | #3	Добавлено: 08.01.04 06:02
	> Sharp, если ты такой умный, то реши задачу 2. > Во второй задаче, если ты решил решать по принципу наименьшей координаты Y у отрезков, то ты глубоко ошибаешься. Ну вот, мне уже приписывают несусветные глупости Если бы я не решил задачу, я бы не стал писать, что она простая. Я вообще редко говорю что-то бездоказательно (матан научил ) и вам того же советую. > Могут быть отрезки, расположенные ниже, но так, что капля на них упасть не может. Правда??? > Я решал на С++ следующим способом: объявил переменные под текущие координаты точки. Разве объявление переменной входит в краткое описание решения олимпиадной задачи? > Вначале ищу отрезок, содержащий X0 точки и имеющий наибольшую координату Y. Ну вот, и как я, по вашему мнению, должен отмыться от вылитой на меня грязи, если решение уже написано??? Сказать, что такое наибольший Y? y0=((x0-x1)/(x2-x1))*(y2-y1)+y1 - это элементарно находится из пропорций в прямоугольном треугольнике. Привести код? А что, кто-то не может перевести алгоритм в C++? > Потом присваиваю текущим координатам точки координаты нижнего конца найденного отрезка. Стоило ли сомневаться? Разве тут есть что-то сложное? > За эту задачу я получил 17 баллов из 20. Каким способом решишь её ТЫ? Разве тут возможно много разных очевидных решений? > Третья задача нормальная, просто не влезла. Там я решал с помощью волнового алгоритма. Не уверен, что это лучший вариант... > Ещё были 4 и 5 задачи, щас кину все. Ждем-сс. Только ты так больше не поступай - навязать другому тупое неправильное решение, а потом привести правильное, чтоб тот не отмылся во веки веков. Не один ты на областной олимпиаде по программингу был. Ответить

Страница: 1 |