Матч 284, Загрузка грузовика (Truckloads)

Дивизион 2, Уровень 1

Имеется кипа из numCrates корзин. Ее следует загрузить в машины, вместительность каждой из которых равна loadSize. Если кипа имеет размер, больший loadSize, то она делится пополам и каждую из частей рекурсивно грузят в машины. Если размер кипы нечетный (numCrates = 2n + 1), то при ее делении пополам в одной кипе окажется n корзин , а в другой n + 1. Сколько потребуется машин, чтобы загрузить все numCrates корзин?

Класс: Truckloads

Метод: int numTrucks(int numCrates, int loadSize)

Ограничения: 2 £ numCrates £ 10000, 1 £ loadSize £ numCrates – 1.

Вход. Количество корзин numCrates в кипе и вместительность машин loadSize.

Выход. Количество машин, требуемое для погрузки всех numCrates корзин.

Пример входа

numCrates	loadSize
14	3
15	1
1024	5

Пример выхода

6

15

256

РЕШЕНИЕ

рекурсия

Задача решается рекурсивным подсчетом числа машин. Если numCrates £ loadSize, то достаточно одной машины. Иначе кипа делится на две части с размерами numCrates / 2 и (numCrates + 1) / 2, после чего рекурсивно распределяется между машинами. Деление на 2 в этих выражениях целочисленное. Поэтому если numCrates четно , то numCrates / 2 = (numCrates + 1) / 2. Если numCrates нечетно, то numCrates / 2 +1 = (numCrates + 1) / 2 (размер полученных кип отличается на единицу).

ПРОГРАММА

#include <stdio.h>

class Truckloads

{

public:

int numTrucks(int numCrates, int loadSize)

{

return (numCrates <= loadSize) ? 1 : numTrucks(numCrates / 2, loadSize) +

numTrucks((numCrates + 1) / 2, loadSize);

}

};