На 10 пронумерованных дисках записано различное количество файлов сколько всего файлов записано
Обновлено: 02.07.2024
Большая подборка задач разного типа на соотношение единиц измерения и передачу информации, на кодирование текстовой, графической, аналоговой информации и определение информационного объема файлов.
Задания могут быть использованы на уроках с 8 по 11 класс, в том числе и при подготовке к ЕГЭ.
Задания на соотношение единиц измерения информации
1. 2 25 бит – сколько Мбайт?
2. Найти значение Х из соотношения 4 2-х Кб=16Мб
3. Найти Х, при котором равны информационные объемы 32 х+3 килобайт и 256 х мегабайт.
Задания на использование формулы Хартли и применение вероятностного подхода к измерению информации
4. Сколько различных звуковых сигналов можно закодировать с помощью 8 бит?
5. Сколько нужно бит, чтобы закодировать алфавит из 64 символов?
6. Когда Вы подошли к светофору, горел желтый свет. Затем зажегся красный. Какой объем информации Вы получили в момент, когда зажегся красный?
8. Измеряется температура воздуха, которая может быть целым числом от -30 до 34 градусов. Какое наименьшее количество бит необходимо, чтобы закодировать одно измеренное значение?
9. Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100 процентов, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем в байтах результатов наблюдений.
11. Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи трех сигнальных флагов, если на корабле имеются флаги четырех различных видов (флагов каждого вида неограниченное количество)?
12. Каждый элемент светового табло может гореть одним из 4 цветов. Какое наименьшее количество элементов должно работать, чтобы можно было передать 500 различных сигналов?
13. Азбука Морзе позволяет кодировать символы для радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код Морзе длиной не менее пяти и не более шести сигналов (точек и тире)?
15. Одна ячейка памяти «троичной ЭВМ» (компьютера, основанного на использовании троичной системы счисления) может принимать одно из трех возможных состояний. Для хранения некоторой величины отвели 6 ячеек памяти. Сколько различных значений может принимать эта величина?
18. Два исполнителя Шалтай и Болтай проставляют 0 и 1 в каждую из имеющихся в их распоряжении клеточку. Шалтай может закодировать 512 символов и у него на две клеточки больше, чем у Болтая. Сколько клеток в распоряжении у Болтая?
19. Каждая клетка поля 8×8 кодируется минимально возможным и одинаковым количеством бит. Решение задачи о прохождении «конем» поля записывается последовательностью кодов посещенных клеток . Каков объем информации в битах после 11 сделанных ходов? (Запись решения начинается с начальной позиции коня).
20. Учитель, выставляя в журнал четвертные оценки по биологии за третью четверть (3, 4, 5), обратил внимание, что комбинация из трех четвертных оценок по этому предмету у всех учеников различна. Какое может быть максимальное количество учеников в этом классе?
22. В некоторой стране автомобильный номер длиной 6 символов составляют из заглавных букв (задействовано 30 различных букв) и десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объем памяти в байтах, отводимый этой программой для записи 50 номеров.
23. Программа генерирует N-символьные пароли следующим образом: в качестве символов используются десятичные цифры, а также строчные и прописные латинские буквы в любом порядке (в латинском алфавите 26 знаков). Все символы кодируются одним и тем же минимально возможным количеством бит и записываются на диск. Программа сгенерировала 128 паролей и записала их в файл подряд, без дополнительных символов. Размер полученного файла составил 1,5 Кбайта. Какова длина пароля (N)?
Задачи на кодирование текстовой информации и определение объема текстового файла
27. Считая, что каждый символ кодируется одним байтом, определите, чему равен информационный объем в битах следующего высказывания Жан-Жака Руссо: Тысячи путей ведут к заблуждению, к истине – только один.
28. Определить объем памяти в Кбайтах, занимаемый текстом из 60 страниц по 512 символов на каждой странице. (кодировка ASCII)
30. Определить максимальное количество страниц текста, содержащего по 80 символов в каждой строке и 64 строки на странице, которое может содержать файл, сохраненный на гибком магнитном диске объемом 10Кбайт. (кодировка ASCII)
33. Два текста содержат одинаковое количество символов. Первый текст составлен в алфавите мощностью 8 символов, второй – 16 символов. Во сколько раз отличается количество информации в этих текстах?
36. В алфавите некоторого языка всего две буквы А и Б. Все слова этого языка состоят из 11 букв. Каков максимальный словарный запас этого языка?
38. Для записи текста использовался 256-символьный алфавит. Каждая страница содержит 30 строк по 70 символов в строке. Какой объем информации в байтах содержит 5 страниц текста?
39. В языке некоторого племени всего 16 букв. Все слова состоят из 5 букв, всего в языке 8000 слов. Сколько памяти в байтах потребуется для хранения всех слов этого языка?
40. В некоторой кодировке слово из 20 букв занимает на 42 байта больше, чем слово из шести букв. Сколько бит отводится на одну букву, если под все символы этой кодировки отводится равный объем памяти?
41. Текст, записанный с помощью 16-ти символьного алфавита, занимает 10 полных секторов на односторонней дискете объемом 180 Кбайт. Дискета разбита на 40 дорожек по 9 секторов. Сколько символов содержит этот текст?
42. Система оптического распознавания символов позволяет преобразовывать отсканированные изображения страниц документа в текстовый формат со скоростью 4 страницы в минуту и использует алфавит мощностью 256 символов. Какое количество информации в байтах будет нести текстовый документ после 5 минут работы приложения, страницы которого содержат 40 строк по 50 символов?
Задания на кодирование графической информации и определение объема графического файла
43. Для хранения изображения размером 128128 точек выделено 4 Кбайт памяти. Определите, какое максимальное число цветов в палитре
44. 16-цветный рисунок содержит 500 байт информации. Из скольких точек он состоит?
45. Определить требуемый объем (в мегабайтах) видеопамяти для реализации графического режима монитора с разрешающей способностью 1024×768 пикселей при количестве отображаемых цветов 4 294 967 296.
46. Определить объем видеопамяти в Кбайтах для графического файла размером 1240480 пикселей и глубиной цвета 16 бит
47. Определить объем видеопамяти в Килобайтах для графического файла размером 640480 пикселей и палитрой из 32 цветов
48. После преобразования графического изображения количество цветов уменьшилось с 256 до 32. Во сколько раз уменьшился объем занимаемой им памяти?
49. Цветной сканер имеет разрешение 1024512 точек на дюйм. Объем памяти, занимаемой просканированным изображением размером 24 дюйма, составляет около 8 Мбайт. Какова выраженная в битах глубина представления цвета сканера?
50. Цвет пикселя, формируемого принтером, определяется тремя составляющими: голубой, пурпурной и желтой. Под каждую составляющую одного пикселя отвели по 4 бита. В какое количество цветов можно раскрасить пиксель?
51. Цвет пикселя монитора определяется тремя составляющими: зеленой, синей и красной. Под красную и синюю составляющие отвели по 5 бит. Сколько бит отвели под зеленую составляющую, если растровое изображение размером 88 пикселей занимает 128 байт?
52. После преобразования растрового 256-цветного графического файла в черно-белый двуцветный формат его размер уменьшился на 70 байт. Каков был размер исходного файла в байтах?
53. В процессе преобразования растрового графического файла его объем уменьшился в 1,5 раза. Сколько цветов было в палитре первоначально, если после преобразования получено изображение того же разрешения в 256-цветной палитре?
54. Фотография размером 1010 см была отсканирована с разрешением 400 dpi при глубине цвета 24 бита. Определите информационную емкость полученного растрового файла в килобайтах. Примечание: принять 1 дюйм = 2,5 см
55. Для кодирования цвета фона интернет-страницы используется атрибут , где в кавычках задаются шестнадцатеричные значения интенсивности цветовых компонент в 24-битной цветовой модели RGB. Какой цвет будет у страницы, задаваемой тегом ?
Задания на кодирование аналоговой информации и определение объема звукового файла
57. Определить информационный объем в Кбайтах моноаудиофайла длительностью звучания 8 сек при глубине звука 8 бит и частоте 8 кГц
58. Определить длительность звучания стереоаудиофайла, занимающего 468,75 Кбайт памяти при глубине звука 16 бит и частоте 48 кГц
59. Музыкальная запись выполнена в формате CDDA (частота дискретизации 44100 Гц, 16 бит, стерео) и имеет продолжительность 19 мин 20 cек. Сколько секунд займет передача этой записи по каналу с пропускной способностью 16000 байт/сек?
60. При переводе в дискретную форму аналогового сигнала длительностью 2 мин 8 сек использовалась частота дискретизации 32 Гц и 16 уровней дискретизации. Найти в байтах размер полученного кода аналогового сигнала.
Задания на передачу информации по каналам связи и определение информационного объема файлов разных типов
61. Скорость передачи данных через ADSL-соединение равна 1240 Кбит/cек. Через данное соединение в течение 2 секунд передают файл. Определите размер файла в килобайтах.
62. Скорость передачи данных через ADSL-соединение равна 1024 000 бит/c. Через данное соединение передают файл размером 2500 Кбайт. Определите время передачи файла в секундах.
63. Пользователь компьютера, хорошо владеющий навыками ввода информации с клавиатуры, может вводить в минуту 100 знаков. Мощность алфавита, используемого в компьютере, равна 256. Какое количество информации в битах может ввести пользователь в компьютер за 1 минуту?
65. Алфавит некоторого языка состоит из 32 символов. За сколько секунд можно передать текст из 1600 оптимального закодированных символов этого алфавита при скорости передачи 100 байт/сек
68. Вычислить объем видеофайла (в Гбайтах) длительностью 64 сек, скоростью смены кадров равной 32 кадров/сек, разрешении 1280*640 точек и разрядностью цвета 16 бит. Объемом звуковой составляющей видеоклипа можно пренебречь.
69. Модем, передающий информацию со скоростью 16 384 бит/сек, передал цветное растровое изображение за 4 мин 16 сек. Укажите максимальное число цветов в палитре изображения, если известно, что его размер составил 1024512 пикселей.
70. Документ состоит из текстовой и графической информации. Текст содержит 30 строк по 30 символов в каждой в кодировке ASCII. Размер черно-белого изображения составляет 120300 точек. Определить информационный объем этого изображения в байтах.
71. Документ содержит несколько страниц текста, на каждой 60 строк по 30 символов в кодировке КОИ-8, и две иллюстрации размером 120*240 пикселей, в каждом изображении используется не более 8 различных цветов. Модем, работающий со скоростью передачи 28800 бит/сек, передал этот документ за 8 сек. Определите, сколько страниц в тексте.
72. Текст подготовлен для передачи по сети и содержит 51200 символов. Каждый символ кодируется двумя байтами и во избежание искажений передается трижды. Время передачи текста составило 64 секунды. Определите скорость передачи в байт/сек.
73. Данные объемом 16 Мбайт поступают на компьютер по линии со скоростью передачи данных 32 Мбит/сек. После получения 4 Мбайт компьютер начинает одновременно передавать эти данные по другой линии связи со скоростью 4 Мбит/сек. Сколько секунд пройдет от начала приема данных по высокоскоростному каналу до полной передачи их по низкоскоростному каналу?
74. У Оли есть доступ к сети Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 221 бит в секунду. У Маши нет скоростного доступа в Интернет, но есть возможность получать информацию от Оли по низкоскоростному телефонному каналу со средней скоростью 213 бит в секунду. Маша договорилась с Олей, что та будет скачивать для нее данные объемом 8 Мбайт по высокоскоростному каналу и ретранслировать их Маше по низкоскоростному каналу. Компьютер Оли может начать ретрансляцию данных не раньше, чем им будет получен 1 Мбайт этих данных. Сколько Кбайт успеет скачать Маша к моменту окончания скачивания информации Олей?
75. Книга, состоящая из 1360 страниц, занимает 40 Мбайт. Часть страниц книги является цветными изображениями в формате 320640 точек. На одной странице книги с текстом размещается 1024 символа. Символы закодированы кодировкой ASCII. Количество страниц с текстом на 560 больше количества страниц с изображениями. Сколько цветов используется в палитре изображений?
smurfi4k ждёт твоего решения. Ответь на вопрос и заработай баллы.
Новые вопросы в Информатика
ДАЮ 85 БАЛОВ Построение таблиц истинности для логических выражений
Задано полное имя файла C:\Users\Desktop\Инструкция.docx Запишите имя каталога, в котором находится этот файл:
пожалуйста прямо сейчас нужно очень На схему квеста к заданию 3 добавлена информация о расстоянии в метрах между экспонатами. Представьте данную инфор … мацию в табличной форме.
1.Составьте многоуровневую иерархическую файловую структуру вашего персонального компьютера. 2. Опишите составляющие базового программного обеспечения … и сервисного программного обеспечения.
СРОЧНО. Составить на Python: 1. Пользователь вводит число – используя целочисленное деление выведите сумму двух последних цифр числа (например поль … зователь вводит 2345, вывод 9 (4+5)). 2. Пользователь вводит фразу. Добавьте вначале фразу «все говорят:», а в конце «а ты возьми и купи слона» (Например, Ввод: Мама мыла раму; Вывод: Все говорят: «мама мыла раму», а ты возьми и купи слона). 3. Сформируйте список из слов введённой пользователем фразы. Выведите все нечётные элементы списка. (Например, Ввод: «Мама мыла раму» Вывод: [‘Мама’, ‘раму’]).
Сергей собирает многоступенчатые ракеты. Для большей точности измерений параметров полета на каждой ступени ракеты он написал её мощность. Но он сове … ршенно забыл, что мощности ступеней любой ракеты должны строго возрастать. К примеру, мощности ступеней ракеты могут принимать значения 147, а 324-не могут Собирать новую ракету Сережа не хочет, однако он может вытащить некоторые ступени, не меняя порядка оставшихся. К примеру, из ракеты с мощностями ступеней 1834 можно получить ракету 134, а ракету 143 и 183 получить нельзя. Помогите Сергею вытащить минимальное количество ступеней так, чтобы мощность остальных ступеней строго возрастала У Сергея 4 ракеты . В таблице ниже приведена последовательность мощностей её ступеней 1-53423 2-163258 3-467567128 4-2535347384967 Могут существовать несколько вариантов ответа на 1 ракету (ответ должен иметь как можно большую длину иметь) Пожалуйста помогите, очень пожалуйста
разрешающая способность экрана,
Во всех подобных задачах требуется найти ту или иную величину.
Видеопамять - это специальная оперативная память, в которой формируется графическое изображение.
Объем видеопамяти рассчитывается по формуле: V=I*X*Y, где I – глубина цвета отдельной точки, X, Y – размеры экрана по горизонтали и по вертикали (произведение х на у – разрешающая способность экрана).
Экран дисплея может работать в двух основных режимах: текстовом и графическом .
В графическом режиме экран разделяется на отдельные светящиеся точки, количество которых зависит от типа дисплея, например 640 по горизонтали и 480 по вертикали. Светящиеся точки на экране обычно называют пикселями , их цвет и яркость может меняться. Графические режимы характеризуются такими показателями как:
- разрешающая способность (количество точек, с помощью которых на экране воспроизводится изображение) - типичные в настоящее время уровни разрешения 800*600 точек или 1024*768 точек.
- глубина цвета (количество бит, используемых для кодирования цвета точки), например, 8, 16, 24, 32 бита. Каждый цвет можно рассматривать как возможное состояние точки, Тогда количество цветов, отображаемых на экране монитора может быть вычислено по формуле K=2I , где K – количество цветов, I – глубина цвета или битовая глубина.
Кроме перечисленных выше знаний учащийся должен иметь представление о палитре:
- палитра (количество цветов, которые используются для воспроизведения изображения).
Виды информации и способы представления ее в компьютере.
В компьютере все виды информации кодируются на машинном языке, в виде логических последовательностей нулей и единиц.
Информация в компьютере представлена в двоичном коде, алфавит которого состоит из двух цифр (0 и 1). Каждая цифра машинного двоичного кода несет количество информации, равное 1 бит.
Например. Латинская буква А представлена в двоичном коде – 01000001.
Русская буква А представлена в двоичном коде - 10000000.
0 - 00110000
1 – 00110001
Задачи на кодирование информации:
уровень 1 - легкие (элементарные)
уровень 2 - простые
уровень 3 - средней сложности
1. Определить размер (в байтах) цифрового аудио-файла, время звучания которого составляет 10 секунд при частоте дискретизации 22,05 кГц и разрешении 8 бит. Файл сжатию не подвержен. Формула для расчета размера (в байтах) цифрового аудиофайла (монофоническое звучание): (частота дискретизации в Гц)*(время записи в секундах)*(разрешение в битах)/8. 2. В распоряжении пользователя имеется память объемом 2,6 Мб. Необходимо записать цифровой аудио-файл с длительностью звучания 1 минута. Какой должна быть частота дискретизации и разрядность? 3. Объем свободной памяти на диске — 5,25 Мб, разрядность звуковой платы — 16. Какова длительность звучания цифрового аудио-файла, записанного с частотой дискретизации 22,05 кГц? 4. Определить объем памяти для хранения цифрового аудио-файла, время звучания которого составляет две минуты при частоте дискретизации 44,1 кГц и разрешении 16 бит.Решение:
44100*(2*60)*16=
10МБайт
Ответ:
5. Одна минута записи цифрового аудио-файла занимает на диске 1,3 Мб, разрядность звуковой платы — 8. С какой частотой дискретизации записан звук?
6. Две минуты записи цифрового аудио-файла занимают на диске 5,1 Мб. Частота дискретизации — 22050 Гц. Какова разрядность аудио-адаптера?
7. Объем свободной памяти на диске — 0,01 Гб, разрядность звуковой платы — 16. Какова длительность звучания цифрового аудио-файла, записанного с частотой дискретизации 44100 Гц?
8. Оцените информационный объем моноаудиофайла длительностью звучания 1 мин. если "глубина" кодирования и частота дискретизации звукового сигнала равны соответственно:
а) 16 бит и 8 кГц;
б) 16 бит и 24 кГц.
Решение:
а).
1) Информационный объем звукового файла длительностью в 1 секунду равен:
16 бит х 8 000 = 128000 бит = 16000 байт = 15,625 Кбайт/с
2) Информационный объем звукового файла длительностью 1 минута равен:
15,625 Кбайт/с х 60 с = 937,5 Кбайт
б).
1) Информационный объем звукового файла длительностью в 1 секунду равен:
16 бит х 24 000 = 384000 бит = 48000 байт = 46,875 Кбайт/с
2) Информационный объем звукового файла длительностью 1 минута равен:
46,875 Кбайт/с х 60 с =2812,5 Кбайт = 2,8 Мбайт
Ответ: а) 937,5 Кбайт; б) 2,8 Мбайт
9. Какой объем памяти требуется для хранения цифрового аудио-файла с записью звука высокого качества при условии, что время звучания составляет 3 минуты? (таблица)
10. Цифровой аудио-файл содержит запись звука низкого качества (звук мрачный и приглушенный). Какова длительность звучания файла, если его объем составляет 650 Кб? (таблица)
Потоки и паросочетания
ограничение по времени на тест: 5 секунд
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дана система из узлов и труб, по которым может течь вода. Для каждой трубы известна наибольшая скорость, с которой вода может протекать через нее. Известно, что вода течет по трубам таким образом, что за единицу времени в каждый узел (за исключением двух — источника и стока) втекает ровно столько воды, сколько из него вытекает.
Ваша задача — найти наибольшее количество воды, которое за единицу времени может протекать между источником и стоком, а также скорость течения воды по каждой из труб.
Трубы являются двусторонними, то есть вода в них может течь в любом направлении. Между любой парой узлов может быть более одной трубы.
В первой строке записано натуральное число N — количество узлов в системе (2 ≤ N ≤ 100). Известно, что источник имеет номер 1, а сток номер N. Во второй строке записано натуральное M (1 ≤ M ≤ 5000) — количество труб в системе. Далее в M строках идет описание труб. Каждая труба задается тройкой целых чисел Ai, Bi, Ci, где Ai, Bi — номера узлов, которые соединяет данная труба (Ai ≠ Bi), а Ci (0 ≤ Ci ≤ 104) — наибольшая допустимая скорость течения воды через данную трубу.
В первой строке выведите наибольшее количество воды, которое протекает между источником и стоком за единицу времени. Далее выведите M строк, в каждой из которых выведите скорость течения воды по соответствующей трубе. Если направление не совпадает с порядком узлов, заданным во входных данных, то выводите скорость со знаком минус. Числа выводите с точностью 10^(-3).
входные данные
выходные данные
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Найдите минимальный разрез между вершинами 1 и n в заданном неориентированном графе.
На первой строке входного файла содержится n (2 ≤ n ≤ 100) — число вершин в графе и m (0 ≤ m ≤ 400) — количество ребер. На следующих m строках входного файла содержится описание ребер. Ребро описывается номерами вершин, которые оно соединяет, и его пропускной способностью (положительное целое число, не превосходящее 10 000 000), при этом никакие две вершины не соединяются более чем одним ребром.
На первой строке выходного файла должны содержаться количество ребер в минимальном разрезе и их суммарная пропускная способность. На следующей строке выведите возрастающую последовательность номеров ребер (ребра нумеруются в том порядке, в каком они были заданы во входном файле).
входные данные
выходные данные
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Две улиточки Маша и Петя сейчас находятся в на лужайке с абрикосами и хотят добраться до своего домика. Лужайки пронумерованы числами от 1 до n и соединены дорожками (может быть несколько дорожек соединяющих две лужайки, могут быть дорожки, соединяющие лужайку с собой же). В виду соображений гигиены, если по дорожке проползла улиточка, то вторая по той же дорожке уже ползти не может. Помогите Пете и Маше добраться до домика.
В первой строке файла записаны четыре целых числа — n, m, s и t (количество лужаек, количество дорог, номер лужайки с абрикосами и номер домика). В следующих m строках записаны пары чисел. Пара чисел (x, y) означает, что есть дорожка с лужайки x до лужайки y (из-за особенностей улиток и местности дорожки односторонние). Ограничения: 2 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5, s_≠_t .
Если существует решение, то выведите YES и на двух отдельных строчках сначала последовательность лужаек для Машеньки (дам нужно пропускать вперед), затем путь для Пети. Если решения не существует, выведите NO. Если решений несколько, выведите любое.
входные данные
выходные данные
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Двудольным графом называется неориентированный граф (V, E),E ⊆ V × V такой, что его множество вершин V можно разбить на два множества A и B, для которых ∀(e1, e2) ∈ E e1 ∈ A, e2 ∈ B и A ∪ B = V,A ⋂ B = ∅ .
Паросочетанием в двудольном графе называется любой набор его несмежных рёбер, то есть такой набор S ⊆ E , что для любых двух рёбер e1 = (u1, v1), e2 = (u2, v2) из S u1 ≠ u2 и v1 ≠ v2.
Ваша задача — найти максимальное паросочетание в двудольном графе, то есть паросочетание с максимально возможным числом рёбер.
В первой строке записаны два целых числа n и m (1 ≤ n, m ≤ 250), где n — число вершин в множестве A, а m — число вершин в B.
Далее следуют n строк с описаниями рёбер — i-я вершина из A описана в (i + 1)-й строке файла. Каждая из этих строк содержит номера вершин из B, соединённых с i-й вершиной A. Гарантируется, что в графе нет кратных ребер. Вершины в A и B нумеруются независимо (с единицы). Список завершается числом 0.
Первая строка выходного файла должна содержать одно целое число l — количество рёбер в максимальном паросочетании. Далее следуют l строк, в каждой из которых должны быть два целых числа uj и vj — концы рёбер паросочетания в A и B соотвественно.
входные данные
выходные данные
E. Шахматная доска
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Вася любит играть в необычные шахматы. Его братишка Коля был еще очень маленький. Как-то раз, когда Вася вернулся из школы, он увидел, что его любимую шахматную доску кто-то перекрасил. Вася не сильно разозлился на Колю, потому что очень любил своего брата. Так как у них дома были только черная и белая краски, каждая клетка доски была покрашена в один из этих двух цветов.
Вам предстоит помочь Васе. Задано испорченное Колей шахматное поле. Вам необходимо определить, за какое минимальное количество действий Вася сможет перекрасить доску так, чтобы она стала шахматной.
В первой строке входного файла записаны два целых числа: n и m (1 ≤ n, m ≤ 100) — количество строчек и количество столбцов шахматного поля соответственно.
В следующих n строках записано поле, в каждой строке по m символов. Каждая строка входного файла описывает одну строку шахматного поля. W соответствует белой клетке, B — черной.
В выходной файл нужно вывести число p, количество действий, которое потребуется Васе, чтобы его доска снова стала шахматной. В следующих p строках описаны действия. Каждое действие описано тремя параметрами: тип диагонали, координаты клетки и цвет. Тип диагонали — это число 1 или 2. Координаты клетки — это два целых числа: строка и столбец одной из клеток, которую покрасили этим действием. Цвет — это символ W или B, белый и черный соответственно.
входные данные
выходные данные
входные данные
выходные данные
входные данные
выходные данные
F. Двигаем предметы
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
На плоскости расположены n предметов, их нужно переместить в заданные n позиций. При этом не важно, какой предмет какую из них займет. Для каждого предмета известна максимальная скорость, с которой его можно перемещать, при этом перемещать все предметы можно одновременно.
Найдите минимальное время, за которое можно переместить предметы на заданные места.
В первой строке записано число n (1 ≤ n ≤ 50), в следующих n строках содержатся описания предметов, в i-ой из которых, находится три числа координаты xi, yi (1 ≤ xi, yi ≤ 1000) и максимальная скорость vi (1 ≤ vi ≤ 10) i-ого предмета соответственно. В следующих n строках содержатся описания финальных позиций, в i-ой из которых, заданы координаты ai, bi (1 ≤ ai, bi ≤ 1000) i-ой финальной позиции.
Выведите одно число — минимальное время, за которое можно переместить предметы. Погрешность не более 10^(-4).
входные данные
выходные данные
входные данные
выходные данные
входные данные
выходные данные
входные данные
выходные данные
G. Великая стена
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
У короля Людовика двое сыновей. Они ненавидят друг друга, и король боится, что после его смерти страна будет уничтожена страшными войнами. Поэтому Людовик решил разделить свою страну на две части, в каждой из которых будет властвовать один из его сыновей. Он посадил их на трон в города A и B, и хочет построить минимально возможное количество фрагментов стены таким образом, чтобы не существовало пути из города A в город B.
Страну, в которой властвует Людовик, можно упрощенно представить в виде прямоугольника m × n. В некоторых клетках этого прямоугольника расположены горы, по остальным же можно свободно перемещаться. Кроме этого, ландшафт в некоторых клетках удобен для строительства стены, в остальных же строительство невозможно.
При поездках по стране можно перемещаться из клетки в соседнюю по стороне, только если ни одна из этих клеток не содержит горы или построенного фрагмента стены.
В первой строке выходного файла должно быть выведено минимальное количество фрагментов стены F, которые необходимо построить. Далее нужно вывести карту в том же формате, как во входном файле. Клетки со стеной обозначьте символом «+».
Если невозможно произвести требуемую застройку, то выведите в выходной файл единственное число -1.
входные данные
выходные данные
входные данные
выходные данные
входные данные
выходные данные
H. Космические перевозки
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: bring.in
вывод: bring.out
К 3141 году человеческая цивилизация распространилась по всей галактике. Для перехода от одной звездной системы к другой используются специальные гипертуннели. Чтобы использовать гипертуннель, нужно прилететь в специальное место рядом с исходной звездой используя ваш космический корабль, активировать гипердрайв, пролететь через гипертуннель, выйти рядом со звездой назначения и лететь на нужную вам планету. Весь процесс занимает ровно один день. Небольшой недостаток системы состоит в том, что по каждому туннелю может пролететь только один космический корабль в день.
Вы работаете в транспортном отделе компании «Intergalaxy Business Machines». Сегодня утром ваш начальник дал вам новую задачу. Чтобы запустить чемпионат по программированию IBM, нужно доставить K суперкомпьютеров от Земли, где находится штаб-квартира компании на планету Эйсиэм.
Поскольку суперкомпьютеры очень большие, нужно, для перевозки одного нужен целый космический корабль. Вас попросили найти план доставки суперкомпьютеров, который позволит доставить все компьютеры за минимальное число дней. Поскольку IBM является очень мощной корпорацией, можете считать, что каждый раз, когда вам нужен какой-то гипертуннель, он к вашим услугам. Однако вы все равно можно использовать каждый туннель только один раз в день.
Первая строка входного файла содержит N — число звездных систем в галактике, M — число туннелей, K — число суперкомпьютеров для доставки, S — номер солнечной системы, где находится планета Земля и T — номер звездной системы, где находится Планета Эйсиэм (N ≤ 50>, M ≤ 200>, K ≤ 50>, S, T ≤ N>, S ≠ T>)
Следующие M строк содержат по два разных целых числа и описывают туннели. Для каждого туннеля даются номера звездных систем, которые он соединяет. По туннелю можно путешествовать в обоих направлениях, но помните, что каждый день только один корабль может использовать туннель. В частности, два судна не могут одновременно проходить через один и тот же туннель в противоположных направлениях. Ни один туннель не соединяет звезду с самим собой и две звезды связаны не более чем одним туннелем.
В первой строке выходного файла выведите L — наименьшее число дней, необходимых для доставки K суперкомпьютеров от звездной системы S до звездной системы T с использованием гипертуннелей.
Следующие L строк должны описывать процесс. Каждая строка должна начинаться с Ci — числа кораблей, которые отправляются из одной системы в другую в этот день. Далее должны следовать Ci пар целых чисел, пара A, B означает, что корабль номер A перемещается из текущей звездной системы в звездную систему B.
входные данные
выходные данные
I. Групповой турнир
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
В нашем капиталистическом и меркантильном мире всё решают деньги, и даже спорт не стал исключением. Все команды-участницы уже купили себе нужное количество очков в следующем сезоне, и местной федерации хоккея осталось только распределить результаты предстоящих игр. Однако, некоторые команды не поскупились и помимо покупки очков также купили ещё и результаты некоторых игр. Поначалу в федерации думали, что это им только упростит задачу: чем для большего числа игр результаты уже определены, тем меньше работы остаётся им. Но позже они поняли, что ошиблись. Они попросили вас стать участником их коррупционной схемы и помочь с распределением результатов игр предстоящего сезона.
Местный хоккейный турнир проходит по круговой системе: в турнире участвуют N команд и каждая команда играет с каждой ровно одно игру. За игру команды получают очки по следующим правилам:
Если победителя удалось выявить в основное время матча, то ему достаётся 3 очка, а проигравшему — 0. Если основное время закончилось вничью и для выявления победителя понадобилось дополнительное время (овертайм), то победителю дают 2 очка, а проигравшему — 1 очко. Овертайм не ограничен во времени и длится до тех пор, пока одна из команд не забьёт гол. По итогам турнира очки команды определяются как сумма её очков по всем сыгранным играм.
В первой строке входного файла содержится целое число N — количество участников турнира (2 ≤ N ≤ 100). Команды занумерованы числами от 1 до N.
Следующие N строк файла содержат по N символов и представляют собой турнирную таблицу на данный момент. Символ aij в строке i (1 ≤ i ≤ N) на позиции j (1 ≤ j ≤ N) означает результат игры команды номер i с командой номер j и может быть одним из:
В выходной файл выведите полностью заполненную турнирную таблицу в формате, аналогичном формату входного файла.
Гарантируется, что решение существует. Если решений несколько, то можно вывести любое из них.
входные данные
выходные данные
ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Несколько чистоплотных тараканьих семей хотят поселиться в однокомнатной квартире. Квартира состоит из большой комнаты и кухни, соединѐнных узким коридором. Тараканов совершенно не интересует коридор сам по себе, однако они хотят иметь доступ и к кухне, и к комнате. Для того чтобы тараканья семья имела такой доступ, ей нужен индивидуальный транспортный путь через коридор. Тараканы — умные насекомые, поэтому они решили составить план коридора и определить, какое максимальное количество транспортных путей можно проложить через коридор.
В тараканьем плане коридор представляется бесконечной в обе стороны полосой шириной W сантиметров. Тараканы начертили прямоугольную систему координат, ось X которой параллельна направлению коридора. Хозяева квартиры расставили в коридоре некоторое количество массивных предметов. Каждый предмет является прямоугольником со сторонами, параллельными осям координат, и вершинами с целыми координатами в сантиметрах. Границы коридора задаются уравнениями y = 0 и y = W. На координатной плоскости тараканы нарисовали квадратную сетку со стороной одной клетки, равной 1 см, начиная от границы коридора.
Тараканы договорились, что каждый транспортный путь является бесконечной в обе стороны цепью квадратных клеток. Цивилизованные тараканы никогда не прыгают, поэтому две подряд идущие клетки в этой цепи должны быть соседними по стороне. Цивилизованные тараканы всегда бегают по полу, поэтому никакая клетка цепи не может пересекаться с хозяйской вещью или выходить за пределы коридора. Тараканы не любят бегать по кругу, поэтому все клетки цепи различны. Тараканы не хотят давки в час пик, поэтому они требуют, чтобы различные транспортные пути не пересекались, то есть не имели общих клеток. Транспортный путь должен соединять кухню и комнату, поэтому разные концы цепи должны уходить в разные стороны коридора.
Ваша задача — определить максимальное количество транспортных путей, которые можно проложить через коридор.
В первой строке входного файла записано два целых числа N и W. N — количество предметов в коридоре, W — ширина коридора в сантиметрах (0 ≤ N ≤ 5000, 0 < W ≤ 10^9).
Каждая из последующих N строк описывает одну из хозяйских вещей. Она содержит четыре целых числа X1, Y1, X2, Y2 — координаты двух противоположных углов прямоугольника ( -10^9 ≤ X1 < X2 ≤ 10^9, 0 ≤ Y1 < Y2 ≤ W). Предметы, расставленные в коридоре, могут пересекаться.-
В выходной файл нужно вывести одно целое число — максимально возможное количество транспортных путей.
Читайте также: