Пример: Транспортная логистика
Я ищу:
На главную  |  Добавить в избранное  

Математика /

2

1

Книга (30 баллов)

Код задачи: Book Время на один тест: 1 сек

Имеется группа из N человек, для каждого человека задан круг его знакомых. Известно, что среди любых 3-х человек есть хотя бы пара знакомых. Требуется найти порядок чтения книги, при котором книга передается от знакомого к знакомому, при этом книгу прочитает как можно больше человек, причем человек может получать книгу несколько раз. Если книга прочитана одинаковым количеством людей, то более предпочтительным является вариант, при котором она передается минимальное число раз.

Входной файл BOOK.IN содержит описание круга знакомств. В первой строке файла находятся целые числа N (1?N?100) и M (0?M?N*(N-1)/2), где M – это количество пар знакомых. В каждой из следующих M строк находятся два целых числа – номера двух человек, являющихся знакомыми. Номера находятся в интервале от 1 до N.

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

Пример входных данных #1

4 3

2 1

2 3

4 3 Пример выходных данных #1

4

1 2 3 4

Числа (20 баллов)Код задачи: Numbers Время на один тест: 1 сек

Имеется N целых чисел. Необходимо определить набор из не более чем K (1?K?N) чисел массива с разными индексами, произведение которых минимально. При этом в наборе должно присутствовать хотя бы одно число массива.

Входной файл NUMBERS.IN содержит следующую информацию. В первой строке файла находятся целое число N (1?N?1000) и целое число K (1?K?N). Каждая из оставшихся N строк входного файла содержит целое число Ai , (-10000?Ai?10000).

Выходной файл NUMBERS.OUT должен содержать количество чисел в наборе и сами числа, упорядоченные в порядке неубывания. Все числа разделяются одним пробелом.

Пример входных данных #1

3 2

-1 0 1

Пример выходных данных #1

1 -1

Таблица (40 баллов)

Код задачи: ARRAY Время на один тест: 1 сек

Имеется матрица размера n*m, для которой известны суммы элементов по каждой строке SLi, i=1,2,…,n и каждому столбцу SRj, j=1,2,…,m. Необходимо заполнить элементы матрицы нулями и единицами таким образом, чтобы получить требуемые суммы или указать, что такое заполнение невозможно.

В первой строке входного файла ARRAY.IN записаны два целых числа N и M (1?N?100, 1?M?100), разделенные пробелом. В i-й из следующих N строк файла записано целое число SLi, затем в j-й из следующих M строк файла записано целое число SRi.

Выходной файл ARRAY.OUT должен состоять из N строк. В i-й строке выходного файла должно быть записано M нулей и/или единиц без пробелов, или ответ должно быть записан ответ ‘NO’ в случае, если требуемой матрицы не существует.

Пример входных данных #1

2 3

1

2

1

1

1

Пример выходных данных #1

100

011

Линия (20 баллов)

Код задачи: LINE Время на один тест: 1 сек

Треугольник задан координатами своих вершин. Необходимо определить коэффициенты уравнения прямой Ax+By+C=0 прямой, которая разрезает заданный треугольник на 2 равновеликие части, A,B,C -целые.

Входной файл LINE.IN состоит из трех строк. В каждой строке файла записаны целые числа Xi, Yi, -10000?Xi?10000, -10000?Yi?10000.

Выходной файл LINE.OUT должен содержать три целых числа A, B и C, разделенных пробелом, которые определяют коэффициенты уравнения прямой.

Пример входных данных #1

2 0

0 4

-2 0 Пример выходных данных #1

1 0 0




Copyright © 2005—2007 «Mark5»