Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадная информатика в Ханты-Мансийском АО-Югре

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Все о тренингах для бизнеса" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Октябрь 2008   →
 1
 2
 3
 4
 5
 6
 7
 8
08.10.2008
12:48:06
14:39:27
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Alexeyev

Статистика

3.211 подписчиков
-1 за неделю
←   Все выпуски   →

Задача в неделю. Олимпиадные задачи по информатике. Разбор задания 2-го занятия


Центр информационных технологий ИРО

Югорский государственный университет

Югорский НИИ информационных технологий

Телекоммуникационный проект "Задача в неделю"

Разбор задания занятия № 2 (29 сентября 2008 года)

 

Задание на сайте в указанное время сдали 18 человек. Их результаты приведены в таблице:

 

Дата

Автор

Язык

Время

Память

29.09.2008 17:52:38

Календо Дима

Pascal

0,007

708 Кб

29.09.2008 18:46:19

Чудов Алексей Евгеньевич

C++

0,025

600 Кб

29.09.2008 20:28:55

Козачук Андрей

C++

0,049

748 Кб

02.10.2008 0:18:55

Andrei Avanessov

C++

0,024

732 Кб

02.10.2008 10:04:49

Захаров Андрей Сергеевич

Pascal

0,007

848 Кб

02.10.2008 19:55:05

Кипелов Владимир Александрович

Pascal

0,01

836 Кб

03.10.2008 19:00:50

Шишкин Андрей Алексеевич

Pascal

0,007

836 Кб

04.10.2008 1:38:09

Муравьев Руслан Владимирович

Pascal

0,006

848 Кб

04.10.2008 11:46:13

Корольчук

Pascal

0,007

820 Кб

04.10.2008 12:13:44

Васюк Илья Викторович

Pascal

0,007

812 Кб

05.10.2008 2:01:51

Соболев Дима

Pascal

0,036

1380 Кб

05.10.2008 9:02:53

Дядьков Ярослав Сергеевич

Pascal

0,008

816 Кб

05.10.2008 14:57:33

Ермилов Ярослав

Pascal

0,008

820 Кб

05.10.2008 15:36:08

Соболев Евгений

Pascal

0,03

1356 Кб

05.10.2008 17:21:02

Адуенко Александр Александрович

Pascal

0,008

840 Кб

05.10.2008 18:47:24

Корчуганова М.Р.

Pascal

0,007

836 Кб

05.10.2008 20:26:32

Лёвочкин Алексей Валентинович

Pascal

0,007

852 Кб

05.10.2008 21:20:51

Никифоров Николай Сергеевич

Pascal

0,007

848 Кб

 

Девять участников проекта прислали свои программы, в 6 присланных работах имелось описание алгоритма. Далее привожу описание Ярослава Ермилова.

Разложим данное число N на множители N=9a8b7c6d5e4f3g2hw. Если w>1 то ответом будет -1. Иначе, так как нам необходимо найти наименьшее число, удовлетворяющее условию задачи, то добьемся максимальности a в первую очередь, максимальности b во вторую, :. Таким образом, если мы запишем число Q=2:23:3:9:9, где каждая цифра повторяется h, g, :, a раз, то произведение его цифр будет равно N; оно будет самым коротким среди всех чисел использующих другое разложение N на множители  и наименьшим среди чисел такой же длины, но другой перестановки цифр, а значит будет является ответом к задаче. Также необходимо рассмотреть отдельно случай N=0, в этом случае Q=10.

Нижеприведенная программа реализации описанного алгоритма принадлежит мне.

Программа

var

  n : longint;

  a : array [2..9] of integer;

  i, j : integer;

begin

  assign(input, 'input.txt'); reset(input);

  assign(output, 'output.txt'); rewrite(output);

  read(n);

  if n=0 then write(10) else

  begin

    for i:=2 to 9 do a[i]:=0;

    for i:=9 downto 2 do

      while n mod i=0 do begin a[i]:=a[i]+1; n:=n div i end;

    if n>1 then write(-1) else

      for i:=2 to 9 do

        for j:=1 to a[i] do write(i)

  end

end..

 

 

Ведущий проекта, к.п.н., доцент

Алексеев Александр Владимирович,

e-mail - aav@uriit.ru, internet - http://zvn.irohmao.ru.

 
В избранное