ЙСОХРЭ СЦНКЭМХЙ

Usloviya zadach zaochnogo turaОлимпиада по компьютерным технологиямдля людей с ограниченными возможностямиРешения задач заочного тура.Организаторы олимпиады не ставили цели формально ("по-спортивному")расставить участников по местам. Поэтому жюри не готовило официальныхформальных решений. К большинству задач публикуются комментарии,содержащие ответ, возможное решение и дополнительную информацию,которая может оказаться интересной участникам олимпиады, а такжевсем, кого заинтересовали предложенные на ней задачи.1. Задачи по компьютерным технологиям.Используя простой графический редактор (например, Paint)нарисуйте "мишень": 10 концентрических окружностей с одинаковымрасстоянием между соседними окружностями и 2 перпендикулярные оси. (Напишите, как Вы это делали. Пришлите файлы, которые считаете необходимыми.)Раскладка английской клавиатуры QWERTY была придумана для СНИЖЕНИЯ скорости набора текста.Как Вы думаете, почему перед кем-то могла возникнуть такая задача?Комментарий. Вот пример правильного и полного ответа изодной работы."В 1867 году поэт, журналист и изобретатель Кристофер Лэтхэм Шолес (Christopher Latham Sholes) из Милуоки изобрёл печатную машинку. Клавиатура первых печатных машинок сильно отличалась от современной. Клавиши размещались в два ряда, а буквы на них шли в алфавитном порядке. Печатать можно было только заглавными буквами, а цифры 1 и 0 заменяли буквы "I" и "O". Размещение клавиш в алфавитном порядке имело один недостаток.При возрастании скорости печати молоточки печатной машинки не успеваливозвращаться на место и цеплялись друг за друга, грозя привести к поломкеустройства. Поскольку молоточки располагались по кругу, то чаще всего припечати заклинивало расположенные поблизости друг от друга литеры. КристоферШолес решил расположить литеры на клавишах так, чтобы буквы, образующиеустойчивые в английском языке пары, располагались как можно дальше друг отдруга. Так появилась на свет клавиатура "QWERTY". Позднее в 1936 годуПрофессор Август Дворак (August Dvorak) решил что клавиатура "QWERTY"совершенно не удобна и изобрёл свой вариант. Использование раскладки"по Двораку" позволяет более чем на 70% повысить скорость печати, но она неполучила широкого распространения так как клавиатура "QWERTY" уже сталастандартом, и использовалась на большинстве устройств. К тому же многие людипросто не захотели переучиваться. (При подготовке ответа использованы материалы с сайтаwww.atlant.ru/comar)"Дополнение жюри: расположение на клавиатуре далеко друг от друга литер,входящих в часто встречающиеся устойчивые комбинации, не только уменьшаетвероятность "перепутывания" рычажков печатной машинки при наборе этихкомбинаций (и заодно снижает скорость их набора, например, слово ПРО набираетсябыстрее, чем НАД), но и вообще снижает темп набора текста (и, тем самым,уменьшает вероятность "перепутывания" рычажков и в других случаях).Разница в 70% между скоростями набора с использованием раскладки клавиатурыQWERTY и изобретенной в 1936 году во многом объясняется тем, что используемыетогда печатные машинки были механическими, их клавиши были достаточно "тугими"(механический механизм машинки приводился в движение как раз силой нажатияна клавиши; кажущийся нам очевидным вариант решения проблемы перепутываниярычажков - механическая блокировка нажатия более одной кнопки - создавалдополнительные физические нагрузки для пользователя печатной машинки,а также увеличивал сложность и стоимость механизма, и поэтому не прижился),существовавшие тогда методики скоростной печати существенно отличалисьот современных. В современных условиях (на клавиатуре компьютера) разницаскорости печати скорее всего будет существенно меньше. Возможно,кодировка QWERTY окажется даже более предпочтительной (учитывая работупроизводителей компьютеров по эргономической адаптации клавиатур,ориентированность на такую раскладку многих компьютерных программ и игр,а также изменение языка, в том числе в результате массового применениякомпьютеров (и клавиатур с раскладкой QWERTY) для обработки текстов).Так что утверждение "Использование раскладки "по Двораку" позволяет болеечем на 70% повысить скорость печати" уже явно устарело, и применение этойраскладки в современных условиях скорее всего нецелесообразно.Компания "Super Modem" продает модем новойконструкции. В рекламе говорится, что пользуясь двумя такими новымиустройствами, Вася и Дима смогут по обычной телефонной сети передавать другдругу файлы со скоростью 1 мегабит в секунду.Стали бы Вы советовать им покупать такие модемы или сочли бы такие обещания явно нереальными?Леша решил купить себе видеокарту, поддерживающуюразрешение 10240*7680 (вместе с драйверами под все версии Windows).Он надеется увидеть на экране в десять раз более мелкие детали,чем раньше при разрешении 1024*768.Как Вы думаете, чего он не учитывает?Часто системные администраторы и опытные программистыактивно "не хвалят" неопытных друзей за использование в имени файларусских букв и пробелов, говоря, что от этого может произойти немало огорченийи неудобств.Согласны ли Вы с таким мнением?Если "да", то придумайте примеры таких неудобств.Если "нет" - поясните свои соображения.Комментарий.Современные файловые системы и программное обеспечение, очевидно, должныкорректно понимать русские буквы (как и символы прочих алфавитов,поддержка которых декларируется); разумеется, такая поддержка может бытьреализована с ошибками (впрочем, ошибки могут быть и в любом другомместе системы).Однако по историческим причинам предшественники многих современныхкомпьютерных систем были "латиноязычными", и "историческими" последствиямиэтого обстоятельства являются в том числе и некоторые проблемы, например:"старая" система, которая вообще не понимают кириллицу (или работаетвопреки предположениям разработчиков, возможно, непредсказуемым образом)современные" ОС понимают кириллицу по-разному (разные версии Windows,Unix, Apple, OS/2)при сбоях многим программам нелатинские имена создают проблемы длякорректной работы (например, EasyRecovery она же Tiramisu способна оченьхорошо восстанавливать диски после вирусной атаки или физических поломок,но почти бессильна с такими именами)немало приложений воспринимают аргументы командной строки, при передачеим файла, в имени которого есть пробел, программы зачастую воспринимают этотпробел как разделитель, и считают, что им передали более одного аргумента(первый --- до пробела, а второй --- после)при попытке скопировать файл с русскими буквами в названии на что-нибудь"не совсем компьютерное" (например, в записную книжку мобильного телефона)также часто возникает множество проблем (даже если и компьютер, и телефонпо отдельноти поддерживают кириллицу в названии файлов и записейсоответственно).Старые черно-белые фотографии предполагается сканироватьи хранить на компакт диске.а) Укажите минимальное оптическое разрешение сканера,который для этого необходим (фотографии предполагается рассматривать наэкране, а также распечатывать на обычном лазерном принтере в масштабе 1:1). Какое разрешение принтера можно использовать для этой цели?б) Те же вопросы, если надо сканировать негативы 24*36 мм,а распечатывать на принтере предполагается фотографии 10*15 см.(На негативе различимы примерно 30 линий на мм.)Комментарий.Основное соображение: сканер представляет оригинал каксовокупность прямоугольных областей ("точек"), количество таких "точек" поширине и высоте квадрата размером дюйм на дюйм называется оптическимразрешением сканера. Считается, что полная и точная информация о цвете каждойточки передается в файл изображения (оговорку см. ниже).Напротив, для принтера разрешением называется количество "уколов" -черных или белых точек, которые он может поставить в квадрате дюйм на дюйм(обратите внимание: количество пикселов, которые принтер может поставитьвдоль стороны дюймового квадрата, таким образом, равно квадратному корнюиз разрешения). Для задания "оптического пикселя" изображения используетсяквадрат n*n уколов, заполненный черными точками относительно равномернои пропорционально уровню черноты нужного оптического пикселя. Количествооптических пикселей на дюйм называется "линеатурой изображения".Пойдем с конца. Мы должны задать требования к окончательному продукту --его линеатуру и количество градаций серого (пусть это L и G).Далее, в разных вариантах задачи сканировались фотографии и негативы --зададим коэффициент увеличения продукта по сравнению с оригиналом K(1 и 4 в рассмотренных типичных случаях).Итак, принтер должен передать L оптических пикселов, эмулируя каждыйквадратом со стороной sqrt G уколов, т.е. разрешение принтерадолжно быть D = L * sqrt G (профессионалы пишут sqrt(2G), закладываянекоторый запас). При "журнальной" линеатуре 133 и 1024 градациях серогополучается 4000 dpi (6000 с запасом), если ужаться и согласиться на"газетные" 100 линий и 256 оттенков, хватает хорошего офисного принтерана 2400 dpi.Сканер должен поддержать это дело, адекватно передав цвет (оттенок серого)для каждого "оптического пикселя". Т.е. надо иметь разрешение сканераS = L * K (желателен еще двукратный запас). Даже при сканированиинегативов и линеатуре 133 любого современного дешевенького сканера хватит.При сканировании фото -- хватит любого просто.Это что касается разрешения. Однако, требование 1024 или более оттенковсерого должно быть тоже поддержано сканером (в теххарактеристикахэто описывается как "столько-то бит на пиксель в сером режиме" - ихдолжно быть 10 для 1024). Для современных сканеров это верно независимо отих дешевизны.Другой подводный камень - это что "расхожие" файловые форматы на диске(например BMP) не поддерживают более 256 оттенков серого. Надо выбиратьформат (например TIFF черно-белый), который отдаст серому более 8 бит.Если решено при печати ограничиться 256 градациями, подходит любойформат, а самым экономным будет GIF с серой палитрой.Да, и наконец, пусть оригиналы уникальны, принтер неизвестен, и хочется ихотсканировать так, чтобы потом можно было печатать на чем угодно - каковыдолжны быть характеристики сканера? Тогда ответ следует из того, чтоизображение на негативе имеет определенные ограничения на четкость, исканировать сильно лучше не имеет смысла. Так, "бытовые" объективы делалиоколо 40 различимых линий на мм в центре кадра (это 1000 линий на дюйм),поэтому слайд-сканер с разрешением 2400 и достаточным количеством оттенковсерого выкачает из этого негатива всю содержащуюся в нем информацию.Жюри считало задание полностью выполненным, если указано, что сканерснимает точки, а принтер генерирует квадраты (длина стороны квадратав пикселах пропорциональна корню из количества градаций серого),и приведены сколько-нибудь правдоподобные расчеты.Вышлите в адрес жюри электронное письмо с неправильным(не совпадающим с вашим и чьим-либо еще) обратным адресом. Опишите, как Вы егосоздали. Расскажите, как бы Вы искали его отправителя, если бы Вы его получилисами. (Не забудьте сообщить жюри, от какого именно адресата послано Вашеписьмо. Длина письма не должна превышать 2 килобайт. Пожалуйста, не посылайте более одного письма.)2. Задачи по программированию.Для произвольных целых положительных чисел x, y выполняется такаяпрограмма на языке Pascal:u:=x;v:=y;p:=y;q:=x;while (u v) do beginif (u > v) then beginu:=u-v;q:=q+p;еnd else beginv:=v-u;p:=p+q;end;end;write ((p+q)/2);Что будет напечатано в результате её работы? (Напечатанное число естьфункция от x и y; требуется указать эту функцию и обосновать свой ответ.)Ответ. Программа напечатает наименьшее общее кратноечисел x и y.Решение.Обозначим за НОД(a,b) набольший общий делитель двух натуральныхчисел a и b, а за НОК(a,b) - их наименьшее общее кратное.Заметим, что НОД(a,b)=НОД (a-b,b) при a>=b. Далее, НОД(a,b) * НОК(a,b)=a*b.Также можно увидеть, что величина u*p+v*q во время работы алгоритма значения не меняет, а в начале она равна 2a*b. Цикл заканчивает работу,когда u=v=НОД(a,b). Отсюда срезу следует ответ.В текстовой строке, которая содержит только круглые скобки (), скобкисчитаются расставленными правильно, если каждой открывающей соответствуетзакрывающая.Примеры правильной расстановки скобок(), (()), ()(()), ((()(())))()() Примеры неправильной расстановки скобок:((), ()), )(Написать программу, которая по заданному N выводит все правильные скобочныеструктуры из N пар скобок.Решение (вариант алгоритма).Немного переформулируем задачу, а именно, будем обозначатькаждую открывающую скобку числом 1, а закрывающую - числом -1,тогда правильность последовательности описывается условием:сумма любого начального отрезка неотрицательна, а длина последовательностиn. Опишем алгоритм вывода всех таких последовательностей, за время пропорциональное числу всех выведенных последовательностей.(Число таких последовательностей называют числом Каталана)Изображая единицу вектором (1,1), а минус единицувектором (1,-1), можно сказать, что мы ищем пути из точки (0,0)в точку (n,0), не опускающиеся ниже оси абсцисс.Будем перечислять последовательности в лексикографическомпорядке, считая, что -1 предшествует 1. Первой последовательностьюбудет "пила"1, -1, 1, -1, ...а последней - "горка"1, 1, 1, ..., 1, -1, -1, ..., -1.Как перейти от последовательности к следующей? До некоторого места они должны совпадать, а затем надо заменить -1 на 1.Место замены должно быть расположено как можно правее. Но заменять -1 на 1 можно только в том случае, если справа от нее естьединица (которую можно заменить на -1). После замены -1 на 1 мыприходим к такой задаче: фиксирован начальный кусок последовательности, надо найти минимальное продолжение. Её решение: надоприписывать -1, если это не нарушит условия неотрицательности, аиначе приписывать 1. Получаем такую программу:...type array2n = array [1..2n] of integer;...procedure get_next (var a: array2n; var last: Boolean);| {в a помещается следующая последовательность, если}| {она есть (при этом last:=false), иначе last:=true}| var k, i, sum: integer;begin| k:=2*n;| {инвариант: в a[k+1..2n] только минус единицы}| while a[k] = -1 do begin k:=k-1; end;| {k - максимальное среди тех, для которых a[k]=1}| while (k>0) and (a[k] = 1) do begin k:=k-1; end;| {a[k] - самая правая -1, за которой есть 1;| если таких нет, то k=0}| if k = 0 then begin| | last := true;| end else begin| | last := false;| | i:=0; sum:=0;| | {sum = a[1]+...+a[i]}| | while ik do begin| | | i:=i+1; sum:= sum+a[i];| | end;| | {sum = a[1]+...+a[k], a[k]=-1}| | a[k]:= 1; sum:= sum+2;| | {вплоть до a[k] все изменено, sum=a[1]+...+a[k]}| | while k 2*n do begin| | | k:=k+1;| | | if sum > 0 then begin| | | | a[k]:=-1| | | end else begin| | | | a[k]:=1;| | | end;| | | sum:= sum+a[k];| | end;| | {k=2n, sum=a[1]+...a[2n]=0}| end;end;Пара носков стоит 10.5 руб.Связка (12 пар) - 102.5 руб.Коробка (12 связок) - 1140.0 руб.По введенному числу N пар носков, которые хочет купить покупатель,вычислить и напечатать количество коробок, связок и пар носков, которые емуследует купить, чтобы получить не меньше N пар носок, и потратить какможно меньше денег.(купленные носки нельзя сдавать, перепродавать и т.п.)Решение (пример алгоритма).Сначала надо выяснить, как выгоднее всего купить ровно N пар носков.Для этого надо купить максимально возможное число коробок, после чего купитьмаксимально возможное число связок, и, наконец, остаток взять парами.Теперь стоит выяснить, не дешевле ли купить ещё одну связку вместо всехпар. Это бывает дешевле, если отдельных пар 10 или 11 (так как уже10*10.5>102.5). После этого надо решить, не дешевле ли вместо всех пар исвязок купить одну коробку. Это бывает, если связок 11, а пар не меньше двух,или если после предыдущего шага связок оказалось 12.Дана шахматная доска нестандартного размера X*Y. На поле (X1, Y1) стоитконь. Ему надо попасть на поле (X2, Y2).а) За какое минимальное количество ходов это возможно (если невозможно,программа должна отвечать, что этого сделать нельзя)?б) Выведите список ходов, которые сделает конь в кратчайшем маршруте.Комментарий.Правильный алгоритм (например) размечает доску (или двумерный массив)следующим образом: на нулевом шаге в конечную клетку ставится 0на i-м шаге далее в каждую из непомеченных клеток, доступныххотя бы из одной клетки с числом (i-1), ставится число iАлгоритм заканчивает работу, если в начальную клетку поставили число. Эточисло равно минимальному количеству ходов. Путь из начальной клетки вконечную можно получить, проходя из клетки с числом k в доступную клетку счислом (k-1).Если на очередном шаге алгоритма никакого числа никуда поставить нельзя -это значит, что конь из начальной клетки в конечную попасть не сможет(это выяснится за конечное число шагов, так как количество клеток на доскеконечно и на каждом шаге мы отмечаем хотя бы одну клетку).Найти 6-угольник как можно большей площади, длины всех сторон и диагоналей которого не превосходят 1. В ответе требуется предъявить параметры шестиугольника (в любой удобнойформе - координаты вершин, или длины сторон, углы и т.п.), его площадь и описание программы.Оценивается площадь найденного шестиугольника и красота алгоритма.ПЮГДЕКШ ЙНМЯСКЭРХПНБЮМХЕ НПЦЮМХГЮЖХЪ ЙНМЯСКЭРХПНБЮМХЕ НПЦЮМХГЮЖХЪ ХМДСЯРПХЮКЭМШИ ЛНМХРНП КЕВЕМХЕ ЫХРНБХДМШИ ФЕКЕГЮ ХГЛЕПХРЕКЭ ТЮГЮ МСКЭ o2 optix ОНЬХБ ЙНПОНПЮРХБМШИ ЙНЯРЧЛ ЙСОХРЭ СЦНКЭМХЙ