Информатика
>>
Книги, журналы
>>
Беров В., Лапунов А., Матюхин В., Пономарев А., Особенности национальных задач по информатике
-
глава 1. Динамическое программирование
(14 задач)
глава 2. Перебор с возвратом
(10 задач)
глава 3. Алгоритмы на графах
(17 задач)
глава 4. Вычислительная геометрия
(12 задач)
глава 5. Комбинаторные алгоритмы
(3 задачи)
глава 6. Задачи на разные темы
(12 задач)
Фильтр
Задачи
Задача 102944[Отравленный пирог ] |
|
|
Требуется написать программу, которая по заданной игровой позиции
определяет все возможные выигрышные ходы для начинающего в этой позиции.
Входные данные
Данные во входном файле расположены в следующем порядке: M, N
(1 ≤ M, N ≤ 9), X1, ..., XM. Здесь Xi
– число оставшихся клеток в i-м снизу горизонтальном ряду. Все числа во входном файле разделяются пробелами
и/или символами перевода строки.
Выходные данные
В первую строку выходного файла необходимо вывести количество различных
выигрышных ходов К, а в последующие K строк – сами выигрышные ходы.
Каждый ход задается парой чисел (i, j), где i – номер (снизу) горизонтального
ряда, а j – номер (справа) вертикального ряда, которому принадлежит
выбранная клетка (1 ≤ i ≤ M, 1 ≤ j ≤ N).
Пример входного файла
3 5
5 4 3
Пример выходного файла
1
3 1
|
|
Решение |
Задача 102947[Острова ] |
|
|
Карта задается прямоугольником N × M, в каждой клетке которого записана
цифра 0 (вода) или цифра 1 (земля). Островом считается максимальное связное
множество клеток, содержащих единички, т.е. такое множество клеток A, что:
из любой клетки A можно пройти до любой другой клетки A, переходя лишь
через клетки A и их стороны;
при добавлении к A любой другой клетки, содержащей 1, предыдущее
условие нарушается.
Входные данные
В первой строке входного файла содержатся числа N и M – размеры карты
(1 ≤ N, M ≤ 1000). Далее записана сама карта – M строк по N чисел (0 или 1) в
каждой. Числа внутри строки разделяются пробелом.
Выходные данные
В выходной файл вывести коэффициент несправедливости с 5 знаками
после десятичной точки. Если на карте нет ни одного острова, вывести 0.
Пример входного файла
7 6
1 1 0 0 0 0 0
0 1 0 1 0 0 0
1 1 0 1 1 0 0
1 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 0 1 0
Пример выходного файла
2.66667
|
|
|
Решение |
Задача 102956[Типы данных ] |
|
|
Всего существует три вида запросов:
SizeInBytes(<Имя типа>) – определить, какое количество байт памяти занимает переменная указанного типа;
SizeInBits(<Имя типа>) – найти количество бит, необходимых для хранения переменной указанного типа при условии, что для каждого элемента этой переменной отводится минимально возможное число бит, способных закодировать все возможные значения этого элемента;
<Имя типа>($<Последовательность 16-х цифр>) – по дампу (т.е. содержимому) участка памяти, занимаемому переменной указанного типа, определить значения всех элементов этой переменной.
Напишите программу, которая вводит описания типов данных и обрабатывает заданную последовательность запросов. Описания типов не будут содержать типов-указателей, типов-файлов, типов-объектов и процедурных типов.
Процесс разработки Вашей программы постройте по следующей схеме:
А) Научите Вашу программу воспринимать стандартные типы данных, используемые в языке Turbo Pascal 7.0.
Б) Введите перечислимый тип и тип-диапазон, граничные значения которого
заданы константами.
В) Реализуйте конструкторы типов данных.
Г) Добавьте возможность использования функций и операций при построении
константного выражения.
Д) Реализуйте остальные возможности, допускаемые языком.
Входные данные
Входной файл начинается с ключевого слова «Definitions», за которым
следуют описания типов данных. Далее следует ключевое слово «Queries» и
список запросов. Каждый запрос записан в отдельной строке входного файла.
Учтите, что длина строки с запросом может превышать 255 символов.
Выходные данные
Ваша программа должна вывести в выходной файл результаты обработки
запросов в том же порядке, в котором запросы встречаются во входном файле.
На запрос первого или второго вида в отдельную строку выходного файла
следует выдать сообщение «Type <Имя типа> requires x bytes/bits», где
x – искомое целое число. На запрос третьего вида необходимо перечислить
значения всех элементов переменной указанного типа в том порядке, в котором
эти элементы хранятся в оперативной памяти. Для каждого из элементов в
отдельную строку выходного файла следует выдать строку «<Имя элемента> =
<Значение>». Формат выходного файла должен соответствовать приведенному
ниже примеру.
Пример входного файла
Definitions
Type
TClass = 1..11;
TScore = 0..100;
TTour = 1..10;
TStrange =
Array
[1..SizeOf(Input)
Div
Ord('A')]
Of
Boolean;
TExample =
Record
a :
Array
[1..2]
Of
Record
b,c :
Set
Of
0..2
End
End
;
TShortStr =
String
[3];
Type
TParticipant =
Record
Sex : (Male, Female);
Name :
String
[20];
Class : TClass;
Place : ShortInt;
TotalSum : 0..High(TScore)*(High(TTour)-Low(TTour)+1);
DayScores :
Array
[TTour]
Of
TScore;
End
;
{ Команда России для участия в международной олимпиаде }
TTeam =
Array
[1..5]
Of
TParticipant;
Queries
SizeInBytes(TStrange)
SizeInBits(TClass)
SizeInBits(TShortStr)
TParticipant(
$
01118AAEABECE6AEA2A02091A2A5E2ABA0ADA00000000A0B4501461D082319501C280A00
)
TExample(
$01020304
)
SizeInBits(TParticipant)
Пример выходного файла
Type TStrange requires 3 bytes
Type TClass requires 4 bits
Type TShortStr requires 26 bits
Sex = Female
Name = 'Кольцова Светлана'
Class = 10
Place = 11
TotalSum = 325
DayScores[1] = 70
DayScores[2] = 29
DayScores[3] = 8
DayScores[4] = 35
DayScores[5] = 25
DayScores[6] = 80
DayScores[7] = 28
DayScores[8] = 40
DayScores[9] = 10
DayScores[10] = 0
a[1].b = [0]
a[1].c = [1]
a[2].b = [0,1]
a[2].c = [2]
Type TParticipant requires 258 bits
|
|
|
Решение |
Задача 102941[Маятник ] |
|
|
Для нашего идеального математического мира считаются выполненными
следующие условия:
гвоздики и нить имеют нулевую толщину;
энергия маятника не теряется (т.е. трение отсутствует);
маятник никогда не сталкивается с гвоздиками (с ними входит в
соприкосновение только нить);
нить изгибается только при соприкосновении с гвоздиком.
Ваша задача состоит в том, чтобы промоделировать движение маятника и вычислить длину установившейся орбиты.
Вниманию тех, кто боится физики! Единственный физический факт,
необходимый для решения этой задачи, таков: маятник никогда не поднимается
выше своей начальной высоты. Следовательно, маятник либо достигнет оси x,
либо будет крутиться вокруг некоторого гвоздика.
Входные данные
В первой строке входного файла записаны целое число N – количество
гвоздиков (0 ≤ N ≤ 500) и вещественное число r – длина нити. В каждой из
следующих N строк через пробел указаны координаты одного из гвоздиков.
Выходные данные
Выведите в выходной файл длину одного цикла периодической орбиты, по
которой станет качаться маятник. Учитывать расстояние, пройденное
маятником до того, как он вышел на эту орбиту, не нужно. Ответ должен быть
указан с точностью до двух знаков после десятичной точки.
Пример входного файла
2 16.0
3 -4
-3 -4
Пример выходного файла
87.66
|
|
|
Решение |
Задача 102948[Микрофония ] |
|
|
Очередность выходов артистов на сцену и их уходов за кулисы указывается в режиссерском плане. Кроме того, в этом плане указывается, через какие кулисы выходит (или уходит) артист и поет ли он в данном выходе.
Напишите программу, которая по заданному режиссерскому плану
определяет минимальное количество требуемых для постановки оперы
микрофонов, их начальное размещение по кулисам и для каждого выхода
указывает, брать или не брать микрофон.
Входные данные
Первая строка входного файла содержит целое число N – количество артистов,
участвующих в спектакле (1 ≤ N ≤ 1000). Во второй строке записано целое число K
– количество выходов артистов на сцену (1 ≤ K ≤ 3000). Далее идут 2K строк,
описывающих режиссерский план спектакля. Каждая из них содержит четверку
AiBiCiDi (1 ≤ i ≤ 2K):
Ai
– символ +, если в данный момент артист выходит на сцену, или символ
-, если артист со сцены уходит;
Bi
– номер артиста (целое число от 1 до N);
Ci
– символ Л, если артист выходит (уходит) через левые кулисы, или
символ П, если он выходит (уходит) через правые кулисы;
Di
– символ Д, если артист поет в данном выходе (пел перед данным
уходом), или символ Н, если он не поет (не пел).
Выходные данные
Первая строка выходного файла должна содержать два целых числа. Первое
число – количество микрофонов перед началом оперы с левой стороны, второе
число – количество микрофонов с правой стороны. В каждой из последующих
K строк необходимо вывести 1 или 0 в зависимости от того, берет ли с собой
микрофон очередной выходящий на сцену артист (1 - берет, 0 - не берет).
Пример входного файла
3
4
+ 1 Л Д
- 1 Л Д
+ 2 Л Н
+ 3 Л Н
- 3 П Н
+ 1 П Д
- 1 Л Д
- 2 П Н
Пример выходного файла
1 0
1
0
1
1
|
|
|
Решение |
Страница: << 8 9 10 11 12 13 14 >> [Всего задач: 67]
