Перейти к содержанию

Решаем сложные и олимпиадные задачи


Рекомендуемые сообщения

muvick, может и не была последней, но в таком случае не сойдутся цифры и запустится следущая итерация, и результат не выдаст положительный. И размер при этом не имеет значения.

Ссылка на комментарий

С вашего позволения)

Коробки

Time limit: 5 секунд

У Пети накопилось много картонных коробок. Они ему еще послужат службу в будущем, но сейчас он хотел бы от них избавиться -- сдать в камеру хранения. В камере хранения за каждое место берут деньги. Помогите Пете уложить коробки друг в друга так, чтобы плата за их хранения была минимальна.

Известно, что никакие две коробки не поместятся ни в какую другую, если их поставить рядом. Коробка со сторонами x1, x2, x3, x1 >= x2 >= x3, помещается в коробку со сторонами y1, y2, y3, y1 >= y2 >= y3, если

x1 < y1, x2 < y2, x3 < y3.

Вход. Вход начинается с числа коробок N <= 500 , затем следует N строчек, содержащих параметры каждой коробки -- длины её трёх сторон -- три натуральных числа меньше 2 000 000.

Выход. Минимальное число коробок, в которые все остальные можно поместить.

ВХОД #1:

2

1 2 3

4 3 2

ВЫХОД #1:

1

ВХОД #2:

2

1 2 3

2 3 3

ВЫХОД #2:

2

ВХОД #3:

4

3 3 3

4 4 4

5 5 5

2 3 4

ВЫХОД #3:

2

Ссылка на источник

Задача интересна всем, оригинальная постановка и способы решения: их 2, один классический долгий, другой быстрый но походящий только к этой постановке.

Итак для зачтения принимаются 2 фразы - постановка, и способ решения. Если нет - тогда прохождение её на соответствующем сервере.

Ссылка на комментарий

Берем коробку - самую большую и выбираем такие коробки которые займут в ней максимальное место при этом, если несколько вариантов равнозначны, брать те где коробок меньше и они больше..

Я думаю.

Но простая сортировка - сильно не вариант.

Ссылка на комментарий

L0K1

Если брать самую большую, в неё ложить следующую меньшую и т.д., то ничего не выйдет/quote]

А разве не одно и тоже?

Жадность не пройдёт в любом виде.

Ссылка на комментарий

0xDEADBEEF

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

Мой вариант был сортировкой с поправкой на несколько коробок.

Тогда в голову приходит только такая метода:

Банда коробок собираются одна в другую:

прогонка по заданному условию + сортировка по площади.

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

Но у меня уже передоз кофе, весьма возможно я не адеквашен..

Ссылка на комментарий

Не, подозревая что этот способ некорректен.

Вобщем подсказка номер раз - в них живут якуты, а главный якут по имени Дилуорт большой мастер по складыванию коробок)

Ссылка на комментарий

чето не могу понять в чем ошибка, WA на седьмом тесте(

uses crt;

var a:array[1..500,1..3]of integer;

b:array[1..500]of boolean;

i,j,k,n:integer;

procedure swap(var x:integer;var y:integer);

var w:integer;

begin

w:=x;

x:=y;

y:=w;

end;

procedure sort(q,p:integer);

var x,l,r:integer;

begin

l:=q;

r:=p;

x:=a[(l+r)div 2,1];

while l<=r do begin

while a[l,1]

while a[r,1]>x do dec®;

if l<=r then begin

swap(a[l,1],a[r,1]);

swap(a[l,2],a[r,2]);

swap(a[l,3],a[r,3]);

dec®;

inc(l);

end;

end;

if l

if r>q then sort(q,r);

end;

begin

readln(n);

for i:=1 to n do b:=true;

for i:=1 to n do begin

readln(a[i,1],a[i,2],a[i,3]);

if a[i,3]>a[i,1] then swap(a[i,1],a[i,3]);

if a[i,2]>a[i,1] then swap(a[i,1],a[i,2]);

if a[i,3]>a[i,2] then swap(a[i,2],a[i,3]);

end;

sort(1,n);

k:=0;

for i:=1 to n do

for j:=i to n do

if (a[i,1]

begin

inc(k);

b[j]:=false;

break;

end;

write(n-k);

end.

Ссылка на комментарий

Пожалуйста, войдите, чтобы комментировать

Вы сможете оставить комментарий после входа в



Войти
  • Последние посетители   0 пользователей онлайн

    • Ни одного зарегистрированного пользователя не просматривает данную страницу
×
×
  • Создать...