80/100 in Meal Tickets

Aiuto
1

Nell’ ultimo subtask dell’ esercizio Meal Tickets non so perchè mi esce dal tempo nonostante ci sia scritto che non ci sono limitazioni aggiuntive.
Qualche consiglio?

#include <bits/stc++.h>

using namespace std;

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    long long T, Variabile = 0, j;
    cin >> T;
    for (j = 1; (Variabile + j) <= T; j++)
    {
        if ((Variabile + j) == T)
        {
            cout << j;
            return 0;
        }
        Variabile = Variabile + j;
    }
    cout << j - 1;
    return 0;
}
2

Il T massimo è 10e18, e ti dico che per quel valore la soluzione è circa 10e9.
Quindi non è possibile fare 100 punti utilizzando un codice che scorre tutti i valori, dato che va in TLE.
Suggerimento: la somma dei primi N numeri é uguale a N*(N+1)/2
Prova a usare questa formula a tuo vantaggio

1 Mi Piace
3

Grazie non avevo pensato di usare direttamente la formula della sommatoria

4

io per non uscire dal tempo limite ho usato la formula della sommatoria ( n * (n + 1) / 2 ) insieme alla ricerca binaria

1 Mi Piace
5

In realtà il problema si può anche risolvere in O(1) riconducendosi ad un’equazione di secondo grado
L’output è

(sqrt(8*T+1)-1)/2

4 Mi Piace
6

Sì, questa la trovi grazie alla formula della sommatoria