Форум Всеукраїнської інтернет-олімпіади NetOI

Bear: O(n):

var
  M, K, i : longint;
begin
  Read(M, K);
  if K mod 2 = 0 then
    for i := 0 to K div 2 do
      Write(i*2*m, ' ')
  else
    for i := 0 to K div 2 do
      Write((i*2+1)*m, ' ');
end.

Решение очевидно

Відредаговано Джулгаков Дмитрий (2005-11-19 20:44:00)

Кстати под чем это компилить твое если так да и еще на авто тестилке по памяти какие ограничения (по незнанию спрашиваю)?

Джулгаков Дмитрий написав:

necro написав:

Кстати под чем это компилить твое если так да и еще на авто тестилке по памяти какие ограничения (по незнанию спрашиваю)?

Компилить все можно и под BP. Только NewPatience нужно под FP. А по поводу памяти, по-моему, всегда было так: сколько система позволяет - все твое. Т.е под BP - 640К. А под FP - много...

То есть никогда не было ограничений. Блин и тестилка компилит под фрипаскаль?

А вы знаете,что на главной странице уже появилась ссылка на результаты первого тура?
Правда она нерабочая... :-(

jack_spektor написав:

А вы знаете,что на главной странице уже появилась ссылка на результаты первого тура?
Правда она нерабочая... :-(

Н-да, прикольно. У всех ?? балов

Джулгаков Дмитрий написав:

Bear: O(n):

Код:

var
  M, K, i : longint;
begin
  Read(M, K);
  if K mod 2 = 0 then
    for i := 0 to K div 2 do
      Write(i*2*m, ' ')
  else
    for i := 0 to K div 2 do
      Write((i*2+1)*m, ' ');
end.

Решение очевидно

я немного сжал:

Var i,j,k:longint;
begin
  read(j,k);
  for i:=0 to (k div 2) do
    write(j*(2*i+(k mod 2)),' ');
end.

ничего, что в конце вывода лишний пробел?

Відредаговано ROBOT (2005-11-23 10:31:47)

Батыев Андрей написав:

Люди!!!!! Блин, неужели есть гении которые способны понять алгоритм по 1-5 кб коду?
И ваще лучше выкладывать и спорить над АЛГОРИТМАМИ чем над ИСХОДНИКАМИ!
Тогда не будет проблем с языком, компилятором и проч.!

АЛГАРИТМЫ трудно объяснить слловами
Легче нарисовать на бумажке рисунок
Кстати как можно разрезать цепь МЕЖДУ звеньями?

Проверь. что будет,  если К у тебя 1. Я правда в решение не вчитывалась, но, по-моему, оно заглючит.
Мой вариант решения:

var M,K,i : integer;
begin
readln(M,K);
if K mod 2 = 0 then i := 0
else i := 1;
while i <= K do
begin
   write(i*M,' ');
   inc(i,2);
end;
writeln;
end.

Відредаговано Anna (2005-11-23 19:09:28)

Ну, у меня, фактически, то же самое, и я тоже 20 балов за это получила. А зачем тебе там р?

Задача Bear.
Маленький медвежонок идет по дороге, вдоль которой на расстоянии М одно от другого растут деревья.Останавливаясь под каждым деревом, медвежонок забывает, откуда пришел, и, двигаясь через некоторое время дальше, случайно выбирает то или иное направление движения. На каком расстоянии от "стартового" дерева может быть медвежонок после К этапов?
Технические условия Программа считывает с клавиатуры числа M и К через пробел (1<=М,К<=10000). Программа выводит на экран в одной строке через пробелы расстояния, на которых может находиться медвежонок (от меньшего до большего).
Пример
Ввод 2 6
Вывод 0 4 8 12


Сперва будем считать М=1. Тогда заметим, что все пройденные мишкой расстояния будут имет одинаковую четность, равную четности числа К (так как при каждом переходе четность меняется). Кроме того, он всегда может попасть в точку с координатой 0 (при четном К) или 1 (при нечетном) а также всегда может попасть в точку с координатой К. Также, можно заметить, что мишка может попасть во все координаты между ними, равные К по четности (несколько раз ходим взад-вперед, а потом а раз прямо, a<=К), поэтому ответом будут: все числа от 0 до К, равные К по четности. При М>1, умножаем все числа в ответе на М.
Сложность алгоритма: O(K)

Задача Piece.
Имеется окружность радиуса R с координатами центра x,y и прямая, заданная координатами двух своих точек.Какой длины отрезок прямой лежит внутри окружности?
Технические условия Программа читает с клавиатуры строку из 7-ми чисел: радиус окружности, координаты x y центра и координаты 2-х точек прямой. Все числа целые, по абсолютной величине не превосходят 10000. Результат вывести на экран, не округляя. Если окружность и прямая не пересекаются, вывести -1, если касаются - вывести 0.
Пример
Ввод 5 0 0 4 1 4 2
Вывод 6.0000000000000000E+0000

Сперва делаем движение на вектор (-x;-y), чтобы точка (x;y) перешла в точку (0;0).
Далее, находим расстояние от центра окружности до нашей прямой. На мой взгляд, самый оптимальный способ – это подсчет высоты в треугольнике OAB как
H= 2*S(OAB)/AB, где 2*S(OAB) подчитывается, как модуль псевдоскалярного произведения векторов OA и OB  ( (a;b)*(c;d) = a*d-b*c). Зная расстояние, легко перейти к длинне секущей:
Если     H>R – пересечения нет
H=R – касание
H<R – пересечение, длинна секущей из т. Пифагора: L2 = 2(R2 – H2)
Не забываем делать “допуск” для условия касания, вместо
H=R пишем
Abs(H-R)<=0.00001
Сложность алгоритма: O(1)
Задача Circuit.
    Дана цепочка, состоящая из k=4n звеньев. Причем 2n звеньев - золотые и 2n звеньев - серебряные. Два разбойника желают справедливо разделить серебро и золото данной цепочки. Составьте программу,которая находит минимальное количество разрезов цепочки,так, чтобы как серебро так и золото можно было бы разделить между двумя разбойниками.
Технические условия Программа читает с клавиатуры количество звеньев k,а далее - k чисел 0 либо 1 (0 - серебряное звено, 1 - золотое).Все числа вводятся одной строкой через пробелы. Программа выводит на экран количество разрезов и номера звеньев, между которыми они были сделаны. Первый разрез должен быть как можно ближе к началу цепи. N<10000
Пример
Ввод 8 0 1 0 0 1 1 0 1
Вывод 2 1 2 5 6


Создадим массив a[i], i=0..k по такому правилу a[0]=0, a[i]= разность золотых и серебряных звеньев цепи среди первых n (создается в один проход) , легко видеть, что цепь можно разделить правильно одним разрезом тогда и только тогда когда a[2n]=0. Проверяем этот случай.
Докажем что в ином случае можно обойтись двумя разрезами и найдем их. Рассмотрим ф-цию f(x) =a[x+2*n-1]-a[x-1]. Она равна разности числа золотых и серебрянных звеньев в отрезке цепи длинной 2n с x по x+2n-1. Если f(x)=0, то этот отрезок даем одному разбойнику, остаток – другому. Все довольны. Докажем, что у ф-ции f всегда есть корень. Заметим, что она всегда принимает четные значения. F(1) = -f(2n) (так как соответствующие куски дают в сумме всю цепь, а количества звеньев в них меняются местами). Также заметим f(x+1) отличается от f(x) не более чем на 2. Значит функчия имеет корень. Так как если f(1)<>0 то f(1) и f(2n) имеют разный знак. Значит, найдется такое t, что  f(t) и f(t+1) имеют разный знак (иначе везде был бы один и тот же знак) но тогда f(t) f(t+1) отличаются как минимум на 4 что невозможно. Значит f(x) имеет корень, находим наименьший из корней перебором и выводим соответствующее ему разрезание цепи. Также заметим, что карни ф-ции f(x) дают нам все возможные «хорошие» разрезания цепи двумя разрезами т.к. в таком случае всегда будет кусок длинны 2n а это значит, что наш ответ будет удовлетворять условию «Первый разрез должен быть как можно ближе к началу цепи.»
Сложность алгоритма: O(K)


Задача Newpatience.
Многие в свободное время увлекаются разложением пасьянсов. Предлагаем вам еще один, правда, карты для него нужно изготовить самостоятельно. Итак, на N карточках нанесите натуральные числа по одному числу на каждой стороне карточки так, что каждое из чисел наносилось ровно 2 раза. Карточки разложите на столе в ряд. Все готово. Можно начинать. В процессе игры карточки можно переворачивать другой стороной. Пасьянс сходится тогда, когда перевернув некоторые карточки, вы получите возможность видеть все N чисел одновременно. Сойдется ли пасьянс, а если да, то какое наименьшее количество карточек необходимо для этого перевернуть?
Технические условия Программа читает с клавиатуры число N (N<10000), а далее 2 группы по N чисел-сначала числа на одной из сторон каждой из N карточек (игрок их видит в начале игры), а затем числа,нанесеннные на эти же карточки,но на противоположную сторону. Все числа вводятся одной строкой через пробелы. Вы выводите на экран одно число: -1, если пасьянс не "сошелся", либо минимальное количество перевернутых другой стороной карточек, если игра завершилась успехом. Пример
Ввод 5 3 2 5 3 2 5 4 1 1 4
Вывод 2


Назовем циклом последовательность из a карточек такой, что у любых двух соседних (а также у 1 и а) карточек есть общее число. Решим задачу для цикла: найдем общее число карточек 1 и 2, повернем карточку 1 этим числом вверх для всех 1<x<=a повернем карточку х вверх тем числом, какое снизу у карточки х-1. В итоге получаем сошедшийся пасьянс. Количество ходов при этом (t) определяется однозначно. Можно заметить, что при этом существует еще всего один способ собрать пасьянс: повернуть все карточки наоборот. Количество ходов при этом: a-t. Поэтому нужно выбрать минимум из этих двух чисел. Это и будет минимальное число ходов, чтобы собрать цикл. Теперь разбиваем наш набор на циклы (последовательность карточек в цикле не обязательно совпадает с последовательностью карточек на столе) и считаем число ходов, необходимое чтобы собрать каждый из них. Сумма ходов и будет ответом. Попутно мы доказали, что любой пасьянс сходится.
Сложность алгоритма: O(N)

Нет! Решение Circuit у меня простое А длинное доказательство достаточности двух разрезов.

Упс. Глюк. Спасибо. В попыхах и не заметил.