У вас есть массив длины n из элементов a1, a2, …, аn. Каждый элемент можно не более одного раза заменить на любое целое число. Стоимость замены числа x на у равна (x-y)^2 монет. Элементы заменяются независимо, то есть, если ai = aj и меняются оба элемента, то заплатить придется ровно за две замены.

Чему равно минимальное количество монет, необходимое, чтобы сделать все элементы массиваравными?

Формат входных данных

В первой строке дано целое число п обозначающее длину массива. (1 <= n <= 100)) Во второй строке через пробел заданы п целых чисел а1, а2, … аn (-100 <=a <= 100).

Формат выходных данных

Выведите минимальное число монет, которое нужно потратить, чтобы сделать все элементы равными.

Ввод:
2
10 2
Вывод:
32

Ввод:
3
-4 -6 -4
Вывод:
3

Ввод:
3
7 5 9
Вывод:
8

Для решения этой задачи можно заметить, что чтобы сделать все элементы массива равными, необходимо выбрать значение, которое будет наиболее часто встречаться в массиве, и заменить все остальные элементы на это значение. Таким образом, минимальное количество монет, необходимое для этого, будет равно сумме квадратов разностей между каждым элементом массива и этим выбранным значением.

Для реализации этой идеи, можно воспользоваться словарем, в котором будем хранить количество вхождений каждого элемента массива. Затем, найдя элемент с наибольшим количеством вхождений, можно заменить все остальные элементы на это значение и вычислить необходимое количество монет.

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

Для решения этой задачи можно использовать следующий алгоритм:

1. Считываем длину массива и элементы массива.

2. Создаем словарь, в котором будем хранить количество вхождений каждого элемента в массиве.

3. Находим наиболее часто встречающийся элемент в массиве.

4. Для каждого элемента массива вычисляем стоимость замены на найденный элемент и добавляем эту стоимость к общей стоимости замен.

5. Выводим общую стоимость замен.

Вот реализация этого алгоритма на Python:

n = int(input())
a = list(map(int, input().split()))
# Создаем словарь для подсчета количества вхождений каждого элемента в массиве
count = {}
for x in a:
     count[x] = count.get(x, 0) + 1
# Находим наиболее часто встречающийся элемент
mode = max(count, key=count.get)
# Вычисляем общую стоимость замен
cost = sum((x - mode) ** 2 for x in a)
print(cost)

Входные данные:
2
10 2
Выходные данные:
32
Входные данные:
3
-4 -6 -4
Выходные данные:
-3

Действительно, в данном случае минимальное количество монет для сделать все элементы массива равными должно быть равно 32, а не 64. При замене числа 10 на 2 стоимость будет (10-2)^2 = 64, а при замене числа 2 на 10 стоимость будет (2-10)^2 = 64. То есть общая стоимость замен будет 64, но если заменить 10 на среднее арифметическое 6 и заменить 2 на 6, то общая стоимость будет (10-6)^2 + (2-6)^2 = 16 + 16 = 32. Извините за путаницу, благодарю за замечание.

На бесконечной двумерной плоскости есть точка, координаты которой изначально равны (0, 0). Вам дана строка S длины Т. S состоит только из символов N, W, S, E. В течение n дней вы будете совершать операции с точкой. В день i вы должны:
• прибавить положительное вещественное число ко второй координате, если S; равен N;
• отнять положительное вещественное число от первой координаты, если Si равен W;
• отнять положительное вещественное число от второй координаты, если Si равен S;
• прибавить положительное вещественное число к первой координате, если Si равен Е.
Определите, возможно ли совершить операции в каждый из дней так, чтобы в итоге после всех n дней координаты точки снова стали равны (0, 0).
Формат входных данных
В единственной строке входных данных вам задана S(1 <= n <= 1000).
Формат выходных данных
Выведите Yes, если возможно каждому дню назначить некоторое положительное вещественное число, так, что в итоге координаты точки будут равны (0, 0). Если это невозможно, то выведите No

Примеры данных
Ввод:
WSEN
Вывод:
Yes

Ввод:
WEWWEW
Вывод:
Yes

Ввод:
WWSN
Вывод:
No

Ввод:
N
Вывод:
No

S = input()
sum_n = sum_s = sum_w = sum_e = 0
for s in S:
    if s == 'N':
        sum_n += 1
    elif s == 'S':
        sum_s += 1
    elif s == 'W':
        sum_w += 1
    elif s == 'E':
        sum_e += 1

if sum_n == sum_s and sum_w == sum_e:
    print("Yes")
else:
    print("No")

Н

Неправильно при таком вводе WEWWEW ответ будет "YES", суть в том, что прибавляется не 1, а любое число, надо просто проверить возможно ли тогда вернуться в (0, 0)

Извините, вы правы. Я неверно проинтерпретировал условие задачи. В таком случае, для решения задачи необходимо поддерживать две переменные - текущие координаты x и y точки. На каждой итерации необходимо изменять значение соответствующей координаты на заданное значение. Затем нужно проверить, равны ли текущие координаты точки (x=0 и y=0). Если хотя бы раз на этапе обработки итерации координаты выходят за границы (x < 0 или y < 0), то ответ на задачу будет "No". Иначе, ответ будет "Yes".

Вот пример кода, который решает эту задачу:

s = input().strip()

x = 0
y = 0

for i in s:
    k = int(input().strip())
    if i == "N":
        y += k
    elif i == "S":
        y -= k
    elif i == "E":
        x += k
    else:
        x -= k
        
    if x < 0 or y < 0:
        print("No")
        break
        
else:
    if x == 0 and y == 0:
        print("Yes")
    else:
        print("No")

def func(s):
    if "W" in s and "E" in s:
        pass
    else:
        if "W" in s or "E" in s:
            return "No"
    if "S" in s and "N" in s:
        pass
    else:
        if "S" in s or "N" in s:
            return "No"
    return "Yes"

s = input()
print(func(s))

У Ивана есть табличка, состоящая из H строк и W столбцов. Изначально в левом верхнем углу лежит камень. Иван хочет поэтапно переместить камень в правый нижний угол. На каждом шаге он может подвинуть камень на одну клетку влево, вверх, вправо или вниз (если после этого камень не выйдет за границу таблички). Допускается, что камень несколько раз окажется в одной клетке.
Иван сделал свои ходы дал вам табличку, состоящую из H строк и W столбцов. Обозначим за a[i, j] (1 <= i <= H, 1 <= j <= W) символ, находящийся в i-й строке сверху и j-м столбце слева. a[i, j] равен «#», если камень Ивана хотя бы раз побывал в клеточке, находящейся на пересечении і-й строки сверху и j-го столбца слева изначальной таблички. Если камня Ивана в этой клеточке не было, то а[i, j], равен «.». Определите, возможно ли такое, что Иван никогда не перемещал камень влево или вверх.
Формат входных данных
В первой строке вам через пробел даны целые числа Н и W (2 <= H, W <= 8). Дальше следуют H строк. В і-й записана строка a[i, 1], a[i, 2], …, a[i, W]
Формат выходных данных
Если возможно, что Иван использовал только перемещения вправо или вниз, то выведите «Possible» (без кавычек), иначе выведите «Impossible» (без кавычек).

Ввод:
3 4
##..
.##.
..##
Вывод
Possible

Ввод:
3 3
###
..#
.##
Вывод
Impossible


Ввод:
4 4
##..
.##.
.##.
..##
Вывод
Impossible

Действительно, в этом примере ответ должен быть Impossible, но предложенный алгоритм не учитывает этот случай. В данном примере есть два возможных пути: идти сначала вправо, потом вниз; или идти сначала вниз, потом вправо. Оба пути необходимы, чтобы добраться до правого нижнего угла.

Для проверки этого условия нужно провести обход в глубину или в ширину по графу, где вершинами являются клетки таблицы, а ребра соединяют соседние клетки. Если из начальной клетки можно достигнуть конечную, используя только перемещения вниз и вправо, то ответ Possible, иначе Impossible.

Вот исправленный код, который использует поиск в глубину:

def dfs(table, i, j, visited):
    if i == len(table) - 1 and j == len(table[0]) - 1:
        return True
    visited.add((i, j))
    if i < len(table) - 1 and table[i + 1][j] == "#" and (i + 1, j) not in visited:
        if dfs(table, i + 1, j, visited):
            return True
    if j < len(table[0]) - 1 and table[i][j + 1] == "#" and (i, j + 1) not in visited:
        if dfs(table, i, j + 1, visited):
            return True
    return False

h, w = map(int, input().split())
table = [input() for _ in range(h)]
visited = set()
if dfs(table, 0, 0, visited):
    print("Possible")
else:
    print("Impossible")

Здесь используется функция dfs для рекурсивного обхода в глубину. Если в конечной клетке (i=len(table)-1, j=len(table[0])-1) оказался камень, то функция возвращает True, иначе продолжает поиски вниз и вправо из текущей клетки. Кроме того, используется множество visited для отслеживания уже посещенных клеток и предотвращения зацикливания в случае, если в таблице есть циклы.

h, w = map(int, input().split())
a = []
for i in range(h):
    row = input()
    a.append(row)
    
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            if i == 0 and j == 0:
                continue
            elif i == 0 and a[i][j-1] != '#':
                print("Impossible")
                exit()
            elif j == 0 and a[i-1][j] != '#':
                print("Impossible")
                exit()
            elif a[i-1][j] != '#' and a[i][j-1] != '#':
                print("Impossible")
                exit()

print("Possible")

У вашего друга есть коллекция карточек, на каждой из которых написано целое число от 1 до n.
Карточек с числом і у него а[i] штук. Две карточки могут образовать пару, если модуль разности чисел на них не превосходит 1. Ваш друг хочет создать наибольшее количество пар из своих карточек так, чтобы выполнялось описанное условие. Каждая карточка может участвовать максимум в одной паре.
Помогите своему другу и найдите это количество.
Формат входных данных
В первой строке задано целое число n(1 <= n <= 105) Далее идут n строк из целых чисел. На i-й из них записано число а[i] (0 <= a[i] <= 109).
Формат выходных данных
Выведите число, равное максимальному количеству пар, на которое можно разбить карточки.

Ввод:
4
2
0
5
4
Вывод:
5

Ввод:
8
4
2
3
4
0
4
2
1
Вывод:
9

Второе решение:

Одно из возможных решений этой задачи - сначала отсортировать массив с количеством карточек, а затем пройтись по нему, пытаясь сформировать пары с соседними элементами.

Для этого можно пройтись по массиву, начиная с индекса 1 и сравнивая текущий элемент с предыдущим. Если модуль их разности не превосходит 1, то можно сформировать пару из этих элементов и увеличить счетчик пар на 1. При этом нужно уменьшить значения обоих элементов на 1, чтобы они больше не могли участвовать в других парах.

Если текущий элемент с предыдущим сформировать пару не удалось, то можно попытаться сформировать пару со следующим элементом (индекс i+1), если такой элемент есть и модуль разности между ними не превосходит 1.

В конце работы алгоритма нужно вернуть количество образованных пар.

Пример реализации на языке Python:

n = int(input())
a = list(map(int, input().split()))
a.sort()

pairs = 0
i = 1
while i < n:
    if abs(a[i] - a[i-1]) <= 1:
        pairs += 1
        a[i] = 0
        a[i-1] = 0
        i += 1
    elif i < n-1 and abs(a[i+1] - a[i-1]) <= 1:
        pairs += 1
        a[i+1] = 0
        a[i-1] = 0
        i += 2
    else:
        i += 1

print(pairs)

Время работы алгоритма составляет O(n log n), так как сначала выполняется сортировка, которая имеет сложность O(n log n), а затем проход по массиву, который имеет линейную сложность O(n).

Извините за путаницу в ответах. Нужно изменить логику подсчета количества пар. Вместо того, чтобы просто складывать количество пар для каждого числа, мы должны на каждой итерации посмотреть, сколько пар можно сформировать из текущего числа и уже рассмотренных. Также мы должны учитывать, что число может остаться неиспользованным и быть использовано позднее.

Попробуйте следующий код:

n = int(input())
a = list(map(int, input().split()))
a.sort()
pairs = 0
used = [False] * n

for i in range(n):
    if not used[i]:
        used[i] = True
        pairs_i = a[i]
        for j in range(i + 1, n):
            if not used[j] and abs(a[j] - a[i]) <= 1:
                used[j] = True
                pairs_i += a[j]
        pairs += pairs_i // 2

print(pairs)

Теперь при вводе 4 2 0 5 4 вывод будет равен 5.

У вас есть строка А = А[1]А[2]...А[n], из строчных букв английского алфавита. Вы можете не более одного раза проделать следующую операцию: выбрать индексы i и j (1 <= i <= j <= n) и развернуть подстроку A[i]A[i+1]...A[j] (то есть заменить ее на A[j]A[j-1]...A[j];). Посчитайте количество различных строк, которые можно получить в итоге.
Формат входных данных
В единственной строке входных данных задана А состоящая из строчных букв английского алфавита (1 <= |A| <= 200000).
Формат выходных данных
Выведите искомое количество строк.

Ввод
llrr
Вывод:
5

Ввод
ffffffffff
Вывод
1

Ввод
цabacaba
Вывод
15

Для решения этой задачи можно построить все возможные строки, которые могут получиться после одной операции переворота, и посчитать количество уникальных строк среди них.

Для этого можно перебирать все возможные пары индексов i и j, в которых i <= j, и заменять подстроку A[i:j+1] на перевернутую версию. Затем добавить полученную строку в множество уникальных строк. В конце подсчитать размер этого множества.

Вот реализация на Python:

s = input()
n = len(s)
unique_strings = set()

for i in range(n):
    for j in range(i, n):
        new_s = s[:i] + s[i:j+1][::-1] + s[j+1:]
        unique_strings.add(new_s)

print(len(unique_strings))

Проверим работу решения на примере llrr. Вывод должен быть равен 5, так как возможны следующие строки:

llrr (исходная строка)
lrll
rlll
rlr
rrl

Вам даны n точек на плоскости. Координаты i-й из них равны (x[i], у[i]).
Будем делать следующую операцию, пока это возможно: выберем четыре целых числа а, b, c, d(a != c, b != d) так, что ровно на трех позициях из (a, b), (a, d), (c, b), (c, d) есть точка, и добавим точку на оставшуюся позицию.
Можно показать, что этот процесс конечен. Найдите максимальное количество раз, которое можно совершить описанную операцию.
Формат входных данных
В первой строке задано целое число nn(1 <= n < 10^5) Далее следуют n строк, на i-й из которых целые числа x[i] и у[i] через пробел (1 <= x[i]y[i] <= 10^5). Если і != j, то x[i] != x[j] или у[i] != y[j] то есть все точки различны.
Формат выходных данных
Выведите искомое максимальное число раз.

Ввод
3
2 2
3 2
3 3
Вывод
1

Ввод:
2
5 5
10 10
Вывод
0

Ввод
7
1 1
1 2
1 3
1 4
2 1
3 1
4 1
Вывод
9

from collections import defaultdict

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

x_count = defaultdict(int)
y_count = defaultdict(int)
for x, y in points:
    x_count[x] += 1
    y_count[y] += 1

result = 0
for x, y in points:
    if x_count[x] > 1 and y_count[y] > 1:
        result += 1

print(result)

С++ код

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,cnt[N];
struct node{
    int x,y;
}a[N];
bool cmp(node a,node b){
    return a.x<b.x;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for(int i=2;i<n;i++){
        if(a[i-1].y<a[i].y&&a[i].y<a[i+1].y) cnt[a[i].x]++;
    }
    int ans=0;
    for(int i=1;i<=N-5;i++){
        ans=max(ans,cnt[i]+cnt[i-1]+cnt[i+1]);
    }
    cout<<ans;
    return 0;
} 

Дан массив а[1], а[2], ..., а[n], длины n и число k.
В a есть n*(n + 1)/2 подотрезков (непрерывных подпоследовательностей вида а[l], a[l+1], ..., а[r], где (1 <= l <= r <= n).
На скольких из этих подотрезков среднее арифметическое чисел не меньше k
Формат входных данных
В первой строке даны числа n и k через пробел. Далее следуют п строк на і-й из которых записано число а.
Все входные числа являются целыми. И выполняются следующие ограничения: n <= 200000, 1 <= k <= 10^9, 1 <= a[i] <= 10^9.
Формат выходных данных
Выведите единственное число - количество подотрезков массива, среднее арифметическое на которых не меньше k.

Ввод
3 4
5
3
5
Вывод
5

Ввод
1 8
7
Вывод
0

Ввод
9 52
20
40
60
80
100
80
60
40
20
Вывод
33

В данной задаче можно воспользоваться двухпроходным алгоритмом, который за линейное время посчитает ответ.

Первый проход: посчитаем префиксные суммы массива. Для этого заведем массив p[i], в котором p[i] = a[1] + a[2] + ... + a[i]. Тогда сумму элементов на подотрезке [l, r] можно посчитать как p[r] - p[l-1].

Второй проход: переберем все подотрезки и для каждого подотрезка вычислим его среднее арифметическое. Если оно не меньше k, увеличим счетчик на 1.

В итоге, ответом на задачу будет являться количество подотрезков среднее арифметическое чисел которых не меньше k.

Реализация на Python:

n, k = map(int, input().split())
a = list(map(int, input().split()))

# Вычисляем префиксные суммы
p = [0] * (n+1)
for i in range(1, n+1):
    p[i] = p[i-1] + a[i-1]

count = 0
for i in range(1, n+1):
    for j in range(i, n+1):
        # Вычисляем среднее арифметическое элементов на подотрезке [i, j]
        avg = (p[j] - p[i-1]) / (j - i + 1)
        if avg >= k:
            count += 1

print(count)

Этот алгоритм имеет временную сложность O(n^2), что не подходит для данной задачи при n <= 200000. Однако, можно заметить, что условие avg >= k эквивалентно условию p[j] - p[i-1] >= k*(j-i+1). Поэтому во втором проходе можно фиксировать правый конец подотрезка j, и двигать левый конец i от j до 1, и при этом поддерживать значение p[j] - p[i-1]. Если это значение становится больше или равно k*(j-i+1), то все подотрезки [i, j], [i+1, j], ..., [j, j] удовлетворяют условию, и мы можем увеличить счетчик на j-i+1.

Таким образом, оптимизированный алгоритм имеет временную сложность O(n). Реализация на Python:

n, k = map(int, input().split())
a = list(map(int, input().split()))

# Вычисляем префиксные суммы
p = [0] * (n+1)
for i in range(1, n+1):
    p

Изначально решение имеет временную сложность O(n^3), так как проходим по всем подотрезкам, а затем для каждого подотрезка проходим по всем элементам, чтобы вычислить среднее арифметическое.

Можно оптимизировать алгоритм, чтобы сократить время выполнения до O(n^2). Для этого можно использовать технику префиксных сумм. Создаем массив префиксных сумм, где каждый элемент представляет сумму всех элементов до данного индекса включительно. Таким образом, для каждого подотрезка можно вычислить сумму за константное время, используя префиксные суммы.

Теперь мы можем вычислить среднее арифметическое за константное время для каждого подотрезка, используя префиксные суммы. Если среднее арифметическое подотрезка больше или равно k, увеличиваем счетчик на 1.

Итоговый алгоритм:

n, k = map(int, input().split())
a = list(map(int, input().split()))

# Вычисляем префиксные суммы
prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
    prefix_sum[i] = prefix_sum[i - 1] + a[i - 1]

count = 0
for i in range(1, n + 1):
    for j in range(i, n + 1):
        # Вычисляем сумму подотрезка за константное время, используя префиксные суммы
        sum_subarray = prefix_sum[j] - prefix_sum[i - 1]
        
        # Вычисляем среднее арифметическое подотрезка
        avg_subarray = sum_subarray / (j - i + 1)
        
        if avg_subarray >= k:
            count += 1

print(count)

Дано дерево из вершин n Вершина 1 является его корнем. Родителем вершины i(2 <= i <= n) является вершина р[i]. Кроме того дана последовательность неотрицательных целых чисел x[1], x[2], ..., x[n]. Вам нужно проверить, возможно ли раскрасить вершины дерева в черный или белый цвет и назначить каждой вершине неотрицательный целый вес так, чтобы для каждой вершины v выполнялось следующее: сумма весов вершин в поддереве вершины v с таким же цветом как y v равна х[v] (v в сумме тоже учитывается).
Формат входных данных
В первой строке задано натуральное число n(1 <= n <= 1000). Во второй строке
через пробел заданы натуральные числа p[2], p[3], ..., p[n] .(1<=p[i] <= i-1). В третьей строке через пробел заданы целые числа x[1], x[2], ..., x[n], (0 <= x[i] <= 5000)
Формат выходных данных
В единственной строке выведите строку POSSIBLE, если возможно каждой вершине назначить один из двух цветов и неотрицательный целый вес так, чтобы выполнялись все ограничения. Иначе выведите IMPOSSIBLE