AIOC Banner

Problem: Lollipops, Sweets and Chocolates II

Want to try solving this problem? You can submit your code online if you log in or register.


Lollipops, Sweets and Chocolates II

Input File: lscin.txt
Output File: lscout.txt
Time Limit: 1 second
Memory Limit: 1 GB

The grand opening of Lollipops, Sweets and Chocolates (LSC) was a great success! Since then a total of N LSC stores have opened along Australian Ice-cream and Oreo Crescent (AIOC), the most candilicious street in Sydney.

The street is divided into L blocks, spaced 1 metre apart. The blocks are labelled with numbers from 1 to L along the street, so that the distance between any two blocks a and b is |a - b| metres.

Each of the N stores occupies a different block. There are also M houses along the street, each occupying a different block. However, houses and stores may occupy the same block!

To keep the little boys and girls of Sydney excited about the stores, LSC has been distributing personalised pamphlets to the houses on the street. There is one pamphlet for each house. The ith pamphlet contains a message of the form:

There are si stores within walking distance of your house!

Wondering how far you have to walk to get your hands on another mouthwatering chlorosulfonic acid sorbet, you decide to investigate how far ‘walking distance’ could be. Walking distance means a distance of at most R metres, and you would like to determine a possible value for R. You know that the street is very long, so R cannot be greater than L.

You have collected all M pamphlets, but in your haste you have forgotten which house each pamphlet came from! Given all the numbers on the pamphlets, your task is to determine a possible value of R. LSC is notorious for distributing inaccurate pamphlets, so it is also possible that no such value of R exists.

Input

Output

Your program must output a single integer (whole number): a possible value of R, or −1 if no such value exists. If there are multiple possible answers, output any one of them. Note that the value of R must not be greater than L.

Sample Input 1

4 5 15
1 5 8 9
3 6 8 10 14
0 2 2 3 3

Sample Output 1

3

Sample Input 2

3 2 6
1 3 5
2 6
1 3

Sample Output 2

-1

Sample Input 3

4 3 14
1 6 10 14
3 9 13
1 1 1

Sample Output 3

2

Explanation

In the first sample input, it is possible that the pamphlets came from the houses in this order:

If R = 3, then:

Note that 4 would also have been a correct output to this sample case.

In the second sample input, no matter which house each pamphlet came from, it is impossible to find a value of R that makes them correct.

In the third sample input, each house is within walking distance of exactly one store. The only value of R that satisfies this is 2.

Subtasks & Constraints

For all cases:

Furthermore:

 


Privacy statement
© Australian Mathematics Trust 2001-2021

Contact: training@orac.amt.edu.au
Page generated: 21 October 2021,  6:42pm AEDT