Capitals and cities
Practice
2.9 (82 votes)
Basic programming
Basics of implementation
Easy
Implementation
Sorting
Problem
92% Success 23525 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Suppose we have $$n$$ cities with integer coordinate on a line. First, we have to select a city to be the capital. Then in each operation, we have to choose a non-capital city and change it's coordinate by $$1$$ ($$-1$$ or $$+1$$). We have to pick the capital and do the operations exactly $$k$$ time so that the sum of distances from cities to the capital is minimized. Print the index of the selected capital and the desired sum after exactly $$k$$ operations. If there are multiple such choices, output the smallest index of an optimal capital. 

You are required to print the index of the selected capital and required sum after \(k\) operations. If there are multiple such choices, print the smallest index of an optimal capital.

Input format

  • First line: Two integers \(n\) and \(k\) \(1 \le n \le 300\ 000\)
  • Second line: \(n\) integers where the \(i^{th}\) integer that contains the coordinate of the \(i^{th}\) city

Output format

Print two integers that represent the index of the capital and the minimized required sum respectively.

Constraints

\(1 \le n \le 300\ 000\)

\(0 \le k, A_i \le 10^9\)

Sample input #2

5 47019
19912129 5 7138912 913 200134

Sample output #2

5 27003104

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
13 votes
Tags:
Basic ProgrammingAlgorithmsGreedy algorithm
Points:30
39 votes
Tags:
Basic ProgrammingBit ManipulationImplementationString Manipulation
Points:30
19 votes
Tags:
Basic ProgrammingBasics of ImplementationImplementation