Let's assume delta is the difference between the nearest number in our set. Then we can approve delta will decrease by half (at least) in every 2 rounds. So the simulation will be executed at most 2log 10^18 time, it's about 120.

1) Try writing an algorithm for finding the minimum difference in a list first (list.sort() method may come in handy)

2) Think of how the usage of sets and lists may assist you in determining whether we have doublets in your list

3) Use counters for finding the number of iterations in your cycle

Enjoy :)

Edited by author 25.07.2021 21:52

Edited by author 25.07.2021 21:52

We have got 3 distinct number, A < B < C.
Let's imagine that the minimum difference Z = (C - B) goes between numbers A and B, closer to B, so new sequence will be A < Z < B < C. And the next minimum difference Y = (B - Z), goes between A and Z, closer to Z, A < Y < Z < B < C and so on.
You see Y + Z = B, Z + B = C, the next number in the sequence (in order from left to right) is equal to the sum of current and previous members (looks like Fibonacci numbers).
Now try to find the sequence with described property.

Look at the example: 1 4 6 10 16 26 ... We can continue this sequence until the last two members will be 519390993822245170 and 840392281454979346. Their sum is more than 10^18. It takes only 83 iterations to build this sequence.

The test case would be: 1 519390993822245170 840392281454979346

So, in the worst case, the number of iteration N < 100.

The naive algorithm, when we just put the minimum diff to the array and sort it again will work. The time complexity will be O(N^2 log N).

Edited by author 01.10.2019 14:24

Hello,
So initially I thought there might some cases like there are in questions regarding divisors, range, odd, even etc. However, there wasn't any such case.

I tried simulating the above problem for a = 1-20, b =1-20, c= 1-20. The maximum possible answer was 3 and minimum was 3 so I was sure simulation was enough. I tried my best to derive some relation but was unable to do so.

So in this way, you could think about solving the problem and just simulate the whole process to solve it.

After we add new pile Z of stones if there is new pair of piles X and Y such that |X-Y| is minimal that either X=Z or Y=Z. So,  just add nee pile and recalculate new pair of piles such that the difference between stones count is minimal in O(n)  where n is tje number of piles present now.

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

#define True 1
#define False 0
#define N 15
#define MAX_DIFF 1000000000000000001

void print_a(unsigned long long a[N])
{
    int i;
    printf("\n----------------\n");
    for (i = 0; a[i] != 0; i++) {
        printf("%llu\n", a[i]);
    }
    printf("\n--------------\n");
}

void sort(unsigned long long a[N])
{
    int i, j, s_fl;
    unsigned long long tmp;
    for (i = 0, s_fl = True; s_fl == True; i++) {
        for (j = 0, s_fl = False; j < N-i-1; j++) {
            if (a[j] < a[j + 1]) {
                s_fl = True;
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}


int main(int argc, char *argv[])
{
    int i, j, c;
    unsigned long long prev, diff;
    unsigned long long max[N] = {0};
    for (i = 0; i < 3; i++)
        scanf("%llu", &max[i]);

    sort(max);

    for (j = 2, c = 0; max[j] != 0; j++, c++) {
        for (i = 0, diff = MAX_DIFF; max[i + 1] != 0; i++) {
        prev = max[i] - max[i + 1];
        if (prev < diff)
            diff = prev;
        }
        max[j + 1] = diff;
        sort(max);
    //    print_a(max);
    }

    printf("%d\n", c);

    return 0;
}

I didn't find a mistake in my program. And what is the test #19? I'am confused(

Try these tests on big input data:
1000000000000000000 999999999999999990 999999999999999999
3

1000000000000000000 10 500000000000000000
3

1000000000000000000 500000000000000000 250000000000000000
2

Tips:
1. Remember, that you should not only forget about using big types (for c++ it's long long int or __int64) but not forget to take big input data correctly.
For example, if you will use scanf("%d", &i), it will not get correctly a big input digit.
2. If you use min function in you program to find the minimum of two digits, don't forget to initialize your min value variable with the maximum value your can input.
For example, __int64 minInit = LLONG_MAX.

If you have such problems, you will have incorrect answers on the second and third tests (you'll get 4 and 3 respectively) and you will have WA on the tests 17 (the first tip) and 18 (the second tip).

What is test 2?

What is in test 33 ?
The same code with Scanner is accepted but with StreamTokenizer and BufferedReader is giving WA33. Very unexpected result!! O_O


Edited by author 16.12.2012 10:56

I use unsigned long long and STL vector with very simple algorithm: store x1, x2, x3 in the vector, then find the minimal diffenrence and push it in the vector (repeat the process until minimal difference is 0). I got AC.
I suppose that the tests are not strong enough. I wonder whether there is any test whose output is very large since I don's believe vector can store too many elements.
P/S: I'm a beginner so I'm very glad to study from all of you :-)!

Edited by author 21.10.2012 03:11

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

int cmp(const void *a, const void *b)
{
    unsigned long long *pa = (unsigned long long *)a,
    *pb = (unsigned long long *)b;
    return *(unsigned long long *)pa - *(unsigned long long *)pb;
}


int main()
{
    unsigned long long arr[15000], min=1000000000000000000;
    int N=3, count=0, i;

    for(i = 0; i<N; i++)
        scanf("%llu", &arr[i]);
    while(min)
    {
        qsort (arr, N, sizeof(unsigned long long), cmp);
        for (i = 0; i<N-1; i++)
            if(arr[i+1] - arr[i]<min) min=arr[i+1] - arr[i];
        arr[N++] = min;
        count++;
    }
    printf("%d", count);

    return 0;
}
Can anybody help me?

For example, I got WA19 at first time.
I changed real to extended and integer to longint and got AC.

subj

пробовал разные способы вычисления, упираюсь в 33 тест.
Какие есть мысли?

Here is my code:

#include <iostream>

using namespace std;

int x[200];

int compare (const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}

int main()
{
    int r[200], a = 3;
    long min;
    bool z = false;
    for (int  i = 0; i<3; i++)
        cin>>x[i];
    for ( ; ; )
    {
        qsort (x, a, sizeof(int), compare);
        min = 1000000000;
        for (int i = 0; i<a-1; i++)
        {
            r[i] = abs(x[i] - x[i+1]);
            if (r[i]<min)
                min = r[i];
        }
        x[a] = min;
        for (int j = 0; j<a; j++)
        {
            if (x[j] == min)
            {
                z = true;
                break;
            }
        }
        if (z == true) break;
        a++;
    }
    printf("%d", a - 1);
    return 0;
}

Where is my mistake?

Edited by author 31.01.2012 15:35

plese give me test 23