Задачи на собеседовании в ABBYY

Довелось мне на днях побывать на собеседовании в ABBYY.

Подробности описывать лениво. Просто ряд задачек, что они дают:

1.  Можно ли заказать семь гирь так, чтобы получить возможность взвешивать на чашечных весах слитки золота от 1 грамма до 1 килограмма? (гири можно класть на любую из чашек). Считать, что слиток золота весит целое число граммов.

2.  В ящике лежит m белых и n черных шаров. Из ящика случайным образом вынимаются по 2 шара. Если вынули 2 шара разного цвета (черный и белый), то в ящик возвращают 1 черный шар. Если вынули 2 шара одинакового цвета (2 белых или 2 черных), то в ящик возвращают 1 белый шар. Считается, что снаружи ящика есть достаточное количество белых шаров, чтобы их вовращать, если вынимается два черных шара. Можно ли, зная числа m и n, сказать, какой шар останется в ящике последним?

3. На языке «Гуси» одного африканского племени словами записаны следующие числа. Язык настоящий, реально действующий.

57 emerongo etano na itano na ibere

82 emerongo etano na etato na ibere

230 amagana abere na emerongo etato

308 amagana atato na itano na itato

705 amagana atano na abere na itano

Напишите на этом языке 28 и 837.

 

4. Даны две длинные текстовые строки (длинной  K и N, где K<=N). В каждой строке записаны различные (т.е. внутри одной строки нет пар одинаковых) натуральные числа, разделенные одиночными пробелами. Числа в строках могут быть очень длинными, например 100 значными. Написать программу, которая находит все числа, которые встречаются в обеих строках сразу, и выводит на экран их позиции в обеих строках. Количество элементарных операций, выполняемых в программе, должно быть O(N) (т.е пропорционально N, не более того) и не зависеть, в частности, от длин чисел. Количество байт используемой дополнительной памяти O(K) (т.е. пропорционально K, не более того).

 

5. Дана функция f(x,y): f(x,0)=x^2; f(0,y)=y^5+y;f(x,y)=[f(x-1, y)^3 + f(x, y-1)]^4. Написать программу, вычисляющую f.

 

6. Дана строка длинной N. Строка состоит из слов, разделенных пробелами. Написать программу, которая меняет порядок СЛОВ (не символов а слов) в строке. Память: O(1), время O(N).