Комментарий. Вот пример правильного и полного ответа из одной работы.
"В 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% повысить скорость печати" уже явно устарело, и применение этой раскладки в современных условиях скорее всего нецелесообразно.
Комментарий.
Современные файловые системы и программное обеспечение, очевидно, должны корректно понимать русские буквы (как и символы прочих алфавитов, поддержка которых декларируется); разумеется, такая поддержка может быть реализована с ошибками (впрочем, ошибки могут быть и в любом другом месте системы).
Однако по историческим причинам предшественники многих современных компьютерных систем были "латиноязычными", и "историческими" последствиями этого обстоятельства являются в том числе и некоторые проблемы, например:
Комментарий.
Основное соображение: сканер представляет оригинал как совокупность прямоугольных областей ("точек"), количество таких "точек" по ширине и высоте квадрата размером дюйм на дюйм называется оптическим разрешением сканера. Считается, что полная и точная информация о цвете каждой точки передается в файл изображения (оговорку см. ниже).
Напротив, для принтера разрешением называется количество "уколов" - черных или белых точек, которые он может поставить в квадрате дюйм на дюйм (обратите внимание: количество пикселов, которые принтер может поставить вдоль стороны дюймового квадрата, таким образом, равно квадратному корню из разрешения). Для задания "оптического пикселя" изображения используется квадрат 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 и достаточным количеством оттенков серого выкачает из этого негатива всю содержащуюся в нем информацию.
Жюри считало задание полностью выполненным, если указано, что сканер снимает точки, а принтер генерирует квадраты (длина стороны квадрата в пикселах пропорциональна корню из количества градаций серого), и приведены сколько-нибудь правдоподобные расчеты.
u:=x;
v:=y;
p:=y;
q:=x;
while (u <> v) do
begin
if (u > v) then
begin
u:=u-v;
q:=q+p;
еnd
else
begin
v:=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 i<>k 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;
Решение (пример алгоритма).
Сначала надо выяснить, как выгоднее всего купить ровно N пар носков. Для этого надо купить максимально возможное число коробок, после чего купить максимально возможное число связок, и, наконец, остаток взять парами.
Теперь стоит выяснить, не дешевле ли купить ещё одну связку вместо всех пар. Это бывает дешевле, если отдельных пар 10 или 11 (так как уже 10*10.5>102.5). После этого надо решить, не дешевле ли вместо всех пар и связок купить одну коробку. Это бывает, если связок 11, а пар не меньше двух, или если после предыдущего шага связок оказалось 12.
Комментарий. Правильный алгоритм (например) размечает доску (или двумерный массив) следующим образом:
Алгоритм заканчивает работу, если в начальную клетку поставили число. Это число равно минимальному количеству ходов. Путь из начальной клетки в конечную можно получить, проходя из клетки с числом k в доступную клетку с числом (k-1).
Если на очередном шаге алгоритма никакого числа никуда поставить нельзя - это значит, что конь из начальной клетки в конечную попасть не сможет (это выяснится за конечное число шагов, так как количество клеток на доске конечно и на каждом шаге мы отмечаем хотя бы одну клетку).
В ответе требуется предъявить параметры шестиугольника (в любой удобной форме - координаты вершин, или длины сторон, углы и т.п.), его площадь и описание программы. Оценивается площадь найденного шестиугольника и красота алгоритма.