Draw Fixing

[obinaysamanoden]

Draw Fixing
Siruseri happens to have some of the best chess player in Indian and one of the most important events in the Siruseri sports calendar is the Annual Chees Challenge where teams from Siruseri and Navalur compete. The event is held alternately at Siruseri and Navalur. This year the tournament is to be held at Siruseri. Since starting a war or accusing Navalur of possessing a weapon of mass destruction is beyond his scope (and he also has a few more brain cells than the average leader of the free world) he decided to do something clever. Draw Fixing!!
To understand what he intended to do, we need to know how the Chees Challenge match is organized. Both Siruseri and Navalur are required to send N players. Every player from both teams participates in exactly one game (and so exactly N games are played). The host is expected to draw lots to determine who plays who. Our secretary plans to fix this draw so that the pairing are exactly as he wants them to be. Each chees player has an ELO rating indicating how good he is. The higher the rating the better the player. The secretary knows the rating of each of the player in the Siruseri and Navalur team and he would like to pair theme up so that the number of pair in which the Siruseri player and Navalur has a higher ELO rating is maximized.For example, supposed that N is 4 and the rating of the player are as below.

Siruseri Team   ELO Rating  Navalur Team    ELO Rating

Player 1 8173 Player 1 2450
Player 2 2134 Player 2 1860
Player 3 1900 Player 3 1700
Player 4 1600 Player 4 2120
Then the secretary can arrange for Siruseri to have higher rating in 3 out of 4 games. He can do this, for example, by pairing them as (1,2), (2,4), (3,3) and (4,1), where (i,j) means Player i from Siruseri plays Player j from Navalur. This is the best he can do as no player from Siruseri can beat Player 1 from Navalur.Your task is help the secretary to find a pairing that maximizes the number of pairs with higher rating for Siruseri.
Input format
The first line of the input contains a single integer N, denoting the number of player in each team. The next N lines (Lines 2 through N+1) list the ratings of the N players in the Siruseri team and the N following lines (Lines+2 through 2N+1) denote the rating of the players in the Navalur team.
Output format
The first line of the output is an integer N (0 ≤ N ≤N) representing the number of pairs where the Siruseri player has a higher rating in the optimal pairing. This should be followed by N lines, each containing a pair indicating the player chosen from the Siruseri team to play against from the player from Navalur.
Examples:
We illustrate the input and output format using the example above.

Sample input

4

1873
2134
1900
1600

2450
1860
1700
2120
Sample output
3

1 vs. 2
2 vs. 4
3 vs. 3 and
4 vs. 1

[obinaysamanoden]

i have a home work. anybody who can help me.

Railway Catering Contracts
The government of Siruseri has just commissioned one of the longest and most modern railway routes in the world. This rout runs the entire length of Siruseri and passes through many of the big cities and a large number of small towns and villages in Siruseri.
The railway station along this rout have all been constructed keeping in mind the comfort of the travelers. Every station has big parking lots, comfortable waiting rooms and plenty of space for eateries. The railway authorities would like to contract out the catering services of this eateries. Unfortunately catering contractor are not philanthropist and would like to maximize their profits. The Siruseri Economic Survey has done a through feasibility study of the different station and documented the expected profit (of lose) for the eateries in all the railway station on this rout. Every contractor would like to run the catering service only the profitable stations and stay away from the lose making ones. On the other hand the authorities would like to ensure that every station was catered to. Toward this end, authorities offered to contract out station in groups. They would fix a minimum size Kand a contractor was only allowed to bid for any contiguous sequence of K or more stations.
For example suppose there are 8 stations along the line and their profitability is as follows:

    Station         1     2    3     4    5    6    7    8


Expected Profits    -20 90 -30 -20 80 -70 -60 125

If Kwas fixedto be 3, a contractor pick station 3, 4, 5, and 6. This would give him a total profit of -40 (i.e. a loss of 40). He could pick 3, 4 and 5, he would make a profit of 120. You can check that this is the best possible choice when K=3.
If K=1, then the best choice would be to bid for just station 8 and make a profit of 125.
You have been hired by a contractor.Your task is to help him identify the segment of stations to bid for so at to maximize his expected profit.
Input format
The first line of the input contains two integer N and K, where N is in the number of station and K is the minimum number of contiguous stations that must form part of the bid. The next N+1 lines (lines 2, …, N+1) describe the profitability of the N stations. Line i+1 contains a single integer denoting the expected profit at station i.
Output format
A single integer P, indicating the maximum possible profit and the contiguous sequence involved.
Example:
Here are the input and output corresponding to the example discussed above.

Sample input1           

8 3

-20
90
-30
-20
80
-70
-60

125 

Sample output1
120 max profit

Station:
2 3 4 5
Contiguous sequence:

`90 -30 -20 80  8 1`

Sample input2
-20
90
-30
-20
80
-70
-60

125 

Sample output2
125 max profit

Station:
8
Contiguous sequence:
125