 # FODCHAIN - Editorial

Author: Daanish Mahajan
Tester: Manan Grover
Editorialist: Vichitr Gandas

CAKEWALK

NONE

# PROBLEM:

Given the initial energy E and it reduces by a factor of K when going to next level. Find the length of food chain where each level has non-zero energy.

# EXPLANATION

It is given that K >= 2 hence we can just loop on E and every time do E = E/K until E becomes 0. The number of loop iterations is the maximum number of levels.

Notice that answer is just \log_{K}{E} as everytime E is reduced by a factor of K.

# TIME COMPLEXITY:

O(\log_{K}{E}) per test case

# SOLUTIONS:

Setter's Solution
``````#include<bits/stdc++.h>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;

const string newln = "\n", space = " ";
const int maxt = 1e5, maxe = 1e9, maxb = 1e9;
int main()
{
int t, e, b;
cin >> t;
while(t--){
cin >> e >> b;
int ans = 1;
while(e / b > 0){
e /= b; ans++;
}
cout << ans << endl;
}
}
``````
Tester's Solution
``````#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n, k;
cin>>n>>k;
int ans = 0;
while(n != 0){
ans++;
n /= k;
}
cout<<ans<<"\n";
}
return 0;
}
``````
Editorialist's Solution
``````/*
* @author: vichitr
* @date: 24th July 2021
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);

void solve() {
int E, K; cin >> E >> K;
int ans = 0;
while (E > 0) {
E = E / K;
ans++;
}
cout << ans << '\n';
}

signed main() {
fast;

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

int t = 1;
cin >> t;
for (int tt = 1; tt <= t; tt++) {
// cout << "Case #" << tt << ": ";
solve();
}
return 0;
}
``````

# VIDEO EDITORIAL:

If you have other approaches or solutions, let’s discuss in comments.If you have other approaches or solutions, let’s discuss in comments.

An efficient solution
https://www.codechef.com/viewsolution/49061461

This is same as my solution or possibly every other solution. The inbuilt function \log also take same time as mentioned in the editorial.

``````#include <bits/stdc++.h>
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

#endif

ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long test_case;
cin >> test_case;
while (test_case--)
{
long long a, b;
cin >> a >> b;
if (a==0)
cout << 0;
else
cout << 1 + (floor)((log(a) / log(b)));
cout << "\n";
}
return 0;
}
``````

Kudos to the Author for generating strong test cases .