When G cell divides, it is divided into two G + 1 cells.
In order for the G cell to divide, energy as much as G is required.
What is the minimum energy required to make the total number of cells x?
Input Example (G for each of 2 cells, total number of cells)
1 3 4
Output Example (minimum energy)
3
Input Description Assuming that there is one cell of the first generation and one cell of the first generation in the beginning, the energy required to make a total of four cells is as follows. 1G 3G -> Generation 1 (Energy 1 required) 2G 2G 3G -> Generation 2 (energy 2 required) 2G 3G 3G 3G (total 4 completed final energy 3)
I've answered the question in C #.
Is there a better way or a way to speed it up?
ex) If Sum is 10 million
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
StringBuilder m_strbuilder = new StringBuilder();
List<int> Cells = new List<int>();
int MinIndex = 0;
int Sum = 0;
int FirstCell = 0;
int SecondCell = 0;
bool etc = true;
ulong Result = 0;
string Inputdata = null;
string[] Textdata = null;
while (etc)
{
try
{
Cells.Clear();
Inputdata = Console.ReadLine();
Textdata = Inputdata.Split(' ');
if (Textdata[0] != null && Textdata[1] != null && Textdata[2] != null)
{
int.TryParse(Textdata[0], out FirstCell);
int.TryParse(Textdata[1], out SecondCell);
int.TryParse(Textdata[2], out Sum);
}
else
continue;
if ( 0 < FirstCell && FirstCell <= 10000000)
{
if (0 < SecondCell && SecondCell <= 10000000)
{
if (2 <= Sum && Sum <= 100000000)
etc = false;
else
continue;
}
else
continue;
}
else
continue;
}
catch (ArgumentException e)
{
Console.WriteLine("Unable to add {0}", e.ToString());
}
catch (NullReferenceException e)
{
Console.WriteLine("Unable to add {0}", e.ToString());
}
catch (IndexOutOfRangeException e)
{
Console.WriteLine("Unable to add {0}", e.ToString());
}
}
Cells.Add(FirstCell);
Cells.Add(SecondCell);
if (Cells[0] > Cells[1])
{
int TempNum = Cells[1];
Cells[1] = Cells[0];
Cells[0] = TempNum;
}
for (int i = 2; i < Sum; i++)
{
Result += (ulong)Cells[MinIndex];
Cells[MinIndex] += 1;
Cells.Insert(MinIndex + 1, Cells[MinIndex]);
if (MinIndex + 1 != Cells.Count - 1)
{
if (Cells[MinIndex + 2] < Cells[MinIndex])
MinIndex = MinIndex + 2;
else
MinIndex = 0;
}
else
MinIndex = 0;
}
m_strbuilder.Append(Result);
Console.WriteLine(m_strbuilder);
}
}
}