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

Can anybody please help me in solving this problem?

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 211 |

2 | awoo | 189 |

3 | Errichto | 186 |

4 | rng_58 | 185 |

5 | SecondThread | 182 |

6 | Ashishgup | 176 |

7 | Um_nik | 175 |

8 | maroonrk | 174 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 169 |

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

Can anybody please help me in solving this problem?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/17/2021 13:40:08 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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:

SpoilerThanks 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.

`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.

OK, I understood. But why the value of the best variable is 1000000000 ? Is there any special reason behind 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.

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