Имя выходного файла output.Txt
В файл OUTPUT.TXT вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.
Примечание:Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.
Пример
| input.txt | output.txt |
| 7 10 | 3 3 2 2 5 2 3 |
| 5 1 | |
| 3 2 | |
| 7 1 | |
| 5 2 | |
| 7 4 6 5 6 4 7 5 2 1 5 3 |
Решение
Program Svetofor;
var n, i, j, k : longint;
a : array [1..100] of integer;
b : array [1..5000, 1..2] of integer;
num : char;
t : integer;
f : text;
procedure swap (var a, b : integer); {замена}
var t : integer;
begin
t := a;
a := b;
b := t;
end;
begin
for num := '1' to '9' do begin
randomize; {случайным образом формируем матрицу}
writeln('Test #', num, ', n = ');
readln(n);
fillchar(a, sizeof(a), 0);
k := 0;
for i := 1 to n do
for j := 1 to i - 1 do
if random(MaxInt) >MaxInt div 2 then begin
inc(a[i]);
inc(a[j]);
inc(k);
b[k, 1] := i;
b[k, 2] := j;
end;
for i := 1 to k do begin
j := random(k)+1;
t := random(k)+1;
swap(b[t, 1], b[j, 1]);
swap(b[t, 2], b[j, 2]);
end;
assign(f, 'y_' + num + 'input.txt');
rewrite(f);
writeln(f, n, ' ', k);
for i := 1 to k do
writeln(f, b[i, 1], ' ', b[i, 2]);
close(f);
assign(f, 'y_' + num + 'output.txt');
rewrite(f);
for i := 1 to n do
write(f, a[i], ' ');
writeln(f);
close(f);
end;
end.
Тема: Метод перебора вариантов.
Задача 3: Зернышки
Имя входного файла: Input.txt.
Имя выходного файла: Output.txt.
В банке находятся белые и черные зернышки. Каждый раз из банки вынимают наугад два зернышка. Если они одинакового цвета, то их выбрасывают, а в банку кладут черное зернышко (черных зернышек достаточное количество). Если же зернышки разного цвета, то черное зернышко выбрасывают, а белое возвращают в банку. Эти действия повторяют, пока не останется одно зернышко.
Задание.Напишите программу, которая по известному количеству черных и белых зернышек определяет цвет последнего зернышка.
Входные данные.В единственной строке записаны два числа – количество белых и черных зернышек.
Выходные данные. Единственная строка выходного текстового файла должна содержать цвет оставшегося зернышка: white – если зернышко белое, black – если зернышко черное.
Пример входных и выходных данных:
| Input.txt | Output.txt |
| 4 3 | black |
program grain;
var white, black:longint;
begin
assign(input, 'input.txt');
reset(input);
assign(output, 'output.txt');
rewrite(output);
read(white, black);
if odd(white) then writeln('white') else {проверка чётности числа}
writeln('black');
close(input);
close(output);
end.
Тема: Работа с большими числами.
Задача 4: Простые гири
Существуют гири массой 1 г, 2г, …, N г (N ≤ 500000). Напишите программу, которая распределяет эти гири на максимально возможное количество пар, так чтобы общий вес гирь в каждой паре выражался простым числом.
Формат входящих данных: входной файл Input.txt содержит одно число N.
Формат выходящих данных: в выходной файл Output.txt выведите список найденных пар, по одной паре в ряду.
Решение
Program Prost_g;
var N:LongInt;
Procedure Read_data; {Процедура чтения начальных данных }
begin
assign(Input, 'Input.txt');
reset(Input);
readln(N);
close(Input)
end;
Function Prost(x:LongInt): Boolean; {Функция определения, является ли число простым}
var
q:Boolean;
i:LongInt;
begin
q:=False;
if Odd(x) then
begin
q:=True;
i:=3;
while (i*i<=x) and q do
if x mod i=0 then q:=False
else inc(i,2)
end;
Prost :=q
end; {End Prost}
Procedure Solve_Write; {Процедура поиска и записи «простых» пap}
var
flag:Boolean;
i, j : LongInt;
begin
assign(Output, 'Output.txt');
rewrite(Output);
repeat
i:=l;
while not Prost(n+i) do inc(i);
j:=i-l;
while i<n do
begin
writeln(i, ‘ ‘ ,n);
inc(i);
dec(n)
end;
n:=j
until n<=l;
close(Output)
end; {End Solve_Write}
BEGIN
Read_Data;
Solve_Write;
END.
Тема: Метод перебора вариантов.
Задача 5: Покупка билетов
Имя входного файла: 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.
Упрощенная (время 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.
Сортировка и поиск
2. Домашнее задание.
Петя успевает по математике лучше всех в классе, поэтому учитель задал ему сложное домашнее задание, в котором нужно в заданном наборе целых чисел найти сумму всех положительных элементов, затем найти где в заданной последовательности находятся максимальный и минимальный элемент и вычислить произведение чисел, расположенных между ними. Так же известно, что минимальный и максимальный элемент встречаются в заданном множестве чисел только один раз. Поскольку задач такого рода учитель дал Пете около ста, то Петя как сильный программист смог написать программу, которая по заданному набору чисел самостоятельно находит решение. А Вам слабо?
Входные данные
В первой строке входного файла INPUT.TXT записано единственное число N – количество элементов массива. Вторая строка содержит N целых чисел, представляющих заданный массив. Все элементы массива разделены пробелом. Каждое из чисел во входном файле не превышает 102 по абсолютной величине.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести два числа, разделенных пробелом: сумму положительных элементов и произведение чисел, расположенных между минимальным и максимальным элементами. Значения суммы и произведения не превышают по модулю 3*104.
Примеры:
| № | INPUT.TXT | OUTPUT.TXT |
| 6 -3 5 7 9 0 5 | 26 35 | |
| 8 1 2 3 4 5 6 7 8 | 36 5040 | |
| 5 8 7 5 -3 2 | 22 35 |
РЕШЕНИЕ
Данная задача решается с помощью классических алгоритмов обработки данных в массиве. Во первых, стоит вычислить сумму всех положительных элементов, которые находятся в массиве. Для этого пройдемся по всем значениям и к значениям суммы будем прибавлять только те элементы, которые больше «0» (то есть, положительные).
Sum:=0;
for i:=1 to n do
if a[i]>0 then Sum:=Sum+a[i];
Далее, согласно условия, нам необходимо найти индексы наибольшего и наименьшего значения элементов в массиве. Введем две переменные minId, MaxId, которые соответственно содержат значения номеров маленького и самого элементов линейной таблицы. Если среди просмотренных элементов мы найдем большее значение, чем то значение, которое мы считали начальным - мы изменим номер индекса максимального элемента
if a[i]>a[MaxId] then MaxId:=i;
Аналогично с минимальным:
if a[i]<a[MinId] then MinId:=i;
Зная позицию нахождения наибольшего и наименьшего элементов, мы можем найти произведение чисел, расположенных между ними:Mult:=1;
for i:=MinId+1 to MaxId-1 do
Mult:=Mult*a[i];
begin
x:=MaxId;
MaxId:=MinId;
MinId:=x;
end;
Полный текст программы «Домашнее задание»:
var f,f1:text;
n,i,minId,MaxId,x,Sum,Mult:Integer;
a:array[1..100] of Integer;
begin
assign(f,’input.txt’);
reset(f);
assign(f1,’output.txt’);
rewrite(f1);
{Считывание данных}
readln(f,n);
for i:=1 to n do
read(f,a[i]);
Sum:=0;
for i:=1 to n do
if a[i]>0 then Sum:=Sum+a[i];
minId:=1;
{ Считаем, что минимальный элемент находится на первой позиции}MaxId:=1;
{ Считаем, что максимальный элемент находится на первой позиции}for i:=2 to n do
begin
if a[i]>a[MaxId] then MaxId:=i;
if a[i]<a[MinId] then MinId:=i;
{Если мы нашли меньше элемент чем считали минимальным, меняем индекс минимального}
end;
{Изменение индексов расположения крупнейшего элемента и наименьшего}
if MaxId<MinId then
begin
x:=MaxId;
MaxId:=MinId;
MinId:=x;
end;
{Нахождение произведения между минимальным и максимальным значением элементов массива}
Mult:=1;
for i:=MinId+1 to MaxId-1 do
Mult:=Mult*a[i];
{Вывод результата}
writeln(f1,Sum,’ ‘,Mult);
close(f);
close(f1);
end.
Метод перебора вариантов, отсечения перебора
3. Сумма двух чисел
Заданы три числа: a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось c.
Формат входных данных
Входной файл содержит три целых числа: a, b, c (0 < a, b, c < 109). Числа разделены пробелом.
Формат выходных данных
Если искомая перестановка цифр возможна, необходимо вывести в выходной файл слово YES, в противном случае — выведите слово NO. При положительном ответе необходимо вывести во второй строке выходного файла число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y не должны содержать ведущих нулей. Числа в строке разделены пробелом.
Примеры входных и выходных файлов
| Input2.txt | output2.txt |
| 12 31 25 | YES 12 13 |
| 12 31 26 | NO |