hw1.org

Домашнее задание №1

1 Задача (1-3)

Вам дано несколько кубиков, каждый задается длинами трех сторон, a, b и c. Считается, что один кубик можно вложить в другой, если их можно так расположить в пространстве, чтобы каждая грань одного кубика была параллельна какой-то грани другого кубика и чтобы при этом один из кубиков полностью содержался внутри другого. Общих точек на границе у них при этом также не должно быть. Нужно определить, какую максимальную цепочку кубиков $C₁, C₂,\ldots{}, C_k$ можно выбрать из данных таким образом, чтобы $C₁$ можно было вложить в $C₂$, $C₂$ — в $C₃$ и так далее.

В первой строке входного потока дано число $n (1 \leq n \leq 1000)$. В следующих $n$ строках описаны кубики, на каждой по три целых положительных числа, не превосходящих $10⁹$, описывающих один кубик. В каждой строке числа выписаны по возрастанию, и первое число следующей строки всегда не меньше первого числа предыдущей. В выходной поток нужно вывести одно число: длину максимальной цепочки вложенных кубиков.

Пример входа	Пример выхода
4	3
1 1 1
2 2 2
3 3 3
3 3 4

\newpage

2 Словесное описание алгоритма

По условию задачи сказано, что кубики должны входить друг в друга, а также, что не должно быть общих точек на границе. Из этого следует, что каждый следующий кубик должен быть строго больше предыдущего по всем измерениям. Алгоритм будет выглядеть так:

3 Доказательство того, что он всегда завершается и корректно работает

• Изначально мы имеем 1 кубик, который не нарушает условий, поэтому и накопленный результат равен 1;
• Проводим проверку для k-го кубика и
  • если удачно, то увеличиваем накопленный результат на еденицу,
  • если неудачно, то возвращаем количество уже накопленных;
• Проводим проверку для k+1-го кубика…
• Если все n кубиков прошли проверку удачно, то возвращаем количество накопленных кубиков.

4 Асимптотическая оценка времени работы алгоритма

Время работы алгоритма в худшем случае, когда все n кубиков проходят провреку будет равно $O(n)$.

5 Асимптотическая оценка памяти, потребляемой алгоритмом

Для выполнения данного алгоритма нам необходимо хранить только значения измерений предыдущего и текущего кубиков, поэтому потребляемая память будет равна $O(1)$. \newpage

6 Реализация алгоритма на языке C

#include <stdio.h>
#include <stdlib.h>

size_t checker(size_t);

int main(void) {
  size_t n;
  size_t result;
  scanf("%zu", &n);

  result = checker(n);
  printf("%zu\n", result);

  return 0;
}

size_t checker(size_t n) {
  size_t result = 1;
  const size_t DIM = 3;
  size_t prev[DIM];
  size_t cur[DIM];
  size_t badcube_flag = 0;

  if (scanf("%zu %zu %zu", prev, prev+1, prev+2) == EOF) {
    exit(1);
  }

  for (size_t I = 1; I < n; I++) {
    if (scanf("%zu %zu %zu", cur, cur+1, cur+2) == EOF) {
      exit(1);
    }
    for (size_t I_dim = 0; I_dim < 3; I_dim++) {
        if (badcube_flag) {
            break;
        }
      for(size_t prev_dim = 0; prev_dim < 3; prev_dim++) {
        if (cur[I_dim] <= prev[prev_dim]) {
            badcube_flag = 1;
            break;
        }
      }
    }
    result++;
    badcube_flag = 0;
    prev[0] = cur[0]; prev[1] = cur[1]; prev[2] = cur[2];
  }
  return result;
}