Пример входных и выходных данных. Можно построить обычный циклических алгоритм, в котором за каждую итерации учитывать количество срубленных и регенерированных голов N = N - M + K

input.dat	output.dat
5 2 3	no
100 10 9	yes

Анализ:

Можно построить обычный циклических алгоритм, в котором за каждую итерации учитывать количество срубленных и регенерированных голов N = N - M + K, до тех пор, пока это возможно, то есть пока N> M.

Замечание. Надо заметить, что этот способ при очень большом значении N и малых значениях M и K (M> K) будет занимать значительное время, поскольку постепенно уменьшаем количество голов и подсчитываем удары, а не сразу ищем соответствующее значение используя операцию деления. Поэтому можно использовать другой, более легкий способ, который представлен в таблице:

Если	Соответствующие действие
M≥ N	минимальное количество ударов, которые нанесет ферзь C = 1
иначе (M < N)	M > K	При любом начальном количестве голов, при каждом ударе, количество голов дракона будет уменьшаться. Сразу учтем и удар, который можно сделать в полную силу, и при котором регенерации голов уже не состоится, то есть ферзю необходимо будет на предыдущих ударах срубить N = N - M голов. Минимальное количество ударов для этого C = N div (M - K), но надо помнить, если N mod (M - K)> 0 тогда ферзю придется сделать еще один "контрольный" удар, после которого дракону уже не выжить.
иначе (M ≤ K)	Очевидно, что ферзь не сможет преодолеть дракона с такой бешеной скоростью регенерации голов. В таком случае ответ охарактеризуем числом C = 1.

Для этого способа код будет выглядеть следующим образом:

var m, n, k, c: longint;

output, input: text;

begin

//организация связи с файлами открытие файов на запись и чтение

assign (input, 'input.dat');

assign (output, 'output.dat');

reset (input); rewrite (output);

// чтение данных из файла

read (input, n,m, k);

// задание начальных условий

c:=0;

// составление вложенных условий согласно таблицы

if m>=n

then c:=1

else if m>k

then begin

n:=n-m;

c:=n div (m-k)+1;

// учет контрольного удара

if n mod (m-k) >0 then

c:=c+1;

end

else c:=-1;

// анализ результатов и вывод в файл результата

if c=-1 then

writeln (output, 'no')

else begin

writeln (output, 'yes');

writeln (output, c);

end;

close (input); close (output);

end.

Первый способ решения (не проходит по времени на граничных условиях):

var m, n, k, c: longint;

output, input: text;

begin

//организация связи с файлами открытие файов на запись и чтение

assign (input, 'input.dat');

assign (output, 'output.dat');

reset (input); rewrite (output);

// чтение данных из файла

read (input, n,m, k); c:=0;

if m>=n

then c:=1

else if m>k

then begin

// организация цикла для подсчета количества ударов

while n>m do begin

n:=n-m+k;

c:=c+1;

end;

if n>0 then c:=c+1;

end

else c:=-1;

//анализ результатов и вывод в файл результата

if c=-1 then

writeln (output, 'no')

else begin

writeln (output, 'yes');

writeln (output, c);

end;

close (input); close (output);

end.

Задача 3. Персики.

Тип: работа с длинными числами

Сложность:

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

Задание. Напишите программу, которая определяет количество персиков, содержащихся в этой пирамидке.

Входные данные. В единственной строке записано одно число K (1 ≤ K ≤100000000) – сторона основания пирамиды.

Выходные данные. Выведите одно целое число - количество персиков в пирамиде.

Ограничение по времени: 1 сек. на тест

Пример входных и выходных данных ввода вывода.

input.dat	output.dat

Анализ. Очевидно, что для построения первого слоя пирамиды из персиков нужно ровно n² фруктов, для второго слоя – (n-1)², третьего (n-2)² и так далее и лишь один персик нужен для создания последнего верхнего слоя. Т.е., для построения всей пирамиды необходимо n² + (n-1)² +... +3² + 2² + 1 персиков. Известно, что эта сумма равна n (n + 1) (2n + 1)/6, то есть решение задачи сводится к нахождению этого произведения.

Так как по условию 1 ≤ N ≤ 100 000 000, то в самом крайнем случае по формуле получим: 100000000 · 100000001 · 200000001/6 = 3 333 333 383 333 333 500 000 000.

Это число превышает даже число 9 223 372 036 854 775 807 (верхний предел типа int64), поэтому при решении данной задачи необходимо испольваты так называемую «длинную арифметику». В нашем случае надо найти произведение длинных чисел (процедура mult).

Чтобы свести количество операций к минимуму, избавимся от операции деления, которая присутствует в формуле, а именно деление на 6. Понятно, что в произведении двух чисел n*(n + 1) одно из этих чисел обязательно делится на 2, соответственно и само произведение также делится на 2. Итак, осталось определить делится ли на 3 это произведение. Если это так, то произведение n (n + 1) можно разделить без остатка на 6, в другом случае 3 является делителем числа 2n + 1. Рассмотрев два варианта отдельно мы избавляемся от операции деления в общей формуле n (n + 1) (2n + 1)/6 следующим образом:

if n∗(n+1) mod 3=0

then mult (n∗(n+1) div 6,2∗n+1)

else mult (n∗(n+1) div 2,(2∗n+1) div 3);

Const NMax = 250;

Type Digit = 0..9;// объявление пользовательского типа для длинного числа

Dl_Ch = Array[1..nmax] Of Digit; // длинное число будет содеражаться в массиве

var n,n1,n2: int64;

rez:real; S,st1: String;

R,K,L: Dl_Ch;

cod:integer;

output, input: text;

//процедура обнуления массива

Procedure Zero(Var A: Dl_Ch);

Var I: Integer;

Begin

For I:= 1 To NMax Do A[I]:= 0;

End;

// процедура перевода строки в массив

Procedure Translate(S: String; Var A: Dl_Ch);

Var I: Word;

Begin

Zero(A); I:= Length(S);

While (I >= 1) Do

Begin

If S[I] In ['0'..'9']

Then A[Length(S)- I + 1]:= Ord(S[I]) - 48;

I:= I - 1

End

End;

// функция определения длины чисел

Function Dlina(C: Dl_Ch): Integer;

Var I: Integer;

Begin

I:= NMax;

While (I > 1) And (C[I] = 0) Do I:= I - 1;

Dlina:= I

End;

// процедура умножения двух длинных чисел

Procedure mult(A, B: Dl_Ch; Var C: Dl_Ch);

Var I, J: Integer; P: Digit; Rez: 0..99;

Begin

Zero(C);

For I:= 1 To Dlina(A) Do { Цикл по количеству цифр в первом числе}

Begin

P:= 0; { } Первоначально перенос равен нулю

For J:= 1 To Dlina(B) Do { Цикл по количеству цифр во втором числе}

Begin

Rez:= A[I] * B[J] + P + C[I + J - 1];

C[I + J - 1]:= Rez Mod 10; { Очередное значение цифры в разряде I + J - 1}

P:= Rez Div 10 { Перенос в следующий разряд}

End;

C[I + J]:= P { последний перенос может быть отличен от нуля, запишем его в пока ещё свободный разряд}

End

End;

// процедура вывода в файл длинного числа

Procedure Print(A: Dl_Ch; ss:text);

Var I: Integer;

Begin

For I:= Dlina(A) DownTo 1 Do Write(ss,A[I]: 1);

WriteLn

End;

begin

//îðãàíèçàöèÿ ñâÿçè ñ ôàéëàìè îòêðûòèå ôàéîâ íà çàïèñü è ÷òåíèå

assign (input, 'input.dat');

assign (output, 'output.dat');

reset (input); rewrite (output);

read (input, n);

n1:=n+1;

n2:=2*n+1;

//проверка условия кратности 3

if n*n1 mod 3=0

then begin // происходит преобразование числа в строку

str(((n*n1) div 6),st1);

str(n2,s);

end

else

begin // происходит преобразование числа в строку

str(((n*n1) div 2),st1);

str(n2 div 3,s);

end;

//преобразование к длинному числу

Translate(st1,K);

Translate(s,L);

//усножение чисел

mult (k, l, r);

//вывод в файл

Print(r, output);

close (input); close (output);

end.

Задача 4. Праздник.

Тип: геометрия

Сложность: средняя

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

Входные данные. В первой строке записан диаметр упаковочной коробки, а во второй – количество приготовленных Софией пряников N (1 ≤ N ≤ 100). Каждая из последующих N строк содержит описание одного пряника. Если пряник имеет форму треугольника, то в начале строки записывается число 1, а затем – длины сторон этого треугольника (треугольник невырожденный).

Для прямоугольного пряника в начале строки записано число 2, а затем длины смежных сторон прямоугольника. Числа разделены одним пробелом. Все размеры – целые положительные числа, не превышающие 10¹⁷.

Выходные данные: Выведите строку с N символами. Каждый символ строки соответствует одному прянику (в порядке ввода данных). Символ "Y" означает, что пряник можно поместить в коробку, а символ "N" - что пряник поместить нельзя.

input.dat	output.dat
2 15 17 2 19 5	NY
1 20 12 16 1 10 10 10 1 20 20 20 2 13 15	YYNY

Анализ.

Случай первый – прямоугольник. Пряник можно поместить в коробку, если его диагональ не превышает диаметр коробки. По известным сторонами прямоугольника a и b найти его диагональ можно с помощью теоремы Пифагора: с =

Хорошая формула и простая, но при значениях аргументов превышающих 10⁹ она не предоставляет требуемой точности вычисления. Лучше вычислить диагональ по формуле . С обратных тригонометрических функций язык Паскаль имеет только arctg, поэтому .

Случай второй – треугольник

1. Если треугольник тупоугольный или прямоугольный, то случай, похож на случай с прямоугольником: достаточно чтобы наибольшая сторона была не более диаметра коробки. Итак, сначала определяем наибольшую сторону и сравниваем ее с диаметром коробки.

2. Если треугольник остроугольный, то ищем диаметр описанной окружности. Это лучше сделать по теореме синусов, а угол – с помощью теоремы косинусов:

var n, i, t: integer; d1, d, cosc, x, y, z: extended;