Олимпиадные задачи по программированию. Ч. 2. Лучшие решения. Ускова О.Ф - 31 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

достоинством в a1,a2,:,ak единиц, имеющимися в неограниченном
количестве. Числа N,a1,:,ak целые.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени: 5 секунд
Формат входных данных:
В первой строке входного файла содержатся числа N и K. Далее в
каждой строке файла содержатся достоинства имеющихся купюр.
Формат выходных данных:
Первая строка выходного файла должна содержать YES, если можно
представить и NO, если нельзя представить.
Пример входного и выходного файла:
INPUT.TXT
13 3
3
7
11
OUTPUT.TXT
NO
Алгоритм решения
Алгоритм простой - перебор всех возможных комбинаций из данных
купюр.
Program Plz3;
{Автор Колбешкин Д.М.}
Var fin,fout :text;
i,N,K :integer;
a :array[1..100]of integer;
bool :boolean;
Procedure NextS(Sum,t:integer); {Sum - сумма денег, которую мы
собрали}
var j,i:integer; {t - номер купюры}
begin
if sum=N then
begin
bool:=true {Мы набрали нужную сумму денег}
end else begin
if sum < N then
begin
for j:=t to K do {Выбираем купюку}
if (a[j]>0) then
begin
i:=1; {i - кол-во купюр, которые мы
добавляем}
while (sum+a[j]*i <= N) and (not bool) do
begin
NextS(sum+a[j]*i,j+1);
i:=i+1;
end;
end;
end;
end;
end;

Страницы