Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Hint | GeekCmore | 1082. Иванушка-дурачок | 10 дек 2022 19:20 | 1 | Hint GeekCmore 10 дек 2022 19:20 Just think of an increasing sequence. The program caculates n+1 times for an increasing sequence with n elements. And then divide it into two subsequences. One is the leftmost element, and anthoer is the left elements. It ends at the length of sequence is 2. Thus, the sum is (n+1) + n + (n-1) + ... + 3 = (n+4)(n-1)/2 = (n*n + 3*n - 4)/2. So output 1 to n is ok. | The solution is just printing 1,2,...,n, but how did you think it out? | Maigo Akisame | 1082. Иванушка-дурачок | 13 апр 2022 12:29 | 7 | Because the procedure P is sorting . The tsar's program is quicksort algorithm it sorts input array and counts in how many swaps it was done (variable c)(not exact value but represents it)... Just try to think about variable c and you will realize that. So the solution is to print not only 1,2,...,n but ANY SORTED ARRAY OF LENGTH N I resolve it by recursively fill the whole array. And I think out sorted array because I think it is easier to make the array sorted(since then the quicksort become bubble sort). | It is simple, isn't it? | Li Yi | 1082. Иванушка-дурачок | 2 апр 2016 01:00 | 9 | Write numbers from 1 to n, that's enough! You should be accepted. > Write numbers from 1 to n, that's enough! You should be > accepted. Write numbers from 1 to n, that's enough! You should MUST be accepted. THANK YOU VERY MUCH! WHY? Kingliest 28 фев 2003 20:03 > Write numbers from 1 to n, that's enough! You should be > accepted. Right. But plainly saying that it works (and it does) spoils the fun. And fun is to figure out WHY it works. I think we can't know why this work. We must check this solution on all tests [1, 1 2, 1 2 3, ..., 1 2 ... 1000]. If solution works on all tests it means that solution is right. you say write num from 1 to n, but the example.... it's very simple, I think Quick_sort procedure and it are very much the same, Yeah , better to guess yourself what is variable c. Please don't put in forum your very simple solving | Как сделать на 0,001? | IT | 1082. Иванушка-дурачок | 2 апр 2016 00:55 | 2 | Just send one more time) (If your time 0.015) | analysis | OvO | 1082. Иванушка-дурачок | 24 мар 2014 02:02 | 4 | let sequence be 1,2,3,...,n I. in each P( l, r ) there will be 1 + r-l+1 times ++ c. II. in each Q( l, n ) = Q( l, l ) there will be 0 time ++ c. III. in each Q( n, r ) = Q( n+1, r ) + P( n, r ). IV. Let F( n ) is the total times of ++ c, so we get F( n ) = F( n-1 ) + n + 1 and F( 1 ) = Q( r, r ) = 0; the sum of ++ c is 3 + 4 +... + n+1 = n*(n-1)/2 + 2*(n-1) = (n-1)*(n+4)/2 = (n*n+3*n-4)/2 Edited by author 24.05.2011 11:12 Edited by author 24.05.2011 11:13 What the fucking analysis do you do? Simply solve the quadratic equation in the IF condition "if(c==(N*N+3*N-4)/2)", and you will see that with any nonnegative value of "c" the program will print out "Beutiful Vasilisa". The variable "c" will be nonnegative in any case, because of the initial value = 0, and increment operator. I guess u read "if(c=(N*N+3*N-4)/2)" instead of "if(c==(N*N+3*N-4)/2)" Я вывел формулу по другому: n*(n+1)/2 - 1 + (n - 1) = n*(n+1)/2 + (n - 2) = (n*n + 3*n - 4) / 2 n*(n+1)/2 - кол-во проверок на возрастание -1 - вычитаем один случай, когда остался один элемент (n - 1) - кол-во проверок на убывание | Proof of solution | Ilian | 1082. Иванушка-дурачок | 21 авг 2013 22:07 | 1 | Everybody who knows quick sort will recognize that the tsar's program is quick sort of N numbers. Let we have a sorted array with n numbers. Let l-r+1=k. Then function P() will increase the value of c by k+1 because it will visit all x elements to distribute them into part smaller than or equal to x and part greater or equal to x. That increases c by k. But the i and j iterators must be equal so there is also one additional increase of c. Because we have a sorted array function P() will partition him into part consisting of 1 element and part consisting of l-r elements. The part consisting of 1 element will be ignored and there won't be any increase of c. In the part with l-r elements it will do the same - partitioned it into 1 and l-r-1. So let begin with l-r+1=N. Then the function Q() will go to l-r+1=N-1 and so on to l-r+1=2. For those calls of function Q() c will be increased with: N+1 + N + N-1 + ... + 5 + 4 + 3 = (N+1)*(N+1+1)/2 - 1 - 2 = N*N + 3*N + 2/2 - 3 = =N*N + 3*N + 2 - 3*2/2 = N*N + 3*N - 4 / 2. So if we give a sorted array to the tsar's program it will print what we want. What is more, we prove that for sorted array quick sort is very bad algorithm with such bad complexity. Note: If the median element was chosen in a different way the solution won't be so easy. But it can be done if we try all permutations of array with elements from [1;n] and check for c. Edited by author 21.08.2013 22:19 | But, Why it work? | Denis | 1082. Иванушка-дурачок | 11 авг 2013 20:02 | 7 | The 1st time P is called, c is increased by N+1 The 2nd time P is called, c is increased by N The 3rd time P is called, c is increased by N-1 ... The (N-1)th time P is called, c is increased by 3 So, the final value of C is (sum of A.P.) ((N+1)+3)*(N-1) div 2 =(N*N+3*N-4) div 2 But I really don't know how it's thought out. Thanks for your comments. Here is what I thought: ** I see it is quicksort ** I know that when the input is sorted, quicksort become a bubblesort(only one side is split each time), that make it easier to think about ** then, use recursive function which fill the entire array, and the result is just a sorted array. If start from 1, it will be 1 2 3 4 .......N But you provide a math provef of how they match:) What a wonderful explanation! Edited by author 06.01.2008 17:36 The 1st time P is called, c is increased by N+1 The 2nd time P is called, c is increased by N The 3rd time P is called, c is increased by N-1 ... The (N-1)th time P is called, c is increased by 3 I don't get it how You came to this analysis? Did You write a program to get how much is c increased the 1st the 2nd and the 3rd time? Why is P called N-1th times? Can somebody please explain me how QS works - I know it divides the array in left:medium:right But I guess medium is just always only one element. Am I correct? Please enlighten me. Thanks ... Edited by author 03.03.2011 16:54 Edited by author 03.03.2011 16:54 Hi, The iteration stops always after 3 comparisons for the pivot element in quicksort. Hence last element of AP is 3. First time iteration is always (N+1). Now number of elments of AP is N-1. Thus the formula proves to be true. Regards Anupam In an ideal case first you should have paid attention to N*N in c's expression. then u realize that answer should be some of the wort-case inputs for QS (one of which being already sorted array). then u copy the procedure and check ur hyphothesis for all N = 1 to 1000. no need to think it over really. | Little typo | Ivan Nikulin | 1082. Иванушка-дурачок | 15 дек 2012 19:53 | 1 | There is one typo in both codes: Beautiful, not Beutiful. | haha ! its really easy ! | Farhad Ghasemi | 1082. Иванушка-дурачок | 11 фев 2012 18:37 | 4 | its quick sort function ! just write a program to print from 1 to n !!!! =)) [code deleted] Edited by moderator 04.02.2020 09:19 o`zingni programmangni jo`nat bekkii. | hmm | TiMiD | 1082. Иванушка-дурачок | 27 июн 2011 14:44 | 2 | hmm TiMiD 25 июн 2011 14:31 Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below. http://www.PaisaLive.com/register.asp?3556638-4847933 After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator. Miss Juliet Admin paisalive.com | What do you think about random? | BlackShark | 1082. Иванушка-дурачок | 10 сен 2010 00:59 | 2 | Tell me please, why my C++ code has WRONG ANSWER 1 #include <iostream> #include <set> using namespace std; int main() { int N; cin>>N; srand((int)__TIME__); set <int> arr; while (arr.size()!=N) { int temp = rand()%(N+1); if (arr.find(temp)==arr.end() && temp!=0) { cout<<temp<<" "; arr.insert(temp); } } return 0; } it is not standart solution, but it is right | very easy!! | zsyzhbc_china | 1082. Иванушка-дурачок | 22 мар 2009 18:50 | 1 | | hoho, P() for Partitioned(),Q() for QuickSort()? | Jeffrey.Xie | 1082. Иванушка-дурачок | 6 фев 2007 06:54 | 1 | | Program on C can't be compiled | Veniamin | 1082. Иванушка-дурачок | 18 фев 2005 19:25 | 2 | I looked at program version on C, and found interesting strings: int main(void) { c=0; for(long i=0; i<N; ++i) scanf("%ld", &A[i]); .... This code can' be compile on C. Because variable “i” can be declared in operator “for”(according to C standard)!!!!Check it! For example, Borland C++ 3.1 cannot compile this, but it is not a bug. Edited by author 18.02.2005 19:25 | puzzled? | qin | 1082. Иванушка-дурачок | 12 янв 2003 17:44 | 1 | when do you have a online contest? |
|
|