Задача о ящике

Задача о ящике

Имеется шесть досок определенного размера (ширина и высота). Необходимо определить, можно ли из этих досок собрать ящик. Входной файл box. in содержит шесть строк, каждая описывает размер доски и состоит из двух чисел w и h — ширины и высоты. Выходной файл box. out должен содержать слово POSSIBLE, если возможно из данных шести досок собрать ящик, либо IMPOSSIBLE, если это невозможно. Ограничение по времени выполнения: 2 секунды, по памяти: 64 Mb. 1 ? w, h? 10000.

Примерные тесты: box. in:

1345 2584

2584 683

2584 1345

683 1345

683 1345

2584 683 box. out:

POSSIBLE box. in:

1234 4567

1234 4567

4567 4321

4322 4567

4321 1234

4321 1234 box. out:

IMPOSSIBLE

Ограничения символичные, в реализации не намечается ни работа с большим объемом данных, ни использование времязатратных алгоритмов.

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

Очевидно, что, во-первых, необходимо иметь три пары равных по размеру досок (противоположные друг-другу доски). Во-вторых, смежные ребра досок должны быть одинаковой длины (отмечены цветами на рисунке выше). Нужно проверить выполнение этих двух условий.

Объявляем структуру для хранения размеров доски: struct doska { int w, h;

};

Считываем из входного файла размеры шести досок. На этом же этапе “переворачиваем” при необходимости доски, то есть в w помещаем меньший размер доски. В этом случае проверить выполнение условий будет гораздо легче.

FILE *fin; doska D[6]; int i, temp; fin = fopen("box. in", "r"); for (i = 0; i < 6; i++)

{ fscanf(fin, "%d %d", &(D[i].w), &temp); if (temp < D[i].w)

{

D[i].h = D[i].w;

D[i].w = temp;

} else

{

D[i].h = temp;

}

} fclose(fin);

Возьмем первый примерный тест для пошагового выполнения операций. После считывания и “переворачивания” имеем следующее:

1345 2584

683 2584

1345 2584

683 1345

683 1345

683 2584

Для проверки выполнения первого условия я предлагаю отсортировать массив досок по w и h. В отсортированном массиве одинаковые доски окажутся рядом и реализовать проверку будет просто. Так как у нас всего шесть элементов, сортировать будем самым примитивным методом пузырька: doska tDoska; int i, j; for (i = 0; i < 6; i++) for (j = i+1; j < 6; j++) if (D[i].w > D[j].w || (D[i].w == D[j].w && D[i].h > D[j].h))

{ tDoska = D[i];

D[i] = D[j];

D[j] = tDoska;

}

Получаем:

683 1345

683 1345

683 2584

683 2584

1345 2584

1345 2584

Теперь все стало наглядно. Три пары одинаковых досок идут друг за другом. Проверить этот факт можно условием: if (D[0].w == D[1].w && D[0].h == D[1].h && D[2].w == D[3].w &&

D[2].h == D[3].h && D[4].w == D[5].w && D[4].h == D[5].h...

Осталось проверить смежные ребра. На самом деле, тут все стало не менее просто после сортировки досок. Ящик состоит из ребер трех разных размеров: длина, ширина и высота, по четыре каждого. Рассмотрим три различные доски (первую, третью и пятую):

683 1345

683 2584

1345 2584

Первой в списке находится доска с наименьшим ребром (так как сортировали по возрастанию). Доска с ребром такого же размера должна быть на втором месте, а само ребро находиться в w (опять же, благодаря сортировке). На рисунке эти ребра отмечены синим цветом.

If (D[0].w == D[2].w) ...

Остальные два ребра первой и второй доски должны совпадать с ребрами третьей доски. При чем ребро первой доски (красное) должно совпадать с меньшим ребром третьей доски, а ребро второй (зеленое) — с большим: if (D[0].h == D[4].w && D[2].h == D[4].h) ...

Осталось вывести результат. Полный текст программы:

#include <stdio. h>

#include <stdlib. h> int main()

{

FILE *fin, *fout; struct doska { int w, h;

} D[6], tDoska; int i, j, temp; fin = fopen("box. in", "r"); for (i = 0; i < 6; i++)

{ fscanf(fin, "%d %d", &(D[i].w), &temp); if (temp < D[i].w)

{

D[i].h = D[i].w;

D[i].w = temp;

} else

{

D[i].h = temp;

}

} fclose(fin); for (i = 0; i < 6; i++) for (j = i+1; j < 6; j++) if (D[i].w > D[j].w || (D[i].w == D[j].w && D[i].h > D[j].h))

{ tDoska = D[i];

D[i] = D[j];

D[j] = tDoska;

} fout = fopen("box. out", "w"); if (D[0].w == D[1].w && D[0].h == D[1].h && D[2].w == D[3].w &&

D[2].h == D[3].h && D[4].w == D[5].w && D[4].h == D[5].h &&

D[0].w == D[2].w && D[0].h == D[4].w && D[2].h == D[4].h) fprintf(fout, "POSSIBLE"); else fprintf(fout, "IMPOSSIBLE"); fclose(fout); return 0;

}


Карта сайта


Информационный сайт Webavtocat.ru