Categories

# 10409: A mid-summer night’s dream

10409: A mid-summer night’s dream
Time Limit: 3 sec

Description
This is year 2200AD. Science has progressed a lot in two hundred years. Two hundred years is mentioned here because this problem is being sent back to 2000AD with the help of time machine. Now it is possible to establish direct connection between man and computer CPU. People can watch other people’s dream on 3D displayer (That is the monitor today) as if they were watching a movie. One problem in this century is that people have become so dependent on computers that their analytical ability is approaching zero. Computers can now read problems and solve them automatically. But they can solve only difficult problems. There are no easy problems now. Our chief scientist is in great trouble as he has forgotten the number of his combination lock. For security reasons computers today cannot solve combination lock related problems. In a mid-summer night the scientist has a dream where he sees a lot of unsigned integer numbers flying around. He records them with the help of his computer, Then he has a clue that if the numbers are (X1, X2, … , Xn) he will have to find an integer number A (This A is the combination lock code) such that
(|X1-A| + |X2-A| + … … + |Xn-A|) is minimum.

Input
Input will contain several blocks. Each block will start with a number n (0

1. #include <iostream>
2. #include <algorithm>
3. #include <vector>
4.
5. using namespace std;
6.
7. int main()
8. {
9.     while(1){
10.         int n;
11.         cin >> n;
12.         vector<int> A(n);
13.         if(cin.eof()) break;
14.         for(int i=0;i<n;i++){
15.             cin >> A[i];
16.         }
17.         int left=(n-1)/2;
18.         int right;
19.         if(n%2==0) right=left+1;
20.         else right=left;
21.         sort(A.begin(),A.end());
22.         //for(int i=0;i<n;i++)
23.             //cout << A[i];
24.         int count=0;
25.         for(int i=0;i<n;i++){
26.             if(A[i]>=A[left] >> A[i]<=A[right])
27.                 count++;
28.         }
29.         cout << A[left] << " " << count << " " << A[right]-A[left]+1 << endl;
30.     }
31.     return 0;
32. }

pls:

This site uses Akismet to reduce spam. Learn how your comment data is processed.