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

Олимпиадные задачи с решениями на Turbo Pascal

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 3.826 RSS
←   Июль 2003   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Открыта: 02-12-2001

Автор
Aslof

Статистика

3.826 подписчиков
0 за неделю
←   Все выпуски   →

Олимпиадные задачи с решениями на Turbo Pascal


Информационный Канал Subscribe.Ru
Здравствуйте, уважаемые подписчики. Извините, был очень занят, поэтому выпуск задержался.

Первое. Если что-то написано курсивом - это не мой текст! Условие и примечание к прошлой задаче прислал один из читателей. По каким-то непонятным причинам я не указал его. Письмо, к сожалению, потерялось. Поэтому он пока остается неизвестным. Напиши!

Далее. Задача, по зрелым размышлениям (и, конечно, участии подписчиков), оказалась очень простой, нужно только дружить с математикой. Спасибо Vladimir Shalamberidze за толковое обьяснение алгоритма (многие обьясняли, но я, такой тормоз, понял только на третье. Именно оно оказалось от Vladimir'a). Вот обьяснение (оно было в транслите, но я перевёл)

Умножать не надо.
Грубо говоря если есть делитель P1, то будет и делитель N/P1 Иx произведение всегда равно N. Т.е произведение делителей в случае когда N<>m^2 равно N^K где K=кол-во делителей. В случае N=m^2 произведение делителей равно N^(K-1/2) (m участвует 1 раз) Кол-во цифр можно посчитать по десятичному логарифму.
1 случай 2*K*Lg(N)
2 случай 2*(K-0.5)*Lg(N)
 Вот до логарифма додумались немногие.

Ещё. Присылайте, пожалуйста, решения для Паскаля. Ну или для Си. Если решаете в Delphi, пишите консольное приложение. И главное - проверяйте и проверяйте. Я-то для рассылки только рабочий код пишу. (Опечатка, из-за которой 999999 не выводилось - не считается :-)). Он должен не только запускаться, но и результаты правильно выводить. Да, понимаю, Вы не могли проверить свой код последней задачи для числа 215040 (502 цифры) или 1000000 (283). Но если для положительного диапазона решение выводит отрицательные номера билетов :-), это-то можно заметить.

Да, присылали ещё решения "в лоб". Не эффективно, но прикольно. Одно такое решение (лучшее, ИМХО) я опубликовываю. Да, возможно я выложу в сети все рабочие решения, тогда дам линки в следующем выпуске.

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

И последнее. Предложили приводить решения типовых проблем. Пожалуй начнём писать модуль (ну, а кто не знает как, а такие есть, заодно научатся). Со следующего выпуска, постепенно накопится. Что скажете?

Да, и самое последнее. Вывода в файл не будет. Если кому он нужен - допишете сами, хорошо?

Решение прислал Ivan Petrov. Кстати, ему спасибо за первое указание на проверку того, не является ли N квадратом какого числа. Ведь в этом случае можно это число посчитать два раза (чем грешили многие решения на логарифмах). Мне пришлось маленько ужать в ширину решение, т.к. оно не проходило по ширине (я же решения оформляю тегом <prе>, но тогда перенос строк не делается автоматически) 

var kol,t,j,i,n,k,a: longint;
b: array [1..250] of longint;
d,s: array [1..5000] of integer;
begin

for i:=0 to 250 do b[i]:=0;

readln (a);
if a<=1 then begin
  writeln ('nepravilnii format chisla A'); exit; end;

n:=2;
k:=0;
while n<=sqrt(a) do begin
if a mod n =0 then begin k:=k+1; b[k]:=n;end;
n:=n+1;
end;
{ishem deliteli menshie kornia iz dannogo chisla}

k:=k+1; b[k]:=1;
for n:=1 to k-1 do begin b[k+n]:=a div b[n]; end;
 {ishem ostalnie deliteli}

k:=k+k-1;
if b[k]*b[k]=a then k:=k-1;
 {proveriaem ne zapisan li kakoi-to delitel dva raza,
                                chto vozmozno, esli b*b=a}

for i:=1 to k do b[k+i]:=b[i];
k:=k+k;
         {berem kazdii delitel 2 raza}

write ('(');
for i:=1 to (k div 2-1) do write (b[i],'*');
writeln(b[k div 2],')^2=');
{vivodim deliteli}


n:=0;
while b[k]>0 do begin
n:=n+1;
d[n]:=b[k] mod 10;
b[k]:=b[k] div 10;
end;
{berem poslednii delitel i razkladivaem
ego v massiv na desiatki, sotni...}


k:=k-1;
for i:=1 to 5000 do s[i]:=0;

t:=0;
{peremnozaem razlozennii poslednii
delitel na ostalnie deliteli chisla a  }
while k>0 do begin
 {(poetapno raskladivaia ostalnie
deliteli na edinici, desiatki...}
while b[k]>0 do begin
i:=b[k] mod 10;
b[k]:=b[k] div 10;
        for j:=1 to n do begin
        if j+t=n+1 then n:=n+1;
        s[j+t]:=s[j+t]+d[j]*i;
        if s[j+t]>=10 then begin
           s[j+1+t]:=s[j+1+t]+(s[j+t] div 10);
           s[j+t]:=s[j+t] mod 10;
        if j+t=n then n:=n+1; end;
        end;
t:=t+1;
if i<>0 then while s[n]=0 do n:=n-1;
{writeln;
for i:=n downto 1 do write (s[i]); }
end;
for i:=1 to n do begin d[i]:=s[i]; s[i]:=0;end;
t:=0;
k:=k-1;
end;

for i:=n downto 1 do write (d[i]);
writeln;writeln;
writeln ('vsego znakov ',n); readln;
end.

Ну и мой вариант. Спасибо, Адель Файзрахманов. На основе твоего письма оно написано. (Он не прислал полный код, только наработку, хотя для такого кода, звучит смешно). Алгоритм: проверяем все числа от 2 до корня из N, являются ли они делителями (мы найдём ровно половину всех делителей, у нас рассылка не по математике, поэтому доказательство приводить не буду). После цикла в k - число пар делителей. Удваиваем. Далее проверка, не является ли N - квадратом какого-то числа, в этом случае мы можем учесть это число 2 раза, поэтому вычитаем единицу. Умножаем на длину N (обьяснение было выше). Ну и прибавляем единицу, чтобы учесть первый разряд. 

var q,n,k: longint;
begin
  writeln('Введите N');
  readln(n);
  k:=0;
  for q:=2 to Trunc(sqrt(n)) do
    if n mod q = 0 then k:=k+1;
  k:=k*2;
  if frac(sqrt(n))=0 then k:=k-1;
  k:=(ln(n)/ln(10))*k;
  writeln(trunc(s)+1);
  readln;
end.

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

Дано выражение типа
a?b?c?f?9=zz
где ? принажлежит множетсву (+,*,-,div)
a,b,c,....,z = числа
zz = контрольный результат

Необходимо написать программу которая выдает все возможные выражения при вычислении которых получим число zz

пример
2?2=4

вывод

2+2=4
2*2=4

Сам sergtemp прислал решение на 4 кб, но что-то меня сомнение берёт... Ну ладно, присылайте свои решения и я сам решу и посмотрим, во сколько уложится лидер.

"Форсаж" - рассылка "Ищешь фильм?"
http://subscribe.ru/catalog/rest.cinema.filmforyou
Aslof aslof@mail.ru
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное