FIFTYPE - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093

DIFFICULTY:

901

PREREQUISITES:

None

PROBLEM:

Chef’s phone battery is currently at N percent, and he wants it to reach exactly 50 percent.
Each minute, the battery can either increase by 2 percent, or decrease by 3 percent.
What’s the minimum time needed for the battery to reach 50 percent?

EXPLANATION:

There is an obvious greedy simulation approach here:

  • If the battery is \gt 50, reduce it by 3.
  • If the battery is \lt 50, increase it by 2.
  • If the battery equals 50, stop.

This greedy is correct, and so directly simulating it is enough to get AC.
This simulation can be done using a while loop and if conditions.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    ans = 0
    while n != 50:
        if n > 50: n -= 3
        else: n += 2
        ans += 1
    print(ans)

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int t,n;
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for(int i=1;i<=t;i++)
{ int count = 0;
n = sc.nextInt();
while(n!=50){
if(n>50){
n=n-3;
count++;
}
else{
n=n+2;
count++;
}
}
System.out.println(count);
}
}
}