/*
Meliodas and Ban are fighting over chocolates.
Meliodas has X chocolates, while Ban has Y.
Whoever has lesser number of chocolates eats as many chocolates as he has from the other's collection.
This eatfest war continues till either they have the same number of chocolates,
or atleast one of them is left with no chocolates.
Can you help Elizabeth predict the total no of chocolates they'll be left with at the end of their war?
Constraints
1 ≤ T ≤100000
0 ≤ X, Y ≤ 109https://www.codechef.com/problems/SINS
*/
#include <stdio.h>
void do_test()
{
int meliodas, ban;
scanf("%d %d", &meliodas, &ban);
do
{
if (meliodas > ban)
meliodas -= ban;
elseif (ban > meliodas)
ban -= meliodas;
}while (meliodas != ban && meliodas != 0 && ban != 0);
printf("%d\n", meliodas + ban);
}
int main()
{
int num_tests;
scanf("%d", &num_tests);
while (num_tests--)
{
do_test();
}
return 0;
}
I found a solution. Instead of the do while loop I used
printf("%d\n", gcd(meliodas,ban) * 2);
Running time was 0.02s
So the output was not the problem.
it would still be faster if you factored out the printf, and it may also be microscopically faster if you make the 2 ints in the do_test static. Shifting once is faster than multiply by 2. Make sure your compile can inline the function, or just DIY... now that you boiled the function down to a couple of statements, get rid of it and just put the scanf & printf/gcd all in the main directly. If you remove the function to go inline, the static tweak isnt useful anymore.
Just some simple ideas to try, you can see if they knock it on down in run time..
If you really also want to go for just speed, read and write from a file
Since it's being run and tested automatically it's not writing to a terminal anyway.
It's probably just piped to the checking program so it's not even writing to a file.
Yes the input and output is coming / going to a file.
Make sure your compile can inline the function
codechef uses GCC with -O2 so maybe it gets inlined, to be sure I will use a macro next time.
I am totally happy with the result now. I will keep the ideas for later tasks in mind.
I am still surprised that the actual problem was the do-while loop with the subractions and comparisons.
I am not terribly interested in codechef but for my personal info, does it score you more points for lower times or just full points for beating the time & getting it right?