Процедуры и функции

Напишите функцию быстрого возведения в степень. Количество действий должно быть пропорционально двоичному логарифму n.

Входные данные
Вводится 2 числа - a (вещественное) и n (целое неотрицательное).

Выходные данные
Необходимо вывести  значение aⁿ.

В подземелье живут гномы. У них есть древняя традиция деления золота:

Когда гном получает N монет:
1. Если N = 0, гном грустит и ничего не делает
2. Если N = 1, гном оставляет монету себе и кричит "МОЁ!"
3. Если N > 1:
   - Гном берёт себе 1 монету и кричит "МОЁ!"
   - Остальные (N-1) монет делит пополам
   - Левую половину (N-1)/2 отдаёт левому ученику-гному
   - Правую половину (N-1) - (N-1)/2 отдаёт правому ученику-гному
   - Каждый ученик делает то же самое по традиции

Подсчитайте, сколько раз прозвучит крик "МОЁ!" при делении N монет.

Формат входных данных
Одно число N (0 ≤ N ≤ 10^9) - начальное количество монет.

Формат выходных данных
Одно число - сколько раз прозвучит "МОЁ!"
 

Разбирая старые задачи олимпиады, Петя наткнулся на алгоритм рекурсивного закрашивания растрового изображения. У Пети есть черно-белое (bitmap) изображение размером 13 на 13 пикселей. На изображении присутствует замкнутый контур, как приведено на рисунке. Пиксели внутри контура пронумерованы.


Традиционно для компьютерной графики, система координат имеет начало в верхнем левому углу, ось X направлена слева направо, а ось Y – сверху вниз.
Алгоритм рекурсивного закрашивания заключается в рекурсивном вызове процедуры «Закрасить», которой передаются два параметра – координаты X и Y пикселя.
Процедура Закрасить(X, Y), может быть описана следующим образом:
1. Если цвет пикселя с координатами (X, Y) белый, то:

Строка формируется из заглавных английских букв следующим образом

1. Начинаем с "A".

2. Каждый следующий шаг: к предыдущей строке приписываем новую строку, в которой каждый символ предыдущей строки сдвинут вправо на 2 по алфавиту (A→C, B→D, ..., Y→A, Z→B).

Вот первые четыре шага:

Шаг 1: A
Шаг 2: AС
Шаг 3: AССE 
Шаг 4: ACCECEGG 

Какой символ стоит на 50-й позиции после 7-го шага?

Первый символ слева стоит на позиции 1. 

 

 

Строка формируется из заглавных английских букв следующим образом

1. Начинаем с "A".

2. Каждый следующий шаг: к предыдущей строке приписываем новую строку, в которой каждый символ предыдущей строки сдвинут вправо на 1 по алфавиту (A→B, B→C и т. д. Z→A).

Вот первые четыре шага:

Шаг 1: A
Шаг 2: AB
Шаг 3: ABBC 
Шаг 4: ABBCBCCD 

Какой символ стоит на 100-й позиции после 8-го шага?

Первый символ слева стоит на позиции 1. 

Строки, состоящие из последовательностей цифр, формируются следующим образом. Первая строка состоит из одной единицы. Каждая из последующих строк создается следующим действием: берется предыдущая строка и после каждой ее цифры вставляется цифра на единицу большая и затем еще раз исходная цифра. Вот первые 3 строки, созданные по этому правилу:
(1) 1
(2) 121
(3) 121232121
(4) 121232121232343232121232121
Какая цифра будет стоять в позиции 1094 в строке (9)?

Первая цифра слева стоит на позиции 1 

Строки, состоящие из последовательностей цифр, формируются следующим образом. Первая строка состоит из четырех единиц. Каждая из последующих строк создается следующим действием: берется предыдущая строка и перед каждой ее цифрой вставляется цифра на единицу большая. Вот первые 3 строки, созданные по этому правилу:
(1) 1111
(2) 21212121
(3) 3221322132213221
Какая цифра будет стоять в позиции 479 в строке (9)?

Первая цифра слева стоит на позиции 1 

Строки, состоящие из последовательностей цифр, формируются следующим образом. Первая строка состоит из четырех единиц. Каждая из последующих строк создается следующим действием: берется предыдущая строка и после каждой ее цифры вставляется цифра на единицу большая. Вот первые 3 строки, созданные по этому правилу:
(1) 1111
(2) 12121212
(3) 1223122312231223
Какая цифра будет стоять в позиции 479 в строке (9)? 

Первая цифра слева стоит на позиции 1 

Строки, состоящие из последовательностей цифр, формируются следующим образом. Первая строка состоит из четырех единиц. Каждая из последующих строк создается следующим действием: берется предыдущая строка и после каждой ее цифры вставляется цифра на единицу большая. Вот первые 3 строки, созданные по этому правилу:
(1) 1111
(2) 12121212
(3) 1223122312231223
Какая цифра будет стоять в позиции 100 в строке (9)?

Первая цифра слева стоит на позиции 1 

На проверку сдается код, содержащий только описание классов!

Объявите базовый класс Aircraft (самолет), объекты которого создаются командой:

air = Aircraft(model, mass, speed, top)

где __model - модель самолета (строка, private); _mass - подъемная масса самолета (любое положительное число, protected ); _speed - максимальная скорость (любое положительное число, protected); _top - максимальная высота полета (любое положительное число, protected).

В каждом объекте класса Aircraft должны создаваться локальные атрибуты с именами: __model, _mass, _speed, _top и соответствующими значениями. Если передаваемые аргументы не соответствуют указанным критериям (строка, любое положительное число), то генерируется исключение командой:

raise TypeError('неверный тип аргумента')

Изменение и считывание значений атрибута __model должна осуществляться по имени (obj.model = ..., print(obj.model)

Далее, в программе объявите следующие дочерние классы:

PassengerAircraft - пассажирский самолет;
WarPlane - военный самолет.

Объекты этих классов создаются командами:

pa = PassengerAircraft(model, mass, speed, top, chairs)  
# chairs - число пассажирских мест (целое положительное число)

wp = WarPlane(model, mass, speed, top, weapons) 
# weapons - вооружение (словарь); ключи - название оружия, значение - количество

В каждом объекте классов PassengerAircraft и WarPlane должны формироваться локальные атрибуты с именами _chairs (protected)  и _weapons (protected) соответственно. Инициализация остальных атрибутов должна выполняться через инициализатор базового класса.

В инициализаторах классов PassengerAircraft и WarPlane проверять корректность передаваемых аргументов chairs и weapons. Если тип данных не совпадает, то генерировать исключение командой:

raise TypeError('неверный тип аргумента')

Пример создания объектов

pa1 = PassengerAircraft('МС-21', 1250, 8000, 12000.5, 140)
pa2 = PassengerAircraft('SuperJet', 1145, 8640, 11034, 80)
wp1 = WarPlane('Миг-35', 7034, 25000, 2000, {"ракета": 4, "бомба": 10})
wp2 = WarPlane('Су-35', 7034, 34000, 2400, {"ракета": 4, "бомба": 7})

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

Объявите класс с именем ListMath, объекты которого можно создавать командами:

lst1 = ListMath() # должен создаваться пустой список
lst2 = ListMath([1, 2, -5, 7.68]) # список с начальными значениями

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

lst = ListMath([1, "abc", -5, 7.68, True]) # ListMath: [1, -5, 7.68]

В каждом объекте класса ListMath должен быть публичный атрибут:

lst_math - ссылка на текущий список объекта (для каждого объекта создается свой список).

Также с объектами класса ListMath должны работать следующие операторы:

lst = lst + 76 # сложение каждого числа списка с определенным числом
lst = 6.5 + lst # сложение каждого числа списка с определенным числом

Команда print(lst1) - в скобка указывается объект класса - должна выводить элементы массива в одной строку, разделяя элементы одним пробелом. В случае если список не содержит элементов, должна выводиться надпись Cписок пуст.

lst1 = ListMath()
print(lst1)    # Список пуст

lst2 = ListMath([1, "abc", -5, 7.68, True]) 
print(lst2)    # 1 -5 7.68

Ввести в символьной форме два многочлена от x с целыми коэффициентами и вывести их произведение в порядке убывания степеней - также в символьной форме.

Ограничения: степень исходных многочленов не более 10, коэффициенты исходных многочленов по модулю не более 10⁴.

Входные данные
В двух строках находятся многочлены.

Выходные данные
В единственной строке выводится многочлен.

Игра для двух игроков определяется её деревом. Соперники делают ходы по очереди. Первый игрок начинает игру. Игра кончается или вничью, или победой одного из игроков. Листья дерева этой игры могут иметь значения, равные одному из трёх чисел: +1 - победа первого игрока, -1 - победа второго игрока, 0 - ничья. Ваша задача - определить, кто выиграет, если оба противника следуют правильной стратегии.

Входные данные
Узлы дерева пронумерованы последовательными целыми числами. Корень дерева всегда имеет номер 1. Первая строка входного файла содержит целое N - число узлов в дереве игры. Следующая N - 1 строка описывает узлы - одна строка для каждого узла (за исключением первого). Вторая строка содержит описание второго узла дерева, третья - третьего узла и т.д. Если узел является листом, первый символ строки - L, затем идёт пробел, затем номер родительского узла, ещё пробел и результат игры (+1 - победа первого игрока, -1 - победа второго, 0 - ничья). Если узел внутренний, то строка содержит N - первый символ, затем пробел и номер родительского узла. 2 <= N <= 1000.

Выходные данные
Выводится +1, если выигрывает первый игрок, -1, если второй, и 0 - в случае ничейного исхода.

Напишите "функцию голосования" bool Election(bool x, bool y, bool z) (C/C++), function Election (x, y, z:boolean): boolean (Pascal), возвращающую то значение (true или false), которое среди значений ее аргументов x, y, z встречается чаще.

Входные данные
Вводится 3 числа - x, y и z (x, y и z равны 0 или 1, 0 соответствует значению false, 1 соответствует значению true).

Выходные данные
Необходимо вывести  значение функции от x, y и z.

Напишите функцию
bool Xor (bool x, bool y) (C/C++),
function _Xor (x, y:boolean): boolean (Pascal),
def xor(x, y):(Python)
реализующую функцию "Исключающее ИЛИ" двух логических переменных x и y. Функция Xor должна возвращать true, если ровно один из ее аргументов x или y, но не оба одновременно равны true.

Входные данные
Вводится 2 числа - x и y (x и y равны 0 или 1, 0 соответствует значению false, 1 соответствует значению true).

Выходные данные
Необходимо вывести 0 или 1 - значение функции от x и y.

Напишите функцию double power (double a, int n) (C/C++), function power (a:real; n:longint): real (Pascal), вычисляющую значение aⁿ.
Входные данные
Вводится 2 числа - a (вещественное) и n (целое неотрицательное).

Выходные данные
Необходимо вывести  значение aⁿ.

Напишите рекурсивную функцию, возводящую число a в степень n. Гарантируется, что все числа "помещаются" в стандартные вещественные (a и ответ) и целые (n) типы.

Входные данные
Вводится 2 числа - a и n (число n может быть отрицательным).

Выходные данные
Необходимо вывести  значение aⁿ

Недавно на кружке по математике Миша узнал про разбиения на слагаемые. Разбиением числа \(n\) на слагаемые называется представление его в виде суммы неубывающего набора натуральных чисел. Например, \(9=1+2+2+4\) является разбиением числа 9 на слагаемые.

Миша называет разбиение интересным, если никакие два слагаемых в наборе не равны и не отличаются ровно на 1. Так, например, разбиение, приведенное выше не является интересным, а разбиение \(9=1+3+5\) — является.

Помогите Мише вывести все интересные разбиения числа \(n\) на слагаемые.

Формат входных данных
На ввод подается одно целое число \(n\) (\(1 \le n \le 80\)).

Формат выходных данных
Выведите все интересные разбиения числа \(n\) на слагаемые. Разбиения можно выводить в любом порядке. Соблюдайте формат из примера.

Вам дано положительное целое число N (\(1<=N<=10^{18}\)). Найдите количество пар целых чисел u и v (\(0<=u, v<=N\)) таких, что существуют два неотрицательных целых числа a и b, удовлетворяющих \(a\ xor\ b=u\) и \(a+b=v\). Здесь xor обозначает побитовое исключающее ИЛИ. Поскольку ответ может быть очень большим, вычислите его по модулю \(10^9+7\).

Входные данные
На вход подается положительное целое число N (\(1<=N<=10^{18}\)).

Выходные данные
Выведите количество возможных пар целых чисел u и v (\(0<=u, v<=N\)) , по модулю \(10^9+7\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3	5	u=0,v=0 (Пусть a=0,b=0, тогда 0 xor 0=0, 0+0=0) u=0,v=2 (Пусть a=1,b=1, тогда 1 xor 1=0, 1+1=2) u=1,v=1 (Пусть a=1,b=0, тогда 1 xor 0=1, 1+0=1) u=2,v=2 (Пусть a=2,b=0, тогда 2 xor 0=2, 2+0=2) u=3,v=3 (Пусть a=3,b=0, тогда 3 xor 0=3, 3+0=3)
2	1422	52277
3	1000000000000000000	787014179

 

Правильный способ определения конструктора данного класса при создании объектов классов:

   maths s1 = new maths();
   maths s2 = new maths(5, 5.4f);

A)

  public maths(int pp, single tt)
   {
       p = pp;
       t = tt;
   }

B) sample s;
C)

 public sample()
   {
      p = 0;
      t = 0.0f;
   }
  public sample(int pp, single tt)
  {
       p = pp;
       t = tt;
  }

D) s = new sample();