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 Can someone give me test #18??? Or give me some tests and answers??? For: 75000000000000000 50000000000000000 25000000000000000 answer is 2 (1 ≤ x1, x2, x3 ≤ 10^18) Try to use int64 Thanks, but i have already use int64/ but i dont know where's my error... :( I have submitted it more than one times with int64, but again and again I got WA on test19, however, same source code in Java using BigInteger was accepted at once. 45 1 12 You can have problems with sorting your array it was helped me. Good luck, bro! Edited by author 13.12.2018 21:43 Edited by author 13.12.2018 21:43 I didn't find a mistake in my program. And what is the test #19? I'am confused( 45 1 12 it was helped me. Good luck, bro! 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 :-)! The simulation works in O(logN), so your solution is correct 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. 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). Hi KOTnt, you helped a lot thank you ...!!! #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; } 1 1 2 1 1 2 3 2 234 532 245 3 12345 87654 23456 4 1223456 8098887645 567321 4 12345 654345678 1234567890 5 Edited by author 05.07.2011 20:09 Hey Maria, Problem states that the input, consists of 3 space-separated pairwise DISTINCT integers so your first example doesn't satisfy conditions and hence, is useless. Regards, Sepehr 99 8 1 3 thanks :) got AC after testing you input and fixing the program P.S. long in JAVA is enough!!!! Maria , for test number 4, I think the answer should be 3 : First aborigine brings a pile of 75309 ( 87654-12345 ) , the second aborigine also brings a pile of 75309 stones , because that's still the biggest difference , and the third points to the two equal piles. Correct me if I'm wrong! hopless dreamer, No, u r wrong. The FIRST aborigine will bring the pile of 64198 stones, becouse it's the LEAST. And the second aborigine will bring the pile of 64198 - 23456 = 40742 stones and so on. "Professor asked one of the aborigines to point at two piles with the MINIMAL difference of numbers of stones in them and tell what this difference is." Edited by author 06.07.2012 18:07 Edited by author 06.07.2012 18:07 subj I didnt use ull & got AC. #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? Use __int64 instead of unsigned long long I changed. But I stil have WA#17 and time limit exceed. #include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b) { __int64 *pa = (__int64 *)a, *pb = (__int64 *)b; return *(__int64 *)pa - *(__int64 *)pb; } int main() { __int64 arr[100], min=1000000000000000000; int N=3, count=0, i; for(i = 0; i<N; i++) scanf("%I64d", &arr[i]); while(min) { qsort (arr, N, sizeof(__int64), 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; } Now I have WA#17 and crash(acces violation). Of course, you have crash :D Replace all number types to __int64, uncluding int. I changed: #include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b) { __int64 *pa = (__int64 *)a, *pb = (__int64 *)b; return *(__int64 *)pa - *(__int64 *)pb; } int main() { __int64 arr[100], min=1000000000000000000, N=3, count=0, i; for(i = 0; i<N; i++) scanf("%I64d", &arr[i]); while(min) { qsort (arr, N, sizeof(__int64), 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("%I64d", count); return 0; } But the same problem remain: WA#17 crasn(access violation) You didn't changed int cmp(const void *a, const void *b) { __int64 *pa = (__int64 *)a, *pb = (__int64 *)b; return *(__int64 *)pa - *(__int64 *)pb; } change to __int64 cmp(const void *a, const void *b) { __int64 *pa = (__int64 *)a, *pb = (__int64 *)b; return *(__int64 *)pa - *(__int64 *)pb; } #include <stdio.h> #include <stdlib.h> __int64 cmp(const void *a, const void *b) { __int64 *pa = (__int64 *)a, *pb = (__int64 *)b; return *(__int64 *)pa - *(__int64 *)pb; } int main() { __int64 arr[100], min=1000000000000000000, N=3, count=0, i; for(i = 0; i<N; i++) scanf("%I64d", &arr[i]); while(min) { qsort (arr, N, sizeof(__int64), 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("%I64d", count); return 0; } No, it doesn't help. Oh,you have too small array size. Use STL vector do it greater. I don't know C++. I tried to change size of array, but I have time limit exceed. Edited by author 08.08.2012 18:32 # include <iostream> # include <vector> # include <algorithm> using namespace std; long long q; int main() { vector <long long> v(3),v1;
for(int i=0; i<3; i++) cin>>v[i];
while(1) { v1.clear();
q++;
for(int i=0; i<(int)v.size(); i++) { for(int h=0; h<(int)v.size(); h++) { if(i!=h) { int a=v[i]-v[h];
if(a>=0) v1.push_back(a); } } }
sort(v1.begin(),v1.end());
if(v1[0]==0) {break;}
v.push_back(v1[0]); } cout<<q; } What is test 2? Try this 10 5 3 Answer: 4. My program is right for this test. 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 Edited by author 21.10.2012 03:11 Edited by author 21.10.2012 03:11 I corrected my mistake!!! sorry for all ;) got AC! I had Crash 1!!! and solve in Java and found my mistake!!! 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? Use long long instead of int For example, I got WA19 at first time. I changed real to extended and integer to longint and got AC. пробовал разные способы вычисления, упираюсь в 33 тест. Какие есть мысли? try more ways reading longs |
|