#include <iostream>
#include <string>
#include <ostream>
#include <math.h>

using namespace std;

int tamanhoString(string texto)
{
    int i = 0;
    while (texto[i] != 0)
    {
        i++;
    }
    return i;
}

int numPalavras(string texto, char delimitador)
{
    int num_palavras = 0;
    for (int i = 0; i < tamanhoString(texto); i++)
    {
        if (i == 0)
        {
            num_palavras = 0;
        }
        else if (((texto[i] == delimitador) && (texto[i - 1] != delimitador)) || ((i == tamanhoString(texto) - 1) && (texto[i] != delimitador)))
        {

            num_palavras++;
        }
    }
    return num_palavras;
}

void split(string texto, string palavras[], char delimitador)
{
    int num_palavras = numPalavras(texto, delimitador);



    string temp = "";
    int contador = 0;
    for (int i = 0; i < tamanhoString(texto); i++)
    {
        if ((texto[i] != delimitador) && (i != tamanhoString(texto) - 1))
        {
            temp = temp + texto[i];
        }
        else if ((i != 0) && (texto[i] == delimitador) && (texto[i - 1] != delimitador))
        {
            palavras[contador] = temp;
            contador++;
            temp = "";
        }
        else if ((i == tamanhoString(texto) - 1) && (texto[i] != delimitador))
        {
            temp = temp + texto[i];
            palavras[contador] = temp;
            temp = "";
            contador = 0;
        }
    }

}

int numLinhas(int totalPalavras, double quebras[])
{
    int i;
    int j = totalPalavras;
    int num_linhas = 0;
    while (j > 0)
    {
        i = quebras[j - 1];
        num_linhas++;
        j = i;
    }
    return num_linhas;
}
int tamanhoItens(string palavras[], int num_palavras)
{
    int tamanho = 0;
    for (int i = 0; i < num_palavras; i++)
    {
        tamanho += tamanhoString(palavras[i]);
    }
    return tamanho;
}

string alinhaTexto(string texto, int larguraLinha, int ultimaLinhaParagrafo)
{
    string* palavras = new string[numPalavras(texto, ' ')];
    string resposta = "";
    int contaEsquerda;
    int num_itens = numPalavras(texto, ' ');
    split(texto, palavras, ' ');
    for (int i = 0; i < num_itens - 1; i++)
    {
        palavras[i] += ' ';
    }
    if (!ultimaLinhaParagrafo)
    {
        contaEsquerda = larguraLinha - tamanhoItens(palavras, num_itens);
        while ((contaEsquerda > 0) && (num_itens > 1))
        {
            for (int i = 0; i < num_itens - 1; i++)
            {
                palavras[i] += ' ';
                contaEsquerda--;
                if (contaEsquerda < 1)
                {
                    break;
                }
            }
        }
    }
    for (int i = 0; i < num_itens; i++)
    {
        resposta += palavras[i];
    }
    return resposta;

}

int contarN(string texto) {
    int contador2 = 0;
    for (int i = 0; i <= tamanhoString(texto); i++) {
        if ((i != tamanhoString(texto)) && (texto[i] == '<' && texto[i + 1] == 'n')) {
            contador2++;
            i = i + 2;
        }
    }
    return contador2;
}

void criarLinhas(string linha[], string texto) {
    int contador = 0;
    for (int i = 0; i <= tamanhoString(texto); i++) {
        if ((i != tamanhoString(texto)) && (texto[i] == '<' && texto[i + 1] == 'n')) {
            contador++;
            i += 2;
        }
        else {
            linha[contador] += texto[i];
        }

    }

}






string justificar2(string texto, int larguraLinha) {
    string textoJustificado = "";
    string* palavras = new string[numPalavras(texto, ' ')];
    split(texto, palavras, ' ');
    int totalPalavras = numPalavras(texto, ' ');
    int** espacoVazio = new int* [totalPalavras];
    for (int i = 0; i < totalPalavras; i++)
        espacoVazio[i] = new int[totalPalavras];

    for (int i = 0; i < totalPalavras; i++)
    {
        espacoVazio[i][i] = larguraLinha - tamanhoString(palavras[i]);
        for (int j = i + 1; j < totalPalavras; j++)
        {
            espacoVazio[i][j] = espacoVazio[i][j - 1] - tamanhoString(palavras[j]) - 1;
        }

    }
    double* minima = new double[totalPalavras + 1];
    double* quebras = new double[totalPalavras];
    double custo;
    minima[0] = 0;
    for (int i = 1; i <= totalPalavras; i++)
    {
        minima[i] = pow(10, 20);
    }
    for (int i = 0; i < totalPalavras; i++)
    {
        quebras[i] = 0;
    }
    int i = 0;
    for (int j = 0; j < totalPalavras; j++)
    {
        i = j;
        while (i >= 0)
        {
            if (espacoVazio[i][j] < 0)
            {
                custo = pow(10, 10);
            }
            else
            {
                custo = minima[i] + pow(espacoVazio[i][j], 2);
            }
            if (minima[j + 1] > custo)
            {
                minima[j + 1] = custo;
                quebras[j] = i;
            }
            i--;

        }

    }
    string* linhas = new string[numLinhas(totalPalavras, quebras)];
    int contador = 0;
    int j = totalPalavras;
    while (j > 0)
    {
        i = quebras[j - 1];
        for (int k = i; k < j; k++)
        {
            if (k != j - 1)
            {
                linhas[contador] = linhas[contador] + palavras[k] + ' ';
            }
            else
            {
                linhas[contador] = linhas[contador] + palavras[k];
            }
        }
        contador++;
        j = i;
    }
    string* temp = new string[contador];
    for (int i = 0; i < contador; i++)
    {
        temp[(contador - 1) - i] = linhas[i];
    }
    for (int i = 0; i < contador; i++)
    {
        linhas[i] = temp[i];
    }
    for (int k = 0; k < contador; k++)
    {
        textoJustificado = textoJustificado + "\n" + alinhaTexto(linhas[k], larguraLinha, 0);
    }
    return textoJustificado;
}



string justificar(string texto, int larguraLinha)
{
    int numeroN = contarN(texto);
    string* linhasSemN = new string[numeroN + 1];
    criarLinhas(linhasSemN, texto);
    string real = "";
    for (int i = 0; i < numeroN; i++) {
        if (i <= numeroN - 1) {
            real += justificar2(linhasSemN[i], larguraLinha) + "\n";
        }
        else {
            real += justificar2(linhasSemN[i], larguraLinha);
        }
    }
    return real;
}



int main()
{
    string texto = "Seja Bem vindo ao 'Soul of Pirates Online'.<n> Você acaba de embarcar em um Mundo conhecido como Orisord, um lugar repleto de criaturas místicas, tesouros e segredos que o aguardam para grandes aventuras.<n> Sua jornada se inicia em uma cidade...";
    int larguraLinha = 38;
    cout << contarN(texto);
    cout << justificar(texto, larguraLinha);
}