Ruler
Есенен Турнир по Информатика, 2018
Time Limit: 1s, Memory Limit: 64MiB
Ели има много странна линийка. Линийката има дължина точно L сантиметра, като има деления в някои (но не задължително всички) от позициите, намиращи се на целочислено разстояние от началото. Считаме, че линийката има деления в началото (0) и края си (L). Интересното при линийката на момичето е, че всички разстояния между произволни две (не задължително съседни) деления са различни! По-формално, ако линийката има деления в позиции 0 = A1 < A2 < … < AN = L, то (за 1 ≤ i, j, k, p ≤ N и i < j) Aj - Ai = Ak - Ap тогава и само тогава, когато j = k и i = p.

Сега Ели иска да си направи такава линийка с N деления, като цели тя да е възможно най-къса. Помогнете ѝ, като определите къде трябва да бъдат деленията.
Вход
На единствен ред на стандартния вход ще бъде зададено едно цяло число N – броя деления (включително началото и края), които трябва да има линийката.
Изход
На единствен ред на стандартния изход изведете N цели неотрицателни числа, подредени в нарастващ ред – позициите на деленията в намерената от вас линийка. Първата позиция задължително трябва да е 0, а последната – L, където L е минималната дължина на линийка с N деления. Ако съществува повече от едно решение, изведете което и да е от тях.
Ограничения
  • 5 ≤ N ≤ 14
Примерен Вход Примерен Изход
5 0 2 7 8 11
8 0 1 4 9 15 22 32 34
Минималната дължина на линийка от този вид с 5 деления е 11. При дадения избор на деления, всички разстояния между две от тях са: {2, 7, 8, 11, 5, 6, 9, 1, 4, 3}. Друг възможен изход за N = 5 би бил {0, 1, 4, 9, 11}.
Мрън!