Задачи за тренинг
Задача 8а. [8.2.2]
Трима братя наследили N парцела земя с лица S1, S2,…,
SN, съответно, и решили да си ги поделят по
братски.
Помогнете им да направят това. Напишете програма, която
разбива
множеството от парцели на три подмножества така, че ако A е сумата
от
лицата на парцелите в първото подмножество, B – на парцелите във
второто и C - на парцелите във третото, то сумата
|A – B| + |A - C| + |B - C|
да е минимална.
Вход:
На входа се задава числото N,
(1 < N < 513) -
брой на парцелите земя и още N числа
-
лицата
на
парчетата
(цели
положителни числа).
Входът съдържа
много примери.
Изход:
За всеки пример на нов ред се отпечатва търсената най-малка стойност
.
Пример:
3 1 1 1
7
4 1 1 1 2 2 9
Решение на примера:
0
8
За втория пример разделянето е 9, 2+2+1+1=6, 4+1=5,
отговорът е (9-6)+(9-5)+(5-5)=8.
Задача 8b. [8.2.7] lns3.c
Да
се
напише програма за намиране на най-дългата ненамаляваща подредица.
Вход:
На входа се задава числото n
- брой
на елемнтите на редицата и след това стойностите на самите
елементи - цели числа в интервала [-10, 105].
Входът
съдържа
много примери.
Изход:
За всеки пример на отделен ред се отпечатва цяло число - дължината
на
най-дългата ненамаляваща подредица.
Пример:
6
6 6 6 2 2 7
6
1 1 1 1 1 2
15
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
3
4 3 2
Решение на примера:
4
6
8
1
Редиците са: 6 6 6 7;
1 1 1 1 1 2; 1 2 2 2 2 2
2 2 (има и друга); 4.