KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem S. 46. (September 2009)

S. 46. Unlike most belief systems, Flagland's mythology is deeply interlaced with elements of natural sciences. They think for example that it brings misfortune if the main sail of a ship is not square-shaped, or its side length (in meters) is not a power of 2. According to this, only square-shaped sailcloths with side length of a power of 2 are sold in local harbors, and tailors only join up 4 sailcloths of the same size to produce a twice as big sail.

Create your program to calculate the minimal price of a sailcloth of required size, if prices of various available sailcloths are known.

The first line of the standard input contains three integers (separated by a space): the number of available sailcloths 1\le N\le
1\;000\;000 on the market, the side length 1\leA=2a\le2048 of the required sailcloth, and the sewing cost 0\leV\le1000 in (linear) meters. Then each of the following N lines contains two integers: the side lengths 1\leBi=2bi\leA of available sailcloths and their prices 1\le C_i \le 1\;000\;000\;000. Lines of the input are ordered monotonically first according to side lengths, then to prices.

The only line of the standard output should contain a single integer: the minimal price to make the required sailcloth. (This price consists of the cost of materials and possible sewing.) You can assume that a solution always exists.

In the figure, ``Bemenet'' is input, ``Kimenet'' is output, ``Optimális megoldás'' is the optimal solution, while ``szaggatott vonal jelöli a varrásokat'' is ``seams are denoted by dashed lines''.

The source code and project files of your solution (without the .exe file or any other auxiliary files generated by the compiler) together with a short documentation describing your solution should be submitted in a compressed folder (s46.zip).

Sample test cases: s46teszt.zip. Your solution has to give (a not neccessarily correct) answer to 5 out of 10 inputs in order to be judged.

(10 pont)

Deadline expired on 12 October 2009.


Statistics:

27 students sent a solution.
10 points:Berecz Dénes, Éles András, Mokcsay 026 Ádám, Várnai Péter.
9 points:Adrián Patrik, Bodosi Eszter, Fejér 267 László, Kovács 125 András, Nagy 111 Miklós, Nagy Róbert.
8 points:8 students.
7 points:4 students.
6 points:2 students.
5 points:1 student.
4 points:1 student.
3 points:1 student.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley