Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Скриптовые языки программирования > Python
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.03.2021, 13:53   #141
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

А пример данных не запомнили? Для одного соревнования даны n и k, а затем n обычных показателей коней? Т.е. неизвестно какие именно k коней (их номера) специальной породы?
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 10.03.2021, 14:19   #142
FsGaCh
Пользователь
 
Регистрация: 08.02.2020
Сообщений: 78
По умолчанию

Да, неизвестно какие именно кони из специальной породы. Поэтому надо проверять все варианты и узнать какие кони (не имеет разницы специальной породы или обычной) смогут стать победителями после всех проверок.
FsGaCh вне форума Ответить с цитированием
Старый 10.03.2021, 15:36   #143
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Допустим: n = 3, k = 1. А показатели коней: 1 2 3. Тогда варианты показателей коней после усиления:
Код:
2 2 3 (усилен 1й)
1 4 3 (усилен 2й)
1 2 6 (усилен 3й)
И каков будет ответ? Только конь под номером 2 (имеет 50% шанс победы в первом варианте и 100% шанс победы во втором варианте) или кони под номерами 2 и 3 (каждый имеет по 100% шансу победы в одном из вариантов) или кони под номерами 1, 2 и 3 (т.к. у каждого есть ненулевой шанс победы в одном из вариантов)?
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )

Последний раз редактировалось BDA; 10.03.2021 в 16:55.
BDA вне форума Ответить с цитированием
Старый 10.03.2021, 16:44   #144
FsGaCh
Пользователь
 
Регистрация: 08.02.2020
Сообщений: 78
По умолчанию

Если конём специальной породы был конь под номером 1, тогда конь под номером 3 выиграл бы.
Если конём специальной породы был конь под номеров 2, тогда он выиграет.
А если же конём специальной породы будет конь под номером 3, тогда он выиграет.
В первом случае победит конь под номеров 3, во втором победит конь под номером 2, в третьем победит конь под номером 3. Значит, кони которые могут выиграть это Второй и Третий конь. Значит ответом для этого соревнования будет "2 3" потому что эти кони могут выиграть.
FsGaCh вне форума Ответить с цитированием
Старый 10.03.2021, 16:55   #145
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Да, я ошибся с описанием примера. Хотел получить ситуацию, что после усиления конь сравнялся по показателям с самым сильным конем без усиления.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 22.03.2021, 16:11   #146
FsGaCh
Пользователь
 
Регистрация: 08.02.2020
Сообщений: 78
По умолчанию

Несколько заданий которые я не смог решить:

1)Пастух Боран не боится оставить своего барана щепать траву в любом месте каменистого поля. Он уверен, что баран всегда найдет самый короткий путь к своему хозяину. Поле, где пасется баран, можно представить прямоугольником, разделенном на квадратные участки со стороной 1 метр. Этот участок или свободный от камней или на нем расположены камни, на которые баран не сумеет забраться. Баран находится на самом левом нижним участке, а Боран на самом правом верхнем участке. Баран может переходить с одного участка на любой соседний участок, если он не занят камнями. А вы сумеете узнать длину самого короткого пути барана к своему хозяину?

Входные данные

В первой строке заданы два натуральных числа N и M (1 <= N, M < 500) – размеры поля (количество строк и столбцов участков поля). В следующих N строках заданы через один пробел M чисел 0 или 1: 0 означает, что соответствующий участок свободен, 1 означает, что на участке находятся камни.

Входные данные

Одно число – длина кратчайшего пути барана к своему хозяину.

2)Два прямоугольника на плоскости со сторонами, параллельными осям координат, заданы координатами левой верхней вершины и нижней правой вершины. Определить площадь их общей части. Если прямоугольники не пересекаются, то вывести 0.

Входные данные

В первой строке задано число k (1 < k < 100), количество тестов. В каждой из следующих k строках заданы 8 целых чисел, координаты левой верхней вершины и нижней правой вершины первого прямоугольника и координаты левой верхней вершины и нижней правой вершины второго прямоугольника.

Выходные данные

Одно число – искомая площадь пересечения.

3)Дан треугольник и K точек. Для каждой точки нужно определить, где она находится – внутри, на границе, или снаружи.

Входные данные

В первой строке входных данных заданы шесть чисел – координаты вершин треугольника. Во второй строке задано число K (0 ≤ K ≤ 100). Далее заданы K точек – запросы. Каждая точка определяется двумя числами – координаты X и Y.

Все координаты – целые числа по модулю не превосходящие 103.

Выходные данные

Для каждого запроса одна строка – INSIDE, BORDER или OUTSIDE.


4)В таблице размером N*N, клетки заполнены случайным образом числами от –100 до 100. Напишите программу, которая поможет Чебурашке найти маршрут из самой нижней левой клетки в самую верхнюю правую клетку и удовлетворяющий следующим условиям:

Если клетки таблицы перенумеровать сверху вниз и слева направо, то клетки (i, j) Чебурашка может перейти в клетки (i – 1, j) (i – 1, j + 1), (i, j + 1), не выходя, конечно за границы таблицы.
Сумма чисел в клетках маршрута максимальна.
Входные данные

В первой строке входных данных задано одно натуральное число N (N <= 100). В следующих N строках заданы числа в клетках таблицы.

Выходные данные

Одно число – максимальная сумма в клетках искомого маршрута.

Мой вариант (Выдаёт ошибку):
Код:
def solve(y, x):
    global i, j, tiles, n, sums
    summ = tiles[n-1][0]
    if y == 0 and x == n - 1:
        sums.append(summ)
    if i > 0:
        summ += tiles[i-1][j]
        solve(i - 1, j)
        if j < n - 1:
            summ += tiles[i - 1][j + 1]
            solve(i - 1, j + 1)
    else:
        if j < n - 1:
            summ += tiles[i][j+1]
            solve(i, j+1)


sums = []
n = int(input())
tiles = []
for i in range(n):
    tiles.append(list(map(int, input().split())))
i = n - 1
j = 0
solve(i, j)
print(max(sums))
5)Рассмотрим множество целых чисел от 1 до 3n. Необходимо распределить эти числа в три массива a, b и c длиной n так, чтобы для любого i от 1 до n выполнялось следующее: ai + bi = ci

Формат входных данных

Единственная строка содержит целое число n (1 ≤ n ≤ 23).

Формат выходных данных

Если решения не существует, то в первой строке выведите единственное число -1. В ином случае, выведите 3 строки, в каждой по n целых чисел, разделенных пробелами. В первой строке должны находиться элементы массива a, во второй – элементы массива b, в третьей – массива c. Каждое число от 1 до 3n должно быть выведено ровно один раз.


Мой вариант (Выдаёт ошибку):
Код:
n = int(input())
numbers = [1, 3*n+1]
a = []
b = []
c = []
for i in range(3*n):
    for k in range(3*n):
        for j in range(3*n):
            if i != k and k != j and i != j:
                if numbers[i] + numbers[k] == numbers[j]:
                    a.append(numbers[i])
                    b.append(numbers[k])
                    c.append(numbers[j])
print(a)
print(b)
print(c)
6)Склад, имеющий форму квадрата со стороной N (1 <= N <= 1000), разбит на пронумерованные слева направо по строкам единичные квадраты (ячейки), в которых содержится огнеопасный груз. Ровно в полночь из-за неисправной электропроводки загорелась ячейка с номером K (1 <= K <= N^2). Каждая ячейка горит 1 мин, а потом пожар перебрасывается во все соседние ячейки через общие стороны. Сколько часов (H) и минут (M) длился пожар, если весь груз сгорел?

Входные данные

Два натуральных числа N и K.

Выходные данные

Два неотрицательных целых числа H и M (количество часов и минут).
FsGaCh вне форума Ответить с цитированием
Старый 22.03.2021, 18:43   #147
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

1) Почитайте и реализуйте волновой алгоритм.
2)
Код:
for _ in range(int(input())):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())
    x5, y5, x6, y6 = max(x1, x3), min(y1, y3), min(x2, x4), max(y2, y4)
    if (x6 > x5 and y5 > y6):
        print((x6 - x5) * (y5 - y6))
    else:
        print(0)
3) Надо выбрать какой-нибудь из существующих способов (например, сравнение суммы площадей треугольников, образованных точкой и сторонами исходного треугольника, с площадью самого треугольника; определение положения точки относительно прямых, содержащих стороны треугольника; векторный способ; метод геометрического луча) и реализовать.
4) На 100% не уверен (не нашел сайта, куда можно заслать решение для проверки на готовых тестах).
Код:
n = int(input())
tiles = []
for _ in range(n):
    tiles.append(list(map(int, input().split())))
for i in range(n - 1, -1, -1):
    for j in range(n):
        if i < n - 1 and j > 0:
            tiles[i][j] += max(tiles[i + 1][j], tiles[i + 1][j - 1], tiles[i][j - 1])
        elif i < n - 1:
            tiles[i][j] += tiles[i + 1][j]
        elif j > 0:
            tiles[i][j] += tiles[i][j - 1]
print(tiles[0][n - 1])
5) Придумал только 1 признак (сумма чисел нечетная), когда ответ сразу -1. А положительный (наверное) ответ ищется для n > 17 неприлично долго.
Код:
import time

sol_calls = 0

def sol(nums, arrs, n, i0 = 0):
    global sol_calls
    sol_calls += 1
    if len(nums) == 0:
        for arr in arrs:
            print(*arr)
        return True
    num = sorted(nums)[0]
    if i0 < n:
        arrs[0][i0] = num
        if sol(nums - set([num]), arrs, n, i0 + 1):
            return True
        arrs[0][i0] = None
    for i in range(i0):
        if arrs[1][i] is None:
            s = num + arrs[0][i]
            if s not in nums:
                continue
            arrs[1][i] = num
            arrs[2][i] = s
            if sol(nums - set([num, s]), arrs, n, i0):
                return True
            arrs[1][i] = None
            arrs[2][i] = None
    return False

n = int(input())

if ((1 + 3 * n) * 3 * n // 2) % 2 == 1:
    print(-1)
    exit()

start = time.time()
if not sol(set(range(1, 3 * n + 1)), [[None] * n, [None] * n, [None] * n], n):
    print(-1)
end = time.time()
print(end - start, "seconds")
print(sol_calls, "calls")
Код:
n = 13
1	2	3	4	5	6	7	8	9	10	11	12	13
14	16	17	19	29	27	31	28	21	22	24	25	26
15	18	20	23	34	33	38	36	30	32	35	37	39
0.04213428497314453 seconds
17578 calls

n = 16
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
17	19	20	22	24	37	38	34	35	30	25	27	28	33	31	32
18	21	23	26	29	43	45	42	44	40	36	39	41	47	46	48
1.529585361480713 seconds
584907 calls

n = 17
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
18	20	21	23	25	39	37	40	26	36	31	38	28	29	32	33	34
19	22	24	27	30	45	44	48	35	46	42	50	41	43	47	49	51
6.767983675003052 seconds
2599712 calls
6)
Код:
n, k = map(int, input().split())
i, j = divmod(k - 1, n)
m = max(i + j, n - i - 1 + j, n - j - 1 + i, n - i - 1 + n - j - 1) + 1
print(*divmod(m, 60))
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )

Последний раз редактировалось BDA; 23.03.2021 в 20:08.
BDA вне форума Ответить с цитированием
Старый 27.03.2021, 00:07   #148
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

К вопросу о 4-ой задаче.
Алгоритм её решения уже обсуждался в этой и других темах.
https://programmersforum.ru/showthread.php?t=338094
Странно, что автор поста не решил её.
Раньше - это пол храма и мышка, а тут несчастный Чебурашка.

PS: Меня, вначале, смутила фраза:
Цитата:
Если клетки таблицы перенумеровать сверху вниз и слева направо, то клетки (i, j)
поскольку "сверху вниз и слева направо", это вроде как:
Код:
1  6 11
2  7 12
3  8 13 ...
4  9 14
5 10 15
но тогда как быть с (i, j).
Тут просто не корректно передан исходный текст задания, думаю.
Думаю, что в исходном тексте говорилось о строках и столбцах.
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 27.03.2021, 00:58   #149
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

ViktorR, и правда. Помню, что в теме были задачки на ДП, но что 99% сходная - забыл (наверное, потому что не решал, а только прочел Ваши ответы).
P.S. Поздравляю с 1800 постом - круглое число
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )

Последний раз редактировалось BDA; 27.03.2021 в 01:00.
BDA вне форума Ответить с цитированием
Старый 27.03.2021, 12:24   #150
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Спасибо за поздравление.
Круглее не бывает.

Эта задача стала моим "коньком"
С книгой В. Потопахина, Turbo Pascal, Решение сложных задач, 2006 познакомился давно.
В ней изложено много интересных алгоритмов и предложены решения на Паскале.
К сожалению, так думаю, книга готовилась во временном цейтноте, иначе сложно объяснить множество огрех, которые в ней сделаны. В частности и по этому алгоритму.

Прямой путь выбора пути может быстро привести к верхней или правой границе (по данному примеру).
А далее путь не ветвится (движение вдоль границы) и следуют либо нули, либо минусы.

PS:
С более простой версией этой задачи столкнулся в пособии по ЕГЭ на 2021г.
Требуется найти решение с использованием Excel.
Так что это уже не очень олимпиадная задача.
Хотя как посмотреть и для каких регионов.
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
готовлюсь к олимпиаде по информатике salauat Паскаль, Turbo Pascal, PascalABC.NET 25 01.12.2013 21:32
Подготовиться к олимпиаде за лето UaKot Свободное общение 20 10.05.2013 18:53
Подготовка к региональной олимпиаде New man Помощь студентам 20 14.12.2012 21:01
Задачи по олимпиаде Darick Помощь студентам 7 23.12.2011 15:45
Как подготовиться к олимпиаде? Kn793 Помощь студентам 16 26.07.2008 12:22