Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 37. (September 2008)

S. 37. A Semiconductor Manufacturing Company plans to introduce dual-core processors.

They want to apply the following well-established method: instead of classifying new processors into predetermined speed ranges, they measure for each processor the highest clock speed at which it can safely operate in the long run, and sell the processor at this speed. Since the quality of new cores varies considerably, the company sells processors with rather different clock speeds.

The new dual-core processor of this company essentially consists of two single-core processors on one chip. Although the maximal clock speeds of single-core processors differ, the pair can only be operated at the same frequency: at the minimum of two frequencies. Therefore, for economical reasons, the maximal frequencies within a pair should not differ much.

Write a program that matches the maximal number of cores such that the difference of the maximal clock speeds of the two cores within a pair is less than a certain threshold. The maximal clock speed of each processor is found in the input file (specified as the first command line argument), and the result of your program should also be written into a file (specified as the second command line argument).

The first line of the input file contains two integers separated by a space: the number of cores

(0\le N\le 10\;000\;000) and the threshold (0\leT\le1000). The each of the following N lines contains a single integer: the maximal frequency 1\le F_i \le 10\;000 of core i is in row i+1. The first line of the output file should contain the maximal number of possible pairs, P, while the following P lines should have the number of the two cores, separated by a space. The order of pairs is arbitrary, and any solutions can be listed, if there are more than one.

In the example in the table, ``Példa Bemenet'' is input, while ``Példa Kimenet'' is output.

The source code of your program (s37.pas, s37.cpp, ...) together with a short documentation (s37.txt, s37.pdf, ...) should be submitted, also containing a brief description of your solution and the name of the developer environment to use.

(10 pont)

Deadline expired on October 15, 2008.


Sorry, the solution is available only in Hungarian. Google translation


Statistics:

27 students sent a solution.
10 points:Kovács 125 András, Seregi Benjamin Martin, Várnai Péter, Wagner Zsolt.
9 points:Énekes Péter, Nagy 111 Miklós, Strenner Péter, Weisz Ágoston.
8 points:8 students.
7 points:1 student.
6 points:3 students.
5 points:1 student.
4 points:2 students.
3 points:1 student.
2 points:2 students.
1 point:1 student.

Problems in Information Technology of KöMaL, September 2008