Драконы и лапки(олимпиадное программирование)

@Anioni13 · Регистрация: 03.11.2019

Author24 — интернет-сервис помощи студентам

D. Драконы и лапки
Ограничение времени 1 секунда
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Группа черных драконов атакует столицу гномов — огромный город-крепость Тор Хралл. Король Вульфстен, стоя на городских стенах, хотел было начать стрелять по нападающим, но тут заметил, что это необычные драконы: у них необязательно четыре лапки (крылья не считаются лапками). Известно, что в сумме у всех драконов было N лапок, при этом разность между количеством лапок у любых двух драконов более, чем 1.

Выведите все возможные варианты вида нападающих драконов (по количеству лапок).

Формат ввода
На вход подается одно целое положительное число N ≤ 100 — суммарное количество лапок у драконов.

Формат вывода
Выведите все возможные варианты вида нападающих драконов по одному в каждой строке в формате N = a1 + a2 + ... + ... ak. Выводите строки в лексикографическом порядке (так, строка 22=10+12 будет идти позже строки 22=1+21), а слагаемые в строках — в порядке неубывания.

Нужен код на С++.Помогите!!!

@_Ivana · 09.11.2019, 17:55

Не ущемляя прав гордых безлапых исключительно крылатых созданий...

C++

void f(int n, int a, std::string s) {
    if (n==0) std::cout << s << "\n";
    else for(int i=a+2; i<=n; i++) f(n-i, i, s + std::to_string(i) + (n-i ? "+" : ""));
}
 
int main() { int n; std::cin >> n; f(n, -2, std::to_string(n)+ "="); }

Код

22=0+2+4+6+10
22=0+2+4+7+9
22=0+2+4+16
22=0+2+5+15
22=0+2+6+14
22=0+2+7+13
22=0+2+8+12
22=0+2+9+11
22=0+2+20
22=0+3+5+14
22=0+3+6+13
22=0+3+7+12
22=0+3+8+11
22=0+3+19
22=0+4+6+12
22=0+4+7+11
22=0+4+8+10
22=0+4+18
22=0+5+7+10
22=0+5+17
22=0+6+16
22=0+7+15
22=0+8+14
22=0+9+13
22=0+10+12
22=0+22
22=1+3+5+13
22=1+3+6+12
22=1+3+7+11
22=1+3+8+10
22=1+3+18
22=1+4+6+11
22=1+4+7+10
22=1+4+17
22=1+5+7+9
22=1+5+16
22=1+6+15
22=1+7+14
22=1+8+13
22=1+9+12
22=1+21
22=2+4+6+10
22=2+4+7+9
22=2+4+16
22=2+5+15
22=2+6+14
22=2+7+13
22=2+8+12
22=2+9+11
22=2+20
22=3+5+14
22=3+6+13
22=3+7+12
22=3+8+11
22=3+19
22=4+6+12
22=4+7+11
22=4+8+10
22=4+18
22=5+7+10
22=5+17
22=6+16
22=7+15
22=8+14
22=9+13
22=10+12
22=22

@nalbe666 · 09.11.2019, 18:08

_Ivana, лексикографический порядок, это же типа такого:

Кликните здесь для просмотра всего текста

22=0+10+12
22=0+2+20
22=0+2+4+16
22=0+2+4+6+10
22=0+2+4+7+9
22=0+2+5+15
22=0+2+6+14
22=0+2+7+13
22=0+2+8+12
22=0+2+9+11
22=0+22
22=0+3+19
22=0+3+5+14
22=0+3+6+13
22=0+3+7+12
22=0+3+8+11
22=0+4+18
22=0+4+6+12
22=0+4+7+11
22=0+4+8+10
22=0+5+17
22=0+5+7+10
22=0+6+16
22=0+7+15
22=0+8+14
22=0+9+13
22=1+21
22=1+3+18
22=1+3+5+13
22=1+3+6+12
22=1+3+7+11
22=1+3+8+10
22=1+4+17
22=1+4+6+11
22=1+4+7+10
22=1+5+16
22=1+5+7+9
22=1+6+15
22=1+7+14
22=1+8+13
22=1+9+12
22=10+12
22=2+20
22=2+4+16
22=2+4+6+10
22=2+4+7+9
22=2+5+15
22=2+6+14
22=2+7+13
22=2+8+12
22=2+9+11
22=22
22=3+19
22=3+5+14
22=3+6+13
22=3+7+12
22=3+8+11
22=4+18
22=4+6+12
22=4+7+11
22=4+8+10
22=5+17
22=5+7+10
22=6+16
22=7+15
22=8+14
22=9+13

@_Ivana · 09.11.2019, 23:01

nalbe666, ммм, да, вы правы. Тогда очевидно вместо цаута складывать результаты в мутабельный глобальный вектор строк, потом вызвать на нем библиотечный сорт (на крайняк, если дефолтный не умеет в строки, то накостылить свой почаровый компаратор) и вывести его содержимое.

@Anioni13 4 / 5 / 0 Регистрация: 03.11.2019 Сообщений: 16
		1
	Драконы и лапки(олимпиадное программирование) 09.11.2019, 10:49. Показов 3099. Ответов 3 Метки нет (Все метки) D. Драконы и лапки Ограничение времени 1 секунда Ограничение памяти 256Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt Группа черных драконов атакует столицу гномов — огромный город-крепость Тор Хралл. Король Вульфстен, стоя на городских стенах, хотел было начать стрелять по нападающим, но тут заметил, что это необычные драконы: у них необязательно четыре лапки (крылья не считаются лапками). Известно, что в сумме у всех драконов было N лапок, при этом разность между количеством лапок у любых двух драконов более, чем 1. Выведите все возможные варианты вида нападающих драконов (по количеству лапок). Формат ввода На вход подается одно целое положительное число N ≤ 100 — суммарное количество лапок у драконов. Формат вывода Выведите все возможные варианты вида нападающих драконов по одному в каждой строке в формате N = a1 + a2 + ... + ... ak. Выводите строки в лексикографическом порядке (так, строка 22=10+12 будет идти позже строки 22=1+21), а слагаемые в строках — в порядке неубывания. Нужен код на С++.Помогите!!! 0

@nalbe666 863 / 513 / 215 Регистрация: 19.01.2019 Сообщений: 1,216
	09.11.2019, 18:08	3
	_Ivana, лексикографический порядок, это же типа такого: Кликните здесь для просмотра всего текста 22=0+10+12 22=0+2+20 22=0+2+4+16 22=0+2+4+6+10 22=0+2+4+7+9 22=0+2+5+15 22=0+2+6+14 22=0+2+7+13 22=0+2+8+12 22=0+2+9+11 22=0+22 22=0+3+19 22=0+3+5+14 22=0+3+6+13 22=0+3+7+12 22=0+3+8+11 22=0+4+18 22=0+4+6+12 22=0+4+7+11 22=0+4+8+10 22=0+5+17 22=0+5+7+10 22=0+6+16 22=0+7+15 22=0+8+14 22=0+9+13 22=1+21 22=1+3+18 22=1+3+5+13 22=1+3+6+12 22=1+3+7+11 22=1+3+8+10 22=1+4+17 22=1+4+6+11 22=1+4+7+10 22=1+5+16 22=1+5+7+9 22=1+6+15 22=1+7+14 22=1+8+13 22=1+9+12 22=10+12 22=2+20 22=2+4+16 22=2+4+6+10 22=2+4+7+9 22=2+5+15 22=2+6+14 22=2+7+13 22=2+8+12 22=2+9+11 22=22 22=3+19 22=3+5+14 22=3+6+13 22=3+7+12 22=3+8+11 22=4+18 22=4+6+12 22=4+7+11 22=4+8+10 22=5+17 22=5+7+10 22=6+16 22=7+15 22=8+14 22=9+13 2

@_Ivana 4820 / 2286 / 287 Регистрация: 01.03.2013 Сообщений: 5,970 Записей в блоге: 29
	09.11.2019, 23:01	4
	nalbe666, ммм, да, вы правы. Тогда очевидно вместо цаута складывать результаты в мутабельный глобальный вектор строк, потом вызвать на нем библиотечный сорт (на крайняк, если дефолтный не умеет в строки, то накостылить свой почаровый компаратор) и вывести его содержимое. 2

Драконы и лапки(олимпиадное программирование)

Решение