Time limit

Dee5 (167)
Lately I wanted some help about this vending machine code though I decided to make some changes to it.
The code does the following
First input is how many customers need to be served
Then second input arethe customers money and number of water bottles they wants.
The vending machine takes in only 50,100,200 coins
At first the machine has zero money and enough bottles to sell.
The program should then decide if the change is less than the money inside the vending machine and there is actual coins to give as change
If yes then it prints yes
If no then prints no

My code passed all the test cases in my assignment but the time limit is not met.
I was asking if someone can make it run faster.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
 #include<iostream>
using namespace std;

int main()
{
  int no_students;
  cin >> no_students;
  int count1=0;
  int count2=0;
  int count3=0;
  int count4=0;
  int count50 = 0;
  int count100 = 0;
  int count200 = 0;
   int studentmoney, no_bottles, Change;
  for (int i = 0; i < no_students; i++) {
   
    cin >> studentmoney >> no_bottles;

  if (studentmoney == 50) {
      count50++;
    }
    if (studentmoney == 100) {
      count100++;
    }
    if (studentmoney == 200) {
      count200++;
    }
   
    if (no_bottles == 1){
       count1++;
    }
    if (no_bottles == 2){
       count2++;
    }
    if (no_bottles == 3){
       count3++;
    }
    if (no_bottles == 4){
       count4++;
    }
}

    int totalbottles = (count1 *1)+(count2*2)+(count3*3)+(count4*4);
    int totalCoins = (count50 * 50) + (count100 * 100) + (count200 * 200);
    Change =totalCoins -(totalbottles* 50);
    cout<<"Change"<<Change;
    cout<<"\n";
    int  machinemoney= totalCoins - Change;
    cout<<"Machinemoney:"<<machinemoney;
    cout<<"\n";
    int count50Change=0;
    int count100Change=0;
    int count200Change=0;
    
          while (Change > 0){
      if (Change >= 50 && count50 > 0) {
        Change -= 50;
        count50Change++;
      }
      else if (Change >= 100 && count100 > 0 ) {
        Change -= 100;
        count100Change++;
      }
      else if (Change >= 200 && count200) {
        Change -= 200;
        count200Change++;
      }
    } 
          while (Change <0){
      if (Change >= 200 && count200 > 0) {
        Change -= 200;
        count200++;
      }
      else if (Change >= 100 && count100 > 0 ) {
        Change -= 100;
        count100++;
      }
      else if (Change >= 50 && count50) {
        Change -= 50;
        count50++;
      }
    }               
    
     int count50machine=(count50-count50Change);
     int count100machine=(count100-count100Change);
     int count200machine=(count200-count200Change);
        
     cout<<"50in machine:"<<count50machine;
     cout<<"\n";
     
            
     cout<<"100in machine:"<<count100machine;
     cout<<"\n";
        
            
     cout<<"200in machine:"<<count200machine;
     cout<<"\n";
        
     cout<<"50in change"<<count50Change;
     cout<<"\n";
              
     cout<<"100in change"<<count100Change;
     cout<<"\n";
              
     cout<<"200in change"<<count200Change;
     cout<<"\n";
        
        
        
        
     if (count50machine<count50Change && count100machine!=count200machine){
       cout <<"NO";
     }else{
       cout<<"YES";
     }
    return 0;
  }
Dee5 (167)
I didnt find the right algorithm so I just cooked up the algorithm for only the test cases which I was given
I know that is so stupid of me but I had to do that because of time.

jonnin (11495)
heh, many a demo has been hacked out in a hurry using hard coded known to work values or the user types in known to work values when showing it off. Time happens.

the first thing I ask of a student who has a time limit issue is whether they compiled the code in release mode. Debug mode can run more than twice as slow, though the actual amount depends on many things.

its clearly too late now but you can kill off a lot of logic with a skip test. If you have a certain amount of coins on hand already, you can always make change, and the answer is known to be yes. You only need to be concerned about making change when you are below that magic amount (I did not try to figure out this number, but if you care to revisit the problem, you can). You should be skipping the logic most of the time, if the input data is somewhat realistic: everyone is going to buy something, and the act of buying should pump up your available money, so after just a few sales you should begin to have the funds on hand for change no matter what they do, most of the time. Does that make sense?
Last edited on
Dee5 (167)
Sorry i think I didn't understand
And about my code how should I make it run faster maybe under one second
mbozzi (3944)
Dee5 (167)
Please read above when I said i made some changes to it
dhayden (5799)
Look at the loop from lines 70-83. If Change < 0 then the look subtracts something from change, ensuring that Change will still be less than zero. The loop will continue until you underflow Change and it becomes positive again.
Topic archived. No new replies allowed.