Magical Well Of Lilies Solution | Round H 2022 - Kick Start 2022

 

Magical Well Of Lilies Solution (8pts, 13pts)

Problem

There is a deep magical well in a forest that has some lilies on its waters. You have a large empty basket and some coins, and are standing next to the well. You have more coins than there are lilies in the well. The well has taken note of the fact that your basket is empty.

If you toss one coin into the well, the well will toss out one lily into your basket. If you toss four coins at once into the well, the well will take note of how many lilies it has tossed out into your basket so far. If you toss two coins at once into the well, the well will toss out as many lilies into your basket as it had last taken note of. If you toss one coin, or two coins at once, into the well, and there are not enough lilies left in the well, the well will not toss out any lilies.

Given the number of lilies L$L$ in the well at the beginning, return the minimum number of coins you will need to toss into the well to make it toss all of its lilies into your basket.

Input

The first line of the input gives the number of test cases, T$T$. T$T$ lines follow.
Each line contains a single integer L$L$, representing the number of lilies in the well at the beginning.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the minimum number of coins you will need to toss into the well to make it toss out all of its L$L$ lilies into your basket.

Limits

Time limit: 15 seconds.
Memory limit: 1 GB.

Test Set 1

1≤T≤20$1\le \mathbf{T}\le 20$.
1≤L≤20$1\le \mathbf{L}\le 20$.

Test Set 2

1≤T≤100$1\le \mathbf{T}\le 100$.
1≤L≤105$1\le \mathbf{L}\le {10}^5$.

Sample

Sample Input

save_alt

content_copy

2
5
20

Sample Output

save_alt

content_copy

Case #1: 5
Case #2: 15

For test case #1, when there are 5$5$ lilies in the well, the least number of coins needed is 5$5$. We toss them, one at a time, into the well, and the well tosses out the 5$5$ lilies, one at a time, into our basket. No other sequence of moves results in a better solution, so 5$5$ is our answer.

For test case #2, first, we toss 5$5$ coins, one at a time, into the well, and the well tosses out 5$5$ lilies, one at a time, into our basket. Next, we toss 4$4$ coins at once into the well, and the well takes note that it has tossed out 5$5$ lilies into our basket so far. Then, we toss 2$2$ coins at once into the well, and the well tosses out 5$5$ lilies (that it took note of) into our basket. Then, we toss another 2$2$ coins at once into the well, and the well tosses out another 5$5$ lilies into our basket. Finally, we toss another 2$2$ coins at once into the well, and the well tosses out the final 5$5$ lilies into our basket. Total coins needed is 15$15$. Getting 20$20$ lilies out of the well is not possible with any lesser number of coins, so 15$15$ is our answer.

Solution:

We need to use DP here to store the minimum number of coins for i lilies.

We can move from i to i+1 with one coin Or we can register with 4 coins and then move with 2 coins from i to 2*i then 3*i and so on.

#include <bits/stdc++.h>

using namespace std;

#define int            long long int

#define F              first

#define S              second

#define pb             push_back

#define si             set <int>

#define vi             vector <int>

#define pii            pair <int, int>

#define vpi            vector <pii>

#define vpp            vector <pair<int, pii>>

#define mii            map <int, int>

#define mpi            map <pii, int>

#define spi            set <pii>

#define endl           "\n"

#define sz(x)          ((int) x.size())

#define all(p)         p.begin(), p.end()

#define double         long double

#define que_max        priority_queue <int>

#define que_min        priority_queue <int, vi, greater<int>>

#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

#define print(a)       for(auto x : a) cout << x << " "; cout << endl

#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl

#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)

{

  int x = 1;

  while (b)

  {

    if (b & 1) x *= a;

    a *= a;

    b >>= 1;

  }

  return x;

}

template <typename Arg1>

void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }

template <typename Arg1, typename... Args>

void __f (const char* names, Arg1&& arg1, Args&&... args)

{

  const char* comma = strchr (names + 1, ',');

  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);

}

const int N = 200005;

void solve(int tc) {

int l;

cin>>l;

vi dp(l+2);

for(int i=0; i<l+2; i++)dp[i]=i;

for (int i = 2; i < l+1; i++)

{

  dp[i+1]=min(dp[i]+1,dp[i+1]);

  int curr=dp[i]+4;

  for(int j=2*i; j<l+2; j+=i){

    curr+=2;

    dp[j]=min(dp[j],curr);

  }

}

cout<<"Case #"<<tc<<": "<<dp[l]<<endl;

}

int32_t main()

{

  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  clock_t z = clock();

  int t = 1;

  cin >> t;

  int k=1;

  while (t--) solve(k++);

  return 0;

}