Задача 1:
Данный алгоритм работает за линейное время O(n), где n - количество элементов в массиве, и это является оптимальным алгоритмом для данной задачи. Поэтому, более эффективное решение здесь невозможно.
Задача 2:
Данное решение работает корректно, но не является эффективным.
Оно использует грубую силу для распределения программ на проверку среди сеньор-разработчиков, перебирая все возможные комбинации распределения и проверяя их на соответствие условиям задачи. Такой подход может работать для небольшого количества джунов и сенёров, но при больших значениях n, m и k может занять значительное количество времени.
Более эффективный подход к решению этой задачи - использование жадного алгоритма. В данном случае можно отсортировать массив джунов по возрастанию количества сеньор-разработчиков, необходимых для проверки каждой программы, и затем последовательно распределять их между сенёрами, начиная с самых "лёгких" программ. Это позволит минимизировать время, затрачиваемое на проверку всех программ.
попробуй так:
fun main() {
val input = readLine()!!.split(" ").map { it.toInt() }
val n = input[0]
val m = input[1]
val k = input[2]
val time = ((n + k - 1) / k) * m
println(time)
}
Задача 3:
Это решение выглядит правильным, но есть несколько моментов, которые могут быть улучшены:
Вместо использования переменной input для чтения первой строки, можно просто использовать readLine()!!.toInt().
Вместо проверки наличия каждого символа в строке можно использовать хэш-таблицу, чтобы проверять, что все символы встречаются хотя бы один раз.
Вложенный цикл for можно упростить, используя функцию windowed, чтобы получить все подстроки длины от 1 до n, а затем фильтровать только те, которые содержат все символы.
Вот улучшенное решение на Kotlin:
fun main() {
val n = readLine()!!.toInt()
val s = readLine()!!
var res = -1
val charSet = mutableSetOf<Char>()
for (length in 1..n) {
for (subStr in s.windowed(length)) {
charSet.addAll(subStr)
if (charSet.size == 4) {
res = if (res == -1) length else minOf(res, length)
}
charSet.clear()
}
}
println(res)
}
Задача 4:
Сразу заметно, что твое решение имеет временную сложность O(n^3), что может быть неэффективным при больших значениях n. Для каждого префикса длины l ты запускаешь вложенный цикл по всем возможным вариантам удаления элемента из этого префикса, а затем в этом префиксе создаешь словарь для подсчета количества вхождений каждого числа. Также в цикле проходишься по всем элементам словаря, чтобы проверить, что каждое число встречается в префиксе одинаковое количество раз.
Чтобы улучшить алгоритм, можно воспользоваться тем, что для любого скучного префикса существует такой скучный префикс меньшей длины. В частности, можно начать с максимального скучного префикса и постепенно уменьшать его длину до тех пор, пока не найдем скучный префикс. Таким образом, нам не придется проверять все возможные префиксы и их комбинации.
Вот пример, как это можно реализовать на Kotlin:
fun main() {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }
var counts = mutableMapOf<Int, Int>()
var i = 0
var j = n - 1
while (i < j) {
for (x in listOf(a[i], a[j])) {
counts[x] = counts.getOrDefault(x, 0) + 1
}
if (counts.size == 2 && counts.values.toSet().size == 1) {
println(j + 1)
return
}
if (counts[a[i]] == 1) {
counts.remove(a[i])
} else {
counts[a[i]] = counts[a[i]]!! - 1
}
if (counts[a[j]] == 1) {
counts.remove(a[j])
} else {
counts[a[j]] = counts[a[j]]!! - 1
}
i++
j--
}
println(n)
}
Задача 5:
Данное решение имеет экспоненциальную сложность, так как использует четыре вложенных цикла. Это может привести к тому, что программа будет работать слишком долго для больших входных данных.
Вы можете улучшить решение, используя два указателя. Один указатель будет указывать на начало подотрезка, а другой будет указывать на конец подотрезка. Вы можете перебирать все возможные комбинации начала и конца подотрезков, проверяя каждый из них на разумность.
Для этого вам нужно пройти по всем индексам i от 1 до n-1. Внутри цикла по i вы можете использовать два указателя l и r, которые будут начинаться с i и увеличиваться до n, суммируя a[l]...a[r]. Если сумма равна нулю, вы можете увеличить счетчик нормальных подотрезков. Если сумма больше нуля, вы можете увеличить r, чтобы увеличить сумму, а если сумма меньше нуля, вы можете увеличить l, чтобы уменьшить сумму.
Вот как может выглядеть код для такого решения:
fun main() {
val n = readLine()!!.toInt()
val a = readLine()!!.split("").map{ it.toInt() }
var count = 0
for (i in 0 until n-1) {
var sum = a[i]
for (j in i+1 until n) {
sum += a[j]
if (sum == 0) count++
}
}
println(count)
}
Это решение имеет сложность O(n^2), что гораздо быстрее, чем предыдущее решение.