B. бонусная программа
ограничение времени 1 секунда
ограничение памяти 32mb
ввод bonus.in
вывод bonus.out
магазин бытовой техники использует новую интерактивную бонусную программу. после очередной покупки клиенту приходит сообщение о начислении бонусных , причем сумма бонусов отображается в сообщении звездочками. под каждой звездочкой скрывается цифра. клиенту предлагают зачеркнуть наугад две любые рядом стоящие звездочки - цифры, после чего число октрывается и из него убираются вычеркнутые наугад покупателем две цифры. получившееся количество бонусов зачисляется на счет. например, клиенту пришло сообщение с такой суммой бонусов: . клиент наугад вычеркнул 3-ю и 4-ю звездочки. после чего число открылось: 735491. далее включилась анимация и вычеркнутые цифры исчезли: 7391. на бонусный счет покупателя зачисляется 7391 бонусных . откроем алгоритмический секрет. исходное число, представляемое системой в виде звездочек, действительно выбирается случайным образом из диапазона от 1000 до включительно. но перед тем, как оно отправится покупателю в виде звездочек, число поступает на вход контрольного модуля. этот модуль определяет, какое наибольшее количество бонусов придется начислить клиенту, в случае максимального везения клиента. в зависимости от ответа контрольного модуля система может заново перегенерировать число. ваша написать этот контрольный модуль.
формат ввода
в первой строке входного файла bonus.in приводится сгенерированное системой число в закодированном виде - в виде звездочек. в следующей строке - оно же, но уже в открытом виде.
формат вывода
в выходной файл следует записать максимальное количество бонусов, которое будет зачислено покупателю, если он наиболее удачно зачеркнет два разряда.
пример
ввод вывод
946024
9464
1. 0..65534 -> 32767
2. 0..32766 -> 16383
3. 0..16382 -> 8191
4. 0..8190 -> 4095
5. 0..4094 -> 2047
6. 2048..4094 -> 3071
7. 2048..3070 -> 2559
8. 2560..3070 -> 2815
9. 2816..3070 -> 2943
10. 2944..3070 -> 3007
11. 2944..3006 -> 2975
12. 2976..3006 -> 2991
13. 2992..3006 -> 2999
14. 3000..3006 -> 3003
15. 3000..3002 -> 3001
Если лень перебирать вручную, можно воспользоваться программой
var k,l,r,x,f:integer;
begin
f := 3001;
l := 0;
r := 65534;
x := (l + r) div 2;
k := 1;
while (x <> f) and (l < r) do
begin
writeln(k,' ',l,' ',r,' ',x);
k := k + 1;
if f < x then r := x - 1
else l := x + 1;
x := (l + r) div 2
end;
writeln(k,' ',l,' ',r,' ',x);
end.
Вот Вам еще два на выбор.
1. Без массива
var
s,n:integer;
begin
Write('Введите сумму: '); Read(s);
n:=s div 5000;
if n>0 then begin
Writeln('Банкнот "5000" всего: ',n);
s:=s mod 5000
end;
n:=s div 1000;
if n>0 then begin
Writeln('Банкнот "1000" всего: ',n);
s:=s mod 1000
end;
n:=s div 500;
if n>0 then begin
Writeln('Банкнот "500" всего: ',n);
s:=s mod 500
end;
n:=s div 100;
if n>0 then begin
Writeln('Банкнот "100" всего: ',n);
s:=s mod 100
end;
n:=s div 50;
if n>0 then begin
Writeln('Банкнот "50" всего: ',n);
s:=s mod 50
end;
n:=s div 10;
if n>0 then begin
Writeln('Банкнот "10" всего: ',n);
s:=s mod 10
end;
if s>0 then Writeln('Недоплачено: ',s)
end.
Пример:
Введите сумму: 162504
Банкнот "5000" всего: 32
Банкнот "1000" всего: 2
Банкнот "500" всего: 1
Недоплачено: 4
2. С массивом
const
k:array[1..6] of integer=(5000,1000,500,100,50,10);
var
s,n,i:integer;
begin
Write('Введите сумму: '); Read(s);
for i:=1 to 6 do begin
n:=s div k[i];
if n>0 then begin
Writeln('Банкнот "',k[i],'" всего: ',n);
s:=s mod k[i]
end
end;
if s>0 then Writeln('Недоплачено: ',s)
end.
Пример
Введите сумму: 15470
Банкнот "5000" всего: 3
Банкнот "100" всего: 4
Банкнот "50" всего: 1
Банкнот "10" всего: 2