Грязные трюки: кеширование

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

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

  1. {i} Почитать о кешировании в Википедии. Какое отношение это может иметь к решению сложных задач?

  2. MCCME Прямоугольники. Дан прямоугольник N×M, состоящий из квадратиков 1 ´ 1. Некоторые квадратики вырезали. Надо найти наименьшее количество прямоугольников, на которое можно разрезать оставшуюся фигуру.

    • Формат входных данных. В первой строке входных данных заданы числа N и M, (1 ≤ N, M ≤ 10). Далее следует N строк. В (i+1)-ой содержится M чисел; j-е число равно 1, если клетку на i-й строке и в j-м столбце вырезали из доски, 0 – если оставили.

      Формат выходных данных. Выведите единственное число – минимальное количество прямоугольников, на которое можно разрезать полученную фигуру.

  3. MCCME. Пилообразные последовательности. Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам n и k определите число пилообразных последовательностей длины n, составленных из чисел 1..k. Программа получает на вход два натуральных числа n и k, не превосходящих 106.

Условные обозначения


CategoryClass CategoryVmsh

LecturesVMSH/Python/2013-03-29 (последним исправлял пользователь FrBrGeorge 2013-04-05 13:35:43)