asim2005's blog

By asim2005, 5 months ago, In English

https://codeforces.com/problemset/problem/1250/F

Can anybody please help me in solving this problem?

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

»
5 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

loop over i: 1 to n. if n is divisible by i, then take best: (i + n / i) and minimize it. then the answer is best * 2. code:

Spoiler
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the solution. But I could not understand the approach. What is the use of best variable in this code? And why should I minimize it? Can you please explain these to me? It would be a great help of me.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      best variable is used to store the minimum value of sum of any 2 non-parallel sides of the rectangle over all possible pairs of such sides.

      Doubling the value of the variable will result in the perimeter of the rectangle.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        OK, I understood. But why the value of the best variable is 1000000000 ? Is there any special reason behind it?

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That's because, no such sum can be greater that this value according to the constraints.

          You can use INT_MAX for int and LLONG_MAX for long long.

          These respective MAXs store the maximum value the can fit in the respective datatypes.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      It can be proved that a rectangle with a given area will have minimum perimeter when it is a square that is all its sides are equal, but since we can not have non-integer values for the sides, this might not be always possible, so to minimize the perimeter we can actually try to find the maximum divisor of the area, that is maximum A that divides AREA, so B will be equal to AREA/A. This turns out to be the most optimal choice. Example: Area = 16 Solution : 1 divides 16 so A=1 and B=16 Perimeter = 34. 2 divides 16 so A=2 and B=8 Perimeter = 20. 3 does not divide 16. 4 divides 16 so A=4 and B=4 Perimeter = 16(This is the best solution).101615902