program Calc;
type
PItem = ^TItem;
TItem = record
Item: Integer;
Parent, Left, Right: PItem;
end;
var
Head: PItem;
n: Integer;
Valid: Boolean;
procedure BuildTree(H: PItem);
var
H1: PItem;
First, Last, Order: Integer;
begin
{Если дошли до единицы, значит число правильное}
if H^.Item = 1 then
Valid := True
else begin
{Если число четное, то заводим левую ветку с элементом, уменьшенным вдвое}
if not Odd(H^.Item) then begin
New(H^.Left);
H1 := H^.Left;
with H1^ do begin
Item := H^.Item div 2;
Parent := H;
Left := nil;
Right := nil;
end;
{Рекурсивно строим дерево}
BuildTree(H1);
end;
{Для того, чтобы построить правую ветку с элементом, у которого поменяли}
{первую и последнюю цифру, надо проверить, что цифры уже не меняли, т.е.}
{текущий элемент дерева не является правой веткой своего родителя, и что}
{число больше 9 (чтобы было что менять)}
if ((H^.Parent = nil) or ((H^.Parent <> nil) and (H^.Parent^.Right <> H)))
and (H^.Item > 9) then begin
New(H^.Right);
H1 := H^.Right;
with H1^ do begin
Last := H^.Item mod 10;
First := H^.Item;
Order := 1;
while First > 10 do begin
First := First div 10;
Order := Order * 10;
end;
Item := H^.Item + (Last - First) * Order + (First - Last);
Parent := H;
Left := nil;
Right := nil;
end;
{Рекурсивно строим дерево}
BuildTree(H1);
end;
end;
end;
begin
{Вводим число}
repeat
Write('Введите n:');
ReadLn(n);
until (n >= 1) and (n <= 10000);
{Заводим корень бинарного дерева}
New(Head);
with Head^ do begin
Item := n;
Parent := nil;
Left := nil;
Right := nil;
end;
{Сбрасываем флаг правильности введенного числа}
Valid := False;
{Строим дерево с помощью рекурсивной процедуры, одновременно проверяя число}
{на правильность}
BuildTree(Head);
if Valid then
WriteLn('Yes')
else
WriteLn('No');
end.
Задача из школьной программы
Школьная задача(условие, как оно есть):
Странные времена настали в Лощине Янтарной Росы. Все куда-то бегут, что-то покупают-продают, постоянно норовят обмануть друг друга. Мудрый Настоятель подозревает, что один из поставщиков Монастыря нечист на руку. Известно, что при подсчете стоимости товара он использует Калькулятор. Этот Калькулятор умеет не так уж и много... Всё, что он умеет, это:
1. Ввести число 1;
2. Удвоить текущее число;
3. Поменять в текущем числе первую и последнюю цифры.
Калькулятор умеет работать лишь с целыми числами от 1 до 10000.
Обычно Торговец привозит в Монастырь товар, затем, пользуясь Калькулятором, подсчитывает стоимость товара, называет сумму Настоятелю, и Настоятель оплачивает товар. Настоятель хачет узнать, не обманывает ли его торговец, называя сумму, которая не может быть получена с помощью Калькулятора. Помогите ему в этом.
Ввод. В файле находится единственное число k - сумма, названная Торговцем (1<= k <= 10000).
Вывод. Выведите "YES", если сумма может быть получена с помощью Калькулятора, и "NO" в противном случае.
Пример:
Ввод #1:
8042
Вывод:
YES.
Ввод #2:
3
Вывод:
No.
Как её решать?
Странные времена настали в Лощине Янтарной Росы. Все куда-то бегут, что-то покупают-продают, постоянно норовят обмануть друг друга. Мудрый Настоятель подозревает, что один из поставщиков Монастыря нечист на руку. Известно, что при подсчете стоимости товара он использует Калькулятор. Этот Калькулятор умеет не так уж и много... Всё, что он умеет, это:
1. Ввести число 1;
2. Удвоить текущее число;
3. Поменять в текущем числе первую и последнюю цифры.
Калькулятор умеет работать лишь с целыми числами от 1 до 10000.
Обычно Торговец привозит в Монастырь товар, затем, пользуясь Калькулятором, подсчитывает стоимость товара, называет сумму Настоятелю, и Настоятель оплачивает товар. Настоятель хачет узнать, не обманывает ли его торговец, называя сумму, которая не может быть получена с помощью Калькулятора. Помогите ему в этом.
Ввод. В файле находится единственное число k - сумма, названная Торговцем (1<= k <= 10000).
Вывод. Выведите "YES", если сумма может быть получена с помощью Калькулятора, и "NO" в противном случае.
Пример:
Ввод #1:
8042
Вывод:
YES.
Ввод #2:
3
Вывод:
No.
Как её решать?
Цитата:
Originally posted by ost-andrew
Школьная задача(условие, как оно есть):
Странные времена настали в Лощине Янтарной Росы. Все куда-то бегут, что-то покупают-продают, постоянно норовят обмануть друг друга. Мудрый Настоятель подозревает, что один из поставщиков Монастыря нечист на руку. Известно, что при подсчете стоимости товара он использует Калькулятор. Этот Калькулятор умеет не так уж и много... Всё, что он умеет, это:
1. Ввести число 1;
2. Удвоить текущее число;
3. Поменять в текущем числе первую и последнюю цифры.
Калькулятор умеет работать лишь с целыми числами от 1 до 10000.
Обычно Торговец привозит в Монастырь товар, затем, пользуясь Калькулятором, подсчитывает стоимость товара, называет сумму Настоятелю, и Настоятель оплачивает товар. Настоятель хачет узнать, не обманывает ли его торговец, называя сумму, которая не может быть получена с помощью Калькулятора. Помогите ему в этом.
Ввод. В файле находится единственное число k - сумма, названная Торговцем (1<= k <= 10000).
Вывод. Выведите "YES", если сумма может быть получена с помощью Калькулятора, и "NO" в противном случае.
Пример:
Ввод #1:
8042
Вывод:
YES.
Ввод #2:
3
Вывод:
No.
Как её решать?
Школьная задача(условие, как оно есть):
Странные времена настали в Лощине Янтарной Росы. Все куда-то бегут, что-то покупают-продают, постоянно норовят обмануть друг друга. Мудрый Настоятель подозревает, что один из поставщиков Монастыря нечист на руку. Известно, что при подсчете стоимости товара он использует Калькулятор. Этот Калькулятор умеет не так уж и много... Всё, что он умеет, это:
1. Ввести число 1;
2. Удвоить текущее число;
3. Поменять в текущем числе первую и последнюю цифры.
Калькулятор умеет работать лишь с целыми числами от 1 до 10000.
Обычно Торговец привозит в Монастырь товар, затем, пользуясь Калькулятором, подсчитывает стоимость товара, называет сумму Настоятелю, и Настоятель оплачивает товар. Настоятель хачет узнать, не обманывает ли его торговец, называя сумму, которая не может быть получена с помощью Калькулятора. Помогите ему в этом.
Ввод. В файле находится единственное число k - сумма, названная Торговцем (1<= k <= 10000).
Вывод. Выведите "YES", если сумма может быть получена с помощью Калькулятора, и "NO" в противном случае.
Пример:
Ввод #1:
8042
Вывод:
YES.
Ввод #2:
3
Вывод:
No.
Как её решать?
Прикольная задачка.
Решить ее можно с помощью бинарного дерева, у которого в корне находится само число, в левых ветках уменьшается вдвое, в правых - переставлены цифры. Т.е. идем от числа обратно к единице, применяя обратные операции калькулятора.
Вот примерно так:
Код:
Удачи!
Цитата:
Originally posted by sp999
Прикольная задачка.
Решить ее можно с помощью бинарного дерева, у которого в корне находится само число, в левых ветках уменьшается вдвое, в правых - переставлены цифры. Т.е. идем от числа обратно к единице, применяя обратные операции калькулятора.
Вот примерно так:
Удачи!
Прикольная задачка.
Решить ее можно с помощью бинарного дерева, у которого в корне находится само число, в левых ветках уменьшается вдвое, в правых - переставлены цифры. Т.е. идем от числа обратно к единице, применяя обратные операции калькулятора.
Вот примерно так:
Код:
program Calc;
type
PItem = ^TItem;
TItem = record
Item: Integer;
Parent, Left, Right: PItem;
end;
var
Head: PItem;
n: Integer;
Valid: Boolean;
procedure BuildTree(H: PItem);
var
H1: PItem;
First, Last, Order: Integer;
begin
{Если дошли до единицы, значит число правильное}
if H^.Item = 1 then
Valid := True
else begin
{Если число четное, то заводим левую ветку с элементом, уменьшенным вдвое}
if not Odd(H^.Item) then begin
New(H^.Left);
H1 := H^.Left;
with H1^ do begin
Item := H^.Item div 2;
Parent := H;
Left := nil;
Right := nil;
end;
{Рекурсивно строим дерево}
BuildTree(H1);
end;
{Для того, чтобы построить правую ветку с элементом, у которого поменяли}
{первую и последнюю цифру, надо проверить, что цифры уже не меняли, т.е.}
{текущий элемент дерева не является правой веткой своего родителя, и что}
{число больше 9 (чтобы было что менять)}
if ((H^.Parent = nil) or ((H^.Parent <> nil) and (H^.Parent^.Right <> H)))
and (H^.Item > 9) then begin
New(H^.Right);
H1 := H^.Right;
with H1^ do begin
Last := H^.Item mod 10;
First := H^.Item;
Order := 1;
while First > 10 do begin
First := First div 10;
Order := Order * 10;
end;
Item := H^.Item + (Last - First) * Order + (First - Last);
Parent := H;
Left := nil;
Right := nil;
end;
{Рекурсивно строим дерево}
BuildTree(H1);
end;
end;
end;
begin
{Вводим число}
repeat
Write('Введите n:');
ReadLn(n);
until (n >= 1) and (n <= 10000);
{Заводим корень бинарного дерева}
New(Head);
with Head^ do begin
Item := n;
Parent := nil;
Left := nil;
Right := nil;
end;
{Сбрасываем флаг правильности введенного числа}
Valid := False;
{Строим дерево с помощью рекурсивной процедуры, одновременно проверяя число}
{на правильность}
BuildTree(Head);
if Valid then
WriteLn('Yes')
else
WriteLn('No');
end.
type
PItem = ^TItem;
TItem = record
Item: Integer;
Parent, Left, Right: PItem;
end;
var
Head: PItem;
n: Integer;
Valid: Boolean;
procedure BuildTree(H: PItem);
var
H1: PItem;
First, Last, Order: Integer;
begin
{Если дошли до единицы, значит число правильное}
if H^.Item = 1 then
Valid := True
else begin
{Если число четное, то заводим левую ветку с элементом, уменьшенным вдвое}
if not Odd(H^.Item) then begin
New(H^.Left);
H1 := H^.Left;
with H1^ do begin
Item := H^.Item div 2;
Parent := H;
Left := nil;
Right := nil;
end;
{Рекурсивно строим дерево}
BuildTree(H1);
end;
{Для того, чтобы построить правую ветку с элементом, у которого поменяли}
{первую и последнюю цифру, надо проверить, что цифры уже не меняли, т.е.}
{текущий элемент дерева не является правой веткой своего родителя, и что}
{число больше 9 (чтобы было что менять)}
if ((H^.Parent = nil) or ((H^.Parent <> nil) and (H^.Parent^.Right <> H)))
and (H^.Item > 9) then begin
New(H^.Right);
H1 := H^.Right;
with H1^ do begin
Last := H^.Item mod 10;
First := H^.Item;
Order := 1;
while First > 10 do begin
First := First div 10;
Order := Order * 10;
end;
Item := H^.Item + (Last - First) * Order + (First - Last);
Parent := H;
Left := nil;
Right := nil;
end;
{Рекурсивно строим дерево}
BuildTree(H1);
end;
end;
end;
begin
{Вводим число}
repeat
Write('Введите n:');
ReadLn(n);
until (n >= 1) and (n <= 10000);
{Заводим корень бинарного дерева}
New(Head);
with Head^ do begin
Item := n;
Parent := nil;
Left := nil;
Right := nil;
end;
{Сбрасываем флаг правильности введенного числа}
Valid := False;
{Строим дерево с помощью рекурсивной процедуры, одновременно проверяя число}
{на правильность}
BuildTree(Head);
if Valid then
WriteLn('Yes')
else
WriteLn('No');
end.
Удачи!
Прикольная задача