Visual Basic, .NET, ASP, VBScript
 

   
   
     

Форум - Олимпиады

Страница: 1 |

 

  Вопрос: Начался второй тур 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-сайт: xury.zx6.ru
 Профиль | | #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-сайт: xury.zx6.ru
 Профиль | | #2
Добавлено: 12.11.06 02:49
ой блин , в случае //decreasing!!! надо поменять >= на > а то глюки идут когда последовательость типа 0 0 0 встречается :)

Ответить

Номер ответа: 3
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #3
Добавлено: 12.11.06 03:03
Вообще-то тур еще не закончился, поэтому не стоит постить свои решения где-то :) Стоит отправлять их с сайта олимпиады и ждать результатов.

Ответить

Номер ответа: 4
Автор ответа:
 Morpheus



Вопросов: 224
Ответов: 3777
 Web-сайт: xury.zx6.ru
 Профиль | | #4
Добавлено: 12.11.06 03:29
да ну их нафиг, и так дел хватает чтобы ещё блин учавствовать где то... тем более это единственная задача в которую я въехал :)

Ответить

Номер ответа: 5
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #5
Добавлено: 12.11.06 03:41
Это называется "сдулся" :)) У меня, например, дел куда больше :)

Ответить

Страница: 1 |

Поиск по форуму



© Copyright 2002-2011 VBNet.RU | Пишите нам