Рубрика «Олимпиада»

Олимпиада по информатике 2025-2026 муниципальный этап Сказ о Луче Великой Справедливости

Олимпиада по информатике 2025-2026 муниципальный этап Сказ о Луче Великой Справедливости Скачать

import sys

input_data = sys.stdin.read().strip().split()
if not input_data:
    sys.exit(0)

it = iter(input_data)
t = int(next(it))

def check_axis_and_diagonal(rects):
    """
    Проверка подзадач 2 и 3:
    - горизонтальная прямая (по y)
    - вертикальная прямая (по x)
    - прямая под 45° (u = x + y)
    - прямая под 135° (v = x - y)
    """
    # вертикальная: пересечение всех [x1, x2]
    max_x1 = max(r[0] for r in rects)
    min_x2 = min(r[2] for r in rects)
    if max_x1 <= min_x2:
        return True

    # горизонтальная: пересечение всех [y1, y2]
    max_y1 = max(r[1] for r in rects)
    min_y2 = min(r[3] for r in rects)
    if max_y1 <= min_y2:
        return True

    # 45 градусов: u = x + y
    # Для прямоугольника [x1,x2]×[y1,y2]:
    # минимум u в (x1,y1), максимум в (x2,y2)
    u_l = -10**30
    u_r = 10**30
    for x1, y1, x2, y2 in rects:
        u_min = x1 + y1
        u_max = x2 + y2
        if u_min > u_l:
            u_l = u_min
        if u_max < u_r:
            u_r = u_max
    if u_l <= u_r:
        return True

    # 135 градусов: v = x - y
    # Для прямоугольника:
    # минимум v в (x1,y2), максимум в (x2,y1)
    v_l = -10**30
    v_r = 10**30
    for x1, y1, x2, y2 in rects:
        v_min = x1 - y2
        v_max = x2 - y1
        if v_min > v_l:
            v_l = v_min
        if v_max < v_r:
            v_r = v_max
    if v_l <= v_r:
        return True

    return False


def sign(x):
    if x > 0:
        return 1
    if x < 0:
        return -1
    return 0


def line_intersects_all(p1, p2, rects):
    """
    Проверка: прямая через точки p1, p2 пересекает ли ВСЕ прямоугольники.
    rects: список (x1,y1,x2,y2)
    """
    x1, y1 = p1
    x2, y2 = p2
    if x1 == x2 and y1 == y2:
        return False  # вырожденная прямая

    dx = x2 - x1
    dy = y2 - y1

    for (rx1, ry1, rx2, ry2) in rects:
        # четыре угла
        corners = (
            (rx1, ry1),
            (rx1, ry2),
            (rx2, ry1),
            (rx2, ry2),
        )
        mn = 0
        mx = 0
        first = True
        for cx, cy in corners:
            # ориентация (x1,y1)->(x2,y2) и (x1,y1)->(cx,cy)
            # cross = (x2-x1)*(cy-y1) - (y2-y1)*(cx-x1)
            cross = dx * (cy - y1) - dy * (cx - x1)
            s = sign(cross)
            if first:
                mn = mx = s
                first = False
            else:
                if s < mn:
                    mn = s
                if s > mx:
                    mx = s
        # если все углы строго по одну сторону (mn>0 или mx<0) — не пересекает
        if mn > 0 or mx < 0:
            return False
        # иначе есть точка на линии или по разные стороны ⇒ пересечение есть
    return True


out_lines = []

for _ in range(t):
    n = int(next(it))
    rects = []
    for _j in range(n):
        x1 = int(next(it))
        y1 = int(next(it))
        x2 = int(next(it))
        y2 = int(next(it))
        rects.append((x1, y1, x2, y2))

    # Подзадача 1: n ≤ 2 — всегда Yes
    if n <= 2:
        out_lines.append("Yes")
        continue

    # Быстрая проверка осевых и 45/135° прямых (подзадачи 2 и 3)
    if check_axis_and_diagonal(rects):
        out_lines.append("Yes")
        continue

    # Подзадача 4: n ≤ 200 — перебор всех направлений по парам углов
    # Если n больше — не лезем в куб по времени (на больших тестах всё равно
    # нужны более продвинутые выпуклые оболочки, которых здесь нет),
    # поэтому остаёмся только с предыдущими проверками.
    if n > 200:
        out_lines.append("No")
        continue

    # подготовим углы
    corners_per_rect = []
    for x1, y1, x2, y2 in rects:
        corners_per_rect.append([
            (x1, y1),
            (x1, y2),
            (x2, y1),
            (x2, y2),
        ])

    found = False
    # перебираем пары различных прямоугольников
    for i in range(n):
        if found:
            break
        for j in range(i + 1, n):
            # каждую пару углов (один от i, другой от j) – кандидат на прямую
            for p1 in corners_per_rect[i]:
                if found:
                    break
                for p2 in corners_per_rect[j]:
                    if p1 == p2:
                        continue
                    if line_intersects_all(p1, p2, rects):
                        found = True
                        break
        # конец по j
    out_lines.append("Yes" if found else "No")

sys.stdout.write("\n".join(out_lines))

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

import sys

input_data = sys.stdin.read().strip().split()

if not input_data:

sys.exit(0)

it = iter(input_data)

t = int(next(it))

def check_axis_and_diagonal(rects):

"""

Проверка подзадач 2 и 3:

- горизонтальная прямая (по y)

- вертикальная прямая (по x)

- прямая под 45° (u = x + y)

- прямая под 135° (v = x - y)

"""

# вертикальная: пересечение всех [x1, x2]

max_x1 = max(r[0] for r in rects)

min_x2 = min(r[2] for r in rects)

if max_x1 <= min_x2:

return True

# горизонтальная: пересечение всех [y1, y2]

max_y1 = max(r[1] for r in rects)

min_y2 = min(r[3] for r in rects)

if max_y1 <= min_y2:

return True

# 45 градусов: u = x + y

# Для прямоугольника [x1,x2]×[y1,y2]:

# минимум u в (x1,y1), максимум в (x2,y2)

u_l = -10**30

u_r = 10**30

for x1, y1, x2, y2 in rects:

u_min = x1 + y1

u_max = x2 + y2

if u_min > u_l:

u_l = u_min

if u_max < u_r:

u_r = u_max

if u_l <= u_r:

return True

# 135 градусов: v = x - y

# Для прямоугольника:

# минимум v в (x1,y2), максимум в (x2,y1)

v_l = -10**30

v_r = 10**30

for x1, y1, x2, y2 in rects:

v_min = x1 - y2

v_max = x2 - y1

if v_min > v_l:

v_l = v_min

if v_max < v_r:

v_r = v_max

if v_l <= v_r:

return True

return False

def sign(x):

if x > 0:

return 1

if x < 0:

return -1

return 0

def line_intersects_all(p1, p2, rects):

"""

Проверка: прямая через точки p1, p2 пересекает ли ВСЕ прямоугольники.

rects: список (x1,y1,x2,y2)

"""

x1, y1 = p1

x2, y2 = p2

if x1 == x2 and y1 == y2:

return False # вырожденная прямая

dx = x2 - x1

dy = y2 - y1

for (rx1, ry1, rx2, ry2) in rects:

# четыре угла

corners = (

(rx1, ry1),

(rx1, ry2),

(rx2, ry1),

(rx2, ry2),

)

mn = 0

mx = 0

first = True

for cx, cy in corners:

# ориентация (x1,y1)->(x2,y2) и (x1,y1)->(cx,cy)

# cross = (x2-x1)*(cy-y1) - (y2-y1)*(cx-x1)

cross = dx * (cy - y1) - dy * (cx - x1)

s = sign(cross)

if first:

mn = mx = s

first = False

else:

if s < mn:

mn = s

if s > mx:

mx = s

# если все углы строго по одну сторону (mn>0 или mx<0) — не пересекает

if mn > 0 or mx < 0:

return False

# иначе есть точка на линии или по разные стороны ⇒ пересечение есть

return True

out_lines = []

for _ in range(t):

n = int(next(it))

rects = []

for _j in range(n):

x1 = int(next(it))

y1 = int(next(it))

x2 = int(next(it))

y2 = int(next(it))

rects.append((x1, y1, x2, y2))

# Подзадача 1: n ≤ 2 — всегда Yes

if n <= 2:

out_lines.append("Yes")

continue

# Быстрая проверка осевых и 45/135° прямых (подзадачи 2 и 3)

if check_axis_and_diagonal(rects):

out_lines.append("Yes")

continue

# Подзадача 4: n ≤ 200 — перебор всех направлений по парам углов

# Если n больше — не лезем в куб по времени (на больших тестах всё равно

# нужны более продвинутые выпуклые оболочки, которых здесь нет),

# поэтому остаёмся только с предыдущими проверками.

if n > 200:

out_lines.append("No")

continue

# подготовим углы

corners_per_rect = []

for x1, y1, x2, y2 in rects:

corners_per_rect.append([

(x1, y1),

(x1, y2),

(x2, y1),

(x2, y2),

])

found = False

# перебираем пары различных прямоугольников

for i in range(n):

if found:

break

for j in range(i + 1, n):

# каждую пару углов (один от i, другой от j) – кандидат на прямую

for p1 in corners_per_rect[i]:

if found:

break

for p2 in corners_per_rect[j]:

if p1 == p2:

continue

if line_intersects_all(p1, p2, rects):

found = True

break

# конец по j

out_lines.append("Yes" if found else "No")

sys.stdout.write("\n".join(out_lines))

Олимпиада по информатике 2025-2026 муниципальный этап Хомяк и двоичные тайны

Олимпиада по информатике 2025-2026 муниципальный этап Хомяк и двоичные тайны Скачать 1. Что делает твой алгоритм (коротко) Задача: посчитать количество чисел x таких, что0 ≤ x ≤ R и popcount(x) ≡ 0 (mod K). Твой код делает следующее: Читает n, K, R (где R — десятичная строка). Переводит R в двоичную строку bin_str. Пусть L …

Олимпиада по информатике 2025-2026 муниципальный этап Нечётно-степенные числа

Олимпиада по информатике 2025-2026 муниципальный этап Нечётно-степенные числа Скачать Короткое объяснение решения Нужно найти первые m подряд идущих чисел на отрезке [l,r][l, r][l,r], у которых все простые делители имеют нечётные степени. Такие числа называют нечётно-степенными. 1. Построение SPF-решета Сначала мы создаём массив SPF (Smallest Prime Factor) для всех чисел до r.SPF для числа — это …

Олимпиада по информатике 2025-2026 муниципальный этап Магическая семёрка

Олимпиада по информатике 2025-2026 муниципальный этап Магическая семёрка Скачать Идея:Пусть f(x) — количество «магических» чисел ≤ x.Число магическое, если: делится на 7 или оканчивается цифрой 7 Посчитаем f(x) по включению–исключению: cnt_div7 = x // 7 — делятся на 7 cnt_end7 — числа, оканчивающиеся на 7: 7, 17, 27, …если x >= 7, то cnt_end7 = …

Олимпиада по информатике 2025-2026 муниципальный этап Хомячья раскраска

Олимпиада по информатике 2025-2026 муниципальный этап Хомячья раскраска Скачать Задача «Хомячья раскраска» — решение на Python Идея решения Цвет клетки задаётся по формуле: color(i, j) = ((i + j — 2) mod k) + 1, то есть цвет зависит только от суммы индексов. Рассмотрим остатки: r = (i — 1) mod k, s = (j …

Олимпиада по информатике 2025-2026 муниципальный этап Республика Татарстан

Олимпиада по информатике 2025-2026 муниципальный этап Республика Татарстан. Всероссийская олимпиада по информатике задания и ответы для муниципального этапа 2025-2026. A. Хомячья раскраска Скачать Решение B. Магическая семёрка Скачать Решение C. Нечётно-степенные числа Скачать Решение D. Хомяк и двоичные тайны Скачать Решение E. Сказ о Луче Великой Справедливости Скачать Решение

Олимпиада по информатике «Искусственный интеллект» 2025–2026 — 9–11 класс

Олимпиада по информатике, профиль «Искусственный интеллект» 2025–2026 — школьный этап, 9–11 класс. Материалы школьного тура ВсОШ по профилю «Искусственный интеллект» для 9–11 классов включают сложные алгоритмические задачи, анализ данных и основы машинного обучения. Рекомендуется для подготовки к муниципальному этапу и олимпиадам по ИИ и информатике. Задания скачать задание (9–11) Решения: скачать решения (9–11) Смотрите также: …

Олимпиада по информатике «Искусственный интеллект» 2025–2026 — 7–8 класс

Олимпиада по информатике «Искусственный интеллект» 2025–2026 — школьный этап, 7–8 класс. Раздел содержит задания и решения школьного этапа олимпиады по информатике в профиле «Искусственный интеллект» для 7–8 классов. Задания направлены на моделирование логических цепочек, анализ данных и базовые алгоритмы обучения. Задания скачать задание (7–8) Решения: скачать решения (7–8) Смотрите также:

Олимпиада по информатике «Искусственный интеллект» 2025–2026 — 5–6 класс

Олимпиада по информатике, профиль «Искусственный интеллект» 2025–2026 — школьный этап, 5–6 класс. На этой странице представлены задания и решения школьного тура ВсОШ по информатике для 5–6 классов в профиле «Искусственный интеллект». Задачи направлены на развитие логического мышления, распознавание закономерностей и работу с простыми алгоритмами искусственного интеллекта. Задания скачать задание (5–6) Решения: скачать решения (5–6) Смотрите …

Олимпиада по информатике «Информационная безопасность» 2025–2026 — 10–11 класс

Олимпиада по информатике «Информационная безопасность» 2025–2026 — школьный этап, 10–11 класс. Материалы для старших классов включают сложные задания по анализу уязвимостей, работе с шифрами и логам безопасности. Подходит для подготовки к муниципальному и региональному этапам олимпиады. Теоретический тур скачать задание (теория) | доп. файлы Решения: скачать Смотрите также: