MDS_2022.md

Вступительное задание в ШМР 2022

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

A. Самая сложная буква

https://contest.yandex.ru/contest/35182/problems/A/

import Foundation

let num = Int(readLine()!)! // сколько букв
let str = readLine()!.map({ String($0) })
var t = [0] + readLine()!.split(separator: " ").map({ Int($0)! }) // потраченное время

var maxT = 0
var char = str[num - 1]
for i in (1 ..< t.count).reversed() {
    let curT = t[i] - t[i - 1]
    if curT > maxT {
        char = str[i - 1]
        maxT = curT
    }
}

print(char)

B. Уникальные пользователи

https://contest.yandex.ru/contest/35182/problems/B/

import Foundation

let num = Int(readLine()!)!
var set = Set<String>()

for _ in 0 ..< num {
    let user = readLine()!.split(separator: "@")
    var name = user.first!.split(separator: "-").first!.split(separator: ".").joined(separator: "")
    if name.isEmpty {
        name = "1"
    }
    var domain = user.last!.split(separator: ".").dropLast().joined(separator: "")
    if domain.isEmpty {
        domain = String(user.last!)
    }
    set.insert("\(name)@\(domain)")
}

print(set.count)

C. Акции

https://contest.yandex.ru/contest/35182/problems/C/

import Foundation

let num = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map({ Int($0)! })

var profit = 0 // прибыль на участке
var ans = 0

if num > 1 {
    var curMax = arr[num - 1]
    arr[0 ... num - 2].enumerated().reversed().forEach { index, val in
        if val <= arr[index + 1] {
            profit = curMax - val
        } else {
            curMax = val
            ans += profit
            profit = 0
        }
    }
}

print(ans + profit)

D. Прокачай героя

https://contest.yandex.ru/contest/35182/problems/D/

import Foundation

let num = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map({ Int($0)! })

var cntNegative = 0
var minNegative = -1_000_000_001
var maxNegative = 0
var cntZero = 0
var cntPositive = 0
var minPositive = 1_000_000_001
var res = 1

arr.forEach { item in
    if item > 0 {
        cntPositive += 1
        minPositive = min(item, minPositive)
        if res != 0 {
            res = res > 0 ? 1 : -1
        }
    } else if item == 0 {
        cntZero += 1
        res = 0
    } else {
        cntNegative += 1
        minNegative = max(minNegative, item)
        maxNegative = min(maxNegative, item)
        if res != 0 {
            res = res > 0 ? -1 : 1
        }
    }
}

// рассмотрел все возможные случаи!
if cntZero > 1 {
    // без разницы
    print(0)
} else if res < 0 {
    // выкидываем минимальный негатив
    print(minNegative)
} else if res == 0 {
    // надо думать)
    if cntNegative > 0 {
        if cntNegative % 2 == 0 {
            print(0)
        } else {
            print(minNegative) // здесь без  разницы
        }
    } else {
        print(0)
    }
} else if res > 0 {
    if cntNegative > 0 {
        if cntPositive > 0 {
            print(minPositive)
        } else {
            // надо выкинуть макс негатив
            print(maxNegative)
        }
    } else {
        print(minPositive)
    }
}

E. Магическая подстрока

https://contest.yandex.ru/contest/35182/problems/E/

import Foundation

let t = readLine()!.map({ String($0) })
let s = readLine()!.map({ String($0) })

var dirS = [String: Int]() // наша заданная строка
s.forEach { item in
    if dirS[item] == nil {
        dirS[item] = 0
    }
    dirS[item]! += 1
}

// границы окна
var left = 0
var right = s.count - 1

var dirT = [String: Int]()
var curDif = 0 // текущее различие
for i in left ... right {
    let char = t[i] // очередной символ из текста
    // точно нет в S
    if dirS[char] == nil {
        curDif += 1 // есть отличие
    }
    if dirT[char] == nil {
        dirT[char] = 0
    }
    dirT[char]! += 1
}

// пройдемся по ключам S и пособираем еще отличия
dirS.keys.forEach { key in
    curDif += max(dirS[key]! - (dirT[key] ?? 0), (dirT[key] ?? 0) - dirS[key]!)
}

var isOK = false
if curDif == 2 {
    print(left)
    isOK = true
} else {
    right += 1
    // состояние на следующем шаге поменяется следующим образом
    // первый символ уйдет - как то повлияв на разницу - убрать из dirT
    // добавится новый символ в конце - добавить в dirT - тоже окажет влияние на разницу
    while right < t.count {
        if t[left] == t[right] {
            // старый и новый символы одинаковые, после сдвига будет то же различие
            // не имеет смысла что-то менять - сразу сдвигаем
            left += 1
            right += 1
            continue
        }

        // убрать символ из dirT
        var char = t[left]
        // а как он повлиял на dif?
        curDif += dirT[char] == dirS[char] ? 1 : -1
        dirT[char]! -= 1
        left += 1
        // добавить новый символ в dirT
        char = t[right]
        if dirT[char] == nil {
            dirT[char] = 0
        }
        dirT[char]! += 1
        // а как он повлиял на dif?
        curDif += dirT[char] == dirS[char] ? -1 : 1
        if curDif == 2 {
            print(left)
            isOK = true
            break
        }
        right += 1
    }
}

if !isOK {
    print(-1)
}