Олимпиада по программированию

2002-2003 учебный год, районно-городской тур

1. Превращение (10 баллов, 5 сек на тест)

Возьмем какое-нибудь натуральное число N. Будем изменять его следующим образом: если число четное, то разделим его на 2, если нечетное, прибавим 1. После нескольких таких изменений мы всегда получаем число 1. Например, из числа 11 получается число 12, затем 6, 3, 4, 2 и, наконец, 1. Таким образом, для получения 1 из 11 нужно проделать 6 изменений.

Напишите программу, которая вводит с клавиатуры натуральное число N (1<=N<=109) и выводит на экран количество изменений данного числа до получения 1.

Пример ввода:

11

Пример вывода:

6

Решение:

Самая простая задача. Необходимо правильно указать тип переменной N (longint) и точно выполнять указанные в задаче шаги, пока значение N не станет равным 1, а затем количество выполненных шагов.

Программа:

var n:longint;

    k:integer;

begin

  readln(n);

  k:=0;

  while n<>1 do

  begin

    if n mod 2=1 then

      n:=n+1

    else

      n:=n div 2;

    inc(k);

  end;

  writeln(k);

end.

Тесты жюри:

Ввод

Правильный ответ

Оценка за правильный ответ

1

0

3

512

9

2

738395

31

2

987987987

48

3

 

2. Разложение на простые слагаемые (40 баллов, 15 сек на тест)

Любое целое число большее 1 можно единственным способом представить в виде произведения  простых множителей (если перечислять множители  в неубывающем порядке). Но если попытаться представлять целые числа в виде суммы простых слагаемых (также в неубывающем порядке), то таких разложений окажется несколько. Например, для числа 11 есть 6 таких разложений: 11=11, 11=2+2+7, 11=3+3+5, 11=2+2+2+5, 11=2+3+3+3, 11=2+2+2+2+3.

Напишите программу, которая вводит с клавиатуры натуральное число N (1<N<=5000) и выводит на экран количество разложений данного числа на простые слагаемые.

Пример ввода:

11

Пример вывода:

6

Решение:

Самая сложная задача. 15 баллов можно было получить с помощью рекурсивного перебора. Полное решение требует одновременно применения “длинной” арифметики (только сложение), динамического программирования и алгоритма для проверки числа на простоту. Самый сложный элемент – динамическое программирование. Количество разложений данного числа N на простые слагаемые является суммой по всем простым числам P<=N количеств разложений числа (N–P) на простые слагаемые меньшие или равные P. Для N=0 существует 1 (пустое) разложение. При правильной организации вычислений необходим только один массив, в котором постепенно будет накапливаться количество разложений числа I на простые слагаемые меньшие и равные P.

Программа:

{Длинная арифметика, храним по 4 цифры в элементе массива}

const maxlen=12;

type number=array [0..maxlen] of integer;

     pnumber=^number;

procedure add(var n1,n2,nr:number);

var i,p:integer;

begin

  p:=0;

  for i:=0 to maxlen do

  begin

    p:=p+n1[i]+n2[i];

    nr[i]:=p mod 10000;

    p:=p div 10000;

  end;

end;

procedure setval(var n:number; v:integer);

var i:integer;

begin

  for i:=1 to maxlen do n[i]:=0;

  n[0]:=v;

end;

procedure print(var n:number);

var i,k:integer;

begin

  k:=maxlen;

  while (k>0) and (n[k]=0) do dec(k);

  write(n[k]);

  for i:=k-1 downto 0 do

    if n[i]<10 then write('000',n[i])

    else if n[i]<100 then write('00',n[i])

    else if n[i]<1000 then write('0',n[i])

    else write(n[i]);

  writeln;

end;

 

function isprime(n:longint):boolean;

var i:longint;

begin

  i:=2;

  while i*i<=n do

  begin

    if n mod i=0 then

    begin

      isprime:=false;

      exit;

    end;

    inc(i);

  end;

  isprime:=true;

end;

 

{Динамическое программирование}

var q:array [2..5000] of pnumber;

    one:number;

procedure init;

var i:integer;

begin

  for i:=2 to 5000 do

  begin

    new(q[i]);

    setval(q[i]^,0);

  end;

  setval(one,1);

end;

procedure fill;

var i,j:integer;

begin

  for i:=2 to 5000 do

    if isprime(i) then

    begin

      add(q[i]^,one,q[i]^);

      for j:=i+2 to 5000 do

        add(q[j]^,q[j-i]^,q[j]^);

    end;

end;

 

var i:integer;

begin

  init;

  fill;

  readln(i);

  print(q[i]^);

end.

Тесты жюри:

Ввод

Правильный ответ

Оценка за правильный ответ

4

1

5

21

30

5

98

35772

5

331

1947093861

5

885

4671632903000008

5

1023

75667898172375905

5

5000

9829862487468285534511318435114100374

10

 

3. Анаграммы (20 баллов, 5 сек на тест)

Напишите программу, которая вводит с клавиатуры слово длиной не более 14 букв и выводит на экран количество различных анаграмм, которые могут получиться из этого слова. Анаграммой слова называется любая перестановка всех букв слова. Например, из слова СОЛО можно получить 12 анаграмм: СОЛО, ЛОСО, ОСЛО, ОЛСО, ОСОЛ, ОЛОС, СЛОО, ЛСОО, ООЛС, ООСЛ, ЛООС, СООЛ.

Пример ввода:

СОЛО

Пример вывода:

12

Решение:

Решение требует применения математических знаний. Необходимо либо вспомнить, либо вывести формулу из комбинаторики для перестановок с повторениями – N!/(K1!*K2!*…*KM!). Если у нас N различных предметов, то существует N! их различных перестановок. Если Q некоторых предметов неразличимы, то число перестановок уменьшается в Q! раз.

Для 14 букв максимальное число различных перестановок равно 14!=87 178 291 200. Это число больше 2*109 (231), следовательно, для результата необходима переменная типа extended.

Программа:

var q:array [char] of integer;

    i:integer;

    s:string;

    k:extended;

begin

  readln(s);

  k:=1.0;

  fillchar(q,sizeof(q),0);

  for i:=1 to length(s) do

  begin

    inc(q[s[i]]);

    k:=(k * i) / q[s[i]];

  end;

  writeln(k:0:0);

end.

Тесты жюри:

Ввод

Правильный ответ

Оценка за правильный ответ

А

1

2

УУУУУ

1

3

БАОБАБ

60

5

МОНОГРАММА

151200

5

РАЗГИЛЬДЯЙСТВО

87178291200

5

 

4. Калькулятор (20 баллов, 5 сек на тест)

Напишите программу, которая моделирует дисплей калькулятора, то есть вводит с клавиатуры целое число N (|N|<1010) и выводит на экран изображение этого числа на дисплее. Знак числа высвечивается непосредственно перед первой цифрой числа.

 

_

 

|

_

|

|

_

|

Изображение каждой цифры или знака числа получается с помощью включения или выключения семи элементов жидкокристаллического дисплея. Состояние дисплея программа должна печатать с помощью символов ‘|’ (вертикальная черта), ‘_’ (подчеркивание) и ‘ ’ (пробел). Цифры и знак минус на дисплее должны быть изображены следующим образом:

    _     _  _     _  _  _  _  _

 _ | |  | _| _||_||_ |_   ||_||_|

   |_|  ||_  _|  | _||_|  ||_| _|

Пример ввода:

-123

Пример вывода:

       _  _

 _   | _| _|

     ||_  _|

Решение:

Простая “техническая” задача. Возможно решение с использованием case и одновременным формированием 3 строк. Использование подпрограммы существенно упрощает программу, так как для всех трех выводимых строк должны быть выполнены одни и те же действия.

Программа:

var s:string;

procedure display(const s,v:string);

var i,k:integer;

begin

  for i:=1 to length(s) do

  begin

    if s[i]='-' then k:=1

    else k:=(ord(s[i])-ord('0'))*3+4;

    if (k>0) and (k<length(v)) then

      write(copy(v,k,3));

  end;

  writeln;

end;

begin

  readln(s);

  display(s,'    _     _  _     _  _  _  _  _ ');

  display(s,' _ | |  | _| _||_||_ |_   ||_||_|');

  display(s,'   |_|  ||_  _|  | _||_|  ||_| _|');

end.

Тесты жюри:

Ввод

Правильный ответ

Оценка за правильный ответ

0

 _

| |

|_|

 

5

-90667

    _  _  _  _  _

 _ |_|| ||_ |_   |

    _||_||_||_|  |

 

5

9876543210

 _  _  _  _  _     _  _     _

|_||_|  ||_ |_ |_| _| _|  || |

 _||_|  ||_| _|  | _||_   ||_|

 

10