/pages/SciencePage.aspx science/mipt/tests/
<< Назад

Кафедра МФТИ

Задача 1

Некогда в Дагестане существовал язык, в котором имелись такие слова:

ккыл ("железо")

ссӱро ("хмельной напиток")

шшеблɔ ("бок")

быссǝ ("кулак")

рикка ("ключ")

ккор ("выть, реветь")

тыкка ("козел")

атта ("мозг")

Ныне в Дагестане существуют два языка-потомка, которые про­изошли от этого языка, - язык А и язык Б, и в этих языках указан­ные слова приобрели следующий вид (даны вперемешку):

кил, тига, кор, река, биза, зеру, шебло, ада, жибра, гер, суро, тека, ата, рига, гур, беси

Задание 1. Для каждого из этих слов определите, к какому слову языка-предка оно восходит, а также установите языковую принадлежность этих слов, если известно, что первые два из них - это слова языка А, а последние два - слова языка Б.

Задание 2. Сформулируйте правила перехода звуков языка-предка в звуки каждого из языков-потомков.

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

Примечание: ɔ, ӱ, ǝ - особые гласные звуки.

Задача 2

Дана строка S, состоящая из N строчных символов латинского алфавита (то есть из символов от ‘a’ до ‘z’). Интервалом в строке будем называть упорядоченную пару (i,j), такую что 0≤i≤j<N. Будем называть интервал хорошим, если в подстроке, в которую входят все символы исходной строки S с i-го по j-й включительно, находится не более L различных символов. Два интервала (i1,j1) и (i2,j2) являются различными, если либо i1≠i2, либо j1≠j2. Итак, даны числа N, L и строка S. Требуется найти число различных хороших интервалов в заданной строке S. Предложите максимально эффективный алгоритм решения, использующий разумное количество памяти.

Задача 3

У Васи было два мешка: в одном 2N настоящих монет, в другом - N настоящих и N фальшивых (более легких, одинаковых). Один мешок он потерял. За сколько взвешиваний на рычажных весах (без стрелок и гирь) Вася сможет узнать, какой именно? (a) N = 18, (b) N = 20?

Задача 4

Дан неориентированный граф G. Известно, что степень каждой вершины не превосходит 2, то есть каждой вершине соответствует не более двух ребер. Для графа делается довольно много (k штук) запросов вида v1 v2, где v1 и v2 – номера некоторых вершин в исходном графе. Для каждого из этих запросов потребуется выдать либо минимальное расстояние между вершинами (минимальное в смысле количества ребер в пути, соединяющем две заданных вершины), либо выдать -1, если между этим нет путей.

Предложите максимально эффективный алгоритм решения, использующий разумное количество памяти.

Задача 5

Дан рюкзак вместимостью C условных единиц, где C – целое число. Также дано N предметов. Каждый i-й предмет характеризуется двумя числами: Vi – его размер в условных единицах и Ui – его полезность, где Vi и Ui – целые числа. Нужно выбрать такое подмножество предметов, чтобы суммарный размер выбранных предметов не превосходил C, и при этом суммарная полезность выбранных предметов была максимальной. Даны числа C, N, Vi, Ui. Требуется найти вышеописанное подмножество предметов.

Задача 6

Даны слова на родственных друг другу языках квенья и синдарин и их переводы на русский язык в перепутанном порядке:

dunadan, beraid, edain, arani, nunatani, orod, atan, barad, erain

человек запада, башня, люди, короли, человек, башни, люди запада, гора (одно из слов на квенья означает то же самое, что и одно из слов на синдарине).

Установить правильные переводы всех приведённых слов. Что означает слово oron на квенья?

Назовите русское слово, которое одинаково переводится и на квенья, и на синдарин.

Задача 7

Дано натуральное число n (возможно, очень большое, для которого используется арифметика длинных чисел). Найти максимальное число k, квадрат которого меньше n. Требуется написать программу, которая работает как можно быстрее (желательно ещё оценить время работы программы). Считаем, что скорость операций над числами зависит от длины этих чисел.

<< Назад