All submissions for this problem are available.
There are n users in a city using mobile phone services of Airtel. Each user needs to physically
visit a store to recharge mobile accounts. Currently, there are m recharge stores in the city
already deployed by Airtel franchisees.
A new franchisee of Airtel wants to enter the city market with new attractive schemes and to this
effect, does a survey of the user physical locations and their store visit preferences. It is always
the case that the user visits his nearest (assumed to be unique for each user) recharge store for
availing recharge options. The new franchisee wishes to take a decision regarding a convenient
location in the city to setup the store. For simplicity, assume that all the user points and the franchisees are placed on an 1-dimensional line.
The objective of this problem is to find the maximum number of users that the new franchisee
can guarantee will always migrate to his new store discarding their existing store preferences,
provided it is setup at a convenient location. An existing user may migrate to the new store in
case it is nearer to him than the one he uses for recharging presently.
The first line specifies the number of test cases.
For each test case, the first line of input specifies the number of users, n (numbered from 0 to n-
The next n lines specify the co-ordinates of the users in the following format:
xi for user pi, on the ith line. (as it is 1-dimensional, so xi only denotes a point on a straight line).
The next line of input specifies the number of franchisees, m (numbered from 0 to m-1).
The next m lines specify the co-ordinates of the franchisees in the following format:
xi for store qi, on the ith line.
The maximum number of users that the new franchisee can guarantee will always
migrate to his new store
Input: 1 // we have only 1 test-case 2 // number of points 2 4 3 1 3 5 Output: 1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.