MONTRANS - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

You just simply need to perform this procedure no more than 10000 times and at each step update the maximal profit and optimal number of times to get it if needed. Also note that after 10000 times we definitely obtain some amount of money that we had before and hence after that we can’t obtain better profit than earlier so it follows that for any input data the answer is not greater than 10000. The last sentence of the output specification was added just to make the problem trivial. In fact the maximal answer is less than 200.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like
2

Please tell us how to arrive at the 10,000 limit?

1 Like
3

Also note that after 10000 times we definitely obtain some amount of money that we had before …
what does it means and how is it proved?

4

why is the maximal answer is less than 200???

5

This code doesnt seem to work , please check

#include
#include<stdio.h>
using namespace std;
int main()
{
int t,a,b,c;
cin>>t;
int i,n,k,temp;
float max;

 for(i=0;i<t;i++)
  {
      cin>>a>>b>>c;
     k=0;
      max=a+b*1.0/100;
      n=0;
      while((a+b*1.0/100) >= c*1.0/100 && k<10000)
       {
          if(b<c)
           {
               a=a-1;
               b=100-c+b;
           }
          else
           {
               b=b-c;
           }
          k++;
          temp=a;
          a=b;
          b=temp;
          
          if((a+b*1.0/100)>max)
           {
               max = a+b*1.0/100;
               n=k;
           }        
       }    
  cout<<n<<"\n";
  }
  
 
 return 0;

}

6

“Also note that after 10000 times we definitely obtain some amount of money that we had before” - @admin How does one prove this?

4 Likes
7

“@programme” the answer can be at max 10000

8

Its given in the problem itself-It is guaranteed that the answer is less than 10000.

9

if anyone wants to know how the maximum attempts are 10000 it is because of pigeon hole principle as you can have 100 dollar and 100 cent so all possible combination will be 10000 if you do this transformation more then that you will end in the same state as in one of the previous attempts. the maximal profit is limited to 200 because 100 dollar +100 cent is the maximum you can get (i know what i have written is 101 dollar but it proves the bound ).