C++ Competition!

[mossad]

Hello,

I am not quite beginner. I program in C++ for long time and you could say I am good at it. I have school competition in few days and I don't know how should I practice those assignments.
Tasks are based on mathematical algorithms and I simply don't know how to start solving it and how to develop fast algorithm with minimum memory used.

Here is one example of competition task:

You work for company which produces gigantic monitors consisting of many smaller computer monitors. Your customers demand monitors with specified height and width (in milimeters). Your task is to design gigantic monitor with specified (or bigger) dimensions, for minimal price!. Gigantic monitor is built with many small monitors of same type. Total dimension and price of gigantic monitor is simply sum of dimensions and prices of smaller monitors (arranged in net). Smaller monitor types have their dimensions and price already defined within a program (user enters that). Small monitors can be arranged vertically or horizontally. Small monitors which make gigantic one all have to be the same type and they are either all placed vertical or horizontal. It is assumed that you have infinitely many monitors of each type at your disposal.

Now, how should I even approach to this type of tasks. I am confuesed and don't want to get embarrassed and score 0(zero) points! :(

[vlad from moscow]

You should find the minimum of price * number_of_monitors

[mossad]

Yes I am completely aware of what I am supposed to find and calculate. I understand it and have picture in my head. But I just don't get it how am I supposed to find effective algorithm. How to start, how to approach etc.

[Lowest0ne]

The simplest algorithm would be to just place them all the same way all the time. From there you can make a totally working program. After that make your algorithm better. I would imagine that in most cases the small screen's longer side should be oriented to the large screen's longer side. Probably do some ratio between the lengths of the small screen vs lengths of large screen to find the best fit. There might be times when you can make something slightly smaller than the large screen and then change the orientation of the small screens to finish it off.

[mossad]

This is what I have so far.
...and please don't mind system pause call, I'm just using it for testing.

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    
    /* DATA */
    int w,h,n,min=1000000,price;
    cout<<"Gigantic monitor width: "; cin>>w;
    cout<<"Gigantic monitor height: "; cin>>h;
    cout<<"Small monitor types: "; cin>>n;
    int small_w[n],small_h[n],small_price[n];
    for(int i=0;i<n;i++){
            cout<<"Small monitor type["<<i+1<<"] width: "; cin>>small_w[i];
            cout<<"Small monitor type["<<i+1<<"] height: "; cin>>small_h[i];
            cout<<"Small monitor type["<<i+1<<"] price: "; cin>>small_price[i];}
    /* DATA */
    
    /* ALGORITHM */
    for(int i=0;i<n;i++){
            price=ceil(w/small_w[i])*ceil(h/small_h[i])*small_price[i];
            if(price<min) min=price;
            price=ceil(w/small_h[i])*ceil(h/small_w[i])*small_price[i];
            if(price<min) min=price;}
    /* ALGORITHM */
    
    cout<<"Minimal price: "<<min<<endl;
    system("PAUSE");
    return 0;
}

[Lowest0ne]

Oh, you can only use one small type and can't change it's orientation during the program?

There is a lot to be said about this. I don't think it will even compile because of line 12. If I were judging this, the first thing I would do is type in a letter instead of a number in those cin calls.

What do you know about classes and static variables?

[qPCR4vir]

Hallo.
fast perfect..
you need only two more variable in the algorthm part: one int for the numer of the small monitor with correspond to the min price and one char with 'h' or 'v' for the configuration (both updated wenn update min) and then report all then together at end.. your antwort ist the design not the price..

[mossad]

@LowestOne: Yes you can only use 1 monitor type and all with same orientation while making a big one. I don't really understand what's wrong with line 12 because it compiles normally and works. The programs on competition won't be judged the way you think (i.e. trying to exploit program by entering character instead of numbere). Data will be entered in specified format. Time and memory usage are the key factors being judged. Now, can we get back to my algorithm. Is it ok? Is there any faster way? I think my solution is not that elegant, I mean it is pure brute forcing...

[qPCR4vir]

Oh... a competition on "fast" and "memory usage" and not on gut C++ style?
Ok, tray this: only one cycle in /*DATA*/ (a do-while, with a 0 value to terminate), without any array, calculating the min “on-the-fly” and eliminating the entery /* ALGORITHM */ block.
(I don't understand how your line 12 compiles; normally you need a const to define arrays size. With what compiler do you compile? But it is here easy replaced with a “new”. Anyway... you don’t need any array)
Having some function with relate the geometry of the small monitor with the price could led to more sophisticate and faster algorithm (I don’t see how in this simple case)… but you don’t have it. pure brute forcing...