Примеры входных и выходных данных

Подарки Деда Мороза асmр.ru

(Время: 1 сек. Память: 16 Мб Сложность: 27%)

Ириска весит X грамм, мандарин – Y грамм, пряник – Z грамм.

Требуется написать программу, которая определит, сколько различных вариантов подарков весом ровно W грамм может сделать Дед Мороз.

Входные данные: В единственной строке входного файла INPUT.TXT содержится четыре целых числа X, Y, Z и W (1 ≤ X, Y, Z ≤ 100, 1 ≤ W ≤ 1000).

Выходные данные: Выходной файл OUTPUT.TXT должен содержать одно целое число – количество вариантов подарков.

Пример

№	INPUT.TXT	OUTPUT.TXT
	10 25 15 40

В этом решении Time limit на 10-м тесте!

Program Podarki_deda_Moroza;

var x,y,z,w,i,j,t,k:integer;

begin

assign(input,'input.txt');

assign(output,'output.txt');

reset(input);

rewrite(output);

readln(x,y,z,w);

k:=0;

for i:=0 to w div x do

for j:=0 to w div y do

for t:=0 to w div z do

if x*i+y*j+z*t=w then inc(k);

write(k);

close(input);

close(output);

end.

А это решение Accepted!

Program Podarki_deda_Moroza;

var x,y,z,w,i,j,t,k:integer;

begin

assign(input,'input.txt');

assign(output,'output.txt');

reset(input);

rewrite(output);

readln(x,y,z,w);

k:=0;

for i:=0 to w div x do

for j:=0 to (w-x*i) div y do

for t:=0 to (w-x*i-y*j) div z do

if x*i+y*j+z*t=w then inc(k);

write(k);

close(input);

close(output);

end.

Идеальный вариант

Program Podarki_deda_Moroza;

var x,y,z,w,i,j,t,k:integer;

begin

readln(x,y,z,w);

k:=0;

for i:=0 to w div x do

for j:=0 to (w-x*i) div y do

if (w-x*i-y*j) mod z=0 then

inc(k);

write(k);

end.

Монетки

Имя входного файла:	g.in
Имя выходного файла:	g.out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта

В Волшебной стране используются монетки достоинством A₁, A₂,…, A_M. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Формат входных данных

Во входном файле записано сначала число N (1£N£10⁹), затем — число M (1£M£15) и далее M попарно различных чисел A₁, A₂,…, A_M (1£A_i£10⁹).

Формат выходных данных

В выходной файл выведите сначала K — количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число –1 (минус один).

Примеры

g.in	g.out
5 2 1 2	2 2 1
7 2 1 2	-1
5 2 3 4

Это решение Accepted!

var s:int64;

n,i,j,k,m,min:longint;

b:array[1..15] of longint;

a,c:array[0..15] of byte;

flag:byte;

begin

assign (input,'input.txt');

reset (input);

assign (output,'output.txt');

rewrite (output);

Читаем входные данные Читаем номиналы монет Считаем сумму денег, если все монеты брать по две

readln(n,m);

s:=0;

for i:=1 to m do

begin

read(b[i]);

s:=s+2*b[i];

end;

if s<n then

begin

Ставим заглушку: если максимально возможного количества денег не хватило, чтобы заплатить указанную сумму

write(-1);

close (input);

close (output);

halt;

end;

	А эта заглушка для случая, когда максимальное возможное количество денег (когда все монеты брали по две) равно требуемой сумме

if s=n then

begin

writeln(2*m);

for i:=1 to m do

write(b[i],' ',b[i],' ');

close (input);

close (output);

halt;

end;

for i:=0 to m do a[i]:=0;

flag:=0;

min:=maxlongint;

	Запускаем троичный перебор Идем по троичному числу Считаем количество монет – это цифры троичного числа и сумму денег

while a[0]=0 do

begin

s:=0; k:=0;

for j:=1 to m do

begin

k:=k+a[j];

s:=s+a[j]*b[j];

Флаговая переменная станет равна 1 – если вариант выдачи денег найден

end;

if s=n then flag:=1;

	Если вариант выдачи денег найден и при этом количество монет меньше чем было раньше, то…

if (s=n) and (k<min) then

То перезапоминаем новое минимальное количество и записываем троичное число в резервный массив С

begin

min:=k;

for j:=1 to m do c[j]:=a[j];

end;

i:=m;

while a[i]=2 do

begin

Это переход к следующему троичному числу

a[i]:=0;

dec(i);

end;

inc(a[i]);

end;

if flag=0 then

begin

Эта заглушка для случая, если варианта выдачи денег не нашлось

write(0);

close (input);

close (output);

halt;

end;

	Это вывод количества монет в лучшем случае

writeln(min);

	А это вывод номиналов монет нужное количество раз, здесь цифра в троичном числе С[j] – это и есть количество монет

for j:=1 to m do

begin

if c[j]=1 then write (b[j],' ');

if c[j]=2 then write (b[j],' ',b[j],' ');

end;

close (input);

close (output);

end.

Имя входного файла: lantern.in

Имя выходного файла: lantern.out

Ограничения по времени: 1 секунда

Ограничения по памяти: 256 Мбайт

Фонари у дороги

Прямой отрезок дороги из Нью-Васюков в Старую Москву длины M снискал дурную славу из-за большого количества аварий на нём, особенно в ночное время. Дорожный департамент в конце концов решил установить фонари и осветить весь этот отрезок. И тут чиновники обратили внимание, что отдельные участки дороги уже освещаются N фонарями, стоящими у заправочных станций, придорожных кафе и т.д., так что выделенные деньги можно сэкономить… В частности, фонарь с номером i (1 ≤ i ≤ N) освещает участок дороги [ai, bi], где 0 ≤ ai < bi ≤ M.

Участок дороги считается безопасным, если он освещен хотя бы одним фонарём.

По информации о расположении освещённых участков дороги определите суммарную длину безопасных участков дороги и количество неосвещённых участков.

Формат входных данных.

Первая строка содержит два целых числа: M – длину дороги, и N – количество фонарей (1 ≤ M ≤ 10⁶, 1 ≤ N ≤ 10⁵). Каждая из последующих N строк задаёт информацию об одном фонаре и содержит два целых числа ai и bi.

Формат выходных данных.

Выведите два числа, разделённые пробелом – суммарную длину безопасных участков дороги и количество неосвещённых участков.

Примеры входных и выходных данных

lantern.in	lantern.out
8 2 1 5 4 8	7 1
8 2 0 6 6 8	8 0

program fonari;

var al,ap:array[1..100000] of longint;

i,j,li,l,p,n,m,k:longint;

procedure quicksort(m,t:longint);

var i,j,w,w1,x:longint;

begin

i:=m; j:=t; x:=al[(m+t) div 2];

repeat

while al[i]<x do inc(i);

while al[j]>x do dec(j);

if i<=j then

begin

w:=al[i]; al[i]:=al[j]; al[j]:=w;

w1:=ap[i]; ap[i]:=ap[j]; ap[j]:=w1;

inc(i); dec(j);

end;

until i>j;

if m<j then quicksort(m,j);

if i<t then quicksort(i,t);

end;

begin

assign(input,'lantern.in');

assign(output,'lantern.out');

reset(input);

rewrite(output);

{ввод исходных данных задачи}

readln(m,n);

for i:=1 to n do

readln(al[i],ap[i]);

{сортируем массивы al и ap}

quicksort(1,n);

{решение задачи}

l:=al[1]; p:=ap[1]; li:=ap[1]-al[1];

if al[1]<>0 then k:=1

else k:=0;

for i:=2 to n do

begin

if ((al[i]>=l)and(al[i]<=p)) and (ap[i]>p)

then

begin

li:=li+(ap[i]-p);

p:=ap[i];

end;

if al[i]>p

then

begin

li:=li+(ap[i]-al[i]);

l:=al[i];

p:=ap[i];

inc(k);

end;

end;

if ap[n]<>m

then inc(k);

{выводим ответ}

write(li,' ',k);

close(input);

close(output);

end.