Results 1 to 25 of 30
Hybrid View
-
20th May 2008 20:55 #1
...
[1..N].
i - Aj, - . , Ai .
- b*N , b*N*N
:
1, 9, 8, 5, 9, 3, 4, 5, 2
9, 0, 9, 9, 0, 4, 5, 0, 0
b , .. 100, , 999999 b*N (99999900) .
.
9-, , 8- ... , , .
''? * *
- !
...
-
20th May 2008 22:33 #2
, : ? , . seen[] , A[] . A - - seen[], - 0. - 10*N, .. b = 10
, . .
"640K ught to be enough for anybody" - Bill Gates, 1981
::Machine specs::Fract::AGG::::Baileys::blog::YouTube channel
-
23rd May 2008 23:51 #3
-
24th May 2008 14:01 #4, . .
"640K ught to be enough for anybody" - Bill Gates, 1981
::Machine specs::Fract::AGG::::Baileys::blog::YouTube channel
-
20th May 2008 22:34 #5
-
20th May 2008 23:03 #6
...
:
:
8, 3, 5, 1, 1, 2, 1, 4, 5, 3, 8
1) 2- , j, j-1 1 (- - 0) 2-, 0 > 2; 2-, -1, .. -2;
:
8, 3, 5, 2, 2, -2, 1, 4, 5, 3, 8
2) 3- , j, j-1 1 -2, 0, 3-, 0, 2 > 3; 3-, -1, .. -3;
:
8, -3, 5, 2, 2, -2, 1, 4, 5, -3, 8
3) 4-, :
8, -3, 5, 2, 2, 4, 4, -4, 5, -3, 8
4) 5-, :
8, 5, -5, 2, 2, 4, 4, 5, -5, -3, 8
...
:
-8, 5, 8, 2, 2, 4, 4, 5, 8, 8, -8
0. :
0, 5, 8, 2, 2, 4, 4, 5, 8, 8, 0
b*N , b- N ; b*N+N =(b+1)*N ;
Edit:
, .. (b+1)*(N + 1) ;
Edit 2:
, , (b+1)*N.
@anrieff, .Last edited by Kaspirtov; 20th May 2008 at 23:20.
" , , , , ."
-
20th May 2008 23:32 #7Registered User
Join Date: Dec:2007
Location:
Posts: 655
-
20th May 2008 23:32 #8
-
20th May 2008 23:38 #9
Kaspirtov, `b'.
"1 2 3 1000000000" ., . .
"640K ught to be enough for anybody" - Bill Gates, 1981
::Machine specs::Fract::AGG::::Baileys::blog::YouTube channel
-
20th May 2008 23:44 #10
-
20th May 2008 23:48 #11
-
20th May 2008 23:52 #12
-
20th May 2008 23:57 #13Registered User
Join Date: Dec:2007
Location:
Posts: 655
,
- , b , . b "" N, , , , ?
, - , . .
-
21st May 2008 00:14 #14
-
21st May 2008 00:21 #15Registered User
Join Date: Dec:2007
Location:
Posts: 655
-
21st May 2008 00:26 #16
-
21st May 2008 00:39 #17Registered User
Join Date: Dec:2007
Location:
Posts: 655
-
21st May 2008 00:59 #18
-
21st May 2008 01:12 #19
( C):
1. A[1..N], : B[1..N] C[1..N], "max".
2. B[N] = 0; max = A[N];
3. for (i = N-1; i >= 1; --i)
3.1. if (A[i] >= max) { B[i] = 0; max = A[i]; continue; }
3.2. for (j = i+1; B[j] != 0; j = C[j])
3.2.1. if (A[j] > A[i]) { B[i] = A[j]; C[i] = j; break; }
3.3. if (B[j] == 0) { B[i] = 0; }
4. A = B
( o worst-case ), . i amortized ( log(N)), O(N), O(N*log(N)). , - .Last edited by Pesho; 21st May 2008 at 01:18.
-
21st May 2008 04:23 #20Registered User
Join Date: Dec:2007
Location:
Posts: 655
: ( - ) - , ( , C[k] , A[k], 0, A[k] >= max).
- . C ?
Kaspirtov, ,
: , . Pesho , (- )
.
Last edited by AK-85; 21st May 2008 at 04:44.
-
21st May 2008 05:30 #21
, ( ...). C, ( , , 0).
... . , C++ ( ):
Code:#include <iostream> #include <vector> std::vector<int> transform(const std::vector<int>& A) { int N = A.size() - 1; int max = A[N]; std::vector<int> B(N + 1), C(N + 1); B[N] = 0; for (int i = N-1; i >= 1; --i) { if (A[i] >= max) { B[i] = 0; max = A[i]; continue; } int j = i+1; while (1) { if (A[j] > A[i]) { B[i] = A[j]; C[i] = j; break; } if (B[j] == 0) { B[i] = 0; break; } j = C[j]; } } return B; } void print(const std::vector<int>& A) { for (unsigned i = 1; i < A.size(); ++i) std::cout << A[i] << ' '; std::cout << std::endl; } int main() { std::vector<int> A(10); A[1] = 1; A[2] = 9; A[3] = 8; A[4] = 5; A[5] = 9; A[6] = 3; A[7] = 4; A[8] = 5; A[9] = 2; print(A); print(transform(A)); }
, - O(N). , (while(1)...) N. "max" , O(N).Last edited by Pesho; 21st May 2008 at 21:44.
-
21st May 2008 21:33 #22
Pesho, !
. 
, ++ , .
- Kaspirtov.
, !
P.S. , , - .
''? * *
- !
...
-
21st May 2008 00:42 #23




Reply With Quote


Lenovo ThinkPad 15 IdeaPad 15
5th May 2023, 22:16 in