Вопросы по олимпиаде

[BDA]

Про 2ю. Еще раз скажу, что лучше запомнить алгоритм Эвклида для поиска НОД. А остальной код:

def nod(x, y):
    # Эвклид

n = int(input())
nums_iter = map(int, input().split())
res = next(nums_iter)
for i in nums_iter:
    res = nod(res, i)
print(res)

[ViktorR]

По третьей:

import math
def Geron(a1, b1, a2, b2, a3, b3):
    a = math.sqrt((a2 - a1)**2 + (b2 - b1)**2)
    b = math.sqrt((a3 - a2)**2 + (b3 - b2)**2)
    c = math.sqrt((a3 - a1)**2 + (b3 - b1)**2)
    p = (a + b + c) / 2
    return math.sqrt(p*(p-a)*(p-b)*(p-c))

x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input('Координаты вершин 4-х угольника').split())
print(x1, y1, x2, y2, x3, y3, x4, y4)
# Делим на треугольники:
# x1, y1, x2, y2, x3, y3 и x1, y1, x3, y3, x4, y4
print(round(Geron(x1, y1, x2, y2, x3, y3) + Geron(x1, y1, x3, y3, x4, y4)))

[FsGaCh]

А это мой вариант для 2 задачи
2)

def nod(x, y):
    for i in range(1, x + 1):
        if x % i == 0 and y % i == 0:
            nodd = i
    return int(nodd)
n = int(input())
nums = list(map(int, input().split()))
nodd = nod(nums[0], nums[1])
if len(nums) > 2:
    for i in range(2, len(nums)):
        nodd = nod(int(nodd), int(nums[i]))
print(nodd)

[ViktorR]

И всё же, как правильно отметил BDA, НОД следует искать через алгоритм Евклида.
Это самый быстрый алгоритм поиска НОД.
В моём решении я про это просто забыл.
Функцию можно записать так: (из ссылок ниже)

def nod(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return abs(a)

См. тут:
https://foxford.ru/wiki/informatika/...evklida-python
или тут:
https://ru.wikibooks.org/wiki/%D0%A0...B8%D0%B4%D0%B0

[FsGaCh]

Это задание, которое я сам сделал, но хотел узнать каким ешё образом это можно решить:

Определить количество предложений в заданном фрагменте текста.
Входные данные
В единственной строке задан фрагмент текста на английском языке, количество символов в котором не превышает 250. Гарантируется, что в тексте отсутствуют тире, дефисы, цифры и числа.
Выходные данные
Единственное число – количество предложений в фрагменте.

Мой вариант:

sentences = input()
puncts = ['...', '???', '!!!', '?!', '!?', '?!?', '!?!', '‽', '.', '??', '!!', '?', '!']
for i in puncts:
    sentences = sentences.replace(i, '///////////')
sentences = sentences.split('///////////')
if sentences[len(sentences) - 1] == '':
    sentences.pop()
print(len(sentences))

[ViktorR]

Так думаю, что тут лучше использовать регулярные выражения.
Типа поиска конца предложения по маске:
- <последний символ>[.]
- <последний символ>!
- <последний символ>\?
С этим знаком слабо, поэтому и написал условно.
Поисковик в помощь -"регулярные выражения python".
Вот один из примеров:
https://medium.com/nuances-of-progra...n-774fb2b62218

[FsGaCh]

Есть две коробки. В первой находится a шаров, во второй b (0 < a + b < 2147483648). Шары разрешается перекладывать из одной коробки в другую. Причем перекладывать в любую из коробок можно только столько шаров, сколько в ней находится. Необходимо определить, можно ли все шары сложить в одну коробку.
Входные данные
Каждая строка содержит два целых числа a и b, разделенных пробелом.
Выходные данные
Для каждого теста в отдельной строке вывести количество перекладываний, необходимое для того чтобы все шары находились в одной коробке, или -1, если это сделать невозможно.

Мой вариант(не работает, дошёл до сюда):

def myfunc(a, b, pos):
    global poss, am
    if a == b:
        h = am
        am = 0
        print(a, b)
        return 1 + h
    elif am > 0 and [a, b].sort() == poss[pos]:
        am = 0
        print(a, b)
        return -1
    else:
        if a > b:
            am += 1
            print(a, b)
            return myfunc(a - b, b + b, pos)
        else:
            am += 1
            print(a, b)
            return myfunc(a + a, b - a, pos)
a, b = map(int, input().split())
a1, b1 = map(int, input().split())
a2, b2 = map(int, input().split())
poss = [[a, b].sort(), [a1, b1].sort(), [a2, b2].sort()]
am = 0
print(myfunc(a, b, 0))
print('')
print(myfunc(a1, b1, 1))
print('')
print(myfunc(a2, b2, 2))

[ViktorR]

Рассмотрим вариант, когда шары перекладываются.
Если рассмотреть процесс с конца, то перед последним перекладыванием в обоих коробках число шаров должно быть поровну m = n, где m, n - число шаров в коробках. m + n = a + b.
Это значит, что число шаров должно быть чётным.
Перед этим шагом в одной коробке должно быть p = (a+b)/4, а во второй - q = 3(a+b)/4.
Если рассмотреть процесс дальше, то можно увидеть, что сумма числа шаров должна быть равна p + q =(2^n)p, где p - min(a,b), а n = 1,2,3, ...
При этом, если меньшее число p, то большее может быть из ряда q = 2^{n-1} p.
Это крайний вариант, когда q делится на p.
Пример: p = 356. Тогда q может быть из ряда: p, 2p, 4p, 8p, ...
Думаю, что из этого можно сделать вывод о том, что не следует использовать перебор.

PS: Это только предварительное решение.
Больше можно получить, если подумать, как определить допустимые соотношения между a и b.
Т.е. смотрим на сумму a + b, определяем n, определяем p.
Далее проверяем отношения вида a/p и b/p. ...
Голова плохо соображает, ...

[FsGaCh]

Спасибо)
Вот это задание я думаю что делаю правильно, но всё равно не получается. Что надо изменить?

Для заданного положительного целого A (1 ≤ A ≤ 100), вывести значение младшего не нулевого бита A.
Например, если A = 26, то его мы можем записать в двоичном виде, как 11010, и значение младшего бита A есть 10, и на выходе должно быть 2.
Другой пример выглядит следующим образом: при A = 88, это число A мы можем записать в двоичной форме 1011000, значение младшего бита в A есть 1000, и на выходе должно быть 8.
Входные данные
Каждая строка входных данных содержит только одно целое число A (1 ≤ A ≤ 100). Строка, содержащая "0" означает конец ввода, и эта строка не является частью входных данных.
Выходные данные
Для каждого числа, полученного на входе, в отдельной строке вывести значение его младшего не нулевого бита.

Мой вариант который не работает:

def convert_base(num, to_base=10, from_base=10):
    if isinstance(num, str):
        n = int(num, from_base)
    else:
        n = int(num)
    alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    if n < to_base:
        return alphabet[n]
    else:
        return convert_base(n // to_base, to_base) + alphabet[n % to_base]
a = int(input())
values = []
while a != 0:
    values.append(a)
    a = int(input())
for i in values:
    number = str(convert_base(i, to_base=2))
    l = number.split('1')
    if i is values[0]:
        del l[0]
    if l[0] == '':
        del l[0]
    if l[-1] == '':
        del l[-1]
    sorted(l)
    #num = convert_base(int('1' + l[-1]), from_base=2, to_base=10)
    #print(num)
    print(convert_base(10**len(l[-1]), from_base=2))

[ViktorR]

Что надо изменить?

Надо использовать двоичные операторы.
Вот пример без проверки ввода на ошибку.

while True:
    a = int(input('Введите целое число (0 - завершение ввода): '))
    if not a:                             # устали вводить
        break
    b = 1                                 # 000000001 - двоичная форма числа.
    while True:
        if a & b:                         # And (И) - логическая операция умножения.
            print(b)                      # Вывод результата
            break                         # Закончили обработку числа
        b = b << 1                        # Сдвиг влево на один бит

После преобразования к типу, числа хранятся в двоичном формате.
Числа в формате символов, например, '2' также хранятся в двоичном формате, но представляют собой код из таблицы.
Так, в ASCII таблице символу '2' соответствует код 50 (десятичное) или 32 (шестнадцатеричное).
Сдвиги битов числа можно делать вправо и влево.
При сдвиге влево правая часть разрядов числа дополняется нулями: 00011 -- 00110 -- 01100 -- 1100 -- 10000 -- 00000
При сдвиге вправо левая часть числа заполняется знаком. Т.е. если число больше нуля, то нулями, а иначе - единицами.

a = 26  =>
 1011000       1011000     ...     1011000
&             &                   &
 0000001       0000010     ...     0001000
 -------       -------             -------
 0000000       0000000             0001000

PS: По поводу корзин с шарами:
У меня получилось вот что:

from math import log2

def changeBolls(a, b):
    a, b = (max(a, b), min(a, b))  # a > b
    if (a + b) % 2:                # сумма не чётная
        return -1
    if a == b:                     # равны
        return 1
    k = a / b + 1                  # (a + b) / b
    n = int(log2(k))               # представление k как 2**n
    if k - 2 ** n:                 # не представимо
        return -1
    else:                          # представимо
        return n

a = 263
b = 8153
print(changeBolls(a, b))