IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Числовая последовательность, вписанная окружность, разрезание прямоугольника, сумма двух чисел, укладка плиток
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 7
Пол: Женский

Репутация: -  0  +


Задачи олимпиадного типа. Хочу нормально подготовиться, а не выходит. Многое не могу решить. Помогите, пожалуйста, хоть чем-нибудь)
Буду очень благодарна!

Задача 1 “Числовая последовательность »

Имя входного файла: numseq.in
Имя выходного файла: numseq.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

Дима недавно поступил на работу в научно-исследовательский институт «Числовые Последовательности». Как следует из названия этого института, основным направлением его работы является проведение различных исследований в области числовых последовательностей. Недавно руководитель отдела, где начал работать Дима, при решении одной из проблем столкнулся с весьма интересной последовательностью чисел a1, a2, …, an, …, которая определяется следующим образом: a1 = 0 и каждое последующее число a i-тое (1 < i ≤ n) определяется как наименьшее большее натуральное число, десятичная запись которого не содержит цифр, представленных в десятичной записи a i-1.
Требуется написать программу, которая по значению числа n вычисляет величину an.
Формат входных данных
Входной файл содержит целое число n (1 ≤ n ≤ 500).
Формат выходных данных
В выходной файл необходимо вывести ответ на задачу.
Примеры входных и выходных файлов
numseq.in numseq.out
1 ***0***
28 ***911***




Задача 2« Вписанная окружность »
Имя входного файла: polygon.in
Имя выходного файла: polygon.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

Требуется написать программу, которая определяет, можно ли в заданный выпуклый многоугольник вписать окружность, и, если это можно сделать, то вычисляет координаты ее центра и радиус.
Формат входных данных
Первая строка входного файла количество вершин многоугольника n (3 ≤ n ≤ 8). Последующие n строк содержат координаты вершин многоугольника в порядке обхода против часовой стрелки, каждая i-ая из них содержит два целых числа: xi и yi, значения которых не превосходят 1000 по абсолютной величине.
Формат выходных данных
Если окружность, вписанная в заданный многоугольник, существует, необходимо вывести в первой строке выходного файла слово YES, иначе – слово NO. В случае положительного ответа выведите во второй строке координаты центра окружности и ее радиус. При проверке решения задачи все величины будут сравниваться с точностью до 10^-6.
Примеры входных и выходных файлов
polygon.in polygon.out
4
0 0 *** YES ***
1 0 ***0.5 0.5 0.5 ***
1 1
0 1


4 *** NO ***
0 0
1 0
1 2
0 2

Задача 3 « Разрезание прямоугольника »
Имя входного файла: rect.in
Имя выходного файла: rect.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

На координатной плоскости задан прямоугольник, высота которого h, а ширина — w. Внутри прямоугольника заданы отрезки, параллельные осям координат и с концами, имеющими целочисленные координаты.
Прямоугольник планируется разрезать на несколько частей горизонтальными или вертикальными разрезами. За один шаг разрешается разрезать на две непустые прямоугольные части только один из имеющихся на этом шаге прямоугольников. При этом запрещается при разрезе пересекать, хотя бы один из заданных отрезков.
Требуется написать программу, позволяющую найти количество способов разрезания исходного прямоугольника на k частей вертикальными и горизонтальными разрезами. Способы, отличающиеся порядком проведения разрезов, считаются различными.

Формат входных данных
Первая строка входного файла содержит размеры прямоугольника – целые числа h и w (1 ≤ h, w ≤ 8). Вторая строка входного файла содержит целое число k – количество частей, на которые требуется разрезать прямоугольник (1 ≤ k ≤ hw). Третья строка содержит целое число cnt (0 ≤ cnt ≤ 10) — количество заданных внутри прямоугольника отрезков. Последующие cnt строк содержат описания этих отрезков, то есть, каждая строка содержит четыре целых числа x1, y1, x2, y2 (0 ≤ x1 ≤ x2 ≤ w, 0 ≤ y1 ≤ y2 ≤ h) — координаты концов отрезка. Все числа в строках разделены пробелом.

Формат выходных данных
В выходной файл необходимо вывести одно целое число — искомое количество способов разрезания исходного прямоугольника. Ответ должен быть представлен по
модулю 230.

Пример входного и выходного файлов
rect.in rect.out
2 2 ***4***
4
0

8 8 *** 767625216***
20
0

4 4 ***3***
2
2
2 0 2 3
2 3 4 3



Задача 4 "Сумма двух чисел"
Имя входного файла: sum.in
Имя выходного файла: sum.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

Заданы три числа: a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось c.

Формат входных данных
Входной файл содержит три целых числа: a, b, c (0 < a, b, c < 109). Числа разделены пробелом.

Формат выходных данных
Если искомая перестановка цифр возможна, необходимо вывести в выходной файл слово YES, в противном случае — выведите слово NO. При положительном ответе необходимо вывести во второй строке выходного файла число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y не должны содержать ведущих нулей. Числа в строке разделены пробелом.
Примеры входных и выходных файлов
sum.in sum.out
12 31 25 ***YES***
***12 13***


12 31 26 ***NO***



Задача 5 «Укладка плиток»
Имя входного файла: tiling.in
Имя выходного файла: tiling.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

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

Для простоты будем считать, что пол помещения представляет собой прямоугольник размером n на m метров, разбитый на m∙n квадратиков со стороной по 1 метру. Кроме этого, будем считать, что имеется четыре типа плиток, показанные в таблице. Каждая из плиток представляет собой квадрат размером 2 на 2 метра, из которого вырезан один квадратик размером 1 на 1 метр.


Прикрепленное изображение


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

Требуется написать программу, которая определяет, какая площадь в соответствии с заданным набором команд будет покрыта плитками.

Формат входных данных
Первая строка входного файла содержит два числа m и n — размеры пола помещения (1 ≤ m, n ≤ 50). Вторая строка содержит число k — количество команд, которые необходимо обработать (0 ≤ k ≤ 1000). Каждая из последующих k строк содержит описание одной команды из набора команд. Описание команды состоит из трех чисел. Первое число определяет тип плитки (число от 1 до 4), а два других - координаты левого верхнего квадрата размером 2 на 2, в который вписана соответствующая плитка.

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

Примеры входных и выходных файлов
tiling.in tiling.out
4 4 ***6***
4
4 1 1
2 2 2
3 1 1
1 3 3



P.S. ***0*** - обозначают, что числа и выражения, находящиеся внутри, относятся к выходному файлу (не получилось нормально написать)

Сообщение отредактировано: Ирбис377 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
Ирбис377   Числовая последовательность, вписанная окружность, разрезание прямоугольника, сумма двух чисел, укладка плиток   15.01.2010 20:33
volvo   1. Заголовок темы должен быть информативным. В про…   15.01.2010 21:27
sheka   Второе: а если ЭТО - задачи текущей олимпиады, то…   15.01.2010 21:51
Ирбис377   1. Это задачи республиканского этапа еще 2007 года…   15.01.2010 21:56
volvo   То есть, интернет-туров как бы не существует по-тв…   15.01.2010 22:03
Ирбис377   Это не интернет-тур. Это всего лишь личная подгото…   15.01.2010 22:17
sheka   Люди, пожалуйста, помогите!) вот это еще убер…   15.01.2010 22:18
Ирбис377   Переименовала)   15.01.2010 22:25
sheka   Вторую задачу я бы решал с помощью аналитической г…   15.01.2010 22:59
Ирбис377   Ммм...А ведь действительно! я попробую) Спасиб…   15.01.2010 23:01
volvo   Ты действительно думаешь, что готовое решение ПОМО…   15.01.2010 23:13
Ирбис377   Готовое решение мне нужно для того, чтоб понять КА…   15.01.2010 23:25
sheka   А при запуске в Turbo вылазит ошибка 116. на позиц…   15.01.2010 23:53
amega   нет, Это мне. зы скачал книгу Turbo_Assembler_2n…   16.01.2010 0:11
Tony   Могу поделиться собственными соображениями по реше…   16.01.2010 0:25
Unconnected   Посмотри обсуждение 4ой задачи в соседней теме. Та…   16.01.2010 21:39
Unconnected   Сделал 5ю. Типов только, кажется, понаописал черес…   17.01.2010 4:54
Ирбис377   Спасибо большое! Вы мне очень помогли)   18.01.2010 0:42


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 17:46
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name