Задача rebus

Составить программу REBUS, которая определяет все 4-значные числа на интервале [M, N], удовлетворяющие условиям:

a) abcd - 4-значное число;

b) a, b, c, d - разные цифры;

c) ad - cd = a + b + c + d;

и подсчитывает общее количество этих чисел.

Во входном файле REBUS.DAT в 1-й и 2-й строчках находятся два числа M и N. В файле REBUS.SOL выводятся числа, удовлетворяющие условиям а)-с), и их количество.

файл REBUS.DAT	файл REBUS.SOL
5128 5467	5139 5302 2

Решение

program REBUS;

var a,b,c,d,m,n,k,i:integer; f:text;

begin

assign (f,'rebus.dat');

reset(f);

readln(f,m,n);

close(f);

assign(f,'rebus.sol');

rewrite(f);

for i:=m to n do

begin

a:=i div 1000;

b:=i mod 1000 div 100;

c:=i mod 100 div 10;

d:=i mod 10;

if (a <> b) and (a <> c) and (a <> d) and (b <> c) and (b <> d) and (c <> d) and (a*d-c*d=a+b+c+d) then

begin

k:=k+1;

append(f);

writeln(f,i);

end;

end;

append(f);

writeln(f,k);

close(f)

end.

Задача “Эчпочмаки”

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

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

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

Необходимо найти номер наиболее ценного эчпочмака, который проходит в отверстие.

Формат входных данных

Во входном файле записано целое число N — количество эчпочмаков (1 Ј N Ј 1000) и вещественное число D (с точностью до 4 знаков после точки, 0 < D Ј 1000). Далее записаны N троек вещественных чисел Ai, Bi, Ci, задающих длины сторон эчпочмаков (с точностью до 4 знаков после точки, 0 < Ai, Bi, Ci Ј 1000).

Формат выходных данных

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

Пример

 

Комментарий к примеру:

Решение

Введем ось x, направленную перпендикулярно прямой, содержащей отверстие. Произвольно ориентируем треугольник в плоскости и начнем двигать его вдоль оси x. Введем функцию d(x), значение которой равно длине отрезка, лежащего в треугольнике на прямой, содержащей отверстие.

Несложно доказать, что с момента прохода вершины A и до момента достижения вершины B функция d(x) будет возрастающей, а затем, до вершины C — убывающей (при доказательстве можно воспользоваться подобием треугольников). Из этого следует, что своего максимума функция d(x) достигнет, когда точка B (средняя вершина треугольника) будет лежать на прямой. То есть, чтобы проверить, проходит ли треугольник при такой ориентации сквозь отверстие, достаточно посчитать значение функции d(x) в средней вершине и проверить, что оно не больше размеров отверстия.

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

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

где a, b, c — длины сторон треугольника, а p — его полупериметр. Длину наименьшей высоты можно вычислить, пользуясь формулой для площади треугольника S = 1/2•h•a, где a — наибольшая сторона. То есть h = 2•S/a, где a — наибольшая сторона.

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

var i, n, bestno: longint;

a, b, c, p, s, d, h, bests: double;

begin

read(n, d); bestno := 0; bests := -1;

for i := 1 to n do begin

read(a, b, c);

p := (a + b + c) / 2;

s := sqrt(p*(p-a)*(p-b)*(p-c));

if b > a then a := b;

if c > a then a := c; h := 2*s/a;

if (h <= d) and (s > bests) then begin

bestno := i; bests := s

end

end;

write(bestno)

end.