mdinfotech.net  



  1. To earn an extra 5% AT THE END OF THE SEMESTER ONLY, complete all of the challenge exercises for your grade.
  2. Print this form, fill it out and give it to Ms. Wear BEFORE the due date.
  3. Follow instructions on individual challenge.
Write a program that given n positive integer values, k1,k2,k3,...,kn, finds the smallest number ki that is in the sequence at least as many times as any other integer in the sequence.

Input File The first line is n, the number of integers in the sequence. Subsequent n lines contain the integers in the sequence. Example:
9
2
3
4
5
3
2
3
1
2
Output File contains one integer k, that is the smallest integer in the sequence at least as many times as any other integers. Solution for above example:
2

Ms. Wear bought a rectangular piece of treed property that she wants to turn into a horse farm. Using a coordinate system where (0,0) is the bottom left corner of the property, Ms. Wear mapped the location of all the trees on the property. (She does stuff like this, don't ask why). Oddly enough, each tree was located at a location with exact integer coordinate points, AND, the trees were located so that there was never a line connecting two trees that was parallel to the x or y axes. This made her very happy, because she realized she could turn this into a programming problem for her APCS class!

Now Ms. Wear loves trees and hates to cut them down. But she loves horses more. So to build the horse farm, a number of rectangular areas need to be cut for things like the riding ring, the barn, paddocks, manure pile. You know, horse stuff. She plans to use the wood from the trees for buildings and fences. Ms. Wear does not have enough money to build the whole facility at once, so she is going to let the trees stay until she has the money to build the next thing. So once in a while, when she needs trees cut, she hires Fred, the tree cutter. She told him to cut the trees as follows:

  1. Ms. Wear will provide the minimum number of trees Fred MUST cut
  2. Fred is to cut all trees within a rectangular area, and no trees outside of it
  3. The sides of the rectangular area must be parallel to x and y axes
  4. Two diagonally opposite corners of the area must be located on trees and these trees are also cut
Since Ms. Wear loves trees, Fred is to fulfill these conditions while cutting as few trees as possible. You are to write a program that, given information on the tree locations and the minimum number t of trees to be cut, selects an area for clearing.

Input

The input file name is march.in. The first line contains one integer n which is the total number of trees on the property. The second line contains one integer t which is the minimum number of trees to cut. The next n lines are the x,y positions of the n trees. The x and y position coordinates are integers.

Output

The output file name is march.out. The file contains one line with two integers a and b separated by one space. Fred should use the tree a (with the position found on line a+2 of the input file) and tree b (with the position found on line b+2 of the input file) as the corners of the area to clear of trees. It does not matter in what order these numbers appear. There may be several methods to choose the two trees. You are to find and output one of them. For each test case, there is at least one solution.

Example input file and corresponding output file

march.inmarch.out
3
2
1 1
2 3
5 6
1 2

Preconditions

1 <= n <= 25000, 0 <= x,y <= 75000 and 1 < t <= n
and in half of the input, 1 < n < 6000

Description

It is 1805, and there are two rock crushing factories, each employing a group of workers. Crushing rock is hard work and the workers need a lot of food to be productive. For each shipment of food that arrives at the factory, the workers crush the same amount of rock. Food arrives in 3 types of shipments: meat, produce, and grains.

The workers are very health conscious and like variety of food types in their diet. They are more productive if the food supply changes a lot. Specifically, for each new shipment, the workers will consider the new shipment and the previous two shipments (or fewer if there haven't been that many) and:

  • If all shipments were the same, they will crush one unit of rock.
  • If there were 2 different types of food, they will crush two units of rock.
  • If there were 3 different types of food, they will crush three units of rock.

As factory owners, know in advance what types of food will be received and in what order. We can influence the amount of rock that is crushed by deciding which food shipment should go to which factory. A shipment cannot be divided and must be sent to either factory as a whole. The two factories do not have to necessarily receive the same number of shipments. You may choose to send all the shipments to one factory and none to the other.

The Program

Read in an input file that contains the types of food shipments in the order in which they will be sent. The program will find the largest total amount of rock that can be crushed (in both factories) by deciding which shipments should be sent to factory 1 and to factory 2.

Input File

There will be multiple test cases. Each test case is two lines. The first line contains an integer K (1 <= K <= 100 000), the number of food shipments. The second line contains a string consisting of K characters: the types of food in the order in which they are to be distributed. Each character is an upper case letter, 'M' (for meat), 'P' (for produce) or 'G' (for grains).

Output

Output a single integer to the console: the largest total amount of crushed rock that can be produced.

Sample Input

6
MGMPPG
16
MMGMGGGGMMMMMGMG

Sample Output

12
29 

Hint

In the first sample, by distributing the shipments in this order: factory 1, factory 1, factory 2, factory 2, factory 1, factory 2, the shipments will result in 1, 2, 1, 2, 3 and 3 units of crushed rock produced in that order, for a total of 12 units. There are other ways to achieve this largest amount.

Downloads this file names.txt (right click and 'Save Link/Target As...'). This is a text file with over 5000 first names. Sort the names in alphabetical order. Then work out the value for each name and multiply this value by its position in the list to obtain a name score. For example, when the list is sorted into alphabetical order, ABBIE, which is worth 1 + 2 + 2 + 9 + 5 = 19, is the 3rd name in the list. So, ABBIE would have a score of 3 × 19 = 57. What is the total of all the name scores in the file?

Description

A certain Mount Doug teacher arrives at the Royal Oak Exchange at 12:00. She hangs out there from 12:00-12:59 playing Candy Crush. The exchange is used by a number of bus routes, and Ms. Wear, oh, I mean, anonymous teacher, notes the times that each bus arrives during the hour. She has time to do this because she is stuck on level 25, has run out of lives, and thinks it is stupid that she has to wait for 24 hours to keep playing. The times when buses arrive are given.

Some interesting facts:

  • buses on the same route number arrive at regular intervals from 12:00 to 12:59 throughout the entire hour
  • times are given as integers from 0 to 59
  • each route stops at least 2 times in one hour at the Royal Oak Exchange
  • the number of bus routes going through the exchange is <= 18
  • multiple buses from different routes may arrive at the same moment
  • multiple bus routes can have the same time of first arrival and/or time interval.
  • even if two bus routes have the same starting time and interval, they are considered unique.

Find the schedule with the least number of bus routes that must stop at the exchange to satisfy the data from the input file. For each bus route, output the starting time (as an integer between, and including, 0 to 59) and the interval.

Input Data

The first line of the input file, input.txt, contains a number K (K <= 400) that indicates the number of arriving buses the teacher has seen at the exchange, followed by the arrival times in ascending order.

Output Data

Write a table, to the console, with one line for each bus route. Each line in the file gives two integers: the time of arrival for the first bus, and the interval time in minutes. The order of the bus routes does not matter. There may be several solutions, but only one is required.

Sample Input

17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

Sample Output

0 13
3 12
5 8