Работа с большими числами

1. Золото племени абба

(Время: 1 сек. Память: 16 Мб Сложность: 40%)

Главный вождь племени Абба не умеет считать. В обмен на одну из его земель вождь другого племени предложил ему выбрать одну из трех куч с золотыми монетами. Но вождю племени Абба хочется получить наибольшее количество золотых монет. Помогите вождю сделать правильный выбор!

Входные данные

В единственной строке входного файла INPUT.TXT записаны три натуральных числа через пробел. Каждое из чисел не превышает 10¹⁰⁰. Выходные данные

В выходной файл OUTPUT.TXT нужно вывести одно целое число – максимальное количество монет, которые может взять вождь.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1 2 3	5 7 3 987531 234 86364 189285 283 4958439238923098349024	7 987531 4958439238923098349024

РЕШЕНИЕ:

Для решения данной задачи необходимо знать темы:

— работа со строками

— обработка одномерных массивов

— длинная арифметика

Из условия задачи видно, что числовые данные 10¹⁰⁰ выходят за все возможные стандартные типы в Free Pascal. Поэтому для решения задачи будем использовать длинную арифметику. Если внимательно посмотреть, можем заметить, что нам необходимо будет найти наибольшее число среди трех куч с золотыми монетами.

Формат входных данных. Числа представлены в одну строку, поэтому для начала нам необходимо будет их преобразовать к нашему удобному виду.

readln(f,s); ReadLong(A,copy(s,1,pos(‘ ‘,s)-1)); delete(s,1,pos(‘ ‘,s)); ReadLong(B,copy(s,1,pos(‘ ‘,s)-1));

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

k:=high(d); while (k>1)and(d[k]=0) do dec(k); write(f1,d[k]);

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

for i:=k-1 downto 1 do begin str(d[i],s); for j:=length(s)+1 to len do s:=’0’+s; write(f1,s); end;

Полный текст программы выглядит так:

const base=10000;len=4; type TLong=array [1..26] of LongInt; var a,b:TLong; f,f1:Text; k:Integer; s:string; {Процедура считывания числа} procedure ReadLong(var d:TLong;s:string); var k,error,i:Integer; begin for i:=1 to high(d) do d[i]:=0; for i:=(length(s) mod len)+1 to len do s:=’0’+s; k:=0; while len*k< length(s) do begin inc(k); val(copy(s,length(s)-len*k+1,len),d[k],error); // delete(s,length(s)-len+1,len); end; end;

{Процедура сравнения длинных чисел} function Compare(number1,number2:Tlong):Integer; var i:Integer; begin i:=high(number1); while (i>1)and(number1[i]=number2[i]) do dec(i); if number1[i]>number2[i] then Compare:=1 else if number1[i]=number2[i] then Compare:=0 else Compare:=-1; end;

{Процедура вывода на экран длинного числа} procedure WriteLong(d:TLong); var i,k,j:Integer; s:string; begin k:=high(d); while (k>1)and(d[k]=0) do dec(k); write(f1,d[k]); for i:=k-1 downto 1 do begin str(d[i],s); for j:=length(s)+1 to len do s:=’0’+s; write(f1,s); end; writeln(f1); end;

begin assign(f,’input.txt’); reset(f); assign(f1,’output.txt’); rewrite(f1); readln(f,s); ReadLong(A,copy(s,1,pos(‘ ‘,s)-1)); delete(s,1,pos(‘ ‘,s)); ReadLong(B,copy(s,1,pos(‘ ‘,s)-1)); delete(s,1,pos(‘ ‘,s)); if Compare(A,B)=-1 then A:=B; ReadLong(B,s); if Compare(A,B)>-1 then WriteLong(A) else WriteLong(B); close(f1); close(f); end.

Упрощенная (время 0,122, память 1164 Кб)

var s,t,p:string;

f:text;

i:integer;

begin

assign(f,'input.txt');

s:='';

reset(f);

read(f,t);

t:=t+' ';

for i:=1 to 3 do

begin p:=copy(t,1,pos(' ',t));

delete(t,1,length(p));

if length(p)>length(s) then s:=p;

if (length(p)=length(s))and(p>=s) then s:=p end;

close(f);

assign(f,'output.txt');

rewrite(f);

write(f,s);

close(f)

end.