Пусть f(n) для натурального числа n равно количеству различных представлений в виде сумм степеней 2, при этом каждая степень не может использоваться более двух раз. Например, f(10)=5 так как 10=1+1+8=1+1+4+4=1+1+2+2+4=2+4+4=2+8.
Чему равно f(2009)?

Одна из систем защиты банковских терминалов устроена следующим образом:

Пользователю сообщается пин-код состоящий из некоторого количества цифр, каждый раз при входе пользователя просят ввести в терминал несколько конкретных символов. Например, для пин-кода 54321 могут попросить ввести 1-й, 3-й и 5-й символы (номера символов всегда возрастают, то есть нужную часть пин-кода можно получить «выкидыванием» оставшихся символов). В этом случае пользователю для авторизации надо ввести '531'. Таким образом просто подсмотрев то, что ввел пользователь злоумышленник не сможет получить доступа. Вам удалось проследить приличное количество авторизаций одного пользователя, хотя Вы и не знаете какие цифры просили вводить. Найдите подходящий пин-код минимальной длины.

Вот лог авторизаций:

'219', '319', '315', '387', '365', '417', '397', '165', '319', '420', '489', '469', '019', '286', '238', '495', '038', '316', '095', '415', '435', '431', '426', '423', '206', '409', '215', '869', '295', '416', '089', '015', '219', '289', '285', '269', '867', '495', '695', '067', '157', '386', '157', '019', '897', '189', '407', '189', '089', '426'

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

Дана таблица из чисел, надо найти разность минимальных путей от верхней границы до нижней и от левой границы до правой. Для движения от верхней границы возможны только движения: вправо, вниз и влево. Длина пути считается так: сумма всех чисел в клетках через которые мы проходим. Для движения от левой границы к правой возможны движения: вверх, вниз и вправо. Путь от верхней границы до нижней — это путь начинающийся в любой из клеток первой строчки и заканчивающийся в любой из клеток последней строки таблицы. В ответ выведите разность длины минимального прохождения квадрата сверху вниз и слева направо(разность найденных минимальных путей).

Пример для таблицы 4 на 4:

40,35,13,32
60,58,40,20
83,18,11,53
72,50,85,75

Длина минимального пути сверху-вниз: 13+40+11+18+50 = 132. Длина минимального пути слева-направо: 40+35+13+32 = 120. Разность 12.

Найдите разность для таблицы размера 40 на 40:

39,27,46,53,47,35,91,17,91,87,34,83,96,68,62,63,18,16,44,15,48,92,23,98,50,63,59,54,83,65,46,46,68,70,51,96,51,78,48,67

89,15,80,97,44,34,22,43,33,11,69,42,45,46,43,74,58,37,31,66,82,39,77,36,85,15,54,24,84,18,58,57,86,29,50,59,79,30,98,84

30,94,97,70,68,31,56,12,48,78,45,92,80,22,88,36,32,49,29,67,62,15,80,84,72,17,29,17,23,62,40,38,86,39,38,78,46,33,83,13

86,85,73,89,60,19,56,71,31,25,43,52,80,37,77,55,38,60,50,44,69,43,47,32,76,23,45,89,44,82,24,42,75,34,50,93,83,22,22,48

99,63,77,57,77,70,31,39,45,18,95,40,84,97,80,92,31,82,37,79,18,68,71,35,56,15,77,73,99,26,87,10,15,40,45,52,22,10,90,86

97,56,86,80,17,19,76,14,77,66,80,97,89,67,69,26,48,67,98,38,62,94,47,97,35,63,78,80,64,80,28,67,11,18,37,16,36,91,99,32

29,72,28,84,32,47,33,69,37,95,83,10,71,94,30,17,58,75,40,72,68,50,25,27,79,81,77,20,63,44,67,41,86,43,18,70,18,92,39,64

27,16,32,91,94,83,80,60,21,81,21,74,88,66,15,76,86,68,35,87,34,90,52,93,98,16,20,13,17,95,70,85,38,23,19,58,53,52,25,70

93,12,26,98,89,78,64,66,11,91,87,17,70,48,38,30,82,42,63,66,33,31,32,96,13,26,63,82,79,41,95,74,62,70,38,82,84,29,68,97

37,11,94,81,97,67,98,92,15,37,67,55,91,79,50,37,71,93,92,11,24,36,40,63,39,68,81,55,30,39,13,49,54,81,73,44,76,42,52,52

87,29,83,51,32,67,57,26,67,34,57,81,61,98,39,88,63,91,46,40,30,44,57,83,72,48,98,16,84,11,64,43,94,69,28,14,79,12,14,94

35,25,17,84,64,55,75,30,38,63,85,91,11,84,13,69,79,93,16,34,61,36,21,68,86,15,32,86,19,84,34,97,98,16,45,73,61,86,14,91

67,53,68,89,57,93,93,90,78,25,85,74,64,82,26,29,46,15,34,95,87,84,75,89,67,69,87,75,23,49,57,20,42,43,51,30,41,62,85,38

52,38,31,13,35,97,45,99,63,83,20,97,20,68,77,89,29,55,43,71,45,36,19,89,59,54,89,35,56,90,10,55,12,10,31,12,25,61,17,40

95,57,98,21,93,99,36,29,52,68,93,52,27,70,95,66,50,35,21,17,35,94,69,99,98,39,92,23,52,22,24,57,32,82,22,56,33,22,92,53

98,51,78,39,46,69,32,38,20,85,31,44,14,34,35,36,62,36,22,25,43,26,80,53,27,34,46,63,33,49,47,52,34,54,63,30,25,52,10,89

33,56,43,25,63,94,80,51,86,74,12,80,96,71,21,77,68,38,86,89,48,26,83,40,78,12,89,32,14,78,66,71,77,15,17,70,79,83,24,56

59,35,12,84,89,54,87,85,31,46,33,29,20,71,30,86,15,13,31,89,61,52,10,60,96,94,90,44,79,89,63,58,67,14,63,56,21,91,44,65

87,43,40,12,10,96,64,80,96,18,33,34,38,86,43,65,67,54,92,17,52,13,69,88,69,67,31,18,41,73,48,39,23,81,61,24,49,71,32,28

70,26,14,41,70,92,21,88,92,99,52,58,47,75,21,66,39,64,20,77,82,88,62,81,17,45,36,88,22,10,69,70,49,82,15,30,14,29,40,45

27,11,97,27,65,44,38,37,63,13,91,89,29,28,80,89,69,83,17,93,84,84,88,27,28,61,90,83,76,68,83,23,38,14,88,78,35,81,87,29

82,41,69,77,26,23,11,79,29,31,34,90,30,52,38,13,69,17,62,82,87,13,85,47,12,99,12,90,67,23,80,99,52,20,76,33,34,34,89,14

77,11,16,31,71,59,42,99,45,54,91,83,62,49,86,49,75,75,17,63,69,84,77,73,23,44,51,25,39,76,77,13,92,56,60,43,56,54,47,21

48,29,99,67,74,23,93,97,56,86,22,79,34,56,69,32,75,12,55,83,57,42,30,62,33,49,82,65,48,60,93,83,24,98,47,53,58,51,12,40

11,79,29,16,84,86,17,97,47,90,31,50,35,82,77,81,97,67,71,20,60,81,82,28,82,20,99,98,99,31,83,73,13,49,72,58,36,42,74,89

30,54,20,40,33,98,99,88,69,58,77,46,75,23,10,57,72,19,16,25,23,21,87,68,77,91,75,36,61,74,19,54,31,57,91,26,90,42,19,83

89,24,39,90,55,84,58,13,85,59,62,31,42,71,48,37,42,48,78,93,96,53,98,90,75,11,36,51,51,17,54,10,47,74,11,81,29,38,50,76

19,95,10,25,23,50,59,75,18,20,62,16,86,21,86,50,67,32,74,73,49,76,62,84,24,88,40,62,51,75,90,84,54,16,55,78,94,60,24,55

48,80,37,52,29,93,34,56,87,28,36,82,28,60,98,46,94,95,66,39,91,57,94,75,47,65,97,57,78,23,34,77,30,62,20,71,82,56,55,36

10,84,37,60,55,68,59,28,32,44,36,40,32,99,61,85,38,20,51,21,57,75,65,44,52,99,85,16,98,16,39,36,24,25,87,95,34,50,95,17

36,74,37,83,66,25,19,97,92,93,19,67,93,73,45,53,68,71,95,27,17,68,53,60,43,87,78,72,64,61,76,74,66,58,86,42,76,64,13,40

46,14,35,80,40,27,44,76,61,59,77,25,32,72,20,21,31,43,40,28,45,38,59,12,10,26,21,17,90,85,20,43,65,40,49,50,87,70,36,36

97,76,47,93,58,30,31,85,46,86,26,77,81,99,44,33,61,84,33,48,88,23,85,57,75,92,55,24,36,74,52,21,58,50,93,91,27,39,40,44

57,91,68,51,63,54,27,18,28,53,77,74,84,14,94,33,73,85,38,15,37,69,54,83,77,29,77,99,11,30,15,88,18,18,88,51,66,51,77,76

81,42,74,63,79,67,11,74,82,10,25,39,24,74,74,20,42,21,81,75,37,65,82,10,42,87,90,20,29,44,40,41,65,48,43,62,64,71,33,66

33,14,31,17,41,40,81,58,23,39,67,54,61,71,65,49,32,31,98,54,46,65,46,81,44,17,39,47,74,94,45,36,14,65,70,11,42,29,23,12

22,13,50,13,62,99,67,22,72,10,76,89,24,13,30,23,37,86,11,99,58,23,31,95,95,52,95,70,36,13,59,46,61,64,24,78,76,18,94,20

12,57,68,56,10,27,33,20,63,44,47,32,95,60,61,76,27,28,77,76,76,30,97,77,65,70,40,24,63,23,69,26,61,76,15,33,13,92,72,31

68,63,23,84,14,14,83,87,17,56,57,54,61,10,37,85,58,79,89,96,65,80,84,48,97,26,42,41,42,14,45,37,21,14,47,65,98,61,70,36

68,83,10,18,86,22,39,43,64,47,72,27,10,75,22,26,17,36,97,22,47,53,65,49,50,60,99,29,29,82,24,95,60,38,73,70,49,15,53,45

Это усложненная версия задачи 81. Дана таблица из чисел, надо найти минимальный путь от левого верхнего угла до правого нижнего. Возможны движения: вправо, вниз, влево, вверх и по диагонали: влево-вверх, вправо-вверх, вправо-вниз и влево-вниз. Длина пути считается так: число в левом верхнем углу, и каждый ход к данному числу прибавляется число на которое мы переходим, если движения через грань, и удвоенное число на которое мы переходим, если движение по диагонали (через угол).

Пример кратчайшего пути для таблицы 4 на 4:

22,18,28,12

65,76,19,95

90,22,96,84

56,92,27,51

Длина: 22+18+2*19+2*22+2*27+51 = 227

Найдите длину минимального пути в таблице 40 на 40:

47,15,61,49,88,45,40,93,82,96,91,84,34,11,96,60,31,90,59,96,40,16,17,50,65,32,92,24,24,29,33,58,70,96,18,37,97,36,28,34

81,73,99,38,88,91,62,74,60,16,69,22,11,54,10,55,15,75,69,84,96,18,33,72,65,65,35,10,13,73,62,50,78,78,84,19,94,33,28,41

90,21,71,21,89,17,66,47,97,64,27,54,31,99,68,61,10,69,56,98,12,73,47,78,25,55,70,17,52,14,66,51,23,46,39,43,12,67,92,34

51,53,97,18,54,20,10,83,78,32,79,40,29,99,77,34,91,31,14,63,50,64,27,88,34,90,49,16,53,89,94,28,19,82,86,75,69,18,27,56

97,74,97,28,82,62,34,67,15,55,86,50,71,38,58,24,68,69,20,43,16,84,35,41,34,77,23,51,64,56,64,32,15,40,26,89,90,42,14,54

54,49,84,16,32,16,20,73,47,10,32,63,35,59,59,65,65,22,75,98,26,31,92,62,89,98,24,31,70,21,29,91,52,91,69,52,50,85,35,10

16,38,83,77,12,10,54,46,43,12,97,50,28,21,55,31,69,51,22,91,83,77,34,52,37,80,58,59,43,32,53,54,62,34,42,17,83,55,20,75

91,14,88,26,99,14,58,79,97,48,71,97,17,65,37,18,31,15,11,21,74,87,31,26,17,24,65,55,35,42,47,88,58,23,80,88,90,77,15,76

70,85,21,34,94,72,64,94,29,89,19,73,15,70,80,74,50,50,88,26,92,13,38,79,43,35,90,51,32,20,82,12,22,17,74,92,42,76,70,10

34,47,28,35,34,58,53,52,23,64,36,91,63,68,88,28,32,22,43,81,75,72,35,22,94,94,27,67,88,20,78,70,90,94,17,38,29,38,21,11

11,91,11,47,35,60,86,20,23,97,53,54,62,62,19,73,49,40,80,22,98,58,47,69,68,42,65,13,55,57,64,79,11,17,79,15,90,29,59,38

55,77,40,84,79,73,46,57,73,27,88,82,11,79,80,24,70,55,92,17,33,50,52,30,64,40,50,23,89,34,41,92,54,47,42,20,72,67,94,14

33,72,41,60,21,73,20,87,39,26,86,28,30,60,13,74,82,92,26,38,17,52,91,43,87,80,24,55,95,79,70,89,83,40,71,35,76,49,87,16

71,83,65,25,73,56,94,39,51,73,85,21,99,94,10,32,40,60,30,64,86,76,59,29,98,70,20,84,71,88,11,69,95,25,74,23,24,82,40,61

72,80,13,57,90,10,67,27,15,21,12,77,96,14,94,52,18,75,85,90,28,79,41,80,12,82,88,22,48,19,35,55,69,65,38,74,24,80,66,18

54,58,86,47,56,33,80,89,46,10,85,98,98,23,74,96,68,26,72,55,74,53,39,41,12,39,38,84,97,77,20,72,70,66,38,93,96,79,60,65

39,97,74,67,11,29,51,96,81,60,34,19,26,28,58,80,42,26,14,99,84,99,86,40,58,17,76,18,29,43,76,79,74,39,40,35,31,65,18,57

18,46,80,89,99,83,51,91,60,80,15,25,99,20,83,19,45,31,66,20,12,34,44,62,96,31,58,60,29,10,16,51,19,62,74,38,30,12,24,24

56,52,48,91,86,28,91,19,82,91,67,84,99,81,36,67,29,26,34,22,42,71,60,69,71,63,51,78,97,96,40,37,72,73,24,13,76,96,42,15

63,98,25,87,51,95,38,15,87,87,53,24,30,86,47,65,32,72,22,40,53,93,39,53,91,23,13,41,38,32,41,79,35,99,52,37,78,93,27,43

77,46,45,35,92,34,98,66,92,37,70,16,36,29,44,15,54,94,64,16,75,41,90,87,53,25,51,17,29,27,74,58,83,92,87,78,72,42,80,24

89,45,35,97,62,88,35,20,39,54,31,81,19,56,15,99,99,28,20,71,29,81,71,66,21,72,68,96,43,40,14,37,66,61,61,80,60,92,90,88

64,52,88,50,51,68,48,18,43,60,20,18,18,63,36,79,27,41,94,12,16,17,37,53,70,66,63,83,69,66,38,99,44,27,82,94,25,66,82,73

18,82,86,93,71,77,67,22,77,66,60,85,70,93,50,76,63,31,89,51,35,88,47,58,94,17,28,12,84,37,16,40,96,74,91,62,78,78,49,81

96,61,64,40,43,26,70,17,78,66,30,93,87,34,51,85,89,93,44,96,63,25,53,58,96,15,16,47,92,91,86,26,67,48,44,34,82,64,69,57

27,58,64,47,16,18,76,69,80,33,90,30,56,48,80,27,51,71,26,32,81,92,34,46,63,47,97,39,24,26,38,64,28,81,34,86,15,12,35,96

81,47,76,59,19,83,83,83,77,51,67,80,65,31,48,96,76,34,19,68,55,85,95,36,28,53,18,47,68,72,65,64,22,84,40,91,27,99,20,23

14,91,91,78,83,40,19,41,52,94,43,71,56,71,73,18,46,21,39,36,35,21,23,97,86,46,39,64,24,63,88,90,49,28,68,92,32,17,26,95

18,33,89,40,81,12,61,33,54,54,16,40,18,31,89,57,46,64,69,48,98,31,18,92,99,47,18,33,81,73,39,42,96,68,41,88,29,82,23,69

32,65,79,31,28,36,43,10,44,25,66,38,93,10,84,80,75,74,22,89,48,30,18,91,12,30,71,68,37,31,57,89,24,67,44,46,93,47,27,15

74,72,69,42,31,61,30,59,90,31,36,86,97,88,44,71,74,92,18,78,78,41,46,43,42,43,92,25,15,56,45,37,76,73,65,85,98,42,84,32

80,36,98,78,95,24,35,87,61,32,55,79,14,66,29,25,57,93,67,47,84,78,94,35,40,63,77,66,95,83,13,91,30,90,69,27,45,75,21,42

12,32,95,29,15,99,88,89,54,49,13,26,89,89,29,63,64,48,74,37,99,76,15,78,89,26,70,23,31,23,35,32,19,42,26,58,43,19,42,43

31,91,52,22,93,32,98,17,69,77,80,44,84,58,98,18,65,49,92,72,52,76,59,32,61,16,51,20,90,99,49,12,49,37,37,96,22,83,28,28

83,86,38,63,52,65,16,43,91,39,67,66,27,59,22,25,35,55,70,55,11,15,78,97,79,50,69,15,43,98,35,71,95,60,65,92,80,76,97,55

72,53,35,84,17,72,43,23,13,92,23,75,75,34,66,84,96,79,69,73,21,36,11,38,86,24,98,13,76,33,58,42,78,36,87,43,16,36,85,77

88,96,18,39,29,56,29,63,96,10,20,63,95,11,75,97,28,55,38,20,52,53,91,99,14,42,49,11,68,23,12,73,36,18,27,84,75,53,78,16

99,15,88,67,24,77,14,52,37,75,15,13,44,21,70,96,20,99,65,78,73,14,31,71,75,23,91,81,89,87,80,82,82,21,82,29,52,34,52,74

63,16,81,19,64,33,71,73,29,53,31,75,66,78,51,68,48,54,85,22,90,15,84,76,95,45,90,83,66,27,16,17,20,48,27,18,38,72,71,25

38,29,23,16,83,68,83,31,52,33,65,33,95,32,52,69,45,53,65,35,88,94,42,89,48,48,19,40,49,84,33,15,31,96,83,57,76,88,27,36

Рассмотрим игру «монополия». Игровое поле следующее:

Движение происходит следующим образом: каждый игрок своим ходом кидает два 6-гранных кубика, и сдвигает фишку на число клеток в сумме выпавших на кубиках. Исключением является случай, когда игрок три раза подряд выкидывает дубль (одинаковые числа на кубиках), в таком случае он попадает на клетку тюрьмы (JAIL). Также, если игрок сдвинув фишку попадает на «G2J», то он перемещается в тюрьму.

Игрок начинает с клетки GO и каждый ход бросает пару кубиков и свдигает фишку на сумму чисел выпавших на кубиках по часовой. Если бы не было дополнительных правил — ожидаемым было бы, что вероятности попадения на каждую клетку после броска равна 1/40. Но попадания на клетки G2J(Go to jail, отправляйтесь в тюрьму), CC(извещение) и CH(шанс) изменяет это распределение. Также существует правило, согласно которому если игрок выкидывает три раза дубль (одинаковые значения на кубиках), то вместо третьего хода он попадает в тюрьму.

Вначале игры все карты CC и CH перетасованы. Когда игрок становится на одну из таких клеток верхняя карта колоды снимается и после использования кладется под низ. В каждой стопке по 16 карт, часть из которых содержит предписания о перемещении на какую-то из клеток карты, остальные нам не важны. Вот эти карты:

• Извещения (2/16 cards):

  1. к старту (GO)

  2. в тюрьму (JAIL)

• Chance (10/16 cards):

  1. К старту (GO)

  2. В тюрьму (JAIL)

  3. На клетку C1

  4. На клетку E3

  5. На клетку H2

  6. На клетку R1

  7. К следующей клетке R (ЖД компания)

  8. К следующей клетке R

  9. К следующей клетке U (Коммунальное предприятие)

  10. Назад на 3 клетки

Ваша задача определить вероятность закончить ход на каждой из клеток после очередного броска кубиков. Очевидно что вероятность для Jail наибольшая, G2J нулевая. Считается что игрок не задерживается в тюрьме. Пронумеруем все клетки от 0(GO) до 39(H2) и найдем вероятности для каждой клетки. Три макимальные вероятности получаются для клеток JAIL(10), 6.24%; E3(24), 3.18% и GO(0), 3.09%.

В какой-то момент вы потеряли кубик и потому решили обходиться для игры монеткой, подкидывая ее три раза и считая что орел - 1, а решка - 2. При этом "дублем" считается выпадения все три раза либо орла, либо решки. Найдите при таком способе игры 5 наиболее популярных клеток и в ответе укажите сумму их номеров.

На поле размером 1000*1000 клеток в разных клетках расположены 10 вирусов. За каждый ход вирус заражает 4 соседние с ним клетки (слева, справа, сверху и снизу).
Определить за какое наибольшее количество ходов будет заражено все поле.

Прямоугольная сетка 3 × 2 на рисунке содержит 18 прямоугольников:

Определим функцию f(a,b) как число прямоугольников, содержащихся в сетке a × b.

Сколько различных значений принимает f(a,b) при 0<a<1000 и 0<b<1000?

Механизм кодиpовки для фоpмата MIME64 (Multitask Internet Mail Extensions) следующий:
1) исходный 8-битовый текст pассматpивается как последовательность битов; она pазбивается, слева напpаво, на 6-битовые отpезки (если последний отpезок "неполный", то он дополняется битовыми нулями);
2) каждая 6-битовая комбинация тpактуется как число из диапазона 0..63;
3) число заменяется символом с соответствующим поpядковым номеpом из стpоки-шаблона, состоящей из 26 заглавных букв латинского алфавита (A..Z), 26 стpочных букв того же алфавита (a..z), цифp (0..9) и символов "+" и "/", то есть из стpоки:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz 0123456789+/

В результате кодировки получилась фраза: UHJvamVjdC8vRGlvZmFudCtpbnR1aXQrb3NwLy9ydQ0K.

Введите текст, который был закодирован.

Паук S сидит в углу комнаты, имеющей форму прямоугольного параллелепипеда и размеры 6×5×3. Муха F сидит в противоположном углу. Чтобы добраться до мухи, паук может ползти по стенам, полу или потолку комнаты. При этом он выбирает кратчайший возможный путь. В данном случае длина кратчайшего пути оказалась равной 10:

Однако, не для всякой комнаты длина кратчайшего пути  будет выражаться целым числом.

Рассмотрим все комнаты, у которых длина, ширина и высота - целые числа, не превышающие M. Оказывается что для M=100 найдется ровно 2060 различных комнат, для которых длина кратчайшего пути  будет целой, и это минимальное число, при котором количество решений превышает 2000, поскольку при M=99 будет только 1975 решений.

Найти наименьшее число M, при котором число решений будет больше 100 000 000.