Karinago

17.05.2023 15:36

Информатика

Есть ответ 👍

9. деревья имя входного файла: input.txt имя выходного файла: output.txt ограничение по времени: 1 секунда ограничение по памяти: 256 мегабайт программист вася продолжает изучать теорию графов. он прочитал главу про деревья и уже несколько дней ломает голову над следующей : необходимо построить корневое дерево с n вершинами, каждая из которых, кроме листьев, имеет k детей. причем ответ нужно записать в виде списка рёбер, а среди всех возможных вариантов ответа надо найти лексикографически минимальный. список рёбер графа записывается в строку следующим образом. каждое ребро графа описывается парой целых чисел — номерами вершин, которые это ребро соединяет. эти два числа должны быть записаны без ведущих нулей, и между ними должен стоять ровно один символ пробела. строка состоит из описаний всех n −1 рёбер графа, записанных подряд и отделённыхдруготдругаоднимпробелом.предполагается,чтовсевершиныпронумерованы числами от 1 до n, причём корень имеет номер 1. васе нужно найти лексикографически минимальную строку, которую можно получить таким образом по корневому дереву требуемого вида. при лексикографическом сравнении следует считать, что пробел как символ меньше всех цифр. например, пусть требуется построить дерево из 5 вершин, все нелистовые вершины которого должны иметь по 2 ребёнка. под заданное требование подходит дерево с рёбрами (12). список его рёбер можно записать в виде строки разными способами: ∙ 4␣2␣4␣3␣1␣4␣1␣5 ∙ 2␣4␣3␣4␣1␣4␣1␣5 ∙ 1␣4␣1␣5␣2␣4␣3␣4 здесь каждый следующий вариант записи лексикографически меньше предыдущего, но ни один не является оптимальным. при таких значениях n и k лексикографически минимальную строку 1␣2␣1␣3␣2␣4␣2␣5 даёт другое дерево. васе решить перед контрольной работой по теории графов. формат входных данных в первой строке входного файла записано два целых числа n и k, где n — количество вершин в искомом дереве, k — количество детей у нелистовых вершин (2 6 n 6 105, 1 6 k 6 105). формат выходных данных если дерева с заданными параметрами не существует, то выведите слово no в единственную строку выходного файла. иначе в первую строку выходного файла нужно вывести слово yes, а во вторую — искомую лексикографически минимальную строку. примеры
input.txt output.txt 5 2
yes 1 2 1 3 2 4 2 5 ;
4 10
no