| Вопрос: NetOI-2004, 4-й тур | Добавлено: 14.02.05 07:50 |
Автор вопроса:  Sharp | Web-сайт: sharpc.livejournal.com | ICQ: 216865379 |
|
Прошел 4-й финальный тур NetOI-2004. Это 5 задач на 6 часов в real-time (правда, я так и не понял, что у них со временем). Проснулся я поздно и полноценно поучаствовать не смог :), отправил только одну задачу
Должен сказать, что задачи меня разочаровали, в прошлом году были куда интереснее и сложнее. Вот они: Задача GARDEN Садоводы знают, что черешневый сад плодоносит намного лучше, если он засажен разными сортами черешни. Фермер Наливайко решил посадить новый черешневый сад. Отведенный для этого участок земли квадратной формы он разделил (N-1) вертикальными и (N-1) горизонтальными дорожками ( которые паралелльны сторонам квадрата) так, что она имеет вид N x N одинаковых клеточек, а в центре каждой клетки планируется посадить саженец одного из двух сортов - "Приусадебная" и "Дончанка". Помогите пану Наливайку посадить саженцы так, чтоб на любом участке сада размером K x K было ровно S саженцев сорта "Дончанка". Технические условия Программа читает с клавиатуры 3 числа N, K, S (1<=N<=100, 1<=K<=N, 0<=S<=K2). Программа выводит на экран план будущего сада в виде таблицы . Где j-ое число в i-ой строке означает сорт саженца, который будет посажен в клетку (i, j). Саженец сорта “Приусадебная” обозначено 0, а “Дончанка” - 1. Числа разделены пробелами. Пустых строк в таблице нет. Если вариантов размещения несколько - выведите любой. Примеры Ввод Вывод Ввод Вывод 3 2 1 0 0 0 4 2 2 1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 0 ====================================== Задача Fence Два соседа-фермера получили сертификаты на право владения землей. Каждый получил участок в виде многоугольника без самопересечений, все углы которого не равны 180. Границы этих участков заданы координатами вершин многоугольника в прямоугольной декартовой системе координат, данные в порядке обхода многоугольника в некотором направлении по часовой стрелке, или против. Позже выяснилось, что эти земли имеют общую часть. Примечательно, что ни одна из вершин многоугольника, который ограничивает земли одного из фермеров, не попадает на границы земли другого. Фермеры решили построить ограждения вокруг общей земли, которая представляет собой некоторое множество многоугольников. Для этого нужно поставить по одному колу в каждую вершину многоугольников, которые получаються при пересечении земель. Причем эти многоугольники также без самопересечений, и все его углы не равны 180. Технические условия Вы вводите с клавиатуры два целых числа n1 и n2 (3<=n1,n2<=100) - количество вершин надела первого и второго фермеров, далее через пробел вводите координаты вершин наделов первого и второго фермеров (целые числа, не превышающие 1000 по абсолютной величине). Вы выводите на экран искомое количество кольев. Пример 1. Ввод: 5 6 2 2 5 3 6 1 8 4 4 7 2 7 5 10 7 8 8 5 6 4 5 5 Вывод: 5 Пример 2. Ввод: 6 6 1 4 4 7 6 4 4 2 6 0 4 -2 4 1 6 -3 12 4 7 7 4 4 8 2 Вывод: 8 ====================================== Задача Farm Герои предыдущей задачи, два соседа-фермера, утомившись от судов и строительства забора, дали взятку районному чиновнику и получили сертификаты на право владения новыми участками. В этот раз каждый получил надел в виде круга, но вновь возникло подозрение, что часть территории одновременно принадлежит и одному, и другому. В суд не обращались - все равно толку мало-, а решили объединится в кооператив и совместно использовать всю имеющуюся у них землю. Какая площадь оказалась в распоряжении кооператива? Технические условия Вы вводите с клавиатуры 6 вещественных чисел через пробел x -, у- координаты и радиус одного круга, а затем так же - второго. Все входные величины не превышают по модулю 1000000 и содержат не более 3 знаков после запятой. Программа выводит на экран единственное число - результат в экспоненциальной форме, не округляя. Ответ будет правильным, если абсолютная погрешность не превысит 10-3 Пример Ввод: 0 0 17 0 21 10 Вывод: 1.15575235315894E+0003 ====================================== Задача PERFECTUM Прототип нового мобильного телефона под кодовым названием "PERFECTUM MOBILE" имеет конечное число состояний N (1<=N<=200) (например, написание sms, прослушивание музыки). При нажатии одной и той же кнопки телефон производит различные действия, в зависимости от текущего состояния. Для каждого состояния известно, в какие состояния перейдет телефон при нажатии на одну из M кнопок (1<=M<=50). Иногда кнопки могут "залипать". Требуется выяснить, насколько опасным может явиться залипание одной из кнопок. Был создан список опасных последовательностей состояний телефона (например, "Архив sms"->"Oпции"->"Удалить все") содержащий L последовательностей (0<=L<=10). Необходимо выяснить, возможно ли возникновение какой-либо из указанных последовательностей при "залипания" одной из кнопок. "Залипнуть" может любая кнопка, в любом состоянии, достижимом состояния с номером 1. Технические условия Программа считывает с клавиатуры входные величины в такой последовательности:3 числа: N, M, L. Далее следует N групп, каждая содержит M чисел от 1 до N. j-ое число в i-ой группе означает, что из состояния с номером i при нажатии на кнопку j телефон перейдет в состояние с указанным номером. Далее следует L групп . Первое число A (1<=A<=1000) в строке - количество состояний в нежелательной последовательности, за которым следует A номеров состояний. Все величины разделены пробелами. Программа выводит на экран одну строку, в которой содержится количество разных состояний, которые могут дать ошибку при "залипании " како-либо кнопки в них , а затем, в порядке возрастания, номера этих состояний. Примеры Ввод Вывод 5 3 1 2 3 2 3 2 1 2 4 5 1 4 3 1 5 5 1 5 3 3 4 5 Ввод Вывод 2 2 1 2 1 2 1 3 1 2 1 0 ====================================== Задача Racing На праздновании Дня города проводятся уличные гонки по следующим правилам: 1. участие принимают T гонщиков (3<=T<=100); 2. проехать нужно N кругов (2<=N<=100, N обязательно четное); 3. на всех кругах с нечетными номерами, гонщик, проехавший данный круг первым, получает одно очко; 4. на всех кругах с четными номерами (кроме последнего круга), очки получают первые четыре гонщика: a. приехавший первым - 5 очков; b. приехавший вторым - 3 очка; c. приехавший третьим - 2 очка; d. приехавший четвертым - 1 очко. 5. на последнем круге, все очки удваиваются относительно предыдущего пункта (10, 6, 4 и 2 очка). Напишите программу, которая будет определять, каким количеством различных способов гонщик может набрать сумму очков K? Способы считаются различными, если отличается последовательность очков по кругам. Технические условия: Вы вводите с клавиатуры три целых числа - K, N и T через пробел. Вы выводите на экран единственное число - количество способов. Примеры Ввод: 10 4 7 Вывод: 6 Ввод: 8 2 5 Вывод: 0 Как эффективно решать Garden, я пока не придумал. Fence - число кольев равно сумме чисел точек пересечения сторон разных многоугольников (для каждой стороны одного многоугольника проверить, пересекается ли она с каждой из сторон другого) и числа вершин многоугольников, лежащих внутри другого прямоугольника. Таким образом, задача сводится к задаче на нахождение точки в невыпуклом многоульнике, которая решается через теорему Жордана с рассмотрением особых случаев: 1) если на луче лежит какая-то вершина, то добавить одно пересечение, если две соседние вершины для этой вершины находятся в разных полуплоскостях от прямой, образованной этим лучом; 2) почти аналогичный случай, если на луче лежит граница, единственное изменение - берутся не две смежные с вершиной вершины, а две смежные с границей. Farm - элементарная задачка на планиметрию, площадь двух секторов + площадь четырехугольника с перпендикулярными диагоналями длиной r (расстояние между центрами) и ф-ла Герона(r1, r2, r)/r*4, если окружности пересекаются, но r>max(r1,r2), банальная сумма площадей, если окружности не пересекаются или площадь большей окружности, если одна окружность вписана в другую и примерно такая же, как в первом случае ф-ла, если центр одной окружности лежит в другой. Perfectum - эту задачу сложнее понять, чем решить; для каждого состояния, "нажимаем" на каждую кнопку, как будто она залипла, и пока не происходит зацикливания (т.е. возникнет состояние, которое уже было), жмем на нее и смотрим, не выпадает ли нехорошая последовательность. Racing - вот эту задачу я отправил, но решил я ее жутко некрасиво, храним кол-во способов, которым можно достичь определенного количества очков на каждом круге и для каждого круга, начиная со 2-го прибавляем в зависимости от числа гонщиков к возможным способам достижения количества баллов+то, что можно набрать за последний круг число способов, которым можно набрать количество баллов в прошлом круге. |
| Ответы | Всего ответов: 3 |
|
Номер ответа: 1 Автор ответа:  SyavX Вопросов: 25 Ответов: 149 |
Профиль | | #1 | Добавлено: 20.03.05 18:17 |
|
Неделю назад участвовал в олимпиаде, где была задача GARDEN, правда по-другому сформулирована:
"Есть квадратная нулевая матрица размером N x N. Разместите на ней единицы так, чтобы в любом квадрате K x K было ровно S единиц. Условие: 1<=N, 1<=K<=N, 0<=S<=K*K" Написал вполне рабочий код. Но понятные коментарии к нему написать не удалось  Разбирайтесь кто как может...
Option Base 1
Const N = 4 Const K = 2 Const S = 2 'Arr - большая матрица (главный участок) 'M - маленькая матрица (проверяемый участок) Dim Arr(N, N) As Byte Dim M(K, K) As Byte Private Function Matrix() 'Если кол. единиц больше, чем влезет в диагональ... If S > K Then 'Заполняем диагональ... For i = 1 To K M(i, i) = 1 Next i 'r - кол. единиц которые не влезли в диагональ 'h - количество уровней вне диагонали r = S - K h = 0 If r Mod 2 = 0 Then Do While r \ 2 > K - (h + 1) h = h + 1 r = r - ((K - h) * 2) Loop For f = 1 To h + 1 If f < h + 1 Then For i = 1 To (K) - f M(i + f, i) = 1 M(i, i + f) = 1 Next i Else For i = 1 To r \ 2 M(i + f, i) = 1 M(i, i + f) = 1 Next i End If Next f Else 'Делаем r - парной r = r + 1 'Далее как и для непарного кол. Do While r \ 2 > K - (h + 1) h = h + 1 r = r - ((K - h) * 2) Loop For f = 1 To h + 1 If f < h + 1 Then For i = 1 To (K) - f M(i + f, i) = 1 M(i, i + f) = 1 Next i Else For i = 1 To r \ 2 M(i + f, i) = 1 M(i, i + f) = 1 Next i End If Next f M((i - 1), (i - 1) + (f - 1)) = 0 End If 'Если кол. единиц меньше диагонали, заполняем диагональ... Else For i = 1 To S M(i, i) = 1 Next i End If 'Розмножаем матрицу M на матрице Arr On Error Resume Next 'Делать без ошибок - влом, поэтому On Error Resume Next For y = 1 To N + K Step K For x = 1 To N + K Step K For j = 1 To K For i = 1 To K Arr(x + i - 1, y + j - 1) = M(i, j) Next i Next j Next x Next y 'Выводим готовую матрицу Arr txt.Text = "" For y = 1 To N For x = 1 To N txt.Text = txt.Text & " " & Arr(x, y) Next x txt.Text = txt.Text & vbCrLf Next y End Function Результатом здесь будет: 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 |
||
|
Номер ответа: 2 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #2 | Добавлено: 20.03.05 22:55 |
|
Да, в этом направлении я не думал...
А что за олимпиада? Остались ли задания? Если да, почему они еще не здесь? |
||
|
Номер ответа: 3 Автор ответа: SyavXВопросов: 25 Ответов: 149 |
Профиль | | #3 | Добавлено: 21.03.05 21:53 |
|
Особо можешь не радоваться:
1. Олимпиада - 1-й (отборочный) тур среди студентов киевских техникумов [ каковым я и являюсь  ]
2. Задания через пару дней кину (5 задач) А эта задачка там была самой интересной... |
||
Страница: 1 |