Przyspieszenie programu

Question

Witam. Robię zadanie Gra Euklidesa ze Spoj.com i skończyłem je. Chyba działa, pewnie można to zrobić w prostszy sposób ponieważ spoj pokazuje, że program wykonuje się zbyt wolno o 0,01s :D Jak można go przyspieszyć ?

 

#include <iostream>

using namespace std;

int main()
{
    int ile;
    int I_gracz,II_gracz;
    int mniejsza;
    int dodatek1 = 0, dodatek2 = 0;

    cin>>ile;

    for(int i=0; i<ile; i++)
    {
        cin>>I_gracz>>II_gracz;

        while((I_gracz - dodatek1) != (II_gracz - dodatek2))
        {
            if (I_gracz<II_gracz)
            {
               mniejsza = I_gracz;
               I_gracz +=mniejsza;
                dodatek1 = mniejsza;
                II_gracz -=mniejsza;
            }
            else if(I_gracz>II_gracz)
            {
                mniejsza=II_gracz;
                II_gracz +=mniejsza;
                dodatek2 = mniejsza;
                I_gracz -=mniejsza;
            }
        }
        if((I_gracz - dodatek1)==(II_gracz-dodatek2))
            cout<<(I_gracz - dodatek1)+(II_gracz-dodatek2)<<endl;

    }

    return 0;
}

 

Comments

Może wystarczy zamiast else if(I_gracz>II_gracz) dać po prostu else...

Myślę, że o 0,01s przyspieszy :)

0,01s to jest tak mało, że kwestia temperatury ramu i procka może dużo zmienić

Answer 1

Co ty robisz z tym dodatek ? Przecież masz podać tylko liczbę żetonów w grze.

a - żetony 1. gracza, b - żetony 2. gracza.

a>b:

a=a-b

b>a

b=b-a

 

I powtarzasz aż a=b.

Po za tym nie rób else if, jeżeli wystarczy samo else.

Comments

Nie wiem czy w tym zadaniu tak ma być ale jak zrobi else to będzie inne działanie programu. Zobacz, że ma w jednym przypadku zbiór (-nsk; 0) a w drugim (0; +nsk) więc nie rozpatruje zera.

---

Nie analizowałem, za bardzo jego kodu, nie zwracałem uwagi na przypadki graniczne. Po za tym, ten jeden if jest mało ważny, więc może zostać. Chodzi głównie o to, że zapamiętuje to co jest nie potrzebne, czyli jakiś dodatek.

---

dodatki robily tu jako części żetonów, których przeciwnik nie może pobierać. Polecenie mnie troche wkręciło w inny tok myślenia ale wykonałem to tym prostszym sposobem który podałeś.

---

Czyli zapamiętywałeś żetony, które nie są w grze. Jednak po co do tego aż dwie zmienne.