| Вопрос: Начался второй тур NetOI-2006 | Добавлено: 12.11.06 00:00 |
Автор вопроса:  Sharp | Web-сайт: sharpc.livejournal.com | ICQ: 216865379 |
|
Начинать участие можно с любого тура. Сайт олимпиады http://www.olymp.vinnica.ua. Решения принимаются до 1 декабря.
Задачи: Задача NewArea
Известная из задачи первого тура Area фирма <Элит-Окраина> вновь вышла на рынок торговли землей. И вновь они при продаже указывали неверные границы участков, хотя участки всегда имели форму прямоугольника с параллельными осям координат сторонами. Каждому покупателю продавалось не более одного участка. После завершения распродажи оказалось, что среди плативших за одну и ту же землю не только Юля Т. и Петя П. (а их участки, естественно, пересекались), но и другие их сотоварищи. Петя и Юля приняли решение из покупателей организовать партии, причем по новому принципу. Если два участка имели хотя бы одну общую точку, то их владельцы попадали в одну партию. В эту же партию попадали все владельцы участков, которые имели хотя бы одну общую точку с участком хотя бы одного ранее принятого партийца(границы принадлежат участкам). Естественно, партия Юли и Пети оказалась самой многочисленной. Однако по причинам, изложенным в задаче Area, они не смогли сосчитать количество членов своей партии. Помогите им и на этот раз. Технические условия: Программа считывает с клавиатуры натуральное число N (2<=N<=200), а далее N групп по 4 целых числа - координаты противоположных вершин участков (-1000<Х_, У_<1000). Все числа вводятся одной строкой через пробел. Программа выводит на экран единственное число-искомую величину. Пример Ввод 6 30 100 -40 120 60 40 40 90 -90 30 -20 -40 -30 50 50 20 20 80 -20 110 -50 80 -70 20 Вывод 4 Задача Ferry Участников полярной экспедиции, зимующих на льдине, постигло большое несчастье: льдина раскололась, и все они оказались на маленьком ее обломке. Нужно как можно быстрее переправиться через широкую трещину. В их распоряжении есть двуместная надувная лодка.Для каждого полярника известно время, необходимое ему для переправы на этой лодке через трещину. Если же в лодке находятся 2 полярника, время переправы равно времени менее расторопного из них. За какое минимальное время все полярники могут переправиться на большую льдину? Технические условия:Программа считывает с клавиатуры натуральное число N (3<=N<=10000) - количество полярников, а далее N натуральных чисел не больших 10000 - времена переправы каждого полярника. Все числа вводятся одной строкой через пробел. Программа выводит на экран единственное число - искомую величину. Пример: Ввод 4 1 6 7 8 Вывод 23 Задача Mayor Мэр города Балдуйска решил вымостить городские тротуары плиткой. Все тротуары в городе имеют ширину 3 метра. Завод, которым, как водится, владел "мэрский" сын, выпускал плитку 1x1 и 1x2 метра, а другую плитку, естественно, городские власти не закупали. Фирма <Балдстрой> получила задачу выстелить кусок тротуара длиной N метров.Сколькими разными способами работники фирмы могут это сделать? Технические условия Программа читает с клавиатуры одно целое число N (2<=N<=1000) - длину тротуара. Программа выводит на экран единственное число - искомую величину. Пример Ввод 2 Вывод 22 Задача Mayor2 Уже известный нам мэр Балдуйска решил уменьшить расходы на организацию автобусных маршрутов. Сам город имел N улиц, идущих строго с юга на север, и N пересекающих их улиц, идущих с запада на восток. Все улицы, естественно, одинаковой длины, а движение по ним одностороннее (т.е. ехать можно либо с юга на север, либо с запада на восток). Утром на некоторых перекрестках собираются люди. Их подбирают безразмерные автобусы, дабы отвезти на работу за город. Да вот одна маленькая проблема: все автобусы начинают свой маршрут с самого юго-западного перекрестка. Какое минимальное количество автобусов следует выпускать на маршрут утром, чтобы подобрать всех стоящих на перекрестках пассажиров? Технические условия: Программа читает с клавиатуры два натуральных числа: N - количество улиц в каждом направлении (N<=1000), P - количество перекрестков с стоящими пассажирами (1<P<=1000000), а далее P групп по 2 числа - координаты перекрестка с пассажирами. Понятно, что "самый юго-западный перекресток" имеет координаты (1,1). Все числа вводятся одной строкой через пробелы. Прoграмма выводит на экран единственное число - искомую величину. Пример Ввод 8 8 3 1 4 2 7 3 2 4 5 4 3 6 4 7 7 6 Вывод 3 Задача Zigzag Последовательность чисел называется зигзагом, если в ней нет ни одной монотонно невозрастающей и ни одной монотонно неубывающей подпоследовательности подряд идущих элементов длиной 3. Дана последовательность. Какое минимальное количество элементов необходимо вставить в нее, чтобы получился зигзаг? Технические условия:Программа читает с клавиатуры количество элементов последовательности N (3<=N<=10000) и N чисел - элементы последовательности (не большие 1000 по абсолютной величине каждый). Все числа вводятся одной строкой через пробел. Программа выводит на экран единственное число - искомую величину. Пример Ввод 6 1 4 7 9 7 4 Вывод 3 ============================================== Г.Кравец, Г.Непомнящий, Ю.Пасихов, А.Присяжнюк ============================================== |
| Ответы | Всего ответов: 5 |
|
Номер ответа: 1 Автор ответа:  Morpheus Вопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #1 | Добавлено: 12.11.06 02:41 |
Ну, зигзаг заметно проще других... вот с неё и начнёмс... Ну ничё, зато твой любимый язык 
program Zigzag; {$APPTYPE CONSOLE} uses SysUtils; VAR S:array [1..10000] of integer; N:integer; i:integer; j:integer; rep:boolean; k:integer; procedure ShiftForward(cp:integer); var g:integer; begin for g:=n downto cp do begin S[g+1]:=s[g]; end; n:=n+1; end; begin k:=0; i:=0; j:=0; rep:=false; write('Enter N: '); readln(n); for j:=1 to n do begin read(s[j]  ;
end; rep:=true; while rep=true do begin rep:=false; for i:=2 to (n-1) do begin if (s[i-1]<=s[i] and (s[i]<=s[i+1] then begin //increasing!!!
ShiftForward(i+1); s[i+1]:=s[i]-1; rep:=true; k:=k+1; end; if (s[i-1]>=s[i] and (s[i]>=s[i+1] then begin //decreasing!!!
ShiftForward(i+1); s[i+1]:=s[i]+1; rep:=true; k:=k+1; end; end; end; writeln(k); readln; readln; end. |
||
|
Номер ответа: 2 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #2 | Добавлено: 12.11.06 02:49 |
|
ой блин , в случае //decreasing!!! надо поменять >= на > а то глюки идут когда последовательость типа 0 0 0 встречается
|
||
|
Номер ответа: 3 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #3 | Добавлено: 12.11.06 03:03 |
|
Вообще-то тур еще не закончился, поэтому не стоит постить свои решения где-то Стоит отправлять их с сайта олимпиады и ждать результатов.
|
||
|
Номер ответа: 4 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #4 | Добавлено: 12.11.06 03:29 |
|
да ну их нафиг, и так дел хватает чтобы ещё блин учавствовать где то... тем более это единственная задача в которую я въехал
|
||
|
Номер ответа: 5 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #5 | Добавлено: 12.11.06 03:41 |
|
Это называется "сдулся" ) У меня, например, дел куда больше
|
||
Страница: 1 |