Bru and the Orange Split
Time limit0.1sMemory limit1024 MB
Given counts X of ascending pairs and Y of descending pairs, the task is to build the shortest sequence of values from 1 to 10^9 that has exactly those counts.
- Level
Medium7 of 10
- Topics
- Combinatorics, Greedy, Implementation
- Solved
- No attempts yet
Problem
Bru has a warehouse with oranges of each taste from to . Bru wants to share the oranges with friends.
Bru will invite a total of friends. The value of is not yet fixed. The friends stand in a line and each takes one orange from Bru. Bru wants to give out the oranges so that the following conditions hold.
Let the friends be numbered , , , in the order they arrive. Let be the taste of the orange given to friend . Then,
- The number of pairs with and is .
- The number of pairs with and is .
If several ways satisfy these conditions, Bru wants to save oranges and picks the way with the smallest . Write a program that invites friends and gives out oranges so that Bru's conditions are met.
Input
The first line contains two integers and , separated by a space.
Output
The first line prints the number of friends .
The second line prints the tastes of the oranges given to the friends, separated by spaces.
If several ways are possible, print a way with the smallest . If there are still several such ways, print any of them.
It is guaranteed that a valid way with always exists.
Constraints
- Each element of is an integer from to .