Предметный тур. Информатика. 3 этап

Сначала предстоит получить комбинации из троек чисел, что можно сделать, используя вложенный цикл или специальные библиотеки комбинаторики. Затем для каждой комбинации посчитать наличие каждой из 10 цифр, для чего удобно использовать множество, добавляя в него по одному символу (цифре). Также можно делить каждое число в комбинации на разряды и учитывать встретившиеся цифры в массиве.

В случае, когда найдены все цифры в комбинации — прервать цикл.

Пример программы-решения

Ниже представлено решение на языке Python.

# Все цифры собрать
from itertools import combinations
numbers = map(int, input().split(' '))
for comb in list(combinations(numbers, 3)):
  combstr = str(comb)[1:-1].replace(', ', ' ')
  if len(set(combstr.replace(' ', ''))) == 10:
    print(" ".join(map(str, sorted(comb))))
    break

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

Пример программы-решения

Ниже представлено решение на языке Python.

import sys

rects = []
for line in sys.stdin:
  rects.append(list(map(int, line.split())))

left, right, top, bottom = \
 (min([min(x1, x2) for (color, x1, y1, x2, y2) in rects ])), \
 (max([max(x1, x2) for (color, x1, y1, x2, y2) in rects ])), \
 (max([max(y1, y2) for (color, x1, y1, x2, y2) in rects ])), \
 (min([min(y1, y2) for (color, x1, y1, x2, y2) in rects ])) \

width = right-left; height = top-bottom
matrix = [[-1 for _ in range(width+1)] for _ in range (height+1)]

for (color, x1, y1, x2, y2) in rects:
  for y in range(y1-y2):
    for x in range(x2-x1):
      matrix[y1-y-bottom][x1+x-left] = color

from collections import Counter
count_colors = Counter([item for row in matrix for item in row])

for color in sorted(count_colors)[1:]:
  print(f"{color} {count_colors[color]}")

Для решения необходимо использовать алгоритм деления числа «столбиком». При таком делении на каждом шаге образуется остаток, число различных остатков ограничено величиной делителя. Создайте массив логических значений длиной \(d\), затем в процессе деления отмечайте в массиве какие остатки встретились. При повторе — прервите цикл, посчитайте число полученных остатков (элементов массива со значением true), это число и будет ответом.

Пример программы-решения

Ниже представлено решение на языке Kotlin.

import java.util.Scanner

fun findLongestRecurringDecimal(n: Int): Int {
    var maxLength = 0
    var number = 0

    for (d in 2 until n) {
        val remainder = BooleanArray(d) { false } //значения по умолчанию
        var numerator = 1
        var position = 0

        while (numerator != 0 && !remainder[numerator]) {
            remainder[numerator] = true
            numerator = (numerator * 10) % d
            position++
        }

        if (position - 1 > maxLength) {
            maxLength = position - 1
            number = d
        }
    }

    return number
}

fun main() {
    val n = Scanner(System.`in`).nextInt()
    println(findLongestRecurringDecimal(n))
}

Размеры тестовых данных позволяют использовать пошаговый алгоритм, отслеживая путь лазерного луча с учетом направления движения. На каждом шаге проверяйте достижение границы поля (конец пути) или наличие зеркала. Смену направления луча на месте зеркала удобно выполнить, используя словарь. Нет необходимости создавать сетку в виде двумерного массива, достаточно создать словарь с ключом в формате \((X, Y)\), содержащем сведения о зеркалах.

Пример программы-решения

Ниже представлено решение на языке Python.

# laser beam and mirrors solution

from enum import Enum
class Direction(Enum):
  UP = 1; RIGHT = 2; DOWN = 3; LEFT = 4

rotate = { '/': {
    Direction.RIGHT: Direction.UP,
    Direction.LEFT: Direction.DOWN,
    Direction.DOWN: Direction.LEFT,
    Direction.UP: Direction.RIGHT },
            '\\': {
    Direction.RIGHT: Direction.DOWN,
    Direction.LEFT: Direction.UP,
    Direction.DOWN: Direction.RIGHT,
    Direction.UP: Direction.LEFT }
}

w, h, n_mirrors = map(int, input().split())
x, y = map(int, input().split())

mirrors = {}
for n in range(n_mirrors):
  mx, my, mtype = input().split()
  mirrors[(int(mx), int(my))] = mtype

def step_forward():
  global x, y
  match dir:
    case Direction.RIGHT: x += 1
    case Direction.LEFT: x -= 1
    case Direction.UP: y -= 1
    case Direction.DOWN: y += 1

dir = Direction.UP # default direction

step_forward() # entering the field 

while (x != 0 and x != w and y != 0 and y != h):
  #print(x, y, dir) # debug
  if (x, y) in mirrors:
    mirror_type = mirrors[(x, y)]
    dir = rotate[mirror_type][dir]
  step_forward()
print(x, y) # finish point

Сгенерируйте все варианты ключей из трех букв английского алфавита и считайте зашифрованный текст, данный в виде кодов символов. Далее для каждого ключа примените циклически операцию XOR для символов зашифрованного текста с номерами 1, 2, 3, затем 4, 5, 6 и т. д. Преобразуйте набор чисел в символы. Полученный набор символов проверьте на выполнение двух условий:

• все символы принадлежат к множеству печатных (printable);
• все указанные в условии слова присутствуют в расшифрованном тексте.

Подходящий под условия код и будет ответом на задачу.

Пример программы-решения

Ниже представлено решение на языке Python.

from itertools import count, product
from string import ascii_lowercase as letters, printable
from operator import xor

cipher = list(map(int, input().split(',')))

allowed = set(printable[:94] + ' ')
words = ["the", "of", "is", "by", "to", "this"]

pass_gen = product(map(ord, letters), repeat=3)
for password in pass_gen:
    plain, rep = "", (password[i % 3] for i in count())
    for char in map(chr, map(xor, cipher, rep)):
        if char not in allowed: break
        plain += char
    else:
        if all(word in plain for word in words):
          print("".join(map(chr, password)))
          break # password found