MDS_2021.md

Школа мобильной разработки 2021

https://contest.yandex.ru/contest/24343/enter/

1. Посещение лекций

https://contest.yandex.ru/contest/24343/problems/1/

import Foundation

let arrNP = readLine()!.split(separator: " ").map { Int($0)! }
let n = arrNP[0]
let p = arrNP[1]
var arr = [Int](repeating: -1, count: n)
var ans = "YES"
for _ in 0 ..< p {
    let pair = readLine()!.split(separator: " ").map { Int($0)! }
    var index = pair[1] // индекс ведущей лекции
    // зависит ли ведущая от других лекций?
    while arr[index] != -1 {
        // зависит - ищем ведущую для ведущей
        index = arr[index]
    }
    if pair[0] == index {
        // если лекция ссылается сама на себя
        ans = "NO"
        break
    }
    arr[pair[0]] = index // фиксируем зависимость
}

print(ans)

2. Форматирование номера телефона

https://contest.yandex.ru/contest/24343/problems/2/

import Foundation

func printError(with str: String, isDebug: Bool = true) {
    if isDebug {
        print(str)
    } else {
        print("error")
    }
}

func getCh(from text: String, by position: Int) -> Character {
    return text[text.index(text.startIndex, offsetBy: position)]
}

func prefixFunction(for text: String) -> [Int] {
    var p = Array(repeating: 0, count: text.count)
    for i in 1 ..< text.count {
        var k = p[i - 1]
        while k > 0,
            getCh(from: text, by: k) != getCh(from: text, by: i) {
            k = p[k - 1]
        }
        if getCh(from: text, by: k) == getCh(from: text, by: i) {
            k += 1
        }
        p[i] = k
    }

    return p
}

func test() {
    // 1. приняли строку и избавились от пробелов
    var inputStr = readLine()!.trimmingCharacters(in: .whitespaces) // - внешних
        .replacingOccurrences(of: " ", with: "") // внутренних

    // 2. обработка + и 7
    // +7 если есть должно быть на первом месте
    if getCh(from: inputStr, by: 0) == "+" {
        if getCh(from: inputStr, by: 1) != "7" {
            printError(with: "error +7")
            return
        }
        // избавимся от +7 - заменим на 8
        inputStr.replaceSubrange(inputStr.startIndex ... inputStr.index(after: inputStr.startIndex), with: "8")
    }
    // если еще есть +, то это ошибка
    if inputStr.contains("+") {
        printError(with: "error +")
        return
    }

    // 3. обработка скобок: позиции 2 и 6 - считаются корректными для ( и ) соответственно
    if getCh(from: inputStr, by: 1) == "(" {
        if getCh(from: inputStr, by: 5) != ")" {
            printError(with: "error ()")
            return
        }
        // избавимся от скобок
        var index = inputStr.index(inputStr.startIndex, offsetBy: 5)
        inputStr.replaceSubrange(index ... index, with: "")
        index = inputStr.index(inputStr.startIndex, offsetBy: 1)
        inputStr.replaceSubrange(index ... index, with: "")
    }
    // если есть еще скобки то это ошибка
    if inputStr.contains("(") || inputStr.contains(")") {
        printError(with: "error ()2")
        return
    }

    // 4. обработка дефисов
    let p = prefixFunction(for: "--#" + inputStr)
    for (i, v) in p.enumerated() {
        if v > 0,
            (i > 2 && i < 5 + 3 || i == (p.count - 1)) {
            printError(with: "error -")
            return
        }
        if v == 2 {
            printError(with: "error --")
            return
        }
    }
    inputStr = inputStr.replacingOccurrences(of: "-", with: "")

    // 5. приведем номер к нормальному виду
    if inputStr.count != 11 {
        printError(with: "error 11")
        return
    }

    inputStr.insert(contentsOf: " (", at: inputStr.index(after: inputStr.startIndex))
    inputStr.insert(contentsOf: ") ", at: inputStr.index(inputStr.startIndex, offsetBy: 6))
    inputStr.insert("-", at: inputStr.index(inputStr.startIndex, offsetBy: 11))
    inputStr.insert("-", at: inputStr.index(inputStr.startIndex, offsetBy: 14))

    print(inputStr)
}

test()

3. Реконструкция домов

https://contest.yandex.ru/contest/24343/problems/3/

import Foundation

let bildings = readLine()!.split(separator: " ").map{Int($0)!}
var ans = bildings
// достраивать этажи можно только тогда
// 1. когда и слева и справа выше нет
// 2. и справа и слева есть выше - берем минимум из них

// ближайший максимум слева и справа
var left = [Int](repeating: 0, count: bildings.count)
var right = [Int](repeating: 0, count: bildings.count)

left[0] = 6 // слева максимума нет
var stack = [6, bildings[0]]
for i in 1..<bildings.count {
    let value = bildings[i]
    while value > stack.last! {
        _ = stack.popLast()
    }
    left[i] = stack.last!
    stack.append(value)
}

right[bildings.count - 1] = 6 // справа максимума нет
stack = [6, bildings[bildings.count - 1]]
for i in (0..<bildings.count - 1).reversed() {
    let value = bildings[i]
    while value > stack.last! {
        _ = stack.popLast()
    }
    right[i] = stack.last!
    stack.append(value)
}

for i in 0..<bildings.count {
    let l = left[i] == 6 ? -1 : left[i]
    let r = right[i] == 6 ? -1 : right[i]
    if max(l, r) == -1 {
        ans[i] = 5
    } else {
        ans[i] = max(bildings[i], min(l, r))
    }
}
print(ans.map{String(describing: $0)}.joined(separator: " "))