Задачи олимпиады 1999 года «Легенда» взяты с сайта "Олимпиады по Кибернетике"

.Согласно древней индийской легенде, при сотворении мира, в том месте, где находится середина земли бог Брама поставил на бронзовой площадке вертикально три алмазные палочки. На одну из палочек надел он 50 золотых кружков разного диаметра так, что они образовали конус. И построил он город Бенарес, и поставил храм, и повелел жрецам перенести все диски с первой палочки на третью, при этом соблюдая условия: переносить за один раз только один кружок и снятый кружок класть или на свободную палочку или на кружок только большего диаметра. И жрецы составили алгоритм переноса кружков и следуют ему неукоснительно. И хотя этот алгоритм оптимален, это самый длинный в мире алгоритм - ведь работает он от сотворения мира до самого его конца потому, что, как только последний из дисков будет положен...

Стоп! Что это за город Бенарес, если всем известно, что название этой задачи - "Ханойские башни"? И кружков на самом деле не 50, а 64. Также общеизвестно, что для решения этой задачи применяется рекурсивный алгоритм, а для переноса N кружков необходимо 2^N-1 раз переложить по одному кружку!

- Да, это так. Но последние находки сотрудников кафедры истории кибернетики Калькуттского Государственного Университета (КГУ) заставляют нас взглянуть по-новому на эту задачу. Оказывается, что жрецы для перекладывания кружков использовали наемную рабочую силу. При этом для защиты трудящихся от инфляции и девальвации применялась прогрессивная система оплаты: за первый переложенный кружок заплатили одну рупию, за второй - три, за третий - пять, за четвертый - семь... За каждый следующий кружок - на две рупии больше предыдущего. Ученые попытались подсчитать расходы на оплату рабочих, но по причине недостаточной осведомленности в вопросах программирования не справились с этой задачей. А вы справитесь?

Требуется написать программу, которая по заданному числу дисков N определит число рупий, израсходованных на оплату труда.

Входной файл INPUT.TXT содержит число N из диапазона от 2 до 100.
Выходной файл OUTPUT.TXT должен содержать число рупий (в десятичной системе счисления).

Ограничение времени - 10 секунд.

Пример 1.

Входной файл:

2

Выходной файл:

9

Пример 2.

Входной файл:

25

Выходной файл:

1125899839733761

Комментарии к задаче

Условия задачи не так сложны, как может показаться при первом прочтении. Соскоблив сюжетную "шелуху", можно обнаружить такую постановку:

Для заданного целого N (от 2 до 100) требуется найти сумму K положительных нечетных чисел, где
K = 2^N - 1 .
Т.е. S = 1 + 3 + 5 + ... (всего K слагаемых).

Решение "в лоб":
1) Возвести 2 в степень N;
2) Вычесть единицу;
3) В цикле до K складывать нечетные числа.

Недостатки:
- При больших значениях N стандартные типы данных (ни целые, ни вещественные) неспособны вместить результат.
- Цикл суммирования будет выполняться невообразимо долго. Компьютер считает быстро, но не до такой же степени!

Хорошее решение:

Сумма представляет собой арифметическую прогрессию, которая сворачивается в более красивую форму:
S = K²

Окончательная формула:
S = (2^N - 1) ²

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

Для нахождения результата нам потребуется реализовать следующие операции с длинными числами:
- Сложение двух длинных чисел.
- Умножение длинного числа на скаляр.
- Умножение двух длинных чисел (выполняется с использованием двух предыдущих операций).
- Вычитание единицы из длинного числа.

Наилучшее решение:

Воспользуемся тем, что число K, которое нужно возвести в квадрат, не произвольно, а имеет вполне определенный вид.
Вспомним свойства:
Двоичное представление числа 2^M содержит 1 в разряде с номером M и 0 в младших разрядах (с 0 по M-1).
Число 2^M-1 содержит 1 в разрядах с 0 по M-1 (всего M единиц).

Перепишем результирующую формулу в виде:
S = (2^N - 1) ² = A - B + 1,
где
A = 2^2N - 1,
B = 2*2^N - 1 = 2^N+1 - 1.

Разность чисел A и B в двоичном представлении содержит единицы в разрядах c номерами с N+1 по 2N-1. Прибавление 1 изменяет только нулевой разряд.

Окончательно, число S состоит (слева, от старших разрядов) из N-1 единицы, N нулей и одной единицы.

Итак, зная число N, мы можем СРАЗУ сказать, как будет выглядеть результат в двоичном представлении.

Пример (N=3):

Осталось только перевести результат в десятичное представление. Для этого найдем последовательно степени двойки с нулевой по 2N-1-ю и степени с N+1 по 2N-1 сложим между собой, не забыв прибавить еще единицу.

Нам потребуются следующие операции:
- Умножение длинного числа на 2.
- Сложение нескольких длинных чисел (прибавление дополнительной единицы можно реализовать здесь же, имитируя перенос единицы в нулевой разряд).

Ниже приведен листинг программы, в которой реализован описанный алгоритм.

#include <stdio.h>

#define maxN 100

#define maxL 1+(int)2*maxN/3

char M[2*maxN][maxL];

int N,L,K,s,p,v;

char R[maxL];

int main(){

  int i,j;

  FILE *f1,*f2;

  f1=fopen("input.txt","rt");

  fscanf(f1,"%d",&N);

  fclose(f1);

  K=2*N;

  L=1+2*N/3;

  // Заполняем массив M[i][] строками,

  // содержащими поразрядное десятичное

  // представление i-й степени двойки

  M[0][L-1]=1;

  for (i=1; i<K; i++){

    // p - перенос при умножении

    p=0;

    // число в i-й строке получаем умножением

    // на 2 числа в предыдущей строке,

    // двигаясь справа налево

    for (j=L-1; j>=0; j--){

      v=2*M[i-1][j]+p;

      M[i][j]=v%10;

      p=v/10;

    }

  }

  // К результату добавляется единица (2^0)

  p=1;

  // Складываем N-1 старших степеней двойки

  // и результат заносим в R

  for (j=L-1; j>=0; j--){

    s=p;

    for (i=N+1; i<=(2*N-1); i++)

      s+=M[i][j];

    R[j]=s%10;

    p=s/10;

  }

  f2=fopen("output.txt","wt");

  j=0; while (R[j]==0) j++;

  for (   ; j<L; j++){

    fprintf(f2,"%d",(int)R[j]);

  }

  fclose(f2);

  return 0;

}

Груз массой m₁ подвешен к нити, намотанной на барабан радиуса r₁, который жестко соединен с барабаном радиуса r₂. На этот барабан также намотана нить, которая через блок соединена с грузом массой m₂.

Определить максимально возможное значение m₁, при котором второй груз останется на месте, если предельная сила трения равняется F_T.

При этом полагаем, что ускорение свободного падения
g = 9.2 м/с² ;
Атмосферное давление
p = 1.013*10⁵ Па.

Входной файл INPUT.TXT содержит вещественные числа m₂, r₁, r₂, F_T.
Выходной файл OUTPUT.TXT должен содержать значение m₁ (точность-два десятичных знака).

Ограничение времени - 10 секунд.

Пример 1.

Входной файл:

5 0.2 1 50

Выходной файл:

27.17

Пример 2.

Входной файл:

6 1.2 0.8 70

Выходной файл:

5.07

Комментарии к задаче

Итак, с одной стороны к барабану приложена сила m₁g, длина плеча равна r₁. С другой - действует сила F_т и плечо - r₂. Требуется определить значение m₁, при котором система будет находиться в равновесии.

Запишем уравнение равновесия: m₁g r₁ = F_т r₂. Отсюда получим m₁ = F_т r₂ / g r₁.

Информация об атмосферном давлении и массе m₂ предназначается только тем, у кого возникают определенные трудности при решении подобных задач.

Ниже приведен полный текст программы, вычисляющей искомое значение.

#include <stdio.h>

#define g 9.2

float m1, m2, r1, r2, ftr;

int main() {

  FILE *f1, *f2;

  f1 = fopen("input.txt", "rt");

  fscanf(f1, "%f%f%f%f", &m2, &r1, &r2, &ftr);

  fclose(f1);

  m1 = ftr*r2/(r1*g);

  f2 = fopen("output.txt", "wt");

  fprintf(f2, "%10.2f", m1);

  fclose(f2);

  return 0;

}

Задачи кибернетической  олимпиады 2002 года «Квадраты»

Имеется бумажный прямоугольник с длинами сторон a и b (целые числа). Его можно разрезать таким образом, что получится N квадратов с целочисленными сторонами. Ясно, что максимально возможное количество квадратов, которое может быть получено из прямоугольника, равно a*b. А каково наименьшее количество квадратов, которое можно получить разрезанием? При этом никаких "лишних" обрезков оставаться не должно.

Входной файл INPUT.TXT содержит числа a и b (a ≤ 30000; b ≤ 30000).
Выходной файл OUTPUT.TXT должен содержать искомое число.

Ограничение на время выполнения программы - 10 секунд.

Пример

Входной файл:

333 555

Выходной файл:

4

Входной файл INPUT.TXT содержит вещественные числа ω, R, и H.
Выходной файл OUTPUT.TXT должен содержать искомое число L с точностью до двух знаков после запятой.

Ограничение на время выполнения программы - 10 секунд.

Пример

Входной файл:

0 2 2

Выходной файл:

4.00

Комментарии к задаче

Приведем сначала алгоритм, который прост в реализации, но не всегда дает правильный ответ (впрочем, на олимпиаде такого решения для этой задачи было достаточно).

Возьмем прямоугольный листок бумаги в клеточку и ножницы (можно мысленно). Действительно, если разрезать листок по каждой из линий, получим максимально возможное количество квадратов - A*B (столько, сколько всего клеточек в прямоугольнике). Квадраты получились маленькие. Если квадраты будут покрупнее, то их количество будет меньше. Пожалуй, стоит резать так, чтобы размеры квадратов были как можно больше.

Как это сделать? Предлагается сначала отрезать от исходного прямоуольника самый большой квадрат, какой только возможен. Очевидно, что сторона этого квадрата равна MIN(A,B). Пусть, например, A > B. Отрежем этот квадрат и отложим в сторону. Теперь у нас остался прямоугольник со сторонами (A-B) и B. Поступим с ним так же - отрежем от него наибольший квадрат. Резать надо до тех пор, пока оставшийся прямоугольник не окажется квадратом. Если A = B, значит пора остановиться. Требуется подсчитать, сколько квадратов у нас получилось при этих манипуляциях.

Получается вот такой цикл:

  cnt := 1; {Меньше одного квадрата не может быть!}

  While a <> b Do Begin

    If a > b Then

      a := a-b

    Else

      b := b-a;

    cnt := cnt + 1;

  End;

По завершении цикла переменная cnt содержит искомое число.
Можно заметить, что этот цикл реализует (попутно) алгоритм Евклида для нахождения наибольшего общего делителя чисел A и B.

Можно попытаться сократить временные затраты (хотя в нашем случае нет такой необходимости), используя вместо вычитания целочисленное деление:

  cnt := 1;

  While a <> b Do

    If a > b Then Begin

      cnt := cnt + (a Div b);

      a := a Mod b;

    End

    Else Begin

      cnt := cnt + (b Div a);

      b := b Mod a;

    End;

Приведенный выше алгоритм использует "жадную" стратегию, однако жадность иногда мешает достичь желаемого результата. В частности, для прямоугольника 5x6 решение не оптимально.

Этот контрпример привел Г.Н. Гутман, он же предложил идею решения методом динамического программирования:

Предположим, мы решили задачу для всех полосок, более узких, чем наша. Тогда разбивая исходную полоску на две разными способами и складывая результаты для каждой из них, получаем набор решений, среди которых ищем оптимальное.

Рассмотрим возможную реализацию этого алгоритма:
Для получения ответа на основной вопрос - каково минимальное количество квадратов в прямоугольнике размера mxn следует сначала найти ответы на промежуточные вопросы о прямоугольниках меньшего размера.

R_m,n = min{ R_m,1+R_m,n-1, R_m,2+R_m,n-2, ... R_m,n-1+R_m,1, R_1,n+R_m-1,n, R_2,n+R_m-2,n, ... R_m-1,n+R_1,n }.

Будем искать решения с помощью таблицы (на примере 5x6-прямоугольника). При этом значения элементов первого столбца, первой строки и главной диагонали таблицы очевидны.

Для заполнения (i,j) ячейки таблицы требуется просмотреть значения элементов i-й строки с 1-го до j-1-го и j-го столбца с 1-го до i-1-го.
(Аналогичную таблицу можно составить и на основе приведенного ранее алгоритма, тогда будет видно, что предыдущий алгоритм для каждой заполняемой ячейки проверяет или только строку, или только столбец.)

После заполнения таблица будет выглядеть так:

Таблица решений обладает симметрией относительно главной диагонали, что позволяет сократить число выполняемых операций.

Задачи олимпиады 2003 года «Ящик»

Под каким углом к горизонту нужно тянуть за веревку тяжелый ящик массы m, кг, для того, чтобы передвигать его волоком по горизонтальной поверхности под действием постоянной по модулю силой F, Н для получения максимального ускорения? Коэффициент трения равен K.
Ускорение свободного падения равно 9.81 м/с².

Входной файл INPUT.TXT содержит вещественные числа m, F, K.
Выходной файл OUTPUT.TXT должен содержать значение угла в градусах с точностью не менее двух знаков после запятой.

Ограничение на время выполнения программы - 10 секунд.

Пример

Входной файл:

10  300  0.2

Выходной файл:

11.31

Задачи кибернетической олимпиады 2004 года

В Вашем доме поселилась мышь и прогрызла целое множество ходов под полом. После тщательного обследования Вы нашли 11 входов/выходов. Также с помощью рентгеновских очков Вы составили карту мышиного лабиринта. И вдруг, совершенно случайно Вы заметили мышь, прыгнувшую в одну из 11 норок. Вам требуется определить все норки, из которых она может появиться, чтобы поставить там мышеловки. Карта лабиринта - лист клетчатой бумаги. Если в клетке стоит 1 - значит там стена, если 0 - значит проход. По диагонали двигаться нельзя. Мышь умеет поворачивать только на прямые углы.

Вход: двумерный массив чисел 0,1, размера 100 на 100, это карта лабиринта. Если в ячейке стоит 1 - значит это стена, если 0 - то это проход. Во всех крайних клетках, кроме 11 стоит число 1 (стена). Нули стоят в клетках с координатами (x,y) (x и y меняются от 0 до 99):
(01,99) - норка номер 0, в нее юркнула мышь;
(01,0) - норка номер 1;
(03,0) - норка номер 2;
(05,0) - норка номер 3;
(07,0) - норка номер 4;
(09,0) - норка номер 5;
(11,0) - норка номер 6;
(13,0) - норка номер 7;
(15,0) - норка номер 8;
(17,0) - норка номер 9;
(19,0) - норка номер 10.

Пример (уменьшенный размер): 

1 0 1 0 1 0 1

1 0 0 0 1 1 1

1 1 1 0 1 1 1

1 1 0 0 1 1 1

1 0 0 0 0 1 1

1 0 1 1 1 1 1

1 0 1 1 1 1 1

Выход: Одномерный массив чисел 0,1, размера 11. Если на i-ом месте стоит 0 - значит, через этот ход мышь выбраться не может, и мышеловку там ставить не имеет смысла, если 1 - то мышеловку необходимо поставить.

Пример: 

1 1 0 1 1 1 0 1 1 1 0

Входной файл - INPUT.TXT, выходной файл - OUTPUT.TXT.

Комментарии к задаче

Отметим сначала, что около норы с номером 0 мышеловку поставить необходимо. С остальными поступим следующим образом. Поместим в нору с номером 0 управляемую мышь и будем ее двигать все время вдоль левой стены. Если однажды она придет в какую-нибудь норку, то в этой норе надо поставить мышеловку. Тогда мы заделаем эту нору (поставим в карту лабиринта число 1) и будем двигать мышь дальше. Когда она вернется в норку 0, тогда все закончится. Мышеловки надо поставить в тех норках, в которых она побывала. Зациклиться этот алгоритм, очевидно, не может.

Пример программы для решения задачи:

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

const R=100;

int L[R][R];

int H[11];

int i,j;

int x,y,n;

/*

n -

0 up

1 right

2 down

3 left

*/

void moveXY();

void main() {

  FILE *f;

  char name[10]="INPUT.TXT";

  f=fopen(name,"r");

  int gh=0;

  for(i=0; i<R; i++)

    for(j=0; j<R; j++) {

      fscanf(f,"%d",&gh);

      L[j][i]=gh;

    }

  fclose(f);

  for(i=0; i<R; i++) {

    L[i][0]=1; L[i][R-1]=1; L[0][i]=1; L[R-1][i]=1;

  }

  for(i=1; i<11; i++)

    H[i]=0;

  H[0]=1;

  x=1; y=R-1; n=0;

  L[x][y]=0;

  moveXY();

  while( !((x==1)&&(y==(R-1))) ) {

    moveXY();

    if(y==1)

      if(x<20)

        if(x%2==1)

          H[int((x-1)/2)+1]=1;

  }

  char outname[11]="OUTPUT.TXT";

  f=fopen(outname,"w");

  for(i=0; i<11; i++)

   fprintf(f,"%d ",H[i]);

  fclose(f);

}

void moveXY() {

  switch(n) {

    case 0: { //up

      if( L[x-1][y]==0 ){

        x--; n=3;

      } else if( L[x][y-1]==0 ) {

        y--; n=0;

      } else if( L[x+1][y]==0 ) {

        x++; n=1;

      } else if( L[x][y+1]==0 ) {

        y++; n=2;

      }

      break;

    }

    case 1: { //right

      if( L[x][y-1]==0 ) {

        y--; n=0;

      } else if( L[x+1][y]==0 ) {

        x++; n=1;

      } else if( L[x][y+1]==0 ) {

        y++; n=2;

      } else if( L[x-1][y]==0 ) {

        x--; n=3;

      }

      break;

    }

    case 2: { //down

      if( L[x+1][y]==0 ) {

        x++; n=1;

      } else if( L[x][y+1]==0 ) {

        y++; n=2;

      } else if( L[x-1][y]==0 ) {

        x--; n=3;

      } else if( L[x][y-1]==0 ) {

        y--; n=0;

      }

      break;

    }

    case 3: { //left

      if( L[x][y+1]==0 ) {

        y++; n=2;

      } else if( L[x-1][y]==0 ) {

        x--; n=3;

      } else if( L[x][y-1]==0 ) {

        y--; n=0;

      } else if( L[x+1][y]==0 ) {

        x++; n=1;

      }

      break;

    }

  }

}

Команда Zugi, в состав которой вошли учащиеся 11а класса: Тарасов Егор,  Малиновский Александр, Неплохов Иван,  дважды принимала участие в кибернетических олимпиадах в Санкт-Петербурге, проводимых преподавателями, аспирантами, студентами ИТМО и СПбГУ, на базе ДТЮ. На седьмой кибернетической олимпиаде команда заняла 39 место, а на восьмой -10-е.