Olympic Cake - Execution timed out

Qualcuno mi sa dare un consiglio su come rendere più veloce l’esecuzione del codice?
I subtask 1-4 funzionano, il subtask 5 che prevede N>1 000 000 da execution timed out.

#include<stdio.h>
#include<stdlib.h>

main()
{
    unsigned long N;
    unsigned long r;
    unsigned long c;
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    r=1;
    c=1;
    scanf("%lu", &N);
    int i=0;
    
    for(i=0; i<N; i+=2)
    {
        c++;
        r++;
    }
    
    if(i>N)
        r--;
    
    printf("%lu", (r*c));
}
1 Mi Piace

Sei sicuro che sia necessario un for() per sapere quante volte puoi togliere 2 da N?

2 Mi Piace

Non c’è bisogno di un for per risolvere quel esercizio, cerca di trovare un calcolo :stuck_out_tongue:

1 Mi Piace

Ho trovato un ottimo algoritmo per ottenere quel risultato e sembra funzionare sempre.
20180923_194053

2 Mi Piace

Potresti spiegare il tuo algoritmo per favore? E’ da molto che cerco di risolverlo ma le risposte date sono troppo criptiche, è un bene non dire la soluzione per farci arrivare gli altri, ma questo penalizza chi è agli inizi e non conosce particolari algoritmi come il tuo

5 Mi Piace

Devi effettuare N tagli di cui x orizzontali e y verticali dove x+y=N devi solamente scegliere il valore di x e y, ma se fai qualche tentativo manualmente ti accorgi tu stesso che è banale.

Anche perché il primo codice postato é corretto, ma lento, trasformarlo da O(n) a O(1) è banale.

3 Mi Piace