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

[X-tender]

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

[muvick]

я согласен с тем что такой алгоритм верный, только у меня он чето на 8 тесте падает

[X-tender]

muvick

покажи код, если ты уже переписал, гляну мб подправлю

[muvick]

я про свой код говорил.

[Lakers]

X-tender

смотри 13-й пост

[X-tender]

Lakers, да я думал он мой алгоритм переписал на плюсы, метод перебора мне не нравится, поэтому даже смотреть не стал

[Lakers]

ну что,кто доделал?

[0xDEADBEEF]

X-tender

Нуну)

Сложна сия задача, не решить нам её...

Ещё раз предлагаю оставить её как гроб и двигатся дальше.

[Lakers]

ну давайте загадывайте следующую тогда=)

[0xDEADBEEF]

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

Коробки

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 фразы - постановка, и способ решения. Если нет - тогда прохождение её на соответствующем сервере.

[toll]

0xDEADBEEF

первая мысль

все коробки в массив и посортировать....

[Lakers]

не,вы не говорите свои мысли,вы пытайтесь ре5шить вначале и сдать на сервере по возможности.

[0xDEADBEEF]

Скажу сразу: жадность - порок, и коробки не исключение.

[Lakers]

типо две в одну не залезут?

[0xDEADBEEF]

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

[Lakers]

а может в одной несколько лежать?

[L0K1]

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

Я думаю.

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

[0xDEADBEEF]

L0K1

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

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

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

[L0K1]

0xDEADBEEF

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

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

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

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

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

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

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

[0xDEADBEEF]

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

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

[Lakers]

чето не могу понять в чем ошибка, 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.

[0xDEADBEEF]

Lakers

Очевидно в неверном алгоритме.

Читай внимателно мои посты, никаких сортировок и жадности здесь нет.

[muvick]

вот примеры где жадность не подходит

4

100 50 40

90 60 10

80 40 5

70 35 35

4

104 90 40

103 80 50

102 60 45

101 70 30

в обоих случаях ответ = 2

[Lakers]

в пкрвом случие 2 а во втором 3?

или я не так щитаю?

[0xDEADBEEF]

Lakers

Во втором случае 3->2; 4->1;