10769. Колонна

Известный архитектор Мистер Фруи планирует построить колонну для колосса высотой h. У него есть n черных блоков с высотами b₁, …, b_n и m белых блоков с высотами w₁, …, w_m. Колонна должна содержать четыре блока, черный блок должен лежать в основании, а далее цвета блоков должны чередоваться.

Мистер Фруи хочет найти наиболее устойчивую комбинацию блоков для построения колонны. Комбинация A = (a₁, a₂, a₃, a₄) считается устойчивее B = (b₁, b₂, b₃, b₄), если либо a₁ > b₁, либо a₁ = b₁ и a₂ > b₂ и так далее (последовательность высот A лексикографически больше последовательности высот B).

Вход. Состоит из нескольких тестов, разделенных пустой строкой. Первая строка теста содержит желаемую высоту колонны h (1 £ h £ 4*10⁸). Вторая и третья строки содержат соответственно последовательности b₁, …, b_n и w₁, …, w_m. Все входные числа целые, 2 £ n, m £ 100, высота каждого блока не более 10⁸.

Выход. Для каждого теста вывести последовательность высот блоков для наиболее устойчивой колонны. Если колонну построить невозможно, то вывести сообщение “no solution”.

Пример входа

100
20 20
30 10 30 50
 
100
20 10 4
50 30 45

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

20 50 20 10
no solution

РЕШЕНИЕ

полный перебор

Анализ алгоритма

Занесем высоты черных блоков в массив b, а белых – в массив w. Отсортируем эти массивы по убыванию. Далее делаем полный перебор четверок b[i], w[j], b[k], w[l] (0 £ i £ lenb-1, 0 £ j £ lenw-1, i + 1 £ k £ lenb, j + 1 £ l £ lenw). Если их сумма равна h, то первая же найденная четверка будет лексикографически наибольшей и колонна, построенная из этих блоков, будет наиболее устойчивой.

Пример

Рассмотрим первый тест. Отсортированные по убыванию массивы высот черных и белых блоков имеют вид: b = (20, 20), w = (50, 30, 30, 10). При полном переборе первой четверкой, сумма которой равна высоте колонны h = 100, будет 20 + 50 + 20 + 10 = 100.

Реализация алгоритма

Массивы b и w содержат высоты белых и черных блоков, lenb и lenw – соответственно длины этих массивов. h – высота колонны.

int b[100], w[100];

int h, lenb, lenw;

Читаем входные данные. Поскольку не задано в явном виде количество черных и белых блоков, то соответствующие значения читаем в массивы b и w до тех пор пока не встретится символ конца строки ‘\n’.

while(scanf("%d",&h) == 1)

{

for(lenb = 0; ; lenb++)

{

scanf("%d",&b[lenb]);

if((c = getchar()) == '\n') break;

}

for(lenw = 0; ; lenw++)

{

scanf("%d",&w[lenw]);

if((c = getchar()) == '\n') break;

}

lenb++; lenw++;

Сортируем по убыванию элементы массивов b и w. Для использования функции greater следует включить заголовок #include <functional>.

sort(b,b+lenb,greater<int>());

sort(w,w+lenw,greater<int>());

Перебираем все возможные четверки b[i], w[j], b[k], w[l] (0 £ i £ lenb-1, 0 £ j £ lenw-1, i + 1 £ k £ lenb, j + 1 £ l £ lenw). Если сумма некоторой четверки равна h, то присвоим переменной-флагу found значение 1 и выйдем из цикла.

found = 0;

for(i = 0; i < lenb - 1; i++)

for(j = 0; j < lenw - 1; j++)

for(k = i + 1; k < lenb; k++)

for(l = j + 1; l < lenw; l++)

if (b[i] + w[j] + b[k] + w[l] == h)

{

found = 1;

goto fin;

}

Если требуемая четверка была найдена (found = 1), то выводим ее. Иначе печатаем сообщение о невозможности построить колонну.

fin:

if (found) printf("%d %d %d %d\n",b[i],w[j],b[k],w[l]);

else printf("no solution\n");

}