Помогите с олимпиадными задачами по программированию

[Gargolev]

http://www.humyo.com/F/772412-131332789

[FEV]

Код: [Выделить]

program stepen;
var
a,b,z:integer;
s:string;

function Power(X:integer;N:integer):integer;
  var
  I:integer;
  Y:integer;
  begin
  if N>0 then
   begin
   Y:=1;
   for I:=1 to N do
   y:=y*x;
   end else;
  Power:=y
end;

begin
writeln('Введите число a и b');
read(a,b);
if a>=1 then
if b<=10000 then
 begin
 z:=power(a,b);
 str(z,s);
 z:=length(s);
 s:=copy(s,z,1);
 writeln(s);
 readln
 end else else;
 readln
end.
Вот пример решения первой задачи на Паскале (TurboPascal 7). Если честно я не понял, в какой среде тебе это надо было. Но данный код можно преобразовать под любую среду... Помог чем мог

[Йобан Матич]

FEV,
Ошибочка
В 0 степень не возводит

Код: [Выделить]

{fix}
function pow(X:integer;N:integer):integer;
var
  i:integer;
begin
  pow:=1;
  if N>0 then
    begin
      for I:=1 to N do
        pow:=pow*x;
    end;
end;


Ещё вариант

Код: [Выделить]

var
 x, y : integer;

function pow(x,y:integer) : double;
begin
  pow := exp(ln(x)*y);
end;

begin
  readln(x);
  readln(y);
  writeln(pow(x,y):0:2);
  readln;
end.


[FEV]

Ошибку 116 выдает в

Код: [Выделить]

pow := exp(ln(x)*y);Ну а про 0 можно было исправить... Пусть сам...
P.S.Напиши мне код без ошибок, чтоб я понял и запомнил твою логику...

[GManiac]

Вы неправильно условие поняли. Там написано: 1 ≤ a, b ≤ 10000. Просто так возводить в степень нельзя, иначе получится большое число. Но известно, что (a * b) mod x = (a mod x) * (b mod x) mod x.
Поэтому самое простое решение выглядит так:

Код: [Выделить]

function last_digit(const a,b:word):byte;
var i:word;
     res:byte; {на Дельфи можно использовать встроенную переменную Result}
begin
  res:=a mod 10;
  for i:=2 to b do res:=res*(a mod 10) mod 10;
  last_digit:=res;
end;Ну и использовать функцию в программе.
Например, 3^56 = 523347633027360537213511521. Программа выдаёт 1.
Более продвинутое решение - использовать биты (как бывает в задачах "Сделайте быстрое умножение, используя только сложение"), т.е. даёт ответ за log2 (10000) = 14 шагов или около того. Но обычно на олимпиадах лишнего усложнения не требуют, даже иногда это нежелательно.

[FEV]

Хм. Да, я забыл. Что олимпиады - это выявление нестандартного мышления... или его развитие. Т.е. уметь обойти трудности простым путем...

[Йобан Матич]

Ошибку 116 выдает

В начало программы добавь

Код: [Выделить]

{$N+}{$E+}

Попробуй FreePascal.

[CaH4e3]

GManiac, шагов O(1).

0. B = 0 дает 1.
1. А mod 10 = 0, 1, 5, 6 дают всегда соответственно 0, 1, 5, 6 независимо от B.
2. A mod 10 = 2 дает всего 4 значения 6, 2, 4, 8 для степеней B mod 4 соответственно.
3. A mod 10 = 8 есть то же, что и пункт 2, только (B + 3) mod 4.
4. A mod 10 = 3 соответственно таблица 1, 3, 9, 7.
5. А mod 10 = 7 степень такая же, как и в п.3 (B + 3) mod 4 для таблицы в п.4.
6. A mod 10 = 4, 9 - соответствено таблицам для п.2 и п.4 но индекс от степени будет (B * 2) mod 4.

Таким образом (пардон муа за мой "паскаль"):

Код: [Выделить]

unsigned char last_digit(unsigned short A, unsigned short B)
{
  unsigned short amod = A % 10;
  unsigned short bmod = B;
  unsigned char amod2[4] = {6, 2, 4, 8};
  unsigned char amod3[4] = {1, 3, 9, 7};

  if (B==0) return 1;
  switch (amod)
  {
    case 0:
    case 1:
    case 5:
    case 6: return amod;
    case 8: bmod += 3;
    case 2: return amod2[bmod % 4];
    case 7: bmod += 3;
    case 3: return amod3[bmod % 4];
    case 4: return amod2[(bmod * 2) % 4];
    case 9: return amod3[(bmod * 2) % 4];
  }
}

Одна итерация.

[GManiac]

Так я привёл самое топорное решение. Насколько я знаю, за "изысканное решение" никаких бонусов, зато в них больше вероятность ошибки. Воообще, олимпиады у нас - это та ещё история.

[CaH4e3]

Ну раз в каждой задаче акцентируется внимание на время отработки тестового задания, из двух тупых решений придется все-таки выбирать более "изысканное". Ладно первая - самая простая задача. А дальше, с поиском площадки, тупым перебором, если до кучи дадут поле гигантское, за секунду не управишься... Хотя... Само условие с ограничением по времени выполнения - тупость какая-то, если на более менее современной машине делать, то самое тупое решение уложится слихвой в норматив. Да и даже если бонусов не дают, все равно есть всегда желание выпендриться.

[Gargolev]

CaH4e3, как только увидел задачу, сразу подумал о таком же решении. Остальные получаются простые, но слишком требовательные к ресурсам. Мое решение будет почти таким же - не пойму, почему у тебя (b+3)mod 4 и (b*2)mod 4, я бы использовал вэтих случаях b mod 4, потом возводил бы a в эту степень и смотрел последнюю цифру.

[CaH4e3]

А ты посчитай, да и зачем возводить что-то в степень, если степени давно известны.

[FEV]

В начало программы добавь

Код: [Выделить]

{$N+}{$E+}

Попробуй FreePascal.

Эээ. Дай сцылку на FreePascal... А твою логику я понял, ниче особенного... Я ранее никогда не пользовался exp(ln(x)*y) для возведения в целую степень, да и лень было искать короткие пути, когда длинным путем можно быстрей накалякать. Но теперь я это запомнил...
Но у Gargolev'а олимпиады прикольные... Настоящее насилование мозгов... Но решив такие задачи раз, будешь крутым перцем

[GManiac]

FEV, это стандартные задачи. Причём для школьников. Много подобных есть на http://neerc.ifmo.ru/, причём судя по внешнему виду описаний ЕГО задач они взяты как раз оттуда. Или откуда-то рядом.
Только вот Gargolev не объяснил, зачем ему это надо???

exp(ln(x)*y)

формула за 10-й класс: a^log_ab=b.

Добавлено позже:
Стоп. 11-й, но это неважно.

[Gargolev]

Мои предположения, как решать (первая задача очевидна, насчет второй никаких идей нет):
3)отбрасываются отрезки, которые ни с чем не пересекаются, из оставшихся строится граф (матрица смежности, для быстродействия можно даже ее наполовину заполнять). Критерий связи элементов в графе - пересечение отрезков. Ну, и на конечных этапах решение можно остановить - когда колво найденных элементов будет превышать колво оставшихся элементов.
4)пока придумал только перебор, правда с некоторым отсечением, но смутно себе представляю каждый раз искать максимальный и минимальный элемент. А смысл такой: от текущего элемента движемся вправо, пока условие не перестанет выполняться или не достигнем правой границы. Далее смещаемся вниз до тех пор, пока условие не перестанет выполняться. Когда условие перестает выполняться смещаемся влево, пока снова не выполнится, потом та же схема (вниз-влево-вниз-влево),  если при этом достигнем нижнего или левого края, то прекращаем решение относительно данного элемента. Точно так же как и в 3-м на конечном этапе можно остановить поиск решения.
5)рассмотреть все возможные варианты сгиба листа (у меня получилось где-то 5-6 вариантов)
6)Движение рикши между городами можно изобразить на одном из двух графиков:
1. 3 участка: V=k*t, V=Vmax, V=Vmzx-kt
2. 2 участка (если маленькое расстояние): V=kt, V=Vmax1-kt, причем Vmax1<=Vmax.

Добавлено позже:
Первую задачу решил и сдал, но пришлось сделать ее самым примитивным способом - фактически то же, что писал GManiac, но в немного более понятном виде

Добавлено позже:
уже неактуально