Question

Chalk
Raj's teacher Anu uses chalk to write on the board. When the chalk reduces to 1/squareroot(n) of its original size, she keeps the chalk aside as it gets too small. She joins all the small pieces of the chalk and makes another chalk of the same size and uses it. If she uses one chalk each day, in how many days will she use the given n number of chalks?
INPUT & OUTPUT FORMAT:

Input consists of 1 integer which corresponds to the number of chalks given. Output corresponds to the number of days in which the given number of chalks will be used.

SAMPLE INPUT:

16

SAMPLE OUTPUT:

21

Answer 1

The Chalk Roots - Java and Python

The problem is a mathematical one, and the solution becomes very elegant once we analyze it a bit.

So, we have $\sf n$ chalks. Raj's teacher Anu will use each of them till they are $\sf \dfrac{1}{\sqrt{n}}$ of their size.

Let us suppose that the length of each chalk is 1 unit.

So, after using $\sf n$ chalks, we are going to be left with

$\sf \textsf{Total length of remaining pieces} = n \times \dfrac{1}{\sqrt{n}} = \sqrt{n} \textsf{ units}$

Now, remember that each chalk is one unit in length. So, when Anu builds new chalks from these pieces, we will have $\sf \sqrt{n}$ chalks.

Remember that chalks come only in integer amounts. So, we will have to round it off with the floor function.

Finally, if $\sf n$ is a perfect square, then $\sf \sqrt{n}$ is an integer and after these chalks are used, we will have:

$\sf \textsf{Total length of remaining pieces in second round} = \sqrt{n} \times \dfrac{1}{\sqrt{n}} = \textsf{1 unit}$

Thus, if $\sf \sqrt{n}$ is an integer, then Anu can build one more chalk.

However, if $\sf n = 1$, then we have a problem. The criteria to throw the chalk away is $\sf \dfrac{1}{\sqrt{1}} = 1$, which means the chalk goes for infinite days. Or zero days if we want to define it that way.

Since we aren't given what to do in this edge case, we will just count it as Infinite.

Finally, we can define a function.

$\sf A = (\mathbb{N} \backslash \{1\}) \cup \{ 0 \} \\\\ \sf f : A \to A \\\\ \sf f(n) = \textsf{Total number of days the chalks work for Anu}$

Based on our analysis, the function definition will look like this:

$\boxed{\sf f(n) = \begin{cases}\sf n + \lfloor \sqrt{n}\rfloor & \textsf{if n is not perfect square} \\\\ \sf n + \sqrt{n} + 1 & \textsf{if n is a perfect square} \end{cases}}$

Or, if we want to simplify further, we would have:

$\boxed{\sf f(n) = n + \lfloor \sqrt{n} \rfloor + \left\lfloor \dfrac{\sqrt{n}}{\lceil \sqrt{n} \rceil} \right\rfloor}$

This combination of floor and ceiling functions takes care of the 0 and 1 thing. In Java, we use the $\sf java.lang.Math$ library and this simply becomes:

$\sf f(n) = (int) (n + Math.floor(n) + Math.floor(Math.sqrt(n) / Math.ceil(Math.sqrt(n))))$

(We need to do a typecast or Java will throw an error)

And in Python, we would have to import the $\sf math$ module and some functions from it. And do this:

$\sf f(n) = int(n + int(sqrt(n)) + sqrt(n) // ceil(sqrt(n)))$

Anyways, let's finally get to the coding part.

$\rule{300}{1}$

Chalk.java

import java.util.Scanner;

public class Chalk

{

   public static void main(String[] args)

   {

       // Create Scanner Object

       Scanner sc = new Scanner(System.in);

       // Take user input of n

       int n = sc.nextInt();

       // Close Scanner Object

       sc.close();

       // If n is 1, return Infinity and exit

       if (n == 1)

       {

           System.out.println(Double.POSITIVE_INFINITY);

           return;

       }

       // Calculate the number of days the chalks will work

       int numberOfDays = (int) (n + Math.floor(Math.sqrt(n)) + Math.floor(Math.sqrt(n) / Math.ceil(Math.sqrt(n))));

       // Print the answer

       System.out.println(numberOfDays);

   }

}

$\rule{300}{1}$

Chalk.py

from math import sqrt, floor, ceil, inf

from sys import exit

# Take user input of n

n = int(input())

# If n is 0, print 0

if n == 0:

   print(0)

   exit(0)

# If n is 1, print math.inf (infinity)

if n == 1:

   print(inf)

   exit(0)

# Calculate number of days the chalks will work

number_of_days = int(n + int(sqrt(n)) + sqrt(n) // ceil(sqrt(n)))

# Print the answer

print(number_of_days)

$\rule{300}{1}$

A few screenshots are attached for reference.