И снова всем привет! После вводной статьи самое время рассмотреть какую-нибудь задачку. Для первого раза возьмем простенькую, чтобы, так сказать, войти в курс дела.

Итак, задача о ящике. Условие задачи взято из системы Cats сайта ДВГУ. Оно на английском языке, я кратко опишу суть. Имеется шесть досок определенного размера (ширина и высота). Необходимо определить, можно ли из этих досок собрать ящик. Входной файл 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;
}

Пробуем отослать решение:

Затем переходим в раздел “консоль” и видим следующее:

“Solution accepted” означает, что программа успешно прошла все тесты автоматической системы проверки, то есть, задача решена. Зарегистрируйтесь в системе для получения более развернутых сообщений в консоли. До встречи!