Отправляет email-рассылки с помощью сервиса Sendsay

Информат - алгоритмическое и математическое мышление

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "физика YES" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Февраль 2003   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Автор
ss77_ss77@mail.ru

Статистика

1.523 подписчиков
+1 за неделю
←   Все выпуски   →

Конкурсы и Олимпиады по Машинному программированию (КОМП)


Информационный Канал Subscribe.Ru

Задачи

Все задачи оцениваются в 40 баллов.

Задача 1. "Многогранник"

ФОРМУЛИРОВКА

Найти объем многогранника с целочисленными координатами вершин. Все грани многогранника --- треугольники. Не треугольные грани могут задаваться несколькими треугольниками, лежащими в одной плоскости. Объем требуется выдать точно в виде несократимой дроби. Многогранник может быть и невыпуклым. Форма многогранника не ограничена. Например, он может быть подобием бублика, или состоять из двух несвязанных частей, или быть подобием двух продетых друг в друга звеньев цепи, или быть подобием бублика, завязанного узлом. Многогранник может даже содержать внутренние пустоты, в которых могут содержаться отдельные части многогранника (типа "матрешки"). Выдать в этом случае нужно объем тела многогранника за вычетом всех пустот.

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение времени тестирования: 1 секунда на 1 тест

ФОРМАТ ВХОДНЫХ ДАННЫХ

Входной файл содержит запись целых неотрицательных чисел в десятичной системе счисления. Последовательно задаются все грани многогранника. Каждая грань задается последовательно тремя тройками неотрицательных целых чисел --- координатами вершин (сначала --- координата х, потом - y, и, наконец, --- z). Вершины всех граней при этом обходятся обязательно в одном и том же направлении: все --- по часовой стрелке или все --- против часовой стрелки, если смотреть на грань снаружи многогранника (то есть из пустоты, а не из тела многогранника) и так, чтобы эта грань не была заслонена другими гранями. Таким образом, если считать, что при задании каждой грани проходятся три ребра в определенном направлении, то в итоге каждое ребро проходится дважды: в одном направлении и в противоположном. Каждая вершина проходится столько раз, сколько граней (а, значит, и ребер) к ней примыкает. Грани между собой могут соприкасаться только своими ребрами. Например, ни одна грань не может рассекать другую посередине, находиться внутри другой грани или соприкасаться с другой гранью вершиной. Все числа не превышают 15, разделяются одиночными или кратными пробелами или переводами строк. Число граней не превышает 1000.

ФОРМАТ ВЫХОДНЫХ ДАННЫХ

Выходной файл содержит одну строку, в которой записаны только два целых числа в десятичной системе счисления: числитель и знаменатель несократимой дроби, выражающей объем многогранника. Числа разделяются одним пробелом. Знаменатель должен быть положительным. Никаких других символов в строке быть не должно. Числитель может быть больше знаменателя. Незначащих нулей в начале чисел быть не должно.

ПРИМЕР ФАЙЛОВ ВХОДНЫХ И ВЫХОДНЫХ ДАННЫХ

---- начало input.txt -----
0 0 1  0 1 0  1 0 0
0 0 0  0 0 1  1 0 0
0 0 0  0 1 0  0 0 1
0 0 0  1 0 0  0 1 0
----- конец input.txt -----

---- начало output.txt ----
1 6
---- конец output.txt -----



Автор задачи: А. Б. Бельтюков


Задача 2. "Помощник риэлтера"

Первоначальный вариант задачи риэлтера на первом туре звучал так:


Есть несколько человек, желающих продать, купить или обменять квартиры. Риэлтер должен помочь им в этом и сам остаться с прибылью. Все обмены осуществляются через продажу старых квартир и покупку новых.

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

Все данные хранятся в файле exchange.txt. В каждой строке файла записана информация ровно об одном обмене. В строке содержится информация в описанном ниже порядке: 

  <номер обмена>
  'пробел'
  <количество комнат первой продаваемой квартиры><пробел><её цена>
  ','
  <количество комнат второй продаваемой квартиры><пробел><её цена>
  ','
  ...
  <количество комнат последней продаваемой квартиры><пробел><её цена>
  ';'
  <максимальная сумма доплаты>
  '='
  <количество комнат первой желаемой квартиры><пробел><её цена>
  ','
  <количество комнат второй желаемой квартиры><пробел><её цена>
  ','
  ...
  <количество комнат последней желаемой квартиры><пробел><её цена>
  ';'
  <минимальная сумма выручки>

ЦЕЛЬ

Найти цепочку взаимных обменов, выгодную для риэлтера. Выдать в файл output.txt последовательность номеров обмена, каждый номер в своей строке.

ПРИМЕР

В файле exchange.txt: 

  20 1 300, 2 400; 0=3 600; 0
  10 2 500, 1 200, 3 700; 0=;1400
  12 5 1100; 100=1 200, 1 200, 2 400; 0
  1  5 1000; 0=;1100
  2  ;1305=4 1100; 0

В файле output.txt: 

  20
  10
  12
  1

Жюри, как "настоящий" заказчик, изменило формулировку, добавив следующее:

Теперь в файле output.txt нужно записать информацию о том, какая квартира меняется и на какую. Квартиры идентифицируются по двум параметрам: номер обмена и номер квартиры в обмене.

Формат output.txt

<номер обмена> <номер продаваемой квартиры> <номер обмена> <номер желаемой квартиры>

Если квартира не для обмена, а для продажи (в желаемой части только деньги), то вторая пара чисел --- нули. В файле output.txt: 

10 3 20 1
20 1 12 1
10 2 12 2
20 2 12 3
 1 1  0 0

ЗАДАЧА

Составить программу, которая по файлам exchange.txt и input.txt (output.txt первоначальной формулировки) выдает output.txt из изменённой формулировки.

Техническое задание

Ограничение времени 10 секунд. Максимальное количество квартир (продаваемых и желаемых) не более 10. Максимальная стоимость квартиры --- целое число от 1 до 10000. Максимальное количество комнат в квартире от 1 до 9. Максимальное количество обменов (количество строк) в exchange.txt --- 100000. Все цены (на квартиры, доплаты и выручки) --- целые числа от 0 до 10000.

Можно использовать свои решения задачи первого тура.



Автор задачи: В. В. Пупышев


Задача 3. "MicroLisp"

Простейший язык функционального программирования задан следующим образом.

Переменными и константами являются малые буквы латинского алфавита.

Элементарными типами являются большие буквы латинского алфавита.

Типы строятся из элементарных по следующим правилам:

Если T1, T2, ..., Tn --- типы, то и (T1 T2 ... Tn) --- тип (n <= 2).

Если T1, ..., Tn, T) --- типы, то и (T1 ... Tn -> T) (n <= 1) тоже тип.

Выражения языка

Переменные и константы считаются выражениями языка.

Применение функции --- запись вида Apply(E E1 ... En), где число аргументов не меньше 1, каждый из аргументов является выражением. Если E имеет тип (A1 ... An -> B), каждое из Ei--- тип Ai, то все это выражение имеет тип B.

Описание функции --- запись вида Lambda(x1 ... xn E), где все xi (1 <= i <= n )--- различные переменные, E--- произвольное выражение. Внутри E все xi считаются связанными. Если считать, что связанным переменным приписаны типы T1, ..., Tn, и после этого оказывается, что выражение E имеет тип T, то описание функции имеет тип (T1 ... Tn -> T).

Список --- запись вида (E1 E2 ... En). Если Ei имеют тип Ti, то список имеет тип (T1 ... Tn).

Извлечение члена списка --- запись вида Mem(i,E), где E имеет тип списка не менее чем с i компонентами.

Постановка задачи

В начале входного файла input.txt идут описания констант, а затем идет тип, пример входного файла 

const
a: (A B -> A)
h: (A B)
j: D
result A
Все буквы, не описанные в списке констант, считаются переменными.

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

В частности, для данной задачи правильным ответом является

Apply(a Mem(1,h) Mem(2,h))

Ответ нужно записать в файл output.txt.

Каждая строка входного файла содержит описание одной константы и не длиннее 250 символов. Выходной файл должен не превышать 1000 символов. Разбиение на строки несущественно, но служебные слова Apply, Mem и Lambda разрывать нельзя.

Внимание! Одна и та же задача может допускать много (в принципе бесконечно много) правильных ответов. Например, для приведенной выше задачи правильными ответами являются также
Mem(1,h)
Apply(Lambda(x x) Mem(1,h)).



Автор задачи: Н. Н. Непейвода


Остальную информациюсмотрите по ссылке>>>
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное