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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2008-11-29 04:50:13

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Разбор решений задач первого тура.

Ну что ж, полночь миновала, настало время разглашать идеи и постить исходники smile
Правда, пока не появились результаты, есть маленькие сомнения в их правильности, но предполагается, что они не содержат ошибок. smile
Исходники доступны здесь: http://drop.io/olymp2008
Итак...

Oldtask2
Здесь надо смоделировать указанную ситуацию (поиск и замену).
Поиск можно делать с помощью встроенных функций с O(N^2) (например, Pos в FP), но если сделать его чуть «умнее», теоретически можно достичь O(N).
При замене мы не вставляем в строку и не удаляем из строки символы непосредственно, так как эти операции занимают сравнительно большое время. Как альтернативный вариант, который я реализовал — у нас есть два массива, первый типа boolean — определяет, какие символы из оригинальной строки мы в конце будем выводить на экран. Изначально все элементы массива равны true; если мы встречаем искомую подстроку в нашей строке, то мы заполняем позиции, на которых лежит эта подстрока false'ами, то есть практически вычёркиваем её, при этом не совершая операций с изменением строк, а во второй массив добавляем очередную величину — индекс, дойдя до которого, мы должны вставить s3 (получается, что символы из оригинальной строки, которые вычеркнуты, и так не пропечатаются, а новая подстрока будет вставлена в этом месте).

Calcplus
Итак, нашим первым нажатием будет «+» (кроме тех случаев, когда N = 1, в этом случае ответ 0, то есть нажимать ничего не надо). Самый простой путь впоследствии «дойти» до числа N — нажать «=» N раз. Но это решение может и не быть наилучшим — в какой-то момент мы можем опять нажать «+», и в следующий момент прибавляться к результату будет записанное до этого момента число.
Операция многократного сложения — это умножение. А поэтому на очередном шаге, когда мы вздумаем нажать кнопку «+», необходимо, чтобы конечное число делилось на текущее, записанное в буфер; иначе мы получим дробное количество нажатий, что противоречит здравому смыслу. Одновременно с этим видим, что нажатие кнопки «+»  в несколько раз сокращает количество оставшихся нажатий, следовательно, наша цель — совершить как можно больше нажатий на «+» таких, чтобы после них возможно было продолжить нажатия и получить правильный результат.
Таким образом видим, что 1 нажатие «+» плюс X – 1 нажатий «=» даёт умножение текущего числа на X, достигаемое в 1 + X – 1 = X нажатий.
В итоге, задачу Calcplus можно упростить до такой:
Дано число N. Найти сумму всех простых множителей N.

Fibo
В этой задаче у нас есть два варианта, когда M ≠ 2 и M = 2. Почему второй вариант такой особый, мы рассмотрим позже, а сейчас рассмотрим первый вариант (M ≠ 2). Кстати, N не может быть равен 2, потому что он строго больше M, а по условию 1 < M < N, поэтому «особый случай только с M = 2».
Определим функию R(X), как X-ый элемент Фибоначчи-подобной последовательности, а также функцию Fib(X), как X-ый элемент оригинальной последовательности Фибоначчи (1, 1, 2, 3, 5, 8, ...)
Допустим, нам известны R(1) и R(2). Рассмотрим последующие значения функции:
R(3) = R(2) + R(1) = 1 * R(2) + 1 * R(1)
R(4) = R(3) + R(2) = 2 * R(2) + 1 * R(1)
R(5) = R(4) + R(3) = 3 * R(2) + 2 * R(1)
R(6) = R(5) + R(4) = 5 * R(2) + 3 * R(1)
R(7) = R(6) + R(5) = 8 * R(2) + 5 * R(1)
Видим закономерность, и выводим общую формулу:
R(N) = R(N – 1) + R(N – 2) = Fib(N – 1) * R(2) + Fib(N – 2) * R(1)
Оригинальную последовательность Фибоначчи мы можем легко вычислить, это мы и делаем, и результат заносим в отдельный массив. (то есть, все Fib(X) нам известны).
По входным данным нам дано M, R(M), N, R(M). Возьмём тест из условия (3 8 7 28), получим:
R(3) = 8 = Fib(3 – 1) * R(2) + Fib(3 – 2) * R(1)
R(7) = 28 = Fib(7 – 1) * R(2) + Fib(7 – 2) * R(1)
Отсюда
1 * R(1) + 1 * R(2) = 8
5 * R(1) + 8 * R(2) = 28
Получили обычную систему уравнений с двумя неизвестными, типа:
A1*X + A2*Y = A3
B1*X + B2*Y = B3
или
1X + 1Y = 8
5X + 8Y = 28
При этом известно всё, кроме X и Y.
Решаем систему...
Умножаем первое уравнение на B2, второе — на A2.
8X + 8Y = 64
5X + 8Y = 28
Вычитаем из одного уравнения другое,
64 – 8X = 28 – 5X, 3X – 36 = 0, 3X = 36, X = 36 / 3 = 12 (А так как X = R(1), то мы нашли ответ задачи).

Вместо 3X = 36 положим, что мы получили T*R(1) = Q при других входных данных. Ответ «Impossible» может быть в случаях, когда:
1) T = 0 и Q ≠ 0. Тут всё понятно, ненулевое число на ноль делить нельзя.
2) Q mod T ≠ 0. Мы должны получить целое число (это оговорено в условии).
Также мы можем получить бесконечное количество ответов. Такой вариант возможен, когда T = 0 и Q = 0, 0/0 может быть любым (в своём коде я вывожу 8).

А теперь вернемся к особому случаю M = 2... почему он особый? Да потому, что нам даётся второй член последовательности, следовательно, мы будем иметь дело не с системой уравнений, а всего лишь с одним уравнением! В уже знакомом нам уравнении известно всё, кроме R(1):
R(1) * Fib(M – 2) + R(2) * Fib(M – 1) = R(M),
таким образом, ответом будет:
R(1) = [R(M) – R(2) * Fib(M – 1)] / Fib(M – 2)
Всё вышесказанное про Impossible-ответ и случаи, когда ответом является любое число, надо проверить и тут.

[UPD]: Задача не прошла 12, 20 и 21 тесты.
12 тест — из-за того, что на целочисленность проверялся X, но не проверялся Y.
20 и 21 тесты — из-за того, что ответ там превышал 10^18 по модулю; в этом случае надо было выводить «Impossible», а я сделал длинную арифметику smile


-------------------------------------------------------------------------------------------------------------------------------------

На сим заканчиваю и предоставляю слово...

Відредаговано guest1 (2008-11-30 18:34:57)

Поза форумом

 

#2 2008-11-29 04:51:00

Cardinal Nightingale
Новий користувач
Звідки: Десь подалі від Александрії
Зареєстрований: 2008-11-24
Повідомлень: 19
Вебсайт

Re: Разбор решений задач первого тура.

      Так-с, на меня возложена гигантская ответственность описания моих решений задач № 1 и 4 (OldTask1 и Skyscraper). Предупреждаю заранее: текст писался ещё до того, как станут (стали) известными результаты, так что за правильность и т. п. я не ручаюсь (хотя и очень надеюсь). Ещё одно предостережение: для меня привычным языком является Си, но зная, что тут бывают всякие глюки с int64 и строками, я перестраховался и переписал всё на Паскаль.
      Последнее напутствие: «>:3 Господи Иисусе! Да это же ЛевЪ! Скорее в машину!!!11»


1. OldTask1

      Итак, для начала скажу, что считать факториал напрямую — это конечно будет на 100 % верным решением, но слишком долгим и жрущим много памяти, так что оно отпадает.
      Следующим шагом будет то, что из бесконечности простых чисел единственные два, которые при перемножении дают число, оканчивающееся на нолик, — это 2 и 5.
      Далее, вспоминая, что любое число можно разложить на произведение простых и то, что факториал — это произведение всех натуральных чисел до данного, я понял, что можно считать всю эту муть так:
      1.  Учитывать двойки и пятёрки отдельно, а всё остальное множить между собой так, как будто мы ничего не знаем.
      2.  Так как нас волнуют только последняя цифра, то надо оставлять только её. Но тут в голову лезет мысль: каким макаром? Естественно, надо делать каждый раз вычисление остатка от деления. Некоторые могут сказать, что это будет неэффективно, что надо делать всё умнее и делать вычисление модуля тогда, когда произведение будет переваливать за какую-то границу и всё такое, но вот подумав, что после того, как мы перевалим к числам за 1000, то это будет случаться чуть ли не каждый раз, так что на эффективность это не будет сильно влиять в отрицательную сторону.
      Проблема учёта двоек и пятёрок решается так: одна двойка × одну пятёрку = один нолик в конце, а значит двойки и пятёрки, смешанные в любой пропорции дают в результате количество ноликов, равное меньшему из количеств двоек и пятёрок. Тут ещё (я не привожу, какого чёрта, — сами догадаетесь) становится понятным, что двоек всегда будет больше чем пятёрок.
      Итак, вводится счётчик, который ведёт учёт количества двоек. Как только мы начинаем множить свой чудо-результат на новое число, мы его (число) предварительно делим на 2 пока делится и увеличиваем счётчик, а потом делим его на пять (тоже, пока делится) и уменьшаем счётчик. То, что осталось, множим на результат и вычисляем модуль от результата по основанию 10. (Блин, как я хочу десятичные машины!)
      После этого у нас есть одна цифра и одна степень двойки. Вспоминая, что последняя цифра любой натуральной степени любой цифры повторяется с периодом 4 (для двойки период: 6, 2, 4, 8), мы находим последнюю цифру степени двойки, множим её на ту цифру результата и вычисляем модуль. Та-дам!..
      Множить числа для факториала можно в любом порядке, мне приглянулся обратный. Плюс, можно чуть оптимизировать вычисление последней цифры степени двойки, здыхавшись case’а. Итак, привожу свой код:

Код:

program OldTask1;

var
  n, t, result, twoC: longint; {На всяк пожарный, я не считал максимумы значений}

begin
  result := 1;
  twoC := 0;
  read(n);
  while (n > 1) do begin {Цикл по всем числам}
    t := n;
    while (t mod 2 = 0) do begin
      t := t div 2;
      twoC := twoC + 1;
    end;
    while (t mod 5 = 0) do begin
      t := t div 5;
      twoC := twoC - 1;
    end;
    {Сократили на двойки и пятёрки}
    result := (result * t) mod 10;
    n := n - 1;
  end;
  if (twoC > 0) then
    result := (result shl (1 + (twoC - 1) mod 8)) mod 10; {Вот этот оптимизированный вариант. Спасибо, что двойки, а то бы пришлось писать case, а так можно shl (двоичный сдвиг влево — для тех, кто не знает).}
  write(result);
end.

4. Skyscraper

      Итак, сразу даю задачу: нам надо найти количество различных вариантов укладки стен здания (m × n) с помощью кирпичей размерами (1 × 1 × a) и (1 × 1 × b). Вопрос стоит так: как это сделать?
      Так-с… перечитывая условие задачи понимаем, что кирпичи не гнутся и не ломаются, так что тут ясно (тут и далее я буду рассматривать не всё здание, а только его какой-то слой толщиной 1, понятие стен остаётся то же, что и у здания), что кирпичи надо уложить так, чтобы все четыре стены были непрерывны. То есть так, чтобы весь слой можно было разрезать вертикально на четыре стены так, чтобы не поломать ко всем чертям ни один кирпич.
      Знаю, это звучить чуть запутанно, но я пока не понял, как сюда можно запостить картинку, так что буду объяснять на словах. Да и лень мне постить картинку.
      Итак, у здания четрые угла (ну надо же), каждый угол может быть «разрезан стенами» двумя способами: если смотреть сверху и так, что стены здания параллельны двум осям координат соответственно, то это горизонтально и вертикально. А так как углов четыре, то способов всю стену разрезать на куски аж 16. Я их тут не привожу, сами в тетрадке себе нарисуйте.
      Далее замечаем, что куски стены, которые мы получим в результате разрезания, могут быть длины (m), (m − 1), (m − 2), (n), (n − 1) или (n − 2). И плюс, подключая мозг, понимаем, что способов уложить весь слой здания при данном способе разрезания есть столько, сколько получим, перемножив количества способов уложить каждый из кусков стен.
      И последняя проблема: как узнать это количество способов? Итак, мы знаем, что если мы хотим уложить кирпичами длиной a и b стену длиной x, то нам надо их количество подобрать так, чтобы то, что мы сложим, было в точности по длине равно x, ни больше и не меньше. А значит нам надо найти все способы представления числа x в виде A × a + B × b, где A и B — это искомые количества. Мне ничего умнее в голову не пришло, как перебрать (естественно, с отсеиванием всего, что в принципе не может подойти) все возможные варианты (нам они всё равно нужны).
      А следующая проблема (количество способов разместить A кирпичей длиной a и B кирпичей длиной b так, чтобы все комбинации были уникальны [кирпичи взаимозаменяемые и равные, если у нас рядом стоит два кирпича длиной a и мы их поменяем местами — это та же самая комбинация]) решается легко: это количество способов выбрать A из (A + B), то есть (A + B)! / (A! × B!), что есть, приведя к другому виду, [(B + 1) × (B + 2) × … (A + B)] / A! если A < B.
      Я не буду здесь рассказывать, почему это всё должно влезть в int64 и не надо делать длинную арифметику, так как это будет долговато, а я уже устал колотить по клавишам, поэтому приведу свой исходник:

Код:

program Skyscraper;

var
  m, n, a, b: longint;
  m0, m1, m2, n0, n1, n2, res: int64;

function C(a: integer; b: integer): int64;
var
  result666: extended; {У меня компилятор чего-то ругался на просто «result»}
  i: integer;
begin
  if (a > b) then begin
    i := a;
    a := b;
    b := i;
  end;
  result666 := 1;
  for i := (b + 1) to (b + a) do
    result666 := result666 * (i / (i - b));
  C := round(result666); {Вдруг чего будет}
end;

function dispatch(x: integer): int64;
var
  sum: int64;
  i, j: longint;
begin
  sum := 0;
  i := 0;
  while (i <= x) do begin
    if (i = x) then begin
      sum := sum + 1;
      break;
    end;
    j := 0;
    while (i + j <= x) do begin
      if (i + j = x) then begin
        sum := sum + C(i div a, j div b);
        break;
      end;
      j := j + b;
    end;
    i := i + a;
  end;
  dispatch := sum;
end;

begin
  read(m, n, a, b);
  m0 := dispatch(m);
  m1 := dispatch(m - 1);
  m2 := dispatch(m - 2);
  n0 := dispatch(n);
  n1 := dispatch(n - 1);
  n2 := dispatch(n - 2);
  res := m0 * m0 * n2 * n2 +
         4 * m0 * m1 * n1 * n2 +
         2 * m0 * m2 * n1 * n1 +
         4 * m1 * m2 * n0 * n1 +
         m2 * m2 * n0 * n0 +
         2 * m1 * m1 * n0 * n2 +
         2 * m1 * m1 * n1 * n1; {Тут уже приведены подобные, так как есть симметричные комбинации разрезания}
  write(res);
end.

В общем, я думаю, вы мне простите некоторые вольности (типа ЛевЪа).


Doesn’t matter that man has no wings
As long as I hear the nightingale sings...

Поза форумом

 

#3 2008-11-29 07:29:36

Cris
Новий користувач
Звідки: Сумы
Зареєстрований: 2007-10-02
Повідомлень: 140

Re: Разбор решений задач первого тура.

калькулятор:

Код:

program calcus;
var n,i,j:longint;
begin
readln(n);
i:=1;
while i<sqrt(n)+1 do
begin
inc(i);
if (n mod i)=0
 then begin
      j:=j+i;
      n:=n div i;
      i:=1;
      end;
end;
if n<>1
 then writeln(j+n)
 else writeln(j+n-1);
end.

башня:

Код:

program sky2;
var m,n,a,b,i:integer;
    nx,mx:array[0..2] of integer;
procedure sl(l,p:integer);
begin
if l=p
 then inc(i);
if (a+l)<=p
 then sl(a+l,p);
if (b+l)<=p
 then sl(b+l,p);
end;
begin
readln(m,n,a,b);
sl(0,n);
nx[0]:=i;
i:=0;
dec(n);
sl(0,n);
nx[1]:=i;
i:=0;
dec(n);
sl(0,n);
nx[2]:=i;
i:=0;
sl(0,m);
dec(m);
mx[0]:=i;
i:=0;
sl(0,m);
dec(m);
mx[1]:=i;
i:=0;
sl(0,m);
dec(m);
mx[2]:=i;
n:=0;
n:=n+nx[0]*mx[2]*nx[0]*mx[2];
n:=n+nx[0]*mx[2]*nx[1]*mx[1];
n:=n+nx[0]*mx[1]*nx[1]*mx[2];
n:=n+nx[0]*mx[1]*nx[2]*mx[1];
n:=n+nx[1]*mx[0]*nx[1]*mx[1];
n:=n+nx[1]*mx[1]*nx[0]*mx[2];
n:=n+nx[1]*mx[1]*nx[0]*mx[2];
n:=n+nx[1]*mx[1]*nx[1]*mx[1];
n:=n+nx[2]*mx[0]*nx[1]*mx[1];
n:=n+nx[2]*mx[0]*nx[2]*mx[0];
n:=n+nx[2]*mx[1]*nx[0]*mx[1];
n:=n+nx[2]*mx[1]*nx[1]*mx[0];
writeln(n);
end.

Поза форумом

 

#4 2008-11-29 07:31:35

Cris
Новий користувач
Звідки: Сумы
Зареєстрований: 2007-10-02
Повідомлень: 140

Re: Разбор решений задач первого тура.

кстати могу сказать про факториал, так как у нас последнее допустимое число 32000+, то чтоб найти последнюю цыфру надо то что у нас есть после умножения делить так чтоб мы получали НЕ последнюю цыфру, А последние 5 цыфр, иначе идет збой

+ чтобы найти последнюю/последнии цыфры числа в паскале делаеться так:
число:=число mod 1000(кол нулей = кол последних чисел)
mod - деление с остатком

число:=число div 1000(кол нулей = кол первых чисел)  - получаем первые цыфры числа
div - деление нацело

Відредаговано Cris (2008-11-29 07:35:44)

Поза форумом

 

#5 2008-11-29 11:04:44

MAXXX
Новий користувач
Звідки: м. Київ
Зареєстрований: 2006-10-17
Повідомлень: 132

Re: Разбор решений задач первого тура.

По поводу Фибо:
Чуть более медленным, но требующим гораздо меньшего времени на размышления/расчеты перед реализацией  решением будет такое:
Делаем двоичный поиск по Fn-1. Зная Fn и Fn-1 проверяем, равно ли Fm требуемому значению. Если полученное нами значение больше(меньше) нужного, то в поиске изменяем верхнюю(нижнюю) границу. В конце, зная Fn и Fn-1, при которым мы получаем правильное значение Fm, вычисляем F1.
Кстати на Тимусе есть чуть более общий вариант этой задачи. Тут.
Основная часть моего кода выглядела так:

Код:

    if (p>q)
    {
        swap(p,q);
        swap(fp,fq);
    }
    low=-2000000000;
    high=-low;
    while(high-low>1)
    {
        if (solve(p,fp,(high+low)/2,q)>fq)
            high=(high+low)/2;
        else
            low=(high+low)/2;
    }
    if (solve(p,fp,low,q)<fq)
        low=high;

Так как весь код я, ясное дело, показывать не собираюсь=),то скажу лишь что solve по значениям Fn и Fn-1 определяло Fm, а в конце верное значение  Fn-1 оказывалось в переменной low.

Відредаговано MAXXX (2008-11-29 11:07:33)


ICQ 426287475

Поза форумом

 

#6 2008-11-29 11:42:18

Гарагатий Ігор
Новий користувач
Зареєстрований: 2006-10-28
Повідомлень: 8
Вебсайт

Re: Разбор решений задач первого тура.

Задача Oldtask1
1)0 на конце мы можем получить только при произведении 2 на 5.
2)Так-же на последнюю цифру произведения влияет только последняя цифра числа.
3)при умножени на 10 последняя ненулевая цифра произведения равна последней ненулевой цифре исходного числа
4)Следовательно чтобы получить последнюю ненулевую цифру факториала перемножаем все последние цифры чисел от 1 до n, но если число а делится на 5, то умножаем на последнюю цифру а/(5^n), где n- максимальная степень 5 на которую делится а, и убираем такое-же количество 2 в последствии

Поза форумом

 

#7 2008-11-29 13:07:56

Саня
Новий користувач
Зареєстрований: 2008-11-24
Повідомлень: 24

Re: Разбор решений задач первого тура.

Задача Fibo
Я для початку знаходив число s[m-1] ,де s-сама послідовність
Якщо воно не ціле ,то даної послідовності не існує.

Код:

var q,d,f,c,b,e,r,l,j,k,m,n,y,a:int64;
s:array[1..50]of int64;
begin
read(m,s[m],n,s[n]);
q:=m;
a:=0;
d:=0;
f:=1;
while q<n do begin
q:=q+1;
a:=d+f;
f:=d;
d:=a;
end;
e:=a;
q:=m;
l:=0;
k:=0;
a:=s[m];
j:=a;
while  q<=n do
begin
q:=q+1;
l:=j+k;
j:=k;
k:=l;
end;
r:=l;
y:=(s[n]-r) div e;
if (s[n]-r) mod e=0 then begin
q:=m;
a:=s[m];
b:=y;
while q<>1 do begin
q:=q-1;
c:=a-b;
a:=b;
b:=c;
end;
write(a);
end
else writeln('Impossible');

end.

Відредаговано Саня (2008-11-29 13:08:53)

Поза форумом

 

#8 2008-11-29 13:16:14

Саня
Новий користувач
Зареєстрований: 2008-11-24
Повідомлень: 24

Re: Разбор решений задач первого тура.

Oldtask2

Код:

var q,a,d,f,j,i:longint;
s1,s2,s3:string;
function sr(s1,s2:string;q,i:longint):boolean;
var l,k,m,n:longint;
begin
n:=0;
k:=i-1;
for l:=1 to d do begin
k:=k+1;
if s1[k]=s2[l] then begin
n:=n+1;
end;
end;
sr:=false;
if n=d then begin
sr:=true;
end;
end;
 begin
 readln(s1);
 readln(s2);
 readln(s3);
 f:=length(s1);
 d:=length(s2);
 q:=length(s3);
 i:=1;
  if f>0 then begin
 while i<=f do begin
if sr(s1,s2,q,i)=false then begin
write(s1[i]);
i:=i+1;
end;
if sr(s1,s2,q,i)=true then begin
for j:=1 to q do begin
write(s3[j]);
end;
i:=i+d;
end;
end;
end;
writeln;
 end.

Поза форумом

 

#9 2008-11-29 14:44:21

sonner
Новий користувач
Зареєстрований: 2008-11-25
Повідомлень: 8

Re: Разбор решений задач первого тура.

Как мне кажется, это одно из самых коротких решений задачи Skyscraper

Код:

#include <cstdlib>
#include <iostream>
#include <stdint.h>
using namespace std;

const int kMaxMN = 40;
typedef int64_t longInt;

longInt count(int m, int n, int a, int b)
{
    longInt wall[4*kMaxMN];
    wall[0] = 1;
    int minIndex = 0;
    for (int i = 1; i <= 2*(m+n-2); i++) {
        wall[i] = 0;
        if (i-a>=minIndex) wall[i] += wall[i-a];
        if (i-b>=minIndex) wall[i] += wall[i-b];
        if (i==m || i==m+n-1 || i==2*m+n-2)
            minIndex = i-1;
    }
    return wall[2*(m+n-2)];
}

int main(int argc, char *argv[])
{
    int m, n, a, b;
    cin >> m >> n >> a >> b;
    cout << count(m, n, a, b) + count(n, m, a, b) << endl;
    return 0;
}

Поза форумом

 

#10 2008-11-29 15:33:11

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: Разбор решений задач первого тура.

Ну вот еще довольно короткое решение скайскрейпер:

Код:

#include <iostream>
#include <cstdlib>
using namespace std;
int v1,v2,a,b,c,d,i,j,n,m,k;
unsigned long long mas[51],res,cur;
inline void um(unsigned long long &cur,int a,bool r,int c1,int c2)
{
    r?cur*=mas[a+(c1!=0)+(c2!=0)]:cur*=mas[a+(c1==0)+(c2==0)];
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&v1,&v2);
    mas[0]=1;
    for (int i=1;i<=max(n,m);i++)
    {
        a=i-v1; b=i-v2;
        if (a>=0) mas[i]+=mas[a];
        if (b>=0) mas[i]+=mas[b];
    }
    res=0;
    for (int i=0;i<16;i++)
    {
        cur=1;
        um(cur,m-2,1,i&1,i&2);
        um(cur,m-2,1,i&4,i&8);
        um(cur,n-2,0,i&2,i&4);
        um(cur,n-2,0,i&1,i&8);
        res+=cur;
    }
    cout<<res<<endl;
}

Решение фибо бинпоиском:

Код:

#include <iostream>
#include <cstdlib>
using namespace std;
int n,m,c,d,i,j,k;
long long a,b,l,p,xx,cur,next;
inline long long check(long long xx)
{
    long long last=a,cur=xx;
    for (int i=m+2;i<=n;i++)
    {
        long long next=last+cur;
        last=cur; cur=next;
        if (cur>1000000000000000000LL || cur<-1000000000000000000LL) return cur;
    }
    return cur;
}
int main()
{
    cin>>m>>a>>n>>b;
    if (n!=m+1)
    {
        l=-1000000000000000000LL; p=-l;
        while (p-l>1)
        {
            xx=(p+l)>>1;
            if (check(xx)>b) p=xx; else l=xx;
        }
        if (check(l)!=b) l=p;
        if (check(l)!=b) { printf("Impossible\n"); exit(0); }
    } else l=b;
    cur=a; next=l;
    for (int i=m-1;i>=1;i--)
    {
        long long prev=next-cur;
        next=cur; cur=prev;
        if (cur>1000000000000000000LL || cur<-1000000000000000000LL) { printf("Impossible\n"); exit(0); }
    }
    cout<<cur<<endl;
}

Oldtask1:

Код:

#include <iostream>
#include <cstdlib>
using namespace std;
#define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
#define rep(i,n) FOR(i,1,n)
#define C(a) memset((a),0,sizeof(a))
const int s5[]={1,5,25,125,625,3125,3125*5,3125*25};
int a,b,c,d,i,j,n,m,k;
int st2[40000];
int st5[40000];
int main()
{
    scanf("%d",&n);
    C(st2); C(st5);
    st2[1]=0;
    st5[1]=0;
    a=1;
    c=0;
    rep(i,n)
    {
        if (i%2==0)    st2[i]=st2[i>>1]+1;
        if (i%5==0)    st5[i]=st5[i/5]+1;
        c+=st2[i]-st5[i];
        a=(a*(i/((1<<st2[i])*(s5[st5[i]]))))%10;
    }
    if (c>0) 
    {
        rep(i,c) a=(a<<1)%10;
    } else if (c<0) a=(a*s5[-c])%10;
    printf("%d\n",a);
}

Поза форумом

 

#11 2008-11-29 19:10:20

NEWUSER
Новий користувач
Зареєстрований: 2007-11-01
Повідомлень: 9

Re: Разбор решений задач первого тура.

Хочу добавить несколько слов по поводу решения задачи OldTask1.
Алгоритм, реализованный Cardinal Nightingale, безусловно правильный, но:
1. Следует заметить, что при решении данной задачи простое нахождение факториала тоже возможно, мало того, оно работает и проходит все тесты. Естественно, при нахождении факториала умножение производится только над последними 7-ю цифрами без учета конечных нулей (лень было думать => просто несколько переделал свой класс, написанный для работы с "длинными числами"). Кроме того, я использовал массив из 9 значений с заранее простчитанными значениями последних 7-ми цифр факториала, равномерно покрывающих весь диапазон возможных значений для N.
2. Если говорить о скорости работы, то ради спортивного интереса я переписал программу, предложенную Cardinal Nightingale, на С++ и
сравнил по скорости со своей (использовалась старенькая MS Visual Studio 6.0, время замерялось с помощью функции timeGetTime() - находится в библиотеке winmm.lib). В результате для N = 32767 моя программа работа 7-8 мс, а программа Cardinal Nightingale - 9мс.
После некоторой оптимизации программа Cardinal Nightingale стала работать 5 мс для того же N = 32767, не утеряв при этом возможность проходить все тесты и стала выглядеть так:

#include <iostream.h>
//#include <windows.h>

typedef    unsigned long int    DWORD;

int main()
{
    DWORD n, t, res = 1, twoC = 0;

    cin >> n;

//    DWORD ms1 = timeGetTime();

    while (n > 1)
    {
        t = n--;

        while (t & 1 == 0)  // Деление работает куда медленнее, чем побитовые операции и сдвиг, даже на современных CPU
        {
            t >>= 1;
            twoC++;
        }

        while (t % 5 == 0)
        {
            t /= 5;
            twoC--;
        }

        res = res * t % 10;
    }


    if (twoC > 0)
        res = (res << ((1 + (twoC - 1) & 7))) % 10;

    cout << res << endl;

//    cout << timeGetTime() - ms1 << endl;

    return 0;
}

Из всего этого следует, что даже эффективный алгоритм при неоптимальной его реализации может проиграть менее эффективному алгоритму, но реализованному с использованием оптимизации, даже в пределах одного языка (не используя ASM)

Поза форумом

 

#12 2008-11-30 13:42:24

Cardinal Nightingale
Новий користувач
Звідки: Десь подалі від Александрії
Зареєстрований: 2008-11-24
Повідомлень: 19
Вебсайт

Re: Разбор решений задач первого тура.

Я не буду комментировать то, что написал NEWUSER, долго, скажу то, что всё это, в принципе, верно. Я не хочу разжигать холивар по поводу того, надо ли делать оптимизацию везде и всегда, выжимая последние миллисекунды и т. п.

У меня есть пара вопросов к администрации насчёт компиляторов. Если это не коммерческая или государственная тайны, то ответьте пожалуйста. Я думаю, это хорошо облегчит жизнь всем участникам.

Вопросы формулируются достаточно просто: какие точные версии компиляторов используются, каким стандартам должен подчиняться код (название и год) и с какими ключами компилирутся программы (включена ли оптимизация и всё такое)?

И ещё одна маленькая просьба-рекомедация всем участникам, выкладывающим сюда коды. Мы не на IOCCC, так что можно делать ваш код более понятным (чуть структурировать и не юзать на всю катушку хаки) широкому населению. Я не говорю, что вы дураки, раз используете хаки, я не говорю, что вы дураки, раз не структурируете код, я не говорю, что я дурак, раз я не могу понять ваш код (я его понимаю). Я не требую того, чтобы это было немедленно исполнено, я просто даю совет, в надежде на то, что хотя бы один человек меня выслушает.

И соцопрос-прикол: что делает этот Си-код и почему он так делает?

Код:

#include <stdio.h>
#include <math.h>

int main(void){
  int i = 5;
  double j;
  i = i++ + i++;
  j = ((i % 2) ? sin : cos)(PI / 3);
  printf("%d %lf", i, j);
/*
  А что будет, если написать вот так:
  printf("%d %lf", i, j, ++i);
*/
  return 0;
}

А вот этот что делает?

Код:

#include   <stdlib.h>
#include    <stdio.h>
#define   P    printf
#define   I      atoi
int main(int a,char*v
[]){int r=5, i;if(a>1
) r=I(v[1]); if(r<=0)
r=5;if(r%2==0)++r;for
(i=0; i<r*r; P(i/r==(
3*r)/2-(i%r+1)||i/r==
r/2 - i%r||i/r==r/2+i
%r||i/r==i%r-r/2?"*":
" "),i++, i % r==0?P(
"\n") : 0);return 0;}

Відредаговано Cardinal Nightingale (2008-11-30 13:59:02)


Doesn’t matter that man has no wings
As long as I hear the nightingale sings...

Поза форумом

 

#13 2008-11-30 15:33:49

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Разбор решений задач первого тура.

Cпасибо всем, кто отписался wink

Кстати, на задаче Fibo таймлимит какой-то странный, один раз выдаёт 0.13 секунд, другой раз — 0.03 секунд... (по одному и тому же тесту)

17:50 -------------------

Разобрался, почему моя Fibo не проходит 12 тест. В системе с уравнениями вида AX + BY = C я проверял на целочисленность X, но не проверял Y. А надо было smile

18:30 -------------------

Почему моя Fibo не проходила два последних теста.
Итак, 20 и 21 тест очень-очень хитрые smile
Как оказалось, ответ на них «в принципе» есть, но...
Ключевая строчка из условия: |a(i)|<=10^18
Я как-то на неё поначалу не обратил внимания, и считал, что в этих пределах находятся только два элемента, указанные во входных данных. Но тогда получалось, что первый элемент может не влезать в int64 и придётся делать длинную арифметику... Я всё-таки сделал длинную арифметику, и ответ, который выдаёт программа, в принципе правильный, но так как он превышает число |a(i)|<=10^18 степени, то следовало выводить «Impossible».
Что ж, могу только пожелать тем, у кого возникла подобная проблема, быть внимательнее в следующих турах wink

----------------

Оффтоп:
Всього зареєстрованих користувачів: 444 smile

Відредаговано guest1 (2008-11-30 18:31:12)

Поза форумом

 

#14 2008-12-02 12:46:03

RReverser
Новий користувач
Зареєстрований: 2008-11-25
Повідомлень: 8

Re: Разбор решений задач первого тура.

> Кстати, на задаче Fibo таймлимит какой-то странный, один раз выдаёт 0.13 секунд, другой раз — 0.03 секунд... (по одному и тому же тесту)
Сервер перевантажений, тому і час різний виходить.

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt