Задачи pascal

задача 1

Станции техобслуживания

Компания занимается продажей персональных компьютеров в N городах (3

решила построить несколько станций техобслуживания так, чтобы для любого города X станция находилась либо непосредственно в X, либо в каком то городе,

напрямую соединенном с X.

Напишите программу, определяющую минимальное число станций, необходимых компании.

Входные данные

Входные данные состоят из нескольких вариантов условия. Каждый вариант начинается с числа городов N и числа пар M, разделенных пробелом. Каждая

из следующих M строк содержит пару целых чисел, определяющих соседние города, причем на одну строку приходится ровно одна пара чисел, разделенных

пробелом. Входные данные завершаются при N=0 и M=0.

Выходные данные

Для каждого блока текстовых данных выведите строку, содержащую число необходимых станций техобслуживания.

задача 2

Перетягивание каната.

Перетягивание каната – это состязание в грубой силе, когда две группы людей тянут канат в противоположные стороны. Та команда, которая сумела

утянуть канат в свою сторону, объявляется победителем. На корпоративном пикнике решили посостязаться в перетягивании каната Участников пикника нужно

честно разбить на две команды. Каждый человек должен попасть в одну или другую команду, число человек в одной команде не должно превышать число человек в

другой более чем на одного, и суммарные веса людей каждой команды должны быть близки, насколько это возможно.

Входные данные

Входные данные начинаются со строки, содержащей одно положительное целое число, которое означает количество тестовых блоков, за которой следует

пустая строка.

Первая строка каждого блока содержит n, число участников пикника. Каждая из следующих n строк содержит вес одного из участников пикника, причем

вес задается целым числом между 1 и 450. Число участников пикника не превышает 100.

Между двумя последовательными текстовыми блоками также находится пустая строка .

Выходные данные

Для каждого текстового блока вы должны вывести строку, содержащую два числа: суммарный вес людей в одной команде и суммарный вес людей в другой

команде. Если эти числа отличны, выведите сначала меньшее.

Выходные данные для двух последовательных блоков должны быть разделены пустой строкой.

Задача 3

Со времен Евклида известно, что для любых положительных целых чисел A и B соответствуют такие целые X и Y, что AX+BY=D, где D – это наибольший общий

делитель чисел A и B. Задача состоит в том, чтобы найти соответствующие X,Y и D заданных A и B.

Входные данные

Входные данные состоят из последовательности строк, каждая из которых содержит целые числа A и B, разделенные пробелом (A, B

Выходные данные

Для каждой строки входных данных выходная строка должна содержать три целых числа X,Y и D, разделенные пробелами. Если существуют несколько различных пар

X и Y, то вы должны вывести такую, что X

Задача 4

Распил брусьев

Вам нужно распилить деревянный брус на несколько кусков. Самая удобная компания Analog Cutting Machinery (ACM) берет плату за пилку в зависимости от

размера бруса, который нужно распилить.

Легко понять, что различные заказы приводят к различным ценам. Например рассмотрим брус длиной 10м, который необходимо распилить на расстоянии 2,4 и 7м,

считая от одного конца. Это можно сделать несколькими способами. Можно распилить сначала на отметке 2м, потом 4 и потом 7м. Это приведет к стоимости:

10+8+6=24, потому что сначала длина бруса, который пилили была 10, затем она стала 8м, и наконец, 6м. А можно распилить иначе: сначала на отметке 4м,

затем 2 и затем 7м. Это приведет к стоимости: 10+4+6=20, что для нас лучше.

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

Входные данные

Входные данные состоят из нескольких тестовых блоков. Первая строка каждого тестового блока содержит положительное число l, задающее длину бруса, который

нужно распилить. Вы можете считать, что l

Следующая строка содержит n положительных чисел ci (0

блок с l=0 задает окончание входных данных.

Выходные данные.

Выведите стоимость пилки минимальной цены.