GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Thursday 8 September 2022

[Solution] Fishermen Codeforces Solution


F. Fishermen
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There are n fishermen who have just returned from a fishing trip. The i-th fisherman has caught a fish of size ai.

The fishermen will choose some order in which they are going to tell the size of the fish they caught (the order is just a permutation of size n). However, they are not entirely honest, and they may "increase" the size of the fish they have caught.

Formally, suppose the chosen order of the fishermen is [p1,p2,p3,,pn]. Let bi be the value which the i-th fisherman in the order will tell to the other fishermen. The values bi are chosen as follows:

  • the first fisherman in the order just honestly tells the actual size of the fish he has caught, so b1=ap1;
  • every other fisherman wants to tell a value that is strictly greater than the value told by the previous fisherman, and is divisible by the size of the fish that the fisherman has caught. So, for i>1bi is the smallest integer that is both strictly greater than bi1 and divisible by api.

For example, let n=7a=[1,8,2,3,2,2,3]. If the chosen order is p=[1,6,7,5,3,2,4], then:

  • b1=ap1=1;
  • b2 is the smallest integer divisible by 2 and greater than 1, which is 2;
  • b3 is the smallest integer divisible by 3 and greater than 2, which is 3;
  • b4 is the smallest integer divisible by 2 and greater than 3, which is 4;
  • b5 is the smallest integer divisible by 2 and greater than 4, which is 6;
  • b6 is the smallest integer divisible by 8 and greater than 6, which is 8;
  • b7 is the smallest integer divisible by 3 and greater than 8, which is 9.

Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

You have to choose the order of fishermen in a way that yields the minimum possible i=1nbi.

Input

The first line contains one integer n (1n1000) — the number of fishermen.

The second line contains n integers a1,a2,,an (1ai106).

Output

Print one integer — the minimum possible value of i=1nbi you can obtain by choosing the order of fishermen optimally.

No comments:

Post a Comment