Question

Сегодня Али в местном магазине сделал покупку за C тенге. Он только хотел расплатится и услышал от продавца фразу "Без сдачи пожалуйста, молодой человек". У него есть всего N монет достоинств a1, a2, ..., aN тенге. Определите, сможет ли он расплатится без сдачи.

Answer 1

.............................

Answer 2

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;beginassign(input,'f.in');reset(input); assign(output,'f.out');rewrite(output);readln(input,a,n);ans:=10000;
for i:=1 to n do beginread(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.

Answer 3

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

Обозначим сумму его покупки за C тенге. Теперь давайте представим, что у нас есть N различных монет с достоинствами a1, a2, ..., aN тенге.

Если сумма покупки C равна какой-то комбинации этих монет, то Али сможет расплатиться без сдачи. Другими словами, мы ищем такие целые неотрицательные числа x1, x2, ..., xN, что:

\[ x1 * a1 + x2 * a2 + ... + xN * aN = C \]

Если такое сочетание существует, то Али может расплатиться без сдачи.

Например, если у Али есть монеты достоинством 5 тенге и 10 тенге, и его покупка составляет 35 тенге, то у нас есть несколько возможных комбинаций:

- 7 монет по 5 тенге, - 3 монеты по 10 тенге и 1 монета по 5 тенге, - и т.д.

Таким образом, чтобы ответить на ваш вопрос, нужно знать сумму покупки C и значения монет a1, a2, ..., aN, чтобы проверить, можно ли найти сочетание монет для расчета суммы C.