Question regarding different constraints in problems

help
1

I’ve recently started coding in c++ and trying to get into competitive programming in general and i have a few questions i can’t find an answer to. some guidance will be greatly appreciated.

In problems there are constraints regarding input, time and memory.

Time is easy to figure out as compiling will give you the time. However input constraints and memory, i can’t figure out. Take this example:

*Time limit: 1.00 s
*Memory limit: 512 MB

Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows:

3→10→5→16→8→4→2→1

Your task is to simulate the execution of the algorithm for a given value of n.

Input

The only input line contains an integer n.

Output
Print a line that contains all values of n during the algorithm.

Constraints
1≤ n ≤10^6

Example
Input:
3

Output:
3 10 5 16 8 4 2 1

Simple enough. But…

  • how do I limit the memory to 512 MB? How can i make sure it won’t take more?
  • the constraint says n has to be positive under 1,000,000. But what if i input a bigger value? what am i supposed to do with those constraints that are not fulfilled? skip the execution?

Thank you for your help!

2

@crimson_deity what I think here you can use a while loop which works until n is not equal to 1. and now you want to print all the values so here is the code. so to ensure that you were use only provided amount of memory you need to know about the size of each data type for eg:-
int takes 4 bytes.
char take 1 byte.
float take 4 bytes.
so according to this you need to ensure that the total amount of memory you are taking for your program by creating variables is not exceed the memory limit.
And about (1<=n<=10^6) means the value of n must be equal to 1 or greater than 1 and the value of n must be equal to 10^6 or less than 10^6.

        #include<iostream>
        using namespace std;

        int main()
        {
           long long n;
           cin>>n;

           while(n>1)
           {
              cout<<n<<" ";
              if(n%2==0)
                 n=n/2;
              else
                 n=n*3+1;
           }

           cout<<n;

           return 0;
        }
3

Thanks for your reply. So, the 512 mb is not going over that while using data in variables? is there a way to limit that besides code?

4

You need to be aware of how much memory each data type consumes and what are the constraints and then figure out the memory your program might use on your own. Also, any online judge guarantees that the input is within the constraints and you do not need to explicitly check for invalid inputs.

2 Likes
5

Oooohh, I understand now. Thank you very much!

1 Like