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

 

Problem I. 100. (March 2005)

I. 100. We are given a square lattice of size mxn (with positive integers m and n). Unit square based columns are put onto each square. The front and side views of this bar chart-like solid are represented by the vectors u=(u1, u2, ..., um) and v=(v1, v2, ..., vn), where the numbers ui and vj are the heights of the rectangles being shadows of the columns.

Prepare a sheet into which coordinates of vectors u and v can be entered, then it computes the matrix describing heights of the columns of the (or, a possible) solid of maximal volume. Your program should recognize with writing ``Error!'' (see the diagram,), if no such solid exists.

      v1 v2 v3 v4 v5 ... ... ... vn        
  Error!     *   *       
              
u1              
u2 *             
...             
um              

Notice that this is a converse of problem I. 98., where a matrix describing the heights of the individual columns was given and we had to display the front and side views of the solid. Now we have to reconstruct the solid of maximal volume from the front and side views.

A text file (i100.txt) is to be submitted containing the precise description of the applied algorithm, further, the detailed justification of the fact that your algorithm gives the correct answer in all cases (that is, whether or not the solid exists, and, if it does, the algorithm produces the one with the required property. Finally, the sheet itself (i100.xls, ...) is also to be submitted.

(15 pont)

Deadline expired on 15 April 2005.


Statistics:

8 students sent a solution.
15 points:Kisfaludi-Bak Sándor, Stippinger Marcell, Ureczky Bálint.
14 points:Acsai Péter, Vincze János.
13 points:1 student.
7 points:1 student.
6 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