Выбрать слово имеющее наименьшую сумму кодов

XV Олимпиада среди школьников г. Петрозаводска по Информатике

Решения олимпиадных задач

Теоретический тур (6 задач)

Задача 1. “Сумма кодов”.

Выбрать слово, имеющее наименьшую сумму кодов символов в таблице кодировки ASCII (используются строчные буквы). Ответ обоснуйте.

Как известно, в таблице кодировки ASCII английские буквы следуют в алфавитном порядке.

Поэтому каждой букве, вместо кода ASCII, можно сопоставить ее алфавитный номер, номера букв суммировать и суммы сравнивать. Получается, что наименьшую сумму кодов символов имеет слово «bear» (2+5+1+18).

Задача 2. “Два берега”.

К реке подошли два мальчика и один взрослый. У берега они увидели маленькую лодку, вмещавшую либо двух мальчиков, либо одного взрослого. Какое минимальное время требуется на переправу, если каждая поездка через реку (в одну сторону) занимает 20 минут? Ответ обоснуйте.

Потребуется 5 переправ, то есть 100 минут, то есть 1 час 40 мин. Переправы такие: 2 мальчика, обратно 1 мальчик, туда 1 взрослый, обратно 1 мальчик, туда 2 мальчика. Для доказательства, что этот алгоритм оптимален, необходимо перебрать все возможные варианты из 5 шагов. Вариантов много, но лишь один из них решает задачу.

Задача 3. “Приветствие племен”.

Алфавит одного племени состоит из Х символов, алфавит другого содержит в четыре раза больше символов. Племена обменялись приветствиями. Каждое по 100 символов. На сколько бит информации одно приветствие больше другого? Ответ обоснуйте.

На 200 бит. Обозначим за N количество букв в первом алфавите. Тогда каждая буква сообщения будет нести log2N бит информации. Во втором алфавите 4*N букв и log2 (4*N) бит на букву.

Тогда разность количеств информации в сообщениях:

100*log2 (4*N) — 100*log2N = 100*(2+ log2N) — 100*log2N = 100*2 = 200.

Организаторы: Комитет по образованию, Петрозаводский государственный университет Спонсоры Олимпиады: компания «Ноутис», корпорация «Крафтвей», LandMark, Диаско, компания ОФИСКЛАБ, магазин «Экслибрис», Карельский Региональный Центр ФИО, Администрация г. Петрозаводска, РЦ НИТ ПетрГУ XV Олимпиада среди школьников г. Петрозаводска по Информатике http://media.karelia.ru/

olimp/ Задача 4. “Количество команд”.

Программист написал программу на языке машинных команд, которая последовательно размещается в памяти начиная с нулевого адреса. Каждая команда занимает 4 байта памяти. Шестнадцатеричный адрес последней команды в программе равен 28. Сколько команд содержит эта программа? Ответ обоснуйте.

11 команд. Объяснение: Адрес последней команды 2816=4010 – это адрес байта, с которого начинается последняя команда (именно начинается, так как сказано, что адрес первой команды равен 0 – это адрес первого байта памяти). Значит, предыдущая команда закончилась байтом с адресом 39, и тогда последний байт последней команды будет иметь адрес 43. А так как адреса отсчитываются с 0, то всего в программе 44 байта, то есть 11 команд.

Задача 5. “Новобранцы”.

На первом построении вновь призванные в армию солдаты построились в шеренгу. По команде старшины «Напра-во!» некоторые солдаты повернулись направо, а некоторые — налево (на 90°). Каждый солдат, оказавшийся лицом к лицу со своим соседом считает, что совершил ошибку и разворачивается на 180°.

Ваша задача — помочь старшине, объяснив, будут ли солдаты вертеться бесконечно или можно указать максимально возможное количество разворотов новобранцев. Возможна ли (если да, при каких условиях) ситуация, когда в конце концов все солдаты построятся правильно? Ответ обоснуйте.

Для того, чтобы ответить на первый вопрос, применим индукцию. Если первый (или последний) солдат уже стоит спиной к строю (далее будем обозначать это положение «в лес»), то он, естественно, больше уже не повернётся. Если первый солдат стоит лицом «к строю», а второй «в лес», то в результате разворота, первый солдат будет смотреть «в лес». Предположим, что это справедливо и для случая, когда i — 1 солдат смотрят «в строй», а i-й — «в лес». Очевидно, если i солдат смотрят «в строй», а i + 1 — «в лес», то последовавшим разворотом доказываем индукцию.

Далее отсекаем крайних солдат и повторяем рассуждения. Поскольку количество новобранцев конечно, процесс конечен. Ответ: «Да, можно». Заметим, что формулировка не требует вывода формулы для оценки максимального количества разворотов.

Ситуация, когда в конце концов солдаты построятся правильно, возможна в единственном случае — если они все изначально повернутся в правильном направлении. В любом другом случае (это следует из рассуждений выше) часть солдат будут смотреть налево, часть — направо.

Задача 6. “ Лягушка”.

Квадратное лесное болото разделено на 8*8 одинаковых клеток. На одной из клеток сидит лягушка, а над какой-то другой клеткой летает комар. Лягушка хочет съесть комара, а комар старается от нее улететь. Перемещаются лягушка и комар по очереди, первый ход за лягушкой. За один прыжок лягушка перемещается на любую из клеток по горизонтали или вертикали, не обязательно соседнюю. Комар за один перелет перемещается на одну из 8 соседних клеток. Если лягушка в прыжке пролетает через клетку, над которой находится комар, или прыгает на клетку, над которой летает комар, то она съедает комара. В последнем прыжке лягушка может перемещаться по диагонали на одну клетку. Требуется составить оптимальный алгоритм перемещения лягушки для того, чтобы съесть комара. Отсчет начинается с левого верхнего угла. Ответ обоснуйте.

Организаторы: Комитет по образованию, Петрозаводский государственный университет Спонсоры Олимпиады: компания «Ноутис», корпорация «Крафтвей», LandMark, Диаско, компания ОФИСКЛАБ, магазин «Экслибрис», Карельский Региональный Центр ФИО, Администрация г. Петрозаводска, РЦ НИТ ПетрГУ XV Олимпиада среди школьников г. Петрозаводска по Информатике http://media.karelia.ru/

Алгоритм:

1. Получить координаты комара (xk, yk).

2. Если координаты комара совпадают с координатами лягушки (xl, yl) перейти к п. 5

3. Если xk=xl или yk=yl или (|xk — xl| = 1 и |yk — yl| = 1), то xl=xk, yl=yk, перейти к п. 5

4. Если (|xk — xl| |yk — yl|), то xl = xl + (xk — xl)/|xk — xl|*(xk – xl -1), иначе yl = yl + (yk — yl)/|yk

5. Съесть комара

Практический тур (5 задач)

Задача 1. “Фишки”.

Рассмотрим шахматную доску размером NxN. Какое наименьшее число фишек нужно поставить на клетки шахматной доски для того, чтобы на каждой прямой, проходящей через центр произвольной клетки и параллельной каким-либо сторонам или диагоналям доски, стояла хотя бы одна фишка? (Фишки ставятся в центры клеток).

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

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

При четном N ответ будет 2*N, при N нечетном – 2*N+1. Расположение такого количества фишек представлено на рис 1,2.

Доказательство того, что что меньшим числом обойтись нельзя, проще для четного N; на каждой прямой, параллельной одной диагонали, должно стоять по фишке, а на самой диагонали – две (в углах).

Другое доказательство: на каждой показанной на рисунках прямой должно стоять по фишке. Именно это доказательство переделывается на случай нечентного N (рис. 2): кроме 2N-2 прямых (на каждой по фишке), следует рассмотреть еще шесть прямых, соединяющих центры клеток A,B,C,D; на них нужно потратить еще не менее 3 фишек.

Осталось отдельно рассмотреть случай N=1. Здесь формула не работает, но программа должна вывести число 1.

Организаторы: Комитет по образованию, Петрозаводский государственный университет Спонсоры Олимпиады: компания «Ноутис», корпорация «Крафтвей», LandMark, Диаско, компания ОФИСКЛАБ, магазин «Экслибрис», Карельский Региональный Центр ФИО, Администрация г. Петрозаводска, РЦ НИТ ПетрГУ XV Олимпиада среди школьников г. Петрозаводска по Информатике http://media.karelia.ru/

Заведем для заданного слова массив A частот появления букв в слове. Т.е. для каждой буквы элемент массива A с номером, равным коду символа, содержит число – количество раз, которое встретился данный символ. Теперь заведем для остальных слов такие же массивы. То слово, у которого все элементы массива частот меньше либо равны элементам A, и будут искомыми словами, которые требуется вывести.

Задача 3. “Змейка”.

На шахматной доске размером NxN расставлено k пронумерованных фишек. Ежик, который собирает эти фишки, выходит из клетки с координатами (1,1) и должен собрать все фишки в порядке возрастания их номеров. Из клетки с координатами (x,y) ежик может переместиться только в одну из четырех соседних, т.е. в одну из клеток с координатаОрганизаторы: Комитет по образованию, Петрозаводский государственный университет Спонсоры Олимпиады: компания «Ноутис», корпорация «Крафтвей», LandMark, Диаско, компания ОФИСКЛАБ, магазин «Экслибрис», Карельский Региональный Центр ФИО, Администрация г. Петрозаводска, РЦ НИТ ПетрГУ XV Олимпиада среди школьников г. Петрозаводска по Информатике http://media.karelia.ru/

olimp/ ми (x+1,y), (x-1,y), (x,y+1) или (x,y-1), конечно с соблюдением условия, что он не должен выходить за границы доски. Требуется определить, какое минимальное количество ходов нужно сделать, чтобы собрать все фишки. Если ежик проходит через клетку, где содержится фишка с большим номером, чем он сейчас должен взять, то ничего не происходит (он просто проходит, а фишка остается стоять).

Вводятся два числа N и k. Затем вводятся k пар координат (x,y) соответствующих фишек, т.е.

сначала для первой фишки, затем для второй фишки и т.д.

Ответом должно быть единственное число – минимальное количество шагов, которое потребуется для сбора всех фишек в порядке возрастания их номеров.

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

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

Пусть перед сбором очередной фишки ежик находится в клетке a (x,y), а фишка расположена в клетке b (x1,y1). Необходимо определить какое количество ходов ему надо сделать, чтобы добраться до фишки. Это сделать довольно просто, т.к. ему, как бы он не шел, нужно пройти через все столбцы, которые находятся между стартовым и конечным (так он попадет в столбец с фишкой).

А теперь двигаясь в этом столбце ему нужно либо подняться, либо опуститься до фишки, т.е.

пройти через все строки между стартовой и конечной. В результате получаем, что для перехода из клетки a (x,y) в клетку b (x1,y1) нужно сделать x-x1 шагов при переходе между столбцами и yy1шагов при переходе между строками. Значит, к общей сумме нужно добавлять сумму модулей разности между соответствующими координатами. Последовательно выполняя суммирование для клеток, в порядке их обхода, и получаем ответ.

x=1;y=1; //стартовая клетка sum=0;

> Задача 4 «Густой лес»

На плоскости во всех точках с целочисленными координатами от 1 до N стоят деревья — всего N деревьев. Путник находится в точке с координатами (x1,y1), где x1,y10 и хоть одна из этих координат больше N (чтобы не оказаться в самом лесу). Требуется определить, видно ли путника из Организаторы: Комитет по образованию, Петрозаводский государственный университет Спонсоры Олимпиады: компания «Ноутис», корпорация «Крафтвей», LandMark, Диаско, компания ОФИСКЛАБ, магазин «Экслибрис», Карельский Региональный Центр ФИО, Администрация г. Петрозаводска, РЦ НИТ ПетрГУ XV Олимпиада среди школьников г. Петрозаводска по Информатике http://media.karelia.ru/

olimp/ точки с координатами (0,0). Путника не видно, если на прямой, проходящей через точку (0,0) и точку (x1,y1), есть хоть одно дерево.

На вход подается три целых числа – N, x1, y1.

Требуется вывести YES, если путника видно и NO иначе.

Пример входных данных1 Пример входных данных2 Пример выходных данных1 Пример выходных данных2 NO YES Путника не будет видно только в том случае, если на прямой, соединяющей точку (0,0) и точку (x1,y1) есть хотя бы одно дерево. Можно было бы перебрать все точки леса и проверять данное условие. А можно поступить следующим образом. Для того, чтобы точки (x1,y1) и (x2,y2) лежали на одной прямой угловые коэффициенты y1/x1 и y2/x2 должны быть равны. Если сократить дробь y1/x1 и в получившейся дроби числитель и знаменатель будут не больше, чем n, значит, есть дерево на прямой соединяющей точку (0,0) и точку (x1,y1). Т.е. задача сводится к сокращению дроби, и если оба коэффициента не больше n, то путника не видно, иначе – видно. Для сокращения можно использовать алгоритм Евклида нахождения наибольшего общего делителя.

long nod (long a, long b) < long ost;

Для решения задачи удобно завести массив, где указывать был подход strike, spare или простой (без бонуса). Для того, чтобы определить сколько очков после очередного подхода необходимо проверить условия в следующем порядке

1. два предыдущих подхода были strike

2. предыдущий подход был strike

3. предыдущий подход был spare

4. предыдущий подход не дает бонусных очков и в соответствии с этим прибавить необходимое число к итоговой сумме.

else if ((x+y)= =10) a[i+1]=2;

Организаторы: Комитет по образованию, Петрозаводский государственный университет Спонсоры Олимпиады: компания «Ноутис», корпорация «Крафтвей», LandMark, Диаско, компания ОФИСКЛАБ, магазин «Экслибрис», Карельский Региональный Центр ФИО, Администрация г. Петрозаводска, РЦ НИТ ПетрГУ XV Олимпиада среди школьников г. Петрозаводска по Информатике http://media.karelia.ru/

olimp/ > else if (a[i]= =2) sum+=2*x+y;

> Организаторы: Комитет по образованию, Петрозаводский государственный университет Спонсоры Олимпиады: компания «Ноутис», корпорация «Крафтвей», LandMark, Диаско, компания ОФИСКЛАБ, магазин «Экслибрис», Карельский Региональный Центр ФИО, Администрация г. Петрозаводска, РЦ НИТ ПетрГУ

«Электронный журнал "Труды МАИ". Выпуск № 65 www.mai.ru/science/trudy/ УДК 519.24.001:512,643,5 Унифицированная интерфейсно-вычислительная платформа для систем интегральной модульной авионики Авакян А. »

«50 Прдаожение № 8. к Приказу от оОО. Jd '[jJJA'J № _ Санкт -Петербургский государственный университет ПРОГРАММА Междисциплинарного экзамена Основная образовательная программа магистратуры "Геоинформационное картограф. »

«Муниципальный этап всероссийской олимпиады по информатике, 9-11 класс 16 ноября 2016 г. Разбор задачи A. Нерасторопный секретарь Очевидно, что первую копию нужно сделать на самом быстром аппарате. В дальнейших рассуждениях будем считать, что мы вычли единицу из N, к ответу в конце прибавим min(x, y), а ко. »

«Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования "Поволжский государственный университет телекоммуникация и информатики" Одобрено методическим советом ПГУ. »

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ Федеральное государственное бюджетное образовательное учреждение высшего образования "ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ" Кафедра автоматической электросвязи Гребешков А.Ю. Организация и настройка локальн. »

«7С УДК 004.94:004.056 А.Б. Степанян, В.А. Дмитриев, В.К. Фисенко Объединенный институт проблем информатики НАН Беларуси, Беларусь Беларусь, 220012, г. Минск, ул. Сурганова, 6 Классификация угроз информационной безопасности автоматизированной системы A.B. St. »

«ИСКУССТВО ПРОГРАММИРОВАНИЯ ЯНВАРЬ-ФЕВРАЛЬ 2004 Никлаус Вирт От разработки языка программирования к созданию компьютера ACM Turing Award Lectures. The First Twenty Years 1966–1985 // ACM Press, 1987. Р. Богатырев, перевод с англ. Никлаус Вирт (Niklaus Wirth). »

«Вычислительные технологии Том 18, № 3, 2013 Численное моделирование устойчивости локализованных возмущений в течении Пуазейля А. В. Проскурин, А. М. Сагалаков Алтайский государственный университет, Барнаул, Россия e-mail: k210@list.ru П. »

«РОСЖЕЛДОР Федеральное государственное бюджетное образовательное учреждение высшего образования "Ростовский государственный университет путей сообщения" (ФГБОУ ВО РГУПС) РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ Б1.В.ОД.6 АВТОМАТИЗАЦИЯ И УПРАВЛЕНИЕ ТЕХНОЛОГИЧЕСКИМИ ПРОЦЕССАМИ И ПРОИЗВОДСТВАМИ Направление подготовки 09. »

2017 www.net.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.

Автор MaXon задал вопрос в разделе Прочее компьютерное

Выбрать слово,имеющее наименьшую сумму кодов символов в таблице кодировке ASCII: А)День Б)Пень В)Медь и получил лучший ответ

Ответ от Анна[гуру]
б) можно было и подсчитать

Теоретический тур школьного этапа

Всероссийской олимпиады школьников по информатике и ИКТ

Внимание! Если в задаче требуется предложить алгоритм, то записать его можно по-разному – лучше всего словесно или на псевдокоде, но можно и блок-схемой или на языке программирования, но это не желательно. Главное, чтобы были пояснения или комментарии. Удачи!

Задача 1. “Сумма кодов”. Выбрать слово, имеющее наименьшую сумму кодов символов в таблице кодировки ASCII (используются строчные буквы). Ответ обоснуйте.

Задача 2. “Два берега”. К реке подошли два мальчика и один взрослый. У берега они увидели маленькую лодку, вмещавшую либо двух мальчиков, либо одного взрослого. Какое минимальное время требуется на переправу, если каждая поездка через реку (в одну сторону) занимает 20 минут? Ответ обоснуйте.

Задача 3. “Приветствие племен”. Алфавит одного племени состоит из Х символов, алфавит другого содержит в четыре раза больше символов. Племена обменялись приветствиями. Каждое по 100 символов. На сколько бит информации одно приветствие больше другого? Ответ обоснуйте.

Задача 4. “Количество команд”. Программист написал программу на языке машинных команд, которая последовательно размещается в памяти начиная с нулевого адреса. Каждая команда занимает 4 байта памяти. Шестнадцатеричный адрес последней команды в программе равен 28. Сколько команд содержит эта программа? Ответ обоснуйте.

Задача 5. “Новобранцы”. На первом построении вновь призванные в армию солдаты построились в шеренгу. По команде старшины «Напра-во!» некоторые солдаты повернулись направо, а некоторые — налево (на 90°). Каждый солдат, оказавшийся лицом к лицу со своим соседом считает, что совершил ошибку и разворачивается на 180°.

Ваша задача — помочь старшине, объяснив, будут ли солдаты вертеться бесконечно или можно указать максимально возможное количество разворотов новобранцев. Возможна ли (если да, при каких условиях) ситуация, когда в конце концов все солдаты построятся правильно? Ответ обоснуйте.

Задача 6. “ Лягушка”. Квадратное лесное болото разделено на 8*8 одинаковых клеток. На одной из клеток сидит лягушка, а над какой-то другой клеткой летает комар. Лягушка хочет съесть комара, а комар старается от нее улететь. Перемещаются лягушка и комар по очереди, первый ход за лягушкой. За один прыжок лягушка перемещается на любую из клеток по горизонтали или вертикали, не обязательно соседнюю. Комар за один перелет перемещается на одну из 8 соседних клеток. Если лягушка в прыжке пролетает через клетку, над которой находится комар, или прыгает на клетку, над которой летает комар, то она съедает комара. В последнем прыжке лягушка может перемещаться по диагонали на одну клетку. Требуется составить оптимальный алгоритм перемещения лягушки для того, чтобы съесть комара. Отсчет начинается с левого верхнего угла. Ответ обоснуйте.

Практический тур школьного этапа

Всероссийской олимпиады школьников по информатике и ИКТ

Во всех задачах входные данные вводятся с клавиатуры, результат выводится на экран. Проверять корректность входных данных не нужно.

В школе продолжительность каждого урока 45 минут, а перемены между уроками – всего 5 минут. Первый урок начинается ровно в 8 часов утра. Напишите программу, отвечающую на вопрос «во сколько в этой школе заканчивается K -ый урок?»

Входные данные. Вводится одно натуральное число K , не превышающее 15.

Выходные данные. Выведите время окончания K -ого урока: сначала часы, потом минуты, разделяя их пробелом.

Задача B . (10 баллов) Расстановка ноутбуков

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

Входные данные. Вводится четыре натуральных числа, первые два задают размеры одного ноутбука, а следующие два — размеры второго. Числа не превышают 1000.

Выходные данные. Выведите два числа — размеры стола. Если возможно несколько ответов, выведите любой из них (но только один).

Задача C . (10 баллов) Карточки

Вася изготовил карточки, написав на них N первых заглавных букв латинского алфавита. Карточки Вася положил в стопку.

Дальше он берет первую сверху карточку и кладет ее в новую стопку. Далее вторую карточку он кладет вниз этой новой стопки, третью — наверх новой стопки, потом четвертую — опять вниз, следующую — наверх и т.д.

После этого оказалось, что карточки лежат строго по алфавиту, если просматривать их сверху вниз.

Напишите программу, которая выведет, в каком порядке карточки лежали в исходной стопке.

Входные данные. Вводится натуральное число N ( N не превышает 26).

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