РЕСПУБЛИКАНСКАЯ ОЛИМПИАДА
ПО ИНФОРМАТИКЕ (1997-й год)

Республиканская олимпиада по информатике в 1997 году проходила в течение двух дней: 9 января - теоретический тур в лицее-интернате №1 и 10 января - практический тур в компьютерных классах Бурятского института повышения квалификации и переподготовки работников образования. Продолжительность каждого тура - 4 часа.

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

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

ТОРТ

(16 баллов)

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

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

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

Поскольку свечи моделируются множеством точек плоскости M₁, M₂, ..., M_n, которые должны находиться в пределах многоугольника со сторонами a и b (размеры торта), то дальнейший процесс решения заключается в том, чтобы ответить на вопрос: найдётся ли среди точек M₁, M₂, ..., M_n такая точка M_i, чтобы все остальные точки находились по одну сторону от прямой, проходящей через точки O и M_i. Если такой точки найти не удастся, то разрез торта, удовлетворяющий условиям задачи, выполнить невозможно. В случае же, когда подходящая точка обнаружена, задача имеет решение: надо немного повернуть вокруг начала координат прямую OM_i таким образом, чтобы точка M_i оказалась в той же полуплоскости, что и остальные точки. Новое положение прямой как раз указывает, каким образом надо сделать разрез торта (смотрите рисунок на предыдущей странице). Описывать строго процедуру поворота прямой (угол поворота, направление поворота) нет необходимости (в задаче не требуется точно описать, как будет проходить разрез): достаточно понять, что такая процедура возможна, в результате чего и получается решение задачи.

Таким образом, задача сводится к проведению прямой через две точки (одна точка фиксированная - это начало координат, вторая точка пробегает множество {M₁, M₂, ..., M_n}) и определению количества точек, находящихся по одну сторону от данной прямой.

Метод, позволяющий решить эту проблему описан (см. решение задачи 2 районной олимпиады): для каждой точки M_i составляется выражение

F(x,y)=x*y_i-y*x_i,

являющееся уравнением прямой OM_i, а затем в зависимости от того, какой знак имеют значения F(x_j,y_j), где j=1,2,...,n, определяется, сколько точек расположено по одну или другую сторону от прямой. Отдельно надо рассмотреть ситуацию, когда для какой-либо точки F(x_j,y_j)= =0, причём i№ j, т.е. точка M_j принадлежит прямой OM_i. В этом случае, если точки M_i и M_j расположены на прямой по разные стороны от начала координат, прямая OM_i, вне зависимости от расположения остальных точек внутри прямоугольника, не может дать решения задачи: при любом повороте прямой OM_i точки M_i и M_j окажутся по разные стороны от прямой (смотрите рисунок).

Реализация на языке BASIC

10 INPUT "Число свечей"; N
20 INPUT "Размеры прямоугольного торта"; A,B
30 DIM X(N),Y(N)
40 PRINT "Введите координаты свечей"
50 FOR I=1 TO N
60 PRINT I;"-я свеча";
70 INPUT X(I),Y(I)
75 IF X(I)=0 AND Y(I)=0 THEN GOTO 170
80 IF ABS(X(I))>A/2 OR ABS(Y(I))>B/2 THEN PRINT "Свеча оказалась вне торта": GOTO 60
90 NEXT I
100 FOR I=1 TO N
105 M1=0: M2=0
110 FOR J=1 TO N
120 D=X(J)*Y(I)-Y(J)*X(I) ў определяем отклонение


j-ой точки от i-ой прямой
130 IF D<0 THEN M1=M1+1 ELSE IF D>0 THEN M2=M2+1
140 IF D=0 THEN IF X(I)*X(J)<0 OR Y(I)*Y(J)<0 THEN 160
145 NEXT J
150 IF M1=0 OR M2=0 THEN PRINT "Решение есть": GOTO 180
160 NEXT I
170 PRINT "Решения нет"
180 END

Реализация на языке PASCAL

const
  MaxN=100;
Var
  N, i, j, M1, M2: Integer;
  A, B, D: Real;
  Candle: array[1..MaxN]of record
                             X, Y: Real;
                           end;
  Solving: Boolean;
begin
  repeat
    Write('Введите число свечей:'); ReadLn(N);
    if (N<=0)or(N>MaxN) then
      WriteLn('Неверное число. Повторите.');
  until (N>0)and(N<=MaxN);
  Write('Введите размеры прямоугольного торта');
  ReadLn(A, B);
  for i := 1 to N do
    repeat
      WriteLn('Введите координаты свечи ', i);
      ReadLn(Candle[i].X, Candle[i].Y);
      if not(Abs(Candle[i].X)<=A)and
        (Abs(Candle[i].Y)<=B) then
        WriteLn('Свеча оказалась вне торта.');
    until (Abs(Candle[i].X)<=A)and(Abs(Candle[i].Y)<=B);
  Solving := False;
  for i := 1 to N do
    begin
      M1 := 0; M2 := 0;
      for  j := 1 to N do
        begin
          D := Candle[j].X*Candle[i].Y-
            Candle[i].X*Candle[j].Y;
          if D<0 then Inc(M1) else
            if D>0 then Inc(M2) else
              if (Candle[i].X*Candle[j].X<0)or
                (Candle[i].Y*Candle[j].Y<0) then
                begin
                  M1 := 1; M2 := 1;
                  Break;
                end;
        end;
      if (M1=0)or(M2=0) then
        begin
          Solving := true;
          Break;
        end;
    end;
  Write('Решение '); if not Solving then Write('не ');
  WriteLn('существует.');
end.

ДЕШИФРОВКА

(16 баллов)

Решение. Количество чисел, превышающих заданное число и стоящих правее в исходной перестановке, очевидно, не может быть больше количества чисел, вообще стоящих справа. Поэтому необходимым условием того, что данная последовательность является шифром некоторой перестановки, является то, что i-е число последовательности не может превышать количества элементов последовательности, следующих за ним. Чтобы показать, что это же условие является и достаточным, предположим, что дана последовательность, удовлетворяющая сформулированному выше условию, и опишем алгоритм дешифровки.

Рассмотрим позицию в исходной перестановке, на которой находится число n. Это самое большое число, поэтому в данной позиции шифра стоит ноль, а левее данной позиции в шифре ноль стоять не может. Следовательно, самый левый ноль в последовательности соответствует числу n в исходной перестановке. (Заметим, что в шифре число ноль обязательно должно быть хотя бы на последнем месте, потому что правее этой позиции в перестановке нет ни одного числа). Таким образом, определено положение, которое занимает число n. Расшифровав n, мы исключаем это число из дальнейшего рассмотрения (для этого надо уменьшить на единицу все числа последовательности, стоящие левее позиции числа n; при этом снова получится последовательность, удовлетворяющая сформулированному условию) и продолжаем расшифровку перестановки чисел от 1 до n-1, используя рассуждения, аналогичные приведённым выше.

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

Реализация на языке BASIC

10 INPUT "Количество чисел в последовательности"; N
20 IF N<1 OR N<>INT(N) THEN PRINT "Некорректные данные": GOTO 10
30 DIM A(N),B(N)
40 PRINT "Введите элементы последовательности"
50 FOR I=1 TO N
60 PRINT I;"-е число";
70 INPUT A(I)
80 IF A(I)>N-I OR A(I)<0 OR A(I)<>INT(A(I)) THEN PRINT "Данная последовательность не может быть шифром никакой перестановки": GOTO 250
90 NEXT I
100 K=N
110 IF K=0 THEN 210
120 FOR I=1 TO N
130 IF A(I)=0 THEN 150
140 NEXT I
150 B(I)=K
160 FOR J=1 TO I
170 A(J)=A(J)-1
180 NEXT J
190 K=K-1
200 GOTO 110
210 PRINT "Расшифрованная перестановка"
220 FOR I=1 TO N
230 PRINT B(I);
240 NEXT I
250 END

Реализация на языке PASCAL

const
  MaxN=100;
Var
  N, i, j, k: Integer;
  A, B: array[1..MaxN]of Integer;
begin
  repeat
    Write('Введите количество чисел в последовательности:');
    ReadLn(N);
    if (N<=1)or(N>MaxN) then
      Write('Неверное количество. Повторите.');
  until (N>1)and(N<=MaxN);
  for i := 1 to N do
    begin
      Write('Введите ', i, '-е число:'); ReadLn(A[i]);
      if (A[i]>N-i)or(A[i]<0) then
        begin
          WriteLn('Данная последовательность не может'+
            ' быть шифром никакой перестановки.');
          Exit;
        end;
    end;
  k := N;
  while k<>0 do
    begin
      i := 1;
      while A[i]<>0 do Inc(i);
      B[i] := k;
      for j := 1 to i do
        Dec(A[j]);
      Dec(k);
    end;
  WriteLn('Расшифрованная перестановка:');
  for i := 1 to N do
    Write(B[i], ' ');
  WriteLn;
end.

СУММА

(24 балла)

Решение. Так как количество действий в алгоритме ограничено, то нельзя использовать методы, основанные на переборе вариантов (например, рассмотреть все непустые подмножества множества {x₁, x₂, ... , x_n}, для каждого подмножества найти сумму элементов и сравнить её с числом K, или перебрать всевозможные представления натурального числа K (если число K не является натуральным, данная задача, очевидно, не имеет решения) в виде суммы одного или нескольких натуральных слагаемых без учёта их порядка и для каждого разбиения проверить, не состоит ли оно только из элементов множества {x₁, x₂, ... , x_n}).

Воспользуемся приёмами динамического программирования. Организуем циклическую процедуру, позволяющую на i-ом шаге получить множество тех целых чисел диапазона [1...K], которые представимы в виде суммы некоторых из чисел x₁, x₂, ... , x_i. Опишем эту процедуру рекуррентно.

Разумеется, на первом шаге это множество состоит либо из одного числа x₁, либо пусто, если x₁>K. Допустим, уже известно множество, полученное на i-ом шаге. На следующем этапе к каждому из чисел этого множества прибавляем x_i+1. Если при этом получаются новые числа диапазона [1...K], мы добавляем их к имеющемуся набору. Кроме того, надо добавить само число x_i+1, если x_i+1Ј K. Следовательно, каждое следующее множество включает в себя всё полученное на предыдущих этапах.

Если в конструируемое таким образом множество на каком-то шаге попадёт число K, задача имеет решение. В противном случае решения нет.

Для реализации описанных действий организуем вспомогательный линейный массив для хранения информации о том, какие целые числа диапазона [1...K] могут быть получены указанным в задаче способом. Если для какого-то числа m это справедливо, m-ый элемент этого вспомогательного массива должен иметь ненулевое значение. Имея в виду, что при положительном ответе на вопрос о возможности представления числа K в виде суммы некоторых из чисел x₁, x₂, ... , x_n, надо сообщить какой-либо вариант такого представления, можно в качестве значения m-го элемента массива запоминать номер i того из чисел x₁, x₂, ... , x_n, которое было последним слагаемым при получении числа m в результате описанной выше процедуры (или номер i этапа, когда число m впервые было получено). Определив разность m-x_i, можно узнать, при сложении с каким числом числа x_i было получено число m. Зная значение элемента массива с номером m-x_i и повторяя применительно к числу m-x_i рассуждения, проведенные для числа m, мы можем восстановить всю цепочку тех из чисел x₁, x₂, ... , x_n, суммой которых оказалось число m.

Организуя на i-ом шаге просмотр вспомогательного массива в поисках ненулевых элементов и определения новых чисел диапазона [1...K], которые могут быть получены, если имеющиеся числа сложить с числом x_i, надо позаботиться, чтобы в эту процедуру не оказались вовлечёнными числа, только что полученные на i-ом шаге. Это можно обеспечить, например, исключая из рассмотрения не только нулевые элементы вспомогательного массива, но и те, значения которых равны i (см. реализацию на языке BASIC), или просматривая массив по убыванию номеров (см. реализацию на языке PASCAL).

Реализация на языке BASIC

10 INPUT "Введите число K"; K
20 IF K<=0 OR K<>INT(K) THEN PRINT "Задача решения не имеет": GOTO 260
30 INPUT "Количество чисел в последовательности"; N
40 IF N<>INT(N) OR N<1 THEN PRINT "Некорректный ввод": GOTO 30
50 DIM X(N),A(K)
60 PRINT "Введите элементы последовательности"
70 FOR I=1 TO N
80 PRINT I;"-;
90 INPUT X(I)
100 IF X(I)<>INT(X(I)) OR X(I)<0 THEN PRINT "Некорректный ввод": GOTO 80
110 NEXT I
120 А(0)=-1
130 FOR I=1 TO N
140 FOR J=0 TO K
150 IF A(J)=0 OR A(J)=I THEN 170
160 IF J+X(I)>K THEN 170 ELSE IF A(J+X(I))=0 THEN A(J+X(I))=I
170 IF A(K)<>0 THEN 210
180 NEXT J
190 NEXT I
200 PRINT "Задача не имеет решения": GOTO 260
210 M=K: PRINT K;"= ";
220 IF M=0 THEN GOTO 260
230 PRINT "X(";A(M);")";
240 M=M-X(A(M))
245 IF M<>0 THEN PRINT "+";
250 GOTO 220
260 PRINT: END

Реализация на языке PASCAL

const
  MaxN=100;
  MaxK=32000;
Var
  X: array[1..MaxN] of Word;
  From: array[1..MaxK] of Integer;
  N, K: Integer;
procedure InputData;
Var
  i: Integer;
begin
  repeat
    Write ('Введите N: '); ReadLn (N);
    if (N<1) or (N>MaxN) then
      WriteLn ('Недопустимое значение N.');
  Until (N>0) and (N<=MaxN);
  for i := 1 to N do
    begin
      Write ('Введите X[', i, ']: '); ReadLn (X[i]);
    end;
  repeat
    Write ('Введите K: '); ReadLn (K);
    if (K<1) or (K>MaxK) then
      WriteLn ('Недопустимое значение K.');
  Until (K>0) and (K<=MaxK);
end;
procedure Solve;
Var
  i, j: Integer;
begin
  for i := 1 to K do
    From[i] := 0;
  for i := N downto 1 do
    begin
      for j := K downto 1 do
        if (From[j]<>0) and (X[i]+j<=K) and
          (From[X[i]+j]=0) then From[X[i]+j] := i;
      if X[i]<=K then
        if From[X[i]]=0 then From[X[i]] := i;
    end;
end;
procedure OutputResult;
Var
  j: Integer;
begin
  if From[K]=0 then
    WriteLn ('Невозможно получить требуемое число.')
   else
    begin
      WriteLn (K,' = ');
      j := K;
      while j<>0 do
        begin
          if j<>K then Write ('+');
          Write ('X[', From[j], ']');
          j := j-X[From[j]];
        end;
    end;
end;
begin
  InputData;
  Solve;
  OutputResult;
end.

СИСТЕМЫ СЧИСЛЕНИЯ

(8 баллов)

Решение. Технические ограничения связаны со следующими соображениями:

• если основание системы счисления больше 36, для записи чисел в такой системе будет недостаточно цифр десятичной системы и букв латинского алфавита;
• исходное число в заданной системе счисления вводится в программу в качестве значения строковой переменной, а длина строки ограничена (числовая переменная в данном случае не подходит, поскольку в записи числа могут присутствовать символы латинского алфавита).

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

В программах, реализующих данный алгоритм решения, предусмотрено хранение в специальной строковой величине упорядоченного множества, состоящего из десятичных цифр и строчных символов латинского алфавита. Элементы этого множества используются в качестве цифр при записи чисел в любой системе счисления, основание которой не больше числа 36. После того, как основание системы счисления введено, из этого множества выделяется подмножество цифр указанной системы счисления. Заметим, что максимальная цифра данной системы счисления является последним элементом сформированного таким образом множества цифр.

Отметим, что в программах реализована проверка введённого исходного числа на наличие недопустимых символов. При этом, если в записи числа используются заглавные символы латинского алфавита, они заменяются соответствующими строчными буквами.

Реализация на языке BASIC

10 INPUT "Основание системы счисления (натуральное число не меньше 2 и не больше 36)"; K
20 IF K<2 OR K>36 OR K<>INT(K) THEN 10
30 C$="0123456789abcdefghijklmnopqrstuvwxyz"
35 C$=LEFT$(C$,K) ў выделяем множество цифр системы счисления с основанием K
40 PRINT "Число в системе счисления с основанием K"; K; INPUT A$
60 IF LEN(A$)>255 OR LEN(A$)<1 THEN PRINT "Не выполнены технические ограничения": GOTO 40
70 FOR I=1 TO LEN(A$)
80 S$=MID$(A$,I,1)
90 IF ASC(S$)>=65 AND ASC(S$)<=90 THEN MID$(A$,I,1)=CHR$(ASC(S$)+32): S$=MID$(A$,I,1) ў переводим заглавные символы в нижний регистр
100 IF INSTR(C$,S$)=0 THEN PRINT "Недопустимый символ. Повторите ввод": GOTO 40
110 NEXT I
120 M$=RIGHT$(C$,1) ў находим обозначение максимальной цифры
130 FOR I=LEN(A$) TO 1 STEP -1
135 S$=MID$(A$,I,1)
140 IF S$=M$ THEN MID$(A$,I,1)="0": GOTO 170
150 L=INSTR(C$,S$)
160 MID$(A$,I,1)=MID$(C$,L+1,1): GOTO 190
170 NEXT I
180 A$="1"+A$
190 PRINT A$

Реализация на языке PASCAL

const
  Figures: String[36]='0123456789abcdefghijklmnopqrstuvwxyz';
Var
  SetFigures: set of Char;
  i, k: Integer;
  Error: Boolean;
  Number: String;
begin
  repeat
    Write('Введите основание системы счисления:');
    ReadLn(k);
    if (k<2)or(k>36) then
      WriteLn('Недопустимое значение. Повторите.');
  until (k>=2)and(k<=36);
  SetFigures := [];
  for i := 1 to k do SetFigures := SetFigures+[Figures[i]];
  repeat
    Write('Введите число:');
    ReadLn(Number);
    Error := False;
    for i := 1 to Length(Number) do
      begin
        if (Ord(Number[i])>=65)and(Ord(Number[i])<=90) then
          Number[i] := Chr(Ord(Number[i])+32);
        if not (Number[i] in SetFigures) then
          begin
            WriteLn('Неверный символ в числе. Повторите.');
            Error := True;
            Break;
          end;
      end;
  until not Error;
  i := Length(Number);
  while (i>0)and(Number[i]=Figures[k]) do
    begin
      Number[i] := '0';
      Dec(i);
    end;
  if i=0 then Number := '1'+Number else
    begin
      Number[i] := Figures[Pos(Number[i], Figures)+1];
    end;
  WriteLn('Результат:', Number);
end.

СЧАСТЛИВЫЕ ЧИСЛА

(16 баллов)

Решение. Как следует из условия задачи, результатом её решения является содержимое файла OUTPUT.TXT, который должен быть создан участником олимпиады во время практического тура и предъявлен жюри для проверки. Ещё раз подчёркиваем: в условии задачи не сказано, что обязательно должна быть разработана программа, подсчитывающая количество 2n-значных счастливых чисел для всех значений n из указанного диапазона изменения и выводящая в файл полученные результаты непосредственно при проверке задач второго тура. Жюри должно проверить файл OUTPUT.TXT. Какими средствами этот файл создаётся, каким образом могут быть получены содержащиеся в нём результаты, в условии задачи не оговаривается. Разумеется, если бы кто-либо из участников сумел составить эффективно работающий алгоритм, который за очень ограниченное время тестирования подсчитывал бы все требуемые значения и выводил бы их в выходной файл, такое решение было бы оценено значительно более высокими баллами, чем объявлено в условии.

В том же варианте задания, который получили участники олимпиады, вполне допускалось, что какие-то значения могут быть подсчитаны "вручную" (например, чтобы понять, что для n=1 результат равен 9, компьютер не нужен), для получения других значений будут составлены алгоритмы, может быть не слишком быстрые, может быть различные для разных разрядностей, но которые дадут возможность заранее определить требуемые значения. (Не следует забывать, что у участников олимпиады при проведении практического тура значительно больше шансов дождаться результата от программы, чем у членов жюри в процессе проверки решений, хотя бы по причине большего запаса времени и терпения.) В зависимости от того, насколько удачными были бы применённые алгоритмы, количество значений, которые успел бы определить участник олимпиады за время проведения тура предполагалось различным, поэтому в условии задачи сделана оговорка по поводу числа правильно определённых значений.

Итак, если не удаётся составить быстро работающий алгоритм, который решал бы задачу в целом, в данном случае допустимо использовать, например, какой-либо переборный алгоритм, который позволил бы найти количество счастливых 2n-значных чисел для конкретного значения n, и модифицировать его для разных разрядностей. Очевидно, что от эффективности выбранного переборного алгоритма зависит, сколько результатов удастся получить за время проведения практического тура. Всё же следует отметить, что даже хороший переборный алгоритм с числами больших разрядностей начинает работать так медленно, что дождаться получения всех указанных в задаче результатов не представляется возможным, даже если потратить всё время второго тура только на данную задачу.

Самый простой вариант переборного алгоритма, когда просматривается в порядке возрастания всё множество 2n-значных чисел, для каждого числа определяются цифры, а затем сравниваются суммы первых и последних n цифр, является самым плохим в силу слишком большого количества действий. Его можно использовать только для самых маленьких разрядностей.

Для организации перебора лучше уж воспользоваться вложенными циклами (смотрите решение задачи 1 раздела "Школьные олимпиады по информатике"), где параметрами циклов являются цифры 2n-значного числа (первая цифра меняется от 1 до 9, остальные - от 0 до 9), а количество циклов определяется разрядностью числа. В таком варианте достигается экономия за счёт исключения действий, связанных с определением цифр. Ниже приведён довольно нетривиальный пример такого алгоритма для определения количества счастливых 18-значных чисел (смотрите реализацию на языке PASCAL). Модификация этого алгоритма для чисел другой размерности не представляет затруднений.

Поясним идею алгоритма. Запишем 18-значное число в виде a₁a₂a₃a₄a₅a₆a₇a₈a₉b₁b₂b₃b₄b₅b₆b₇b₈b₉. Очевидно, что его первые девять цифр a₁a₂a₃a₄a₅a₆a₇a₈a₉ составляют целое число из диапазона [100000000...999999999], а последние девять цифр b₁b₂b₃b₄b₅b₆b₇b₈b₉ - целое число из диапазона [0...999999999], дополненное (при необходимости) нулевыми разрядами до 9-значного. Число будет счастливым, если для его цифр справедливо равенство a₁+a₂+...+a₉=b₁+b₂+...+b₉.

Введём ряд обозначений: U(18) - количество счастливых 18-значных билетов; T(18,s) - количество счастливых 18-значных билетов, у которых

a₁+a₂+...+a₉=b₁+b₂+...+b₉=s,

очевидно, что s может принимать значения 1, 2, ..., 9*9; A(9,s) и B(9,s) - количества целых чисел диапазонов [100000000...999999999], [0...999999999] соответственно, у которых сумма цифр равна s.

Запишем два очевидных соотношения:

; T(18,s)=A(9,s)*B(9,s)

Подсчёт значений A(9,s) и B(9,s) производится с помощью переборного алгоритма с вложенными циклами, причём при определении A(9,s) параметр самого внешнего цикла должен быть отличен от 0, так как a_1і 1.

В реализацию приведённого алгоритма на языке PASCAL включены специфические средства языка, позволяющие определить время работы программы. Скажем, для 16-значных чисел это время - около двух минут, для 18-значных чисел - 20-25 минут (в зависимости от характеристик процессора). Для 20-значных чисел результат будет получен только через несколько часов непрерывной работы.

Обсудим полное решение задачи. Обобщив обозначения, введённые выше, и проведя рассуждения, аналогичные вышеизложенным, получим соотношение

*B(n,s) (1)

Рассмотрим n-значное число a₁a₂...a_n, у которого сумма цифр равна s. Пусть значение старшего разряда этого числа равно a. Тогда остальные цифры образуют
(n-1)-значное число с суммой цифр s-a. Очевидно, что одновременно должны выполняться соотношения 1Ј aЈ 9 и aЈ s. Поэтому 1Ј aЈ min(9,s). Так как число a₂...a_n с суммой цифр s-a может иметь старший разряд, равный нулю, то количество таких чисел равно B(n-1,s-a). Введя обозначение m=min(9,s), получаем, что

.

Аналогичные рассуждения позволяют сделать вывод, что

(2)

Отделив в последнем равенстве слагаемое, соответствующее b=0, получим соотношение

откуда

A(n,s)=B(n,s)-B(n-1,s) (3)

Очевидно, что при n=1 имеем B(1,0)=B(1,1)=B(1,2)=
=...=B(1,9)=1. Для других значений s справедливо равенство B(1,s)=0. Формула (2) позволяет заполнить таблицу B(10,9*10), значение элемента B(n,s) которой равно количеству целых чисел, которые принадлежат диапазону [0...], с суммой цифр, равной s. По формуле (3) находим значения A(n,s) и, наконец, используя равенство (1), определяем количество счастливых 2n-значных чисел для всех n от 1 до 10.

Заметим, что в реализации данного алгоритма на языке PASCAL, для определения значений B(n,s), вместо формулы (2), использовано другое рекуррентное соотношение, легко следующее из равенства (2).

Реализация на языке BASIC

5 'полное решение
10 OPEN "OUTPUT.TXT" FOR OUTPUT AS #1
20 DIM A(90),B(10,90)
30 FOR S=0 TO 9
40 B(1,S)=1
50 NEXT S
60 FOR N=1 TO 10
70 IF N=1 THEN U=9:GOTO 200 ELSE U=0
80 FOR S=0 TO 9*N
90 IF S<9 THEN M=S ELSE M=9
100 FOR A=0 TO M
110 B(N,S)=B(N,S)+B(N-1,S-A)
120 NEXT A
130 NEXT S
140 FOR S=1 TO 9*N
150 A(S)=B(N,S)-B(N-1,S)
160 NEXT S
170 FOR S=1 TO 9*N
180 U=U+A(S)*B(N,S)
190 NEXT S
200 PRINT #1,U
210 NEXT N
220 CLOSE

Реализация на языке PASCAL

{переборный вариант}
{$n+,e+}
uses
 dos;
var
  i, j, k, l, m, n, o, p, q, s: integer;
  A, B: array[1..9*9]of Comp;
  U: Comp;
  h, min, sec, s100: Word;
  Time: Real;
begin
  GetTime(h,min,sec,s100);
  Time := h*3600+min*60+sec+s100/100;
  for s := 1 to 9*9 do
    begin
      A[s] := 0;
      B[s] := 0;
    end;
  for i := 0 to 9 do
    for j := 0 to 9 do
      for k := 0 to 9 do
        for l := 0 to 9 do
          for m := 0 to 9 do
            for n := 0 to 9 do
              for o := 0 to 9 do
                for p := 0 to 9 do
                  for q := 0 to 9 do
      if i+j+k+l+m+n+o+p+q<>0 then
        begin
          if i<>0 then
            A[i+j+k+l+m+n+o+p+q] := A[i+j+k+l+m+n+o+p+q] + 1;
            B[i+j+k+l+m+n+o+p+q] := B[i+j+k+l+m+n+o+p+q] + 1;
        end;
  U := 0;
  for s := 1 to 9*9 do
    U := U + A[s]*B[s];
  WriteLn(U:25:0);
  GetTime(h,min,sec,s100);
  WriteLn(h*3600+min*60+sec+s100/100-time:0:2);
end.

{полное решение}
{$n+,e+}
const
  MaxN=10;
var
  B: array[1..MaxN, 0..9*MaxN] of Comp;
  A: array[1..9*MaxN] of Comp;
  U: array[1..MaxN] of Comp;
  s, n, a: byte;
  f: Text;
begin
  Assign (f, 'Output.txt');
  ReWrite (f);
  for s := 0 to 9 do
    B[1,s] := 1;
  WriteLn (f, 1:10, 9:25);
  for n := 2 to MaxN do
    begin
      for s := 0 to 9*(n-1) do
        for a := 0 to 9 do
          B[n, s+a] := B[n, s+a] + B[n-1, s]*B[1,a];
      for s := 1 to 9*n do
        A[s] := B[n,s] - B[n-1,s];
      U[n] := 0;
      for s := 1 to 9*n do
        U[n] := U[n] + A[s]*B[n, s]);
      WriteLn(f, n:10, U[n]:25:0);
    end;
  Close(f);
end.

Распечатка файла Output.txt :

1 9
2 615
3 50412
4 4379055
5 392406145
6 35866068766
7 3323483518810
8 311088525668335
9 29344719005694973
10 2785022004925340460

АРИФМЕТИКА ПО-РУССКИ

вход: сорок восемь умножить на двенадцать;

выход: пятьсот семьдесят шесть.

плюс, прибавить, минус, вычесть, умножить.

(24 балла)

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

Естественным образом возникает потребность в нескольких вспомогательных процедурах, которые выполняют следующие действия:

а) подпрограмма, удаляющая "лишние" пробелы во введённой строке ("лишним" считается пробел, который следует за пробелом, в каком бы месте строки он ни находился);

б) подпрограмма, переводящая все символы введённой строки (в данном случае это символы русского алфавита) к одному регистру, например, нижнему;

в) подпрограмма, разделяющая вводимую строку на первое числительное, арифметическое действие и второе числительное;

г) подпрограмма, преобразующая символьную запись числа в виде числительного русского языка (диапазона от 1 до 99) в числовую форму;

д) подпрограмма, выполняющая обратное преобразование числа (диапазона от –98 до 99*99) в символьную форму в виде числительного русского языка.

Рассмотрим перечисленные подпрограммы по порядку.

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

Эта подзадача легко реализуется в рамках простого конечного автомата-преобразователя.

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

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

Очевидно, что в данном случае автомат закончит работу, когда будет прочитана посимвольно вся строка.

Поскольку нам надо удалить всякий пробел, следующий за другим пробелом, то множество состояний автомата будет содержать всего два состояния – "после пробела" и "после не пробела". Функции переходов и выходов определятся следующей таблицей:

Чтобы конструируемый автомат удалял лидирующие пробелы начальным должно быть состояние «после пробела».

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

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

Заметим, что данная поäçàäàча также реализуется конечным автоматом. Этот автомат имеет всего одно состояние и его функции переходов и выходов задаются следующей таблицей (состояние опущено, так как от него ничего не зависит):

Будем предполагать, что ввåäёííàÿ ñòðîêà óæå íå ñîäåðæèò ëèøíèõ ïðîáåëîâ è âñå её сиìâîëû íàõîäÿòñÿ â íèæíåì ðåãèñòðå. Теперь моæíî çàíÿòüñÿ ðàçäåëåíèåì åå íà ëîãèческие части – первое числительное, собственно арифметическое действие и второе числительное.

Для этого нам понадобится массив строк, содержащий все допустимые в данном задании способы словесного описания всех арèôìåòèческих действий. Имея такой массив, достаточно проверить, встречается ли хотя бы одно из этих действий во вâåäёííîé ñòðîêå (для этого можно воспользоваться стандартной функцией поиска заданной подстроки в строке). Есëè âñòðåчается, то всё, что стоит в строке леâåå, должно обозначать пеðâое чиñëèòåëüíое, а вñё, что стоит в строке прàâåå, должно быть втîðым числительным. Есëè íå âñòðåчается, то входная стðîêà ñîäåðæèò что-то, что не является словесным описанием арифметического действия, т.е. допущена ошибка при вводе.

Отдельно надо рассмотреть два следующих способа словесного описания арифметического действия, в кîòîðûõ ïðåäëîã ñòàâèòñÿ â íàчале: "к … прибавить …" и "из … вычесть …" (в последнем выражении из первого операнда вычитается второй, а не наоборот!!!).

Стоèò отмеòèòü, что проверка на наличие в строке обозначения арèôìåòèческого действия "прибавить к " должна следовать раньше проверки обозначения деéñòâèÿ "прибавить " (так как строка "прибавить " является подстрокой строки "прибавить к "), поэтому порядок следования вариантов описания сложения в массиве описания действий не является случайным. Аналогичным образом следует поступать с вариантами описания вычитания: "вычесть из " следует раíüøå "вычесть".

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

Выделив во входном выражении операнды, мы должны преобразовать символьную запись числа в виде числительного в числовую форму.

Чтобы сделать это, нам понадобится ряд двумерных строковых массивов. Эти массивы будут хранить числительные, обозначающие единицы, десятки и числа от 10 до 19 во всех падежах, которые могут встретиться во входной строке у первого или второго операндов. У элементов этих массивов первый индекс будет определять соответствующий падеж числительного , а второй индекс - само число.

Сначала надо посмотреть, не обозначает ли преобразуемый в числовую форму операнд число от 10 до 19. И только если это не так, проверить, соответствует ли начало символьной записи какому-либо десятку, а остаток единице.

После того, как во введённом выражении выделены словесные описания операндов, определено требуемое арифметическое действие и найдены значения операндов в числовом виде, несложно вычислить результат указанного действия. Остаётся только вывести этот результата в словесном виде, а для этого нужна процедура преобразования числовой записи результата в символьную форму в виде числительного.

Отдельно необходимо рассмотреть случай, когда результат равен нулю.

Что касается ненулевого результата, то сначала проверяется, не является ли результат отрицательным числом. Если да, то запомним это, чтобы записать "минус" в начале выходной строки. В дальнейшем учитывается только модуль результата.

Поскольку результат может быть трёхзначным и даже четырёхзначным числом, нам понадобятся числительные, обозначающие сотни и тысячи. Для их хранения, как и ранее, заведём массивы (на этот раз одномерные, так как вывод результата всегда должен осуществляться в именительном падеже). Что касается других необходимых числительных, то для десятков, единиц и чисел от 10 до 19 мы будем использовать массивы, введёнными ранее при преобразовании символьной записи операндов в числовую.

Преобразование результата в словесную форму разобьём на два этапа: преобразование части, содержащей десятки и единицы, и преобразование части, касающейся сотен и тысяч. Это необходимо сделать, так как при преобразовании десятков и единиц приходится отдельно рассматривать случай, когда преобразуемое число попадает в диапазон от 10 до 19.

Реализация на языке BASIC

10 DATA "умножить на ","разделить на ","прибавить к "
20 DATA "прибавить ","плюс ","вычесть из ","вычесть ","минус "
30 DATA "","один ","два ","три ","четыре ","пять "
40 DATA "шесть ","семь ","восемь ","девять "
50 DATA "","одному ","двум ","трем ","четырем ","пяти "
60 DATA "шести ","семи ","восьми ","девяти "
70 DATA "","одного ","двух ","трех ","четырех ","пяти "
80 DATA "шести ","семи ","восьми ","девяти "
90 DATA "десять ","одиннадцать ","двенадцать "
100 DATA "тринадцать ","четырнадцать ","пятнадцать "
110 DATA "шестнадцать ","семнадцать ","восемнадцать "
120 DATA "девятнадцать "
130 DATA "десяти ","одиннадцати ","двенадцати "
140 DATA "тринадцати ","четырнадцати ","пятнадцати "
150 DATA "шестнадцати ","семнадцати ","восемнадцати "
160 DATA "девятнадцати "
170 DATA "","десять ","двадцать ","тридцать ","сорок "
180 DATA "пятьдесят ","шестьдесят ","семьдесят "
190 DATA "восемьдесят ","девяносто "
200 DATA "","десяти ","двадцати ","тридцати ","сорока "
210 DATA "пятидесяти ","шестидесяти ","семидесяти "
220 DATA "восьмидесяти ","девяноста "
230 DATA "","сто ","двести ","триста ","четыреста ","пятьсот "
240 DATA "шестьсот ","семьсот ","восемьсот ","девятьсот "
250 DATA "","одна тысяча ","две тысячи ","три тысячи "
260 DATA "четыре тысячи ","пять тысяч ","шесть тысяч "
270 DATA "семь тысяч ","восемь тысяч ","девять тысяч "
280 DIM A$(8),O$(3,10),T$(2,10),T2$(2,10),H$(10),T3$(10)
290 FOR i=1 TO 8: READ A$(i): NEXT i
300 FOR i=1 TO 3: FOR j=1 TO 10
310 READ O$(i,j)
320 NEXT j: NEXT i
330 FOR i=1 TO 2: FOR j=1 TO 10
340 READ T$(i,j)
350 NEXT j: NEXT i
360 FOR i=1 TO 2: FOR j=1 TO 10
370 READ T2$(i,j)
380 NEXT j: NEXT i
390 FOR i=1 TO 10: READ H$(i): NEXT i
400 FOR i=1 TO 10: READ T3$(i): NEXT i
410 U$="АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ"
420 L$="абвгдежзийклмнопрстуфхцчшщьыъэюя"
430 INPUT "Вход"; D$: D$=D$+" "
440 GOSUB 1000
450 GOSUB 1200
460 S$=" "
470 FOR i=1 TO 8
480 j=INSTR(D$,A$(i))
490 IF j=0 THEN 620
500 O1$=MID$(D$,1,j-1): O2$=MID$(D$,j+LEN(A$(i)),255)
510 IF i=1 THEN S$="*"
520 IF i=2 THEN S$="/"
530 IF (i>2) AND (i<6) THEN S$="+"
540 IF i=6 THEN S$="_"  особый случай вычитания
550 IF i>6 THEN S$="-"
560 IF i=3 THEN M2=2: GOTO 590
570 IF i=6 THEN M2=3: GOTO 590
580 M2=1
590 IF i=4 THEN M1=2: GOTO 615
600 IF i=7 THEN M1=3: GOTO 615
610 M1=1
615 GOTO 630
620 NEXT i
630 E=0
640 IF S$=" " THEN E=1: GOTO 770
650 IF i<>4 THEN 670
660 IF MID$(O1$,1,2)="к " THEN O1$=MID$(O1$,3,255) ELSE M1=1
670 IF i<>7 THEN 690
680 IF MID$(O1$,1,3)="из " THEN O1$=MID$(O1$,4,255) ELSE E=1: GOTO 770
690 M=M1: OO$=O1$: GOSUB 1400: N1=N
700 M=M2: OO$=O2$: GOSUB 1400: N2=N
710 IF S$="+" THEN R=N1+N2
720 IF S$="-" THEN R=N1-N2
730 IF S$="_" THEN R=N2-N1
740 IF S$="*" THEN R=N1*N2
750 IF S$="/" THEN R=INT(N1/N2)
760 GOSUB 1600
770 IF E=0 THEN PRINT "выход: "; RS$ ELSE PRINT "Неверный ввод."
780 END
1000  удаление лишних пробелов
1010 T$="": St=0
1020 FOR i=1 TO LEN(D$)
1030 IF St<>0 THEN 1060
1040 IF MID$(D$,i,1)<>" " THEN St=1: T$=T$+MID$(D$,i,1)
1050 GOTO 1080
1060 T$=T$+MID$(D$,i,1)
1070 IF MID$(D$,i,1)=" " THEN St=0
1080 NEXT i
1090 D$=T$
1100 RETURN
1200  перевод в нижний регистр
1210 FOR i=1 TO LEN(D$)
1220 j=INSTR(U$,MID$(D$,i,1))
1230 IF j<>0 THEN MID$(D$,i,1)=MID$(L$,j,1)
1240 NEXT i
1250 RETURN
1400 перевод строки в числовую форму
1410 N=0: MM=M
1420 IF M=3 THEN MM=2
1430 FOR i=0 TO 9
1440 IF OO$=T$(MM,i+1) THEN N=10+i: GOTO 1530
1450 NEXT i
1460 FOR i=2 TO 9
1470 IF INSTR(OO$,T2$(MM,i+1))=1 THEN N=i*10: OO$=MID$(OO$,LEN(T2$(MM,i+1))+1,255): GOTO 1490
1480 NEXT i
1490 FOR i=1 TO 9
1500 IF INSTR(OO$,O$(M,i+1))=1 THEN N=N+i: OO$=MID$(OO$,LEN(O$(M,i+1))+1,255): GOTO 1520
1510 NEXT i
1520 IF OO$<>"" THEN E=1
1530 RETURN
1600  перевод числа в строковую форму
1610 IF R<0 THEN Mi=1: R=ABS(R) ELSE Mi=0
1620 RS$=""
1630 IF R=0 THEN RS$="ноль": GOTO 1680
1640 IF INT(R/10)-10*INT(R/100)=1 THEN RS$=T$(1,1+R-10*INT(R/10)): GOTO 1660
1650 RS$=T2$(1,1+INT(R/10)-10*INT(R/100)): RS$=RS$+O$(1,1+R-10*INT(R/10))
1660 RS$=T3$(1+INT(R/1000))+H$(1+INT(R/100)-10*INT(R/1000))+RS$
1670 IF Mi=1 THEN RS$="минус "+RS$
1680 RETURN

Реализация на языке PASCAL

uses Crt;
const
  UpRusSet=['А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ж', 'З', 'И', 'Й',
   'К', 'Л', 'М', 'Н', 'О', 'П', 'Р', 'С', 'Т', 'У', 'Ф','Х',
   'Ц', 'Ч', 'Ш', 'Щ', 'Ь', 'Ы', 'Ъ', 'Э', 'Ю', 'Я'];
  UpRus: string[33] ='АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ';
  LoRus: string[33] ='абвгдежзийклмнопрстуфхцчшщьыъэюя';
  Signs: array[1..8]of string[13]=
    ('умножить на ', 'разделить на ', 'прибавить к ',
     'прибавить ', 'плюс ', 'вычесть из ', 'вычесть ',
     'минус ');
  Ones: array[1..3, 0..9] of string[8]=
  (('', 'один ', 'два ', 'три ', 'четыре ', 'пять ',
    'шесть ', 'семь ', 'восемь ', 'девять '),
   ('', 'одному ', 'двум ', 'трем ', 'четырем ', 'пяти ',
    'шести ', 'семи ', 'восьми ', 'девяти '),
   ('', 'одного ', 'двух ', 'трех ', 'четырех ', 'пяти ',
    'шести ', 'семи ', 'восьми ', 'девяти '));
  Teens: array[1..2, 0..9] of string[13]=
  (('десять ', 'одиннадцать ', 'двенадцать ', 'тринадцать ',
    'четырнадцать ', 'пятнадцать ', 'шестнадцать ',
    'семнадцать ', 'восемнадцать ', 'девятнадцать '),
   ('десяти ', 'одиннадцати ', 'двенадцати ', 'тринадцати ',
    'четырнадцати ', 'пятнадцати ', 'шестнадцати ',
    'семнадцати ', 'восемнадцати ', 'девятнадцати '));
  Tens: array[1..2, 0..9] of string[13]=
  (('', 'десять ', 'двадцать ', 'тридцать ', 'сорок ',
    'пятьдесят ', 'шестьдесят ', 'семьдесят ',
    'восемьдесят ', 'девяносто '),
   ('', 'десяти ', 'двадцати ', 'тридцати ', 'сорока ',
    'пятидесяти ', 'шестидесяти ', 'семидесяти ',
    'восьмидесяти ', 'девяноста '));
  Hundreds: array[0..9] of string[10]=
    ('', 'сто ', 'двести ', 'триста ', 'четыреста ',
     'пятьсот ','шестьсот ', 'семьсот ', 'восемьсот ',
     'девятьсот ');
  Thousands: array[0..9] of string[14]=
    ('', 'одна тысяча ', 'две тысячи ', 'три тысячи ',
     'четыре тысячи ', 'пять тысяч ', 'шесть тысяч ',
     'семь тысяч ', 'восемь тысяч ', 'девять тысяч ');
Var
  Data, Result: string; {Входные данные и результат}
  Error: Boolean; {Признак наличия ошибки входных данных}
function LoCaseRus(c: Char): Char;
{Перевод русского символа к нижнему регистру}
begin
  if c in UpRusSet then
    c := LoRus[Pos(c, UpRus)];
  LoCaseRus := c;
end;
function LoCaseRusStr(S: string): string;
{Перевод строки русских символов к нижнему регистру}
Var
  i: Byte;
begin
  for i := 1 to Length(S) do
    S[i] := LoCaseRus(S[i]);
  LoCaseRusStr := S;
end;
function Trim(S: string): string;
{Удаление лишних пробелов (остается не более одного подряд,
 а также удаляются лидирующие пробелы)}
Var
  State: (AfterSpace, AfterNotSpace);
  i: Byte;
  Result: string;
begin
  Result := '';
  State := AfterSpace;
  for i := 1 to Length(S) do
    case State of
      AfterSpace:
        if S[i] <> ' ' then
          begin
            State := AfterNotSpace;
            Result := Result + S[i];
          end;
      AfterNotSpace:
        begin
          Result := Result + S[i];
          if S[i] = ' ' then
            State := AfterSpace;
        end;
    end;
  Trim := Result;
end;
procedure InputData;{Ввод данных}
begin
  Write ('вход: ');
  ReadLn (Data);
end;
procedure Solve;{Решение поставленной задачи}
Var
  Op1, Op2: string;
  Sign: Char;
  N1, N2, i, j, Res, Mode_2, Mode_1: Integer;
  function ValToStr(Value: Integer): string;
  {Перевод числа в строковую форму}
  Var
    i: Integer;
    Result: string;
    Minus: Boolean;
  begin
    if Value<0 then
      begin
        Minus := True;
        Value := Abs(Value);
      end
     else
      Minus := False;
    Result := '';
    if Value=0 then
      Result := 'ноль'
     else
      begin
        {единицы и десятки}
        if (Value mod 100)div 10 = 1 then
          Result := Teens[1, Value mod 10]
         else
          begin
            Result := Tens[1, (Value mod 100)div 10]+
              Ones[1, Value mod 10];
          end;
        {тысячи и сотни}
        Result := Thousands[Value div 1000]+
          Hundreds[(Value mod 1000)div 100]+Result;
      end;
    if Minus then Result := 'минус '+Result;
    ValToStr := Result;
  end;
  function StrToVal(S: string; Mode: Byte): Integer;
  {Перевод строки в числовую форму}
  Var
    Result, i, Mode2: Integer;
  begin
    Result := 0; Mode2 := Mode;
    if Mode=3 then Mode2 := 2;
    for i := 0 to 9 do{от 10 до 19}
      if S=Teens[Mode2, i] then
        begin
          Result := 10+i; Break;
        end;
    if Result=0 then
      begin
        for i := 2 to 9 do {десятки}
          if Pos(Tens[Mode2, i], S)=1 then
            begin
              Result := i*10;
              S := Copy(S, Length(Tens[Mode2, i])+1, 255);
              Break;
            end;
        for i := 1 to 9 do {единицы}
          if Pos(Ones[Mode, i], S)=1 then
            begin
              Result := Result+i;
              S := Copy(S, Length(Ones[Mode, i])+1, 255);
              Break;
            end;
        if S<>'' then Error := True;
      end;
    StrToVal := Result;
  end;
begin
  {Удалим лишнее и приведем к верхнему регистру}
  Data := LoCaseRusStr(Trim(Data+' '));
  {Разобьем строку на три логические части - Op1, Op2 и
   Sign, а также определим нужный режим записи первого и
   второго операндов (падеж)}
  Sign := ' ';
  for i := 1 to 8 do
    begin
      j := Pos(Signs[i], Data);
      if j<>0 then
        begin
          Op1 := Copy(Data, 1, j-1);
          Op2 := Copy(Data, j+Length(Signs[i]), 255);
          Case i of
            1: Sign := '*';
            2: Sign := '/';
            3, 4, 5: Sign := '+';
            7, 8: Sign := '-';
            6: Sign := '_'; {особый случай вычитания}
          end;
          if i=3 then
            Mode_2 := 2
           else
            if i=6 then
              Mode_2 := 3
             else
              Mode_2 := 1;
          if i=4 then
            Mode_1 := 2
           else
            if i=7 then
              Mode_1 := 3
             else
              Mode_1 := 1;
          Break;
        end;
    end;
  if Sign=' ' then
    begin
      Error := True;
      Exit;
    end;
  if i=4 then
    if Copy(Op1, 1, 2)='к ' then
      Op1 := Copy(Op1, 3, 255)
     else
      Mode_1 := 1;
  if i=7 then
    if Copy(Op1, 1, 3)='из ' then
      Op1 := Copy(Op1, 4, 255)
     else
      begin
        Error := True;
        Exit;
      end;
  {вычислим значение и преобразуем его обратно в строку}
  N1 := StrToVal(Op1, Mode_1);
  N2 := StrToVal(Op2, Mode_2);
  if Error then Exit;
  Case Sign of
    '+': Res := N1+N2;
    '-': Res := N1-N2;
    '_': Res := N2-N1;
    '*': Res := N1*N2;
    '/': Res := N1 div N2;
  end;
  Result := ValToStr(Res);
end;
procedure OutputResult; {Вывод результата}
begin
  WriteLn ('выход: ', Result);
end;
Var
  c: Char;
begin {Основная программа}
  repeat
    Error := False;
    InputData;
    Solve;
    if Error then
      begin
        Write ('Неверный ввод. ');
      end
     else
      OutputResult;
    Write ('Хотите еще (д/н|y/n)?');
    repeat
      c := UpCase(LoCaseRus(ReadKey));
    Until c in ['д', 'н', 'Y', 'N'];
    WriteLn (c);
    if (c='н') or (c='N') then Break;
  until False;
end.

"Русский ДОМ СЕЛЕНГА"

(8 баллов)

Решение. В алгоритме производится расчёт на каждый день растущей суммы вклада и отслеживается ежедневное изменение даты с учётом месяцев и високосных лет вплоть до дня, когда текущая сумма вклада достигнет требуемой величины. Високосным считается год, номер которого делится на 4, но не делится на 400.

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

Реализация на языке BASIC

10 DIM D(12)
20 DATA 31,28,31,30,31,30,31,31,30,31,30,31
30 FOR I=1 TO 12
40 READ D(I)
50 NEXT I
60 PRINT "Укажите день открытия счёта";
70 PRINT "(формат ввода даты - дд.мм.гггг , например,  08.01.1997 )"
80 INPUT A$
90 IF LEN(A$)<>10 OR MID$(A$,3,1)<>"." OR MID$(A$,6,1)<>"." THEN PRINT "Некорректный ввод":
GOTO 70
100 FOR I=1 TO 10
110 IF I=3 OR I=6 THEN 130
120 IF MID$(A$,I,1)<"0" OR MID$(A$,I,1)>"9" THEN PRINT "Недопустимые символы": GOTO 70
130 NEXT i
140 DD=VAL(MID$(A$,1,2)): DM=VAL(MID$(A$,4,2)): DG=VAL(MID$(A$,7))
150 IF DG/4=DG\4 AND DG/400<>DG\400 THEN D(2)=29
160 IF DM<1 OR DM>12 THEN PRINT "Некорректные данные": GOTO 70
170 IF DD<1 OR DD>D(DM) THEN PRINT "Некорректные данные": GOTO 70
180 INPUT "Величина первоначального вклада (в рублях)"; N
190 IF N<1 OR N<>INT(N) THEN PRINT "Некорректные данные": GOTO 180
195 IF N<1000 THEN PRINT "Вклад не будет увеличиваться": GOTO 290
200 INPUT "Величина ежедневного прироста каждой тысячи вклада ( в рублях)"; K
210 IF K<1 OR K<>INT(K) THEN PRINT "Некорректные данные": GOTO 200
220 INPUT "Предельное значение вклада (в рублях)"; M
230 IF M<1 OR M<>INT(M) THEN PRINT "Некорректные данные": GOTO 220
240 IF M<=N THEN 280
250 N=N+K*(N\1000)
260 GOSUB 300
270 GOTO 240
280 GOSUB 400
285 PRINT "Определяемая дата - ";A$,"Величина вклада в рублях -";N
290 END
300 'определение даты очередного дня
310 IF DD<D(DM) THEN DD=DD+1: GOTO 350
320 DD=1: IF DM<12 THEN DM=DM+1: GOTO 350
330 DM=1: DG=DG+1
335 IF DG>9999 THEN PRINT "Переполнение даты": GOTO 290
340 IF DG/4=DG\4 AND DG/400<>DG\400 THEN D(2)=29 ELSE D(2)=28
350 RETURN
400 'восстановление формата даты
410 DD$=RIGHT$(STR$(DD),LEN(STR$(DD))-1): DD$=RIGHT$("00"+DD$,2)
420 DM$=RIGHT$(STR$(DM),LEN(STR$(DM))-1): DM$=RIGHT$("00"+DM$,2)
430 DG$=RIGHT$(STR$(DG),LEN(STR$(DG))-1): DG$=RIGHT$("0000"+DG$,4)
440 A$=DD$+"."+DM$+"."+DG$
450 RETURN

Реализация на языке Паскаль

const
  Days: array[1..12] of Integer=
    (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31);
Var
  Date:record{Структура, в которой хранится текущая дата
    в процессе решения}
         Day, Month, Year: Integer;
       end;
  N, K, M: Real;
  Can: Boolean;{Признак возможности получить требуемую сумму}
function Vis: Byte;{Возвращает 1 для февраля високосного
  года, иначе - 0}
begin
  if (Date.Month=2)and((Date.Year mod 4=0)
    and(Date.Year mod 400<>0)) then
    Vis := 1
   else
    Vis := 0;
end;
procedure NextDay;{Процедура, осуществляющая переход от
  текущего дня к следующему}
begin
  if Date.Day<Days[Date.Month]+Vis then
    Inc(Date.Day)
   else
    if Date.Month<12 then
      begin
        Inc(Date.Month);
        Date.Day := 1;
      end
     else
      begin
        Inc(Date.Year);
        Date.Month := 1;
        Date.Day := 1;
      end;
end;
procedure InputData;{Ввод данных}
Var
  S: String;
  Error: Boolean;
  i: Integer;
begin
  repeat
    Write('Введите сумму первоначального вклада: ');
    ReadLn(N);
    if N<=0 then WriteLn('Вклад должен быть положительным'+
      ' числом.');
  Until N>0;
  repeat
    Write('Введите прирост на каждую целую тысячу в день: ');
    ReadLn(K);
    if K<=0 then WriteLn('Прирост должен быть положительным'+
      ' числом.');
  Until K>0;
  repeat
    Error := False;
    Write('Введите дату вклада: '); ReadLn(S);
    if (Length(S)<>10)or(S[3]<>'.')or(S[6]<>'.') then
      Error := True
     else
      begin
        S := Copy(S, 1, 2)+Copy(S, 4, 2)+Copy(S, 7, 4);
        for i := 1 to 8 do
          if (S[i]<'0')or(S[i]>'9') then
            begin
              Error := True;
              Break;
            end;
        if not Error then
          begin
            Val(Copy(S, 1, 2), Date.Day, i);
            Val(Copy(S, 3, 2), Date.Month, i);
            Val(Copy(S, 5, 4), Date.Year, i);
            if (Date.Day<1)or(Date.Day>Days[Date.Month]+Vis)
              or (Date.Month<1)or(Date.Month>12) then
              Error := True;
          end;
      end;
    if Error then WriteLn('Не соблюден формат даты.');
  Until not Error;
  repeat
    Write('Введите сумму, которую надо получить: ');
    ReadLn(M);
    if M<=0 then WriteLn('Сумма должна быть положительным'+
      ' числом.');
  Until M>0;
end;
procedure Solve;{Решение поставленной задачи}
begin
  Can := (N>=1000)or(N>=M);
  if not Can then Exit;
  while N<M do
    begin
      NextDay;
      N := N+Int(N/1000)*k;
    end;
end;
procedure OutputResult;{Вывод результата}
Var
  S, s2: String[11];
begin
  if not Can then
    begin
      WriteLn('Невозможно получить требуемую сумму.'); Exit;
    end;
  Str(Date.Day, S); if Length(S)=1 then S := '0'+S;
  Str(Date.Month, s2); if Length(s2)=1 then s2 := '0'+s2;
  S := S+'.'+s2+'.';
  Str(Date.Year, s2); while Length(s2)<4 do s2 := '0'+s2;
  S := S+s2;
  if Length(S)<>10 then
    WriteLn('Невозможно вывести результат, придерживаясь'+
      ' формата вывода даты.')
   else
    WriteLn('Сумма накопится к ', S, '.');
end;
begin
  InputData;
  Solve;
  OutputResult;
end.