2017-11-30
2401
Имя входного файла: Input.txt.
Имя выходного файла: Output.txt.
Максимальное время работы на одном тесте: 5 секунд.
Максимальный объем использованной памяти: 4 Мбайты.
За билетами на премьеру нового мюзикла собралась очередь из N лиц, каждое из которых хочет купить 1 билет. На всю очередь работала только одна касса, потому продажа билетов продвигалась очень медленно, от чего «клиенты» очереди впадали в отчаяние. Самые сообразительные быстро приметили, что, как правило, несколько билетов в одни руки кассир продает быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким людям, которые стоят рядом, отдавать деньги первому из них, чтобы он купил билеты на всех.
Но для борьбы со спекулянтами кассир продавала не больше 3-х билетов в одни руки, потому договориться таким образом между собой могли лишь 2 или 3 лица, которые стоят рядом.
Известно, что на продажу і лицу из очереди одного билета кассир тратит Аі секунд, на продажу двух билетов – Ві секунд, трёх билетов – Сi секунд.
|
|
|
Задание. Напишите программу, которая определит минимальное время, за которое можно было бы обслужить всех покупателей.
Обратите внимание, что билеты на группу людей, которые объединились, всегда покупает первый из них. Также никто с целью ускорения не покупает лишние билеты (то есть билеты, которые никому не нужные).
Входные данные. Первая строка входного файла содержит единственное число N – количество покупателей в очереди (1£ N £5000). В каждой из следующих N строк записана тройка натуральных чисел Аі, Bi, Сi. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы
Выходные данные. Исходный файл содержит одно число – минимальное время в секундах, за которое можно было бы обслужить всех покупателей.
Пример входных и выходных данных
| Input.txt | Output.txt |
| 5 10 15 | |
| 2 10 15 | |
| 5 5 5 | |
| 20 20 1 | |
| 20 1 1 | |
| 3 4 5 | |
| 1 1 1 |
Решение
program buying_tickets;
const size=5000;
var
a, b, c: array [1..size] of integer;
time: array [1..size of longint;
n:integer;
procedure read_data; {процедура считающая количество людей в очереди}
var i:integer;
begin
assign(input, 'input.txt');
reset(input);
readln(n);
for i:=1 to n do readln(a[i], b[i], c[i]);
close(input);
end;
function min(x,y:longint:longint);
begin
if x<y then min:=x else min:=y;
end;
procedure solv; {процедура подсчитывает время продажи билетов}
var i:integer;
begin
time[1]:=a[1];
time[2]:=min(a[1]+a[2], b[1]);
time[3]:=min(time[2]+a[3], min(a[1]+b[2], c[1]));
for i:=4 to n do
time[i]:=min(time[i-1]+a[i], min(time[i-2]+b[i-1],
time[i-3]+c[i-2]));
end;
procedure write_data; {запись результатов в файл}
begin
assign(output, 'output.txt');
rewrite(output);
writeln(time(n));
close(output);
end;
begin
read_data;
solve;
write_data;
end.
Оглавление
Работа с большими числами. 2
Сортировка и поиск. 5
|
|
|
Метод перебора вариантов, отсечения перебора. 8
Элементы вычислительной геометрии. 11
Эффективные структуры данных. 14
Работа с большими числами
Золото племени АББА
(Время: 1 сек. Память: 16 Мб Сложность: 40%)
Главный вождь племени Абба не умеет считать. В обмен на одну из его земель вождь другого племени предложил ему выбрать одну из трех куч с золотыми монетами. Но вождю племени Абба хочется получить наибольшее количество золотых монет. Помогите вождю сделать правильный выбор!
Входные данные
В единственной строке входного файла INPUT.TXT записаны три натуральных числа через пробел. Каждое из чисел не превышает 10100. Выходные данные
В выходной файл OUTPUT.TXT нужно вывести одно целое число – максимальное количество монет, которые может взять вождь.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
| 5 7 3 987531 234 86364 189285 283 4958439238923098349024 |
РЕШЕНИЕ:
Для решения данной задачи необходимо знать темы:
— работа со строками
— обработка одномерных массивов
— длинная арифметика
Из условия задачи видно, что числовые данные 10100 выходят за все возможные стандартные типы в 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.
