Задача Монетки

@Venus · Регистрация: 21.12.2012

Author24 — интернет-сервис помощи студентам

Монетки
В волшебной стране используются монетки достоинством А1, А2, …, Ам. Волшебный человек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.
Формат входных данных.
Во входном файле записано сначала число N (1 ≤ N ≤ 109), затем – число М (1 ≤ М ≤ 15) и далее М попарно различных чисел А1, А2, …, Ам (1 ≤ Аi ≤ 109).
Формат выходных данных.
В выходной файл выведите сначала К – количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите К чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человечек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них. Если без сдачи не обойтись, то выведите одно число 0. если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1(минус один).
Примеры:
B.in B.out
5 2 3
1 2 2 2 1
-----------
7 2 -1
1 2
-----------
5 2 0
3 4

Добавлено через 21 час 35 минут

Pascal

var input,output:text; n,i,j,g,nm,ans,t:integer;ara:array[0..1000] of integer;ar,arq:array[0..1000] of integer; ts,sum,a:integer;
begin
assign(input,'input.txt');reset(input);
 assign(output,'output.txt');rewrite(output);
readln(input,a,n);
ans:=10000;
 
for i:=1 to n do begin
read(input,ar[i]);ts:=ts+2*ar[i];end;
 
  if ts<a then writeln(output,'-1') else
 
  begin
 
     ara[1]:=3;for i:=2 to 15 do begin ara[i]:=3*ara[i-1];end;
 
 for i:=1 to ara[n] do begin if arq[n]<2 then begin
  inc(arq[n]);sum:=sum+ar[n];inc(nm);
  end
 else
  begin
   g:=n;while arq[g]>1 do begin sum:=sum-ar[g]*arq[g];dec(nm,arq[g]);arq[g]:=0;dec(g);end;
 
 inc(arq[g]);sum:=sum+ar[g];inc(nm);end;
if sum=a then begin if nm<ans then ans:=nm;end;end;
 
 if ans>1000 then writeln(output,'0') else writeln(output,ans);   end;
 
close(output);close(input);
end.

вот код программы но здесь выходит ошибка

Pascal

1	ara[i]:=3*ara[i-1];

что арифметическое переполнение, пожалуйста исправьте ошибки, и если исправили попробуйте просмотреть пример в условии.

24.12.2012, 19:46

Сообщение от Venus

вот код программы но здесь выходит ошибка что арифметическое переполнение, пожалуйста исправьте ошибки, и если исправили попробуйте просмотреть пример в условии.

Здесь:

Pascal

1	ara[1]:=3;for i:=2 to 15 do begin ara[i]:=3*ara[i-1];end;

Тип integer допускает максимальное значение -32768..32767, а у тебя получится число 3¹⁵, это больше миллиона, поэтому ошибка.

@Venus · 24.12.2012, 19:57 **[ТС]**

Сообщение от Smash Mouth

Здесь:

Pascal

1	ara[1]:=3;for i:=2 to 15 do begin ara[i]:=3*ara[i-1];end;

Тип integer допускает максимальное значение -32768..32767, а у тебя получится число 3¹⁵, это больше миллиона, поэтому ошибка.

Сделал, теперь работает, но надо еще вывести какие цифры нужны. Ну, например в первом примере
введено:
5 2
1 2
а должен выйти результат:
3
2 2 1
а у меня выходит просто 3, помогите еще добавить в выводу числа(монеты) которые нужно заплатить

24.12.2012, 20:10

Я в твоем коде ничего не понял, напиши хотя бы какая переменная зачем нужна, а то сумбур какой-то.

Smash Mouth
	24.12.2012, 20:10	4
	Я в твоем коде ничего не понял, напиши хотя бы какая переменная зачем нужна, а то сумбур какой-то.