inf tasks round-2 2011

Профили «Гуманитарный и юридический», «Экономика и управление»

Задание 1.
Бурундуки-спасатели Чип и Дейл играют в «крестики-нолики» на поле размером 13EMBED Equation.DSMT41415 клетки. Чип начинает и ставит крестик в центральную клетку, как показано на рисунке:
.
После того как Дейл поставит нолик в какую-нибудь клетку, Чип получит информацию количеством ___ бит (-а).
Ответ: 3.

Задание 2.
Для каждого числа из заданного набора чисел в десятичной системе счисления определите наименьшее основание системы счисления, в которой данное число будет записываться не более чем 5 цифрами.
Например, для числа 35 ответ 3, так как для записи числа 35 в двоичной системе счисления необходимо 6 цифр (1000112), а в троичной – 4 цифры (10223).
Найдите ответы для набора (1000,14348906,161051).
Ответы введите через запятую, без пробелов.
Ответ: 4,27,11.

Задание 3.
Для записи рисунка c количеством различных цветов не более 256 в формате BMP может использоваться следующий способ сжатия информации. Информация хранится в кусочках по два байта. Если первый байт кусочка не равен 0, то в нем содержится количество последовательных пикселов, имеющих одинаковый цвет, а номер цвета пиксела в диапазоне от 0 до 255 указан в следующем байте. Таким образом кодируются последовательности из трех и более пикселов одного цвета и одиночные пикселы. Два последовательных пиксела одного цвета кодируются как последовательность пикселов разного цвета . Если необходимо закодировать последовательность из двух и более пикселов, имеющих разные цвета (такая последовательность не должна содержать подпоследовательности из трех или более пикселов, имеющих одинаковый цвет, так как они кодируются способом, указанным выше), то в первом байте кусочка указывается значение 0, во втором – длина последовательности, затем номера цветов пикселов. Если длина последовательности из разноцветных пикселов нечетна, то к последовательности добавляется нулевой байт, чтобы выровнять на границу кусочка.
Каждая строка изображения кодируется отдельно, конец строки обозначается кусочком, содержащим два нулевых байта (см. пример).
Примеры:


Закодируйте изображение размером 16x16, показанное на рисунке и содержащее пикселы семи различных цветов. В ответе введите длину результата кодирования (в байтах) .
Ответ: 230.

Задание 4.
На вершине лесенки, содержащей 20 ступенек, находится спортивного вида Дед Мороз, который начинает прыгать по ним к основанию лесенки, у которого стоит Миша Иванов и ждет новогоднего подарка. Дед Мороз может прыгнуть на следующую ступеньку, через одну ступеньку или через две (то есть если Дед Мороз стоит на 8-ой ступеньке, то он может переместиться на 7-ую, 6-ую или 5-ую). Определите число всевозможных "маршрутов" Деда Мороза с вершины лесенки на землю к ждущему подарка Мише Иванову.
Ответ: 121415.

Задание 5.
Для каждого числа из заданного набора чисел найдите его наименьший простой делитель, не совпадающий с самим числом. Если число является простым, в качестве ответа укажите 0.
Например, для набора чисел (6,5,15) получаются ответы 2,0,3.
Найдите ответы для набора (29560969, 27974761, 28543027, 26714717).
Ответы введите через запятую, без пробелов.
Ответ: 5437,293,0,5107.

Задание 6.
Для шифрования некоторого текста используется следующий алгоритм. Из текста удаляются все символы пробела и знаки препинания, затем в шифрованное сообщение записывается каждый K-й символ из получившейся строки, и использованный символ из строки удаляется. При достижении конца строки счет продолжается с начала строки (можно представить, что символы строки записаны по кругу). Шифрование заканчивается после удаления последнего символа из строки.
Например, из текста «IT'S SAMPLE» после шифрования с K=3 получается шифрованное сообщение «SMESLATPI».
Зашифруйте с помощью K=17 следующее высказывание Р. Декарта «NOTHING IS MORE FAIRLY DISTRIBUTED THAN COMMON SENSE: NO ONE THINKS HE NEEDS MORE OF IT THAN HE ALREADY HAS». В качестве ответа укажите последние 10 символов шифрованного сообщения.
Ответ: STEARILSAI.

Задание 7.
В написанном выражении ((((1?2)?3)?4)?5)?6 вместо каждого знака? вставить знак одного из пяти арифметических действий – сложение, вычитание, умножение, целочисленное деление и возведение в степень – так, чтобы результат вычислений равнялся 4096 (при делении дробная часть в частном отбрасывается: 3 / 2 = 1 или 1 / 2 = 0). Необходимо подсчитать общее количество таких решений.
Ответ: 19.

Задание 8.
Слова из N бит будем называть существенно различными, если одно из слов нельзя привести к другому, применяя ноль или более раз следующую операцию: последовательность, содержащая четное количество единичных битов, заменяется на последовательность из тех же битов, записанных в обратном порядке.
Например, для N=5 слова 01010 и 00110 являются существенно различными, а слова 01010 и 00101 – нет (одна операция над битами с 2-го по 5-й).
Определите количество существенно различных слов из N=16 бит.
Ответ: 121.

Задание 9.
Числа, обладающие свойством самовоспроизводимости при выполнении некоторых действий над ними, называют автоморфами. Например, 93762=87909376, четыре последние цифры квадрата совпадают с исходным числом. Найдите все n-значные числа x, удовлетворяющие уравнению x2 mod 10n = x в диапазоне от 1000000 до 10000000. В ответе числа запишите в порядке возрастания через запятую, без пробела.
Например, 1111111,2222222,3333333.
Ответ: 2890625,7109376.

Задание 10.
Вычислите, сколько существует различных путей для путешествия «хромого» короля из левого нижнего угла доски размером NxN в правый верхний угол, при котором король не проходит дважды по одной и той же клетке. «Хромой» король в отличие от обычного короля в шахматах не может выполнять ход по диагонали вниз-влево (см. рисунок).

Пути считаются различными, если они проходят по различным клеткам или обходят клетки в разном порядке. Например, для доски 2x2 существует 5 различных путей: a1-b2, a1-a2-b2, a1-b1-b2, a1-a2-b1-b2, a1-b1-a2-b2.
Вычислите ответ для N=4.
Ответ: 59547.

Задание 11.
Японский гексаворд
Все (или многие) знают, что такое японский кроссворд. Он располагается на прямоугольном поле. В отличие от него гексаворд располагается на шестиугольном поле в виде пчелиных сот. А количество закрашенных клеток задается не по двум координатам (вертикали и горизонтали) а по трем, как показано на рисунке 1.

Направления нумеруются против часовой стрелки, начиная с верхнего западного. Для рисунка 1) нумерация количества закрашенных в каждом направлении клеток следующая:
2 1 1
2 1 1
0 2 2.
Требуется по имеющимся числовым значениям (обозначающим общее число закрашенных сот в данном направлении) сосчитать количество различных вариантов закраски гексаворда.
Формат входных данных (файл Gex.in)
В первой строке входного файла содержится натуральное нечетное число N (1<=N<=7). В следующих 3 строках содержатся по N разделенных пробелами натуральных чисел в диапазоне от 0 до N.
Количество чисел равно 3*N. Для рисунка 1) N=3, для рисунка 2) N=5 и для рисунка 3) N=7.
Формат выходных данных (файл Gex.out)
В выходной файл необходимо вывести одно целое число – количество различных вариантов закраски гексаворда.
Составьте программу и просчитайте для трех тестовых файлов Gex.in:

Тест1
7
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 2 3 4 3 2 1

Тест 2
7
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 2 3 4 3 2 1

Тест 3
5
1 3 2 3 1
1 3 2 3 1
1 3 2 3 1

В ответе запишите результаты тестов через запятую, без пробелов.

Пример входных, выходных данных и вывода ответа.

Пример записи ответа: 2,1,28
Ответ: 388,4,8.

Задание 12.
Экспорт апельсинов из страны Лимонии осуществляется в бочках, установленных на палубе судна на воздушной подушке. Чтобы не нарушать центровку судна в каждой из N бочек должно находиться одинаковое количество апельсинов. Причем в каждой бочке могут находиться апельсины только одного из M сортов. Зная число апельсинов каждого сорта на складе, требуется по заданным N и M определить, сколько апельсинов можно уложить в каждую бочку так, чтобы вывезти за 1 рейс максимальный груз апельсинов.
Формат входных данных (файл Apelsin.in)
В первой строке входного файла содержатся разделенные пробелом натуральные числа N и M (1<=M,N<=1000). В следующих M строках содержится по одному натуральному числу Ai (0<=Ai<=1000000; 1<=i<=M), обозначающему количество апельсинов i-го сорта на складе.
Формат выходных данных (файл Apelsin.out)
В выходной файл необходимо вывести одно целое число – количество апельсинов в каждой бочке.

Составьте программу и просчитайте для трех тестовых файлов:

Тест 1
289 3
3288
2918
5454

Тест 2
47 19
4665
4098
5974
9197
4855
6276
3702
5732
8591
7540
4989
9129
9124
6267
336
1011
2213
3300
2832

Тест 3
17 12
89
636
639
639
795
292
595
244
817
975
555
589


В ответе запишите результаты тестов через запятую, без пробелов.
Пример входных и выходных данных
Apelsin.in
Apelsin.out

5 3
1
1
2
0

5 2
1000
5
200

3 3
500
300
100
250


Запись ответа: 0,200,250
Ответ: 40,1825,297.
Профили «Техника и технологии», «Специализированный»

Задание 1.
В урне находится несколько разноцветных шаров. Известно, что шаров каждого цвета в урне поровну. Проведен эксперимент – из урны извлечен зеленый шар. При этом получена информация количеством 3 бита. Тогда шары в урне окрашены в ___ цветов.
Ответ: 8.

Задание 2.
Из последовательности натуральных чисел вычеркнуты все числа, содержащие 0 в десятичной записи. Нужно определить, какое число будет
K-м в получившейся последовательности.
Например, для К=100 таким числом будет число 121.
Вычислите ответ для K=1018 .
Ответ: 6585837139636825191.

Задание 3.
Для предотвращения перехвата пароля можно использовать следующую схему неявного ввода пароля. Пользователю показывается поочередно несколько множеств букв, и для каждого множества он должен щелкнуть по тем позициям букв в пароле, которые есть в этом множестве. Множества букв генерируются при каждом входе случайно, но таким образом, чтобы пароль можно было восстановить однозначно.
Пусть были сгенерированы следующие множества букв:
1. {D,G,K,N,O,P,Q,R,S,T,U,V,Y,Z}
2. {B,C,H,I,J,K,P,Q,U,V,W,Y,Z}
3. {A,C,D,F,G,J,L,M,N,P,R,V,W,Y}
4. {B,C,E,F,I,M,N,O,Q,R,S,U,V,W}
5. {A,B,E,F,G,H,J,O,Q,R,T,W,Y,Z}
При вводе пароля SAMPLE нужно щелкнуть по следующим позициям букв: для 1-го множества – (1,4), для 2-го – (4), для 3-го – (2,3,4,5), для 4-го – (1,3,6), для 5-го – (2,6).
Определите, какой пароль из 10 букв был введен следующим образом:
(2,5,7,8), (1,2,4,6,10), (1,7,8,9,10), (6,8,9,10), (1,4,5,7,9).
Ответ: JKXHTIGNFC.

Задание 4.
Выражение, построенное из констант a,b,c,d,e,f,g,h и комбинаторов I, K, S, будем называть корректным, если оно удовлетворяет следующей грамматике:
<выр> ::= a | b | c | d | e | f | g | h | I <выр> | K <выр> <выр> | S <выр> <выр> <выр>.
Корректному выражению соответствует ответ 1, некорректному – 0.
Например, выражение IKcd является корректным, а SbKd – нет. Вывод ответа: 1,0.
Определите, являются ли корректными следующие выражения:
1. SKghaIISdKIbhId
2. IKScgKSgeIIKcfd
3. KShfIKaSbebIIeISdfIc
4. SKKhKaIeebdKIScIhKcIIb
5. KeSaSefSffISKIIfSeaIIeIKbceIIg
6. KSdSIabaSfdghSIKIbIfd
Ответы введите через запятую без пробелов, для корректного выражения укажите ответ 1, для некорректного – 0.
Ответ: 1,0,0,0,1,0.

Задание 5.
Для каждого числа из заданного набора чисел найдите его наименьший простой делитель, не совпадающий с самим числом. Если число является простым, в качестве ответа укажите 0.
Например, для набора чисел (6,5,15) получаются ответы 2,0,3
Найдите ответы для набора
(9472755740454889, 9183266438487959, 9567439417680461, 9755772061532773).
Ответы введите через запятую, без пробелов.
Ответ: 97328083,197909,0,95659279.

Задание 6.
Для шифрования некоторого текста используется следующий алгоритм. Из текста удаляются все символы пробела и знаки препинания, затем в шифрованное сообщение записывается каждый K-й символ из получившейся строки, и использованный символ из строки удаляется. При достижении конца строки счет продолжается с начала строки (можно представить, что символы строки записаны по кругу). Шифрование заканчивается после удаления последнего символа из строки.
Например, из текста «IT'S SAMPLE» после шифрования с K=3 получается шифрованное сообщение «SMESLATPI».
Некоторый текст был зашифрован с помощью некоторого значения K в диапазоне от 2 до 100, и получилось следующее шифрованное сообщение:
CEUBAOTSSRCRIBEOEUOTESOSISETRUIRCIPCOYSHUTAMTNMTAMOCRETSNCLOTNMREEPPESANOOOTC.
Известно, что в исходном тексте было слово «SCIENCE». Расшифруйте сообщение и в качестве ответа укажите 10 первых символов исходного текста.
Ответ: SRCTRIEOTC.

Задание 7.
Найти на интервале от 80 до 100 включительно числа Ni, которые представляются суммой четырех квадратов натуральных чисел более чем тремя разными способами. Перестановка слагаемых в сумме квадратов нового решения не дает!
Так, для числа 13 существует одно представление: 12+22+22+22=13, то есть Ni=1,2,2,2.
Например, от 60 до 69 результатом будет всего одно число 63, которое имеет 4 представления:
12+12+52+62=63
12+22+32+72=63
22+32+52+52=63
32+32+32+62=63.
Ответ записать в порядке возрастания чисел через запятую, без пробелов. Например: 66,67,68,69.
Ответ: 82,84,87,90,91,93,97,98,100.

Задание 8.
Числа, обладающие свойством самовоспроизводимости при выполнении некоторых действий над ними, называют автоморфами. Например, 93762=87909376, четыре последние цифры квадрата совпадают с исходным числом. Найдите все n-значные числа x, удовлетворяющие уравнению
x2 mod 10n = x в диапазоне от 1000000 до 10000000. В ответе числа запишите в порядке возрастания через запятую, без пробела.
Например, 1111111,2222222,3333333.
Ответ: 2890625,7109376.

Задание 9.
Мозаика
Компания «Headache», занимающаяся выпуском логических игрушек для детей, представила свою новую мозаику. В нее входит прямоугольная пластина, состоящая из N*M квадратов. Некоторые квадраты пластины изначально заняты, и в них ничего нельзя поставить. В комплекте поставляются также детали для складывания мозаики. Различных типов деталей всего 9, пронумерованы они от 1 до 9 в том порядке, в котором изображены на рисунке:
.
Конструкция каждой детали не позволяет поставить ее на пластину как бы то ни было повернутой. Все типы деталей являются различными, и нельзя с помощью поворота получить деталь другого типа. Деталь можно поставить только на свободные квадраты. Конструкция деталей была тщательно продумана, поэтому с помощью деталей 3 и 4 можно, например, сложить квадрат 2*2. В наборе деталей каждого типа достаточно для того, чтобы не заботиться об их количестве.
Каждый тип детали имеет свой уникальный цвет. Мозаика называется сложенной, если все квадраты пластины заняты. Два мозаичных узора различны, если есть квадраты, занятые деталями различных типов (цветов). Создателям очень хочется знать, сколько различных узоров сложенной мозаики может получиться. Это необходимо им для рекламной кампании. Ваша задача – помочь им разобраться в этом непростом вопросе.
Формат ввода
В первой строке находятся N – размер пластины по вертикали, и M – размер пластины по горизонтали. Затем в следующих N строках находятся ровно по M чисел, равных нулю или единице. Единица обозначает занятый квадрат, ноль – свободный.
Формат вывода
В первой строке должно находиться единственное число, равное количеству различных узоров сложенной мозаики.
.
Найдите число различных узоров для следующей структуры (доступно для копирования в буфер обмена):
8 6
0 1 0 0 0 1
1 0 1 0 0 1
1 0 1 0 1 1
0 1 0 0 1 1
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 1 1 1 1 1
Ответ: 45.

Задание 10.
Японский гексаворд
Все (или многие) знают, что такое японский кроссворд. Он располагается на прямоугольном поле. В отличие от него гексаворд располагается на шестиугольном поле в виде пчелиных сот. А количество закрашенных клеток задается не по двум координатам (вертикали и горизонтали) а по трем, как показано на рисунке 1.

Направления нумеруются против часовой стрелки, начиная с верхнего западного. Для рисунка 1) нумерация количества закрашенных в каждом направлении клеток следующая:
2 1 1
2 1 1
0 2 2.
Требуется по имеющимся числовым значениям (обозначающим общее число закрашенных сот в данном направлении) сосчитать количество различных вариантов закраски гексаворда.
Формат входных данных (файл Gex.in)
В первой строке входного файла содержится натуральное нечетное число N (1<=N<=7). В следующих 3 строках содержатся по N разделенных пробелами натуральных чисел в диапазоне от 0 до N.
Количество чисел равно 3*N. Для рисунка 1) N=3, для рисунка 2) N=5 и для рисунка 3) N=7.
Формат выходных данных (файл Gex.out)
В выходной файл необходимо вывести одно целое число – количество различных вариантов закраски гексаворда.
Составьте программу и просчитайте для трех тестовых файлов Gex.in (доступно для копирования в буфер обмена):

Тест1
7
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 2 3 4 3 2 1

Тест 2
7
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 2 3 4 3 2 1

Тест 3
5
1 3 2 3 1
1 3 2 3 1
1 3 2 3 1.

В ответе запишите результаты тестов через запятую, без пробелов.
Пример входных, выходных данных и вывода ответа.

Запись ответа: 2,1,28

Ответ: 388,4,8.

Задание 11.
Транспорт
В каждом из N городов страны Лимонии имеется ж/д вокзал и аэропорт. Поэтому сообщение между любыми двумя городами может быть осуществлено либо поездом, либо самолетом. Стоимость организации сообщения между i-м и j-м городами складывается из двух видов составляющих: постоянных AVIACONST или POEZDCONST и зависящей от расстояния между городами. Например, чтобы соединить 1-й и 5-й город ж/д сообщением потребуется затратить:
SUM = POEZDCONST+POEZD*RASST15,
где POEZD – стоимость одного метра провоза по ж/д, а
RASST15 – расстояние между первым и пятым городом в метрах.
Аналогично считается стоимость для авиасообщения:
SUM = AVIACONST+AVIA*RASST15,
где AVIA – стоимость одного метра провоза на самолете.
Власти страны очень экономны. Но они хотят, чтобы житель любого города имел возможность попасть в любой другой город (пусть с пересадками). Требуется по заданному N, POEZD, AVIA, AVIACONST, POEZDCONST и имеющимся для каждого i-го города координатам Xi, Yi найти минимальную стоимость организации сообщения между городами.
Формат входных данных(файл Trans.in)
В первой строке входного файла содержатся разделенные пробелом натуральные числа N, POEZD, AVIA, POEZDCONST, AVIACONST (1<=N<=100; 1<=POEZD,AVIA<=1000; 1<=POEZDCONST, AVIACONST<=10000). В следующих N строках содержится разделенные пробелами целые числа X,Y для каждого города (–10000<=X,Y<=10000).
Формат выходных данных (файл Trans.out)
В выходной файл необходимо вывести одно число – минимальную стоимость организации сообщения между городами.

Составьте программу и просчитайте для трех тестовых файлов Trans.in (доступно для копирования в буфер обмена):

Тест 1
4 332 168 2868 7148
7881 -3752
7937 -3754
-64 6767
1326 6242

Тест 2
17 331 266 4989 5485
2341 5678
1209 -8256
7507 1866
2591 2760
-6025 8913
7099 -2713
-8762 -411
-7326 -7247
-6737 -6755
-2488 5824
-3699 2378
372 -8533
1701 4191
5895 7012
3722 -2843
-5088 1216
2345 2581

Тест 3
4 400 200 2000 4000
-100 100
-100 -100
100 -100
100 100

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

Запись ответа: 17000,299548.

Ответ: 2288400,14272939,132000.

Задание 12.
Тур магараджи
Магараджей называется шахматная фигура, сочетающая в себе возможности шахматных ладьи, коня и слона. За один ход она может быть перемещена в пределах шахматного поля на любое количество клеток по горизонтали, или по вертикали, или по диагонали, или (как конь) на две клетки по горизонтали (вертикали) и одну клетку по вертикали (горизонтали).
Игрок сделал магараджей N ходов по доске, после чего фигура вновь оказалась на исходной клетке с координатами XY. К сожалению, координаты ходов не сохранились, а имеется лишь запись последовательности ходов, в которой указывается, каким способом был сделан очередной ход (конем, ладьей или слоном) и на сколько клеток (для слона или ладьи). Составить программу для подсчета количества различных путей, которыми игрок может осуществить тур.
Формат входных данных (файл Tur.in)
В первой строке входного файла содержится координата начальной клетки на шахматной доске в формате XY (X=A,B,C,D,E,F,G,H; Y=1,2,3,4,5,6,7,8) и через пробел натуральное число N (1<=N<=20).
Во второй строке входного файла содержится текстовая строка, содержащая последовательность ходов. Запись каждого хода представляет из себя 2 символа: первый символ – S,L или K; второй символ – цифра (1 – для коня и от 1 до 7 – для ладьи и слона)
Формат выходных данных (файл Tur.out)
В выходной файл необходимо вывести одно целое число – число различных путей магараджи.

Составьте программу и просчитайте для пяти тестовых файлов Tur.in:

Тест 1
D5 20
K1S1L1K1S1L1K1S1L1K1S1L1K1S1L1K1S1L1S1L2

Тест 2
A8 20
S7L7S7L7S7L7S7L7S7L7S7L7S7L7S7L7S7L7S7L7

Тест 3
B1 5
K1K1K1L7S6

Тест 4
B1 20
L6S6L1S1K1L1S1K1L1S1K1L1S1K1L1S1K1L1S1K1

Тест 5
E4 20
K1K1K1K1K1K1K1K1K1K1K1K1K1K1K1K1K1K1K1K1

В ответе результаты тестов запишите через запятую без пробелов.

Пример входных, выходных данных и записи ответа.

Запись ответа: 0,156,1.
Ответ: 238579514032,512,2,3853653576,306516847814840.
















Root Entry

Приложенные файлы

  • doc 19127478
    Размер файла: 183 kB Загрузок: 1

Добавить комментарий