Heuristic methods


Plus
Pin


Problem description Progress
ID 38351. Gather the numbers
Темы: Heuristic methods   

Vasya had a set of cubes at his disposal. Vasya decided to write a number on each side of each cube and then use the cubes to add numbers from them. Vasya wants to write numbers in such a way that he can add any number from 1 to some number K. Calculate the maximum K, up to which Vasya will be able to lay out all the numbers, if Vasya has N cubes at his disposal. Note that if the number 6 is written on some face of a die, then the same face can also be used as the number 9 by simply flipping the corresponding die.

When laying out the number, Vasya is not obliged to use all the cubes. Leading zeros are not needed in numbers.

Let's look at some examples.

Let N=1. Then, by writing numbers from 1 to 6 on the faces of the cube, Vasya will be able to lay out numbers from 1 to 6. Thus, K=6.

Let N=2. Then, by writing the numbers from 1 to 6 on the faces of one cube, and the numbers 0, 1, 2, 3, 7, 8 on the faces of another, Vasya will be able to lay out any number from 1 to 43.

Input
The input file contains one number N (1≤N≤1000000).

Imprint
In the output file, output the maximum value of K such that, having N cubes, Vasya can write numbers on their faces in such a way that it would be possible to lay out any number from 1 to K.

Examples
# Input Output
1 1 6
2 2 43

ID 38920. elves and deer
Темы: Heuristic methods    Binary search by answer    Quick sort    Greedy Algorithm   

The New Year is coming soon and Santa Claus has already started preparing his magical reindeer team, on which he delivers gifts to children. It is known that the team is driven by several magical deer, each of which is ridden by two elves.

But the magical deer – obstinate animals, so not any two elves can ride any deer. Namely, each deer is characterized by some obstinacy ai, and each elf – temperament bi. Two elves j and k can ride the i-th reindeer if and only if either bj < ai < bk or bk < ai < bj.

To make his appearance as spectacular as possible, Santa Claus wants his team to have as many reindeer as possible. About every deer Santa knows his obstinacy, and about every elf – his temperament.

Help Santa figure out the maximum number of reindeer he can include in his team, which reindeer he should choose, and which elves should ride them.

Input
The first line contains two integers m and n – the number of deer and elves, respectively ( 1 ≤ m, n ≤ 100,000).

The second line contains m integers ai – deer obstinacy ( 0 ≤ ai ≤ 109). The third line contains n integers bi – elves temperament ( 0 ≤ bi ≤ 109).

Imprint
In the first line  print a single number k – the maximum number of reindeer that Santa Claus can include in his team. In the next k lines print three integers each: di, ei, 1, ei, 2 – for each reindeer in the team print its number and the numbers of the elves that will ride it. If there are several solutions, print any one.

Both elves and deer are numbered, starting from one, in the order in which they are given in the input.

Examples
# Input Output
1 4 6
2 3 4 5
1 3 2 2 5 2 		2
1 1 2
3 4 5