|
|
|
|
|
|
|
| 1 Хакимов Мухаммадазиз, 27 января 2026 г. 7:42:13 |
| import sys # Увеличиваем лимит рекурсии для глубоких деревьев sys.setrecursionlimit(2000) def solve(): input_data = sys.stdin.read().split() if not input_data: return n = int(input_data[0]) p = int(input_data[1]) adj = [[] for _ in range(n + 1)] for i in range(2, len(input_data), 2): u = int(input_data[i]) v = int(input_data[i+1]) adj[u].append(v) adj[v].append(u) # dp[u][k] - мин. разрезов в поддереве u для компоненты размера k с корнем u # Инициализируем бесконечностью inf = float('inf') dp = [[inf] * (p + 1) for _ in range(n + 1)] subtree_size = [0] * (n + 1) def dfs(u, parent): dp[u][1] = len(adj[u]) # Изначально "отрезаем" всех соседей subtree_size[u] = 1 for v in adj[u]: if v == parent: continue dfs(v, u) # Временный массив для обновления текущей вершины (рюкзак)
|
|
|
| 2 Ерасыл Данияров, 07 декабря 2025 г. 13:28:24 |
| #include <iostream> using namespace std; int main() { long long n; cin >> n; long long res = n / 5; int q = n % 5; if (q == 1 || q == 3) { cout << res + 1; } else if (q == 2 && n != 7) { cout << res + 2; } else if (q == 4 && n != 4) { cout << res + 2; } else if (q == 0) { cout << res; } else { cout << -1; } return 0; }
|
|
|
| 3 Матус Даниил Дмитриевич, 03 марта 2021 г. 8:42:04 |
| O(N*P*P)
|
|
|
| 4 Матус Даниил Дмитриевич, 03 марта 2021 г. 8:41:36 |
| изи дп
|
|
|
| 5 Винк В В, 02 июля 2018 г. 21:30:07 |
В обсуждении задачи №139 "Лабиринт знаний" 3 апреля я написал тест, на который одно из моих решений выдавало неверный ответ, но было успешно принято системой. Так же я писал письма администратору, в которых объяснял в чём ошибка этого решения. До сих пор ничего не изменилось, поэтому я не знаю, есть ли в этом смысл.
Присылаете два файла - правильный ввод и правильный вывод - и с хорошей вероятностью они будут добавлены.
|
|
|
| 6 Винк В В, 29 мая 2018 г. 13:03:33 |
Сделал неполный перебор с хитрым костылём. В итоге менее 300 символов на Си++. Думаю, если добавить тестов посерьёзней, моя программа завалится.
Найдите тест, заваливающий Ваше решение, и пришлите администратору на bsn@mail.ru
|
|
|
| 7 Гайнуллин Ильдар Ленарович, 02 октября 2016 г. 20:55:01 |
| на самом деле время работы алгоритма есть N*N, если перебирать до размера поддерева
|
|
|
| 8 Бережко Герман Игоревич, 21 сентября 2012 г. 19:20:28 |
| У меня решение за N*K*K. Кто нибудь знает лучше? Но у задачи сложность переоценена, если асимптотики лучше нет. Но это вряд ли, потому что в лучших попытках меньше 0,1 секунды есть.
|
|
|
| 9 Каменко&Барышев, 09 апреля 2011 г. 1:16:08 |
| тут ДП на графах круто) решил с первого раза, для каждой вершины хранил массив наилучших вариантов, т.е a[i,j]=минимальному кол-ву ребер чтобы задействовать вершину i в построении из J городов... формула вырисовывается потом и она не очень то и сложная, удачи )
|
|
|
| 10 Фурко Роман Владимирович, 16 марта 2011 г. 19:37:31 |
Здесь что-то типа рюкзака , для каждой вершины?
|
|
|
| 11 Ivan Dvitriev Vaslylev, 13 апреля 2010 г. 18:02:06 |
| да задача хороша, не знаю даже что тут и придумать если ДП то ни как не пойму что с ней делать даже(
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
