Topic Text   Topic Comments (0)   Topic Properties   Topic Information huq2002@gma...
Topic title: sfsafasdf Monday May 30, 2011 06:30:30

Download topic text | View in variable-width font | Tab width set to 4 (change to 8)

Files in topic:  
[Jump to] program.c   {+1583,-0}

[Add General Comment] to topic.

File program.c (Revision 1.0) [Add File Comment] [Top]
 
1 #if 1
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <memory.h>
5
6 //#define TEST/* UNDEFINE IT IN RELEASE VER */
7
8 unsigned int N = 0, K = 0;
9 unsigned int *SEQUENCE = NULL;
10 char *SEQ_DIG_FOUND = NULL;
11
12 #ifdef TEST
13 #include <time.h>
14 unsigned int find_func_times = 0;
15 #endif
16
17 #define ABS_IN_K(a,b) ((a>K?(a-K):0) <= b && a+K >= b)
18
19 unsigned int find(unsigned int pre, unsigned int *input, unsigned int *output_pos)
20 {
21 #ifdef TEST
22 find_func_times++;
23 #endif
24
25 while(input <= SEQUENCE+N-1)
26 {
27 if (ABS_IN_K(pre,*input))
28 {/* a right digit is found */
29 unsigned int len = 1;
30 unsigned int pos = input-SEQUENCE;
31 *output_pos = pos;
32 *(SEQ_DIG_FOUND+pos) = '\1'; /* mark it found before */
33
34 while (ABS_IN_K(*input,*(input+1)) && (N-pos)>1)
35 {
36 pos = input+1-SEQUENCE;
37 *(output_pos+len) = pos;
38 *(SEQ_DIG_FOUND+pos) = '\1'; /* mark it found before */
39
40 input++;
41 len++;
42 }
43
44 if ((N-pos)>1)
45 {
46 /* result of taking the digit into account */
47 unsigned int len = 1+find(*input, input+1, output_pos+1);
48 unsigned int len_new;
49 unsigned int *output_new_pos = (unsigned int *)malloc(sizeof(unsigned int)*(N-pos));
50 memset(output_new_pos, 0, sizeof(unsigned int)*(N-pos));
51
52 /* result of ignoring the digit*/
53 len_new = find(pre, input+1, output_new_pos);
54
55 /* compare the output with the right digit and without */
56 if (len <= len_new)
57 {
58 memcpy(output_pos, output_new_pos, sizeof(unsigned int)*len_new);
59 len = len_new;
60 }
61
62 free(output_new_pos);
63 return len;
64 }
65 else
66 return len;
67 }
68
69 input++;
70 };
71
72 return 0;
73 }
74
75 unsigned int i = 0;
76 unsigned int *final_output_pos = NULL;
77 unsigned int *output_pos = NULL;
78 unsigned int output_len = 0;
79 unsigned int final_output_len = 0;
80 unsigned int *temp = NULL;
81
82 //#define N 6
83 //#define K 3
84 //unsigned int SEQUENCE[N] = {2, 9, 7, 2, 5, 8}; /*9 7 5 8*/ 7
85 //unsigned int SEQUENCE[N] = {3, 3, 3, 3, 3, 3}; /*3 3 3 3 3 3*/ 5
86 //unsigned int SEQUENCE[N] = {9, 2, 5, 1, 1, 1}; /*2 1 1 1*/ 8
87 //unsigned int SEQUENCE[N] = {2, 5, 8, 1, 1, 1}; /*2 1 1 1*/ 4
88 //unsigned int SEQUENCE[N] = {1, 1, 1, 8, 5, 2}; /*1 1 1 2*/
89 //#define N 3
90 //#define K 3
91 //unsigned int SEQUENCE[N] = {2, 5, 1}; /*2 5*/ 2
92 //#define N 10
93 //#define K 3
94 //unsigned int SEQUENCE[N] = {2, 5, 1, 7, 90, 100, 3, 6, 8, 2}; /*2 5 7 6 8*/ 20
95
96 int main(int argc, char *argv[])
97 {
98 #if !defined(TEST)
99 // clock_t start,finish;
100 // start = clock();
101 scanf("%d %d", &N, &K);
102
103 SEQUENCE = (unsigned int *)malloc(sizeof(unsigned int)*N);
104 memset(SEQUENCE, 0, sizeof(unsigned int)*N);
105 #else
106 clock_t start,finish;
107 start = clock();
108 N=5000;K=1; //20:524287(0.374) 21:1048575(0.765) 22:2097151(1.462) 23:4194303(3.064) 24:8388607(5.999) 25:16777215(16.201)
109 //20:19 100:99 1000:999 10000:
110 SEQUENCE = (unsigned int *)malloc(sizeof(unsigned int)*N);
111 for (i; i<N; i++)
112 {
113 *(SEQUENCE+N-(i+1)) = 6;//2*i+1; //4999,5000
114 }
115 // *(SEQUENCE+10) = 8;
116 printf("starting...\n");
117 #endif
118
119 SEQ_DIG_FOUND = (char *)malloc(sizeof(char)*N);
120 memset(SEQ_DIG_FOUND, 0, sizeof(char)*N);
121
122 final_output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
123 memset(final_output_pos, 0, sizeof(unsigned int)*N);
124
125 output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
126
127 #if !defined(TEST)
128 for (; i<N; i++)
129 {
130 scanf("%d", SEQUENCE+N-(i+1));
131 }
132 #endif
133
134 for (i=0; final_output_len <= N-i && *(SEQ_DIG_FOUND+i) != '\1'; i++)
135 {
136 memset(output_pos, 0, sizeof(unsigned int)*N);
137
138 *output_pos = i;
139
140 output_len = 1+find(*(SEQUENCE+i), SEQUENCE+i+1, output_pos+1);
141
142 /* compare the found one for i with current longest one */
143 if (output_len >= final_output_len)
144 {
145 temp = final_output_pos;
146 final_output_pos = output_pos;
147 output_pos = temp;
148 final_output_len = output_len;
149 }
150 }
151
152 for (i=final_output_len;i>0;i--)
153 {
154 printf("%d ", *(SEQUENCE+*(final_output_pos+i-1)));
155 }
156
157 #ifdef TEST
158 finish = clock();
159 printf("\n%d %f", find_func_times, (double)(finish-start)/CLOCKS_PER_SEC);
160 #endif
161
162 return 0; /* return here, free will use cpu time */
163
164 free(SEQUENCE);
165 free(SEQ_DIG_FOUND);
166 free(final_output_pos);
167 free(output_pos);
168
169 return 0;
170 }
171 #elif 0
172 #include <stdio.h>
173 #include <stdlib.h>
174 #include <memory.h>
175
176 #define TEST/* UNDEFINE IT IN RELEASE VER */
177
178 unsigned int N = 0, K = 0;
179 unsigned int *SEQUENCE = NULL;
180
181 char *SEQ_DIG_FOUND = NULL;
182
183 #ifdef TEST
184 #include <time.h>
185 unsigned int find_func_times = 0;
186 #endif
187
188
189 unsigned int find(unsigned int pre, unsigned int *input, unsigned int *output_pos)
190 {
191 unsigned int pos = input-SEQUENCE;
192
193 #ifdef TEST
194 find_func_times++;
195 #endif
196
197 if ((pre>K?(pre-K):0) <= *input && pre+K >= *input)
198 {/* a right digit is found */
199 *output_pos = pos;
200 *(SEQ_DIG_FOUND+pos) = '\1'; /* mark it found before */
201
202 if ((N-pos)>1)
203 {
204 if (!((*(input+1)>K?(*(input+1)-K):0) <= *input && *(input+1)+K >= *input))
205 {
206 /* result of taking the digit into account */
207 unsigned int len = 1+find(*input, input+1, output_pos+1);
208 unsigned int len_new;
209 unsigned int *output_new_pos = (unsigned int *)malloc(sizeof(unsigned int)*(N-pos));
210 memset(output_new_pos, 0, sizeof(unsigned int)*(N-pos));
211
212 /* result of ignoring the digit*/
213 len_new = find(pre, input+1, output_new_pos);
214
215 /* compare the output with the right digit and without */
216 if (len <= len_new)
217 {
218 memcpy(output_pos, output_new_pos, sizeof(unsigned int)*len_new);
219 len = len_new;
220 }
221
222 free(output_new_pos);
223 return len;
224 }
225 else
226 return 1+find(*input, input+1, output_pos+1);
227 }
228 else
229 return 1;
230 }
231 else
232 {/* not found */
233 if ((N-pos)>1)
234 return find(pre, input+1, output_pos);
235 else
236 return 0;
237 }
238 }
239
240 unsigned int i = 0;
241 unsigned int *final_output_pos = NULL;
242 unsigned int *output_pos = NULL;
243 unsigned int output_len = 0;
244 unsigned int final_output_len = 0;
245 unsigned int *temp = NULL;
246
247
248 //#if 0
249 //#define N 6
250 //#define K 3
251 //
252 //unsigned int SEQUENCE[N] = {2, 9, 7, 2, 5, 8}; /*9 7 5 8*/ 19
253 //unsigned int SEQUENCE[N] = {3, 3, 3, 3, 3, 3}; /*3 3 3 3 3 3*/ 6:31 7:63 8:127 9:255 10:511 20:524287(0.374)
254 // one not in 6:17 7:35 8:71 9:143 10:287 20:262655
255 // quan wu guan 6:16 7:22 8:29 9:37 10:46 20:191
256 //unsigned int SEQUENCE[N] = {9, 2, 5, 1, 1, 1}; /*2 1 1 1*/ 19
257 //unsigned int SEQUENCE[N] = {2, 5, 6, 1, 1, 1}; /*2 1 1 1*/ 15
258 //#elif 0
259 //#define N 3
260 //#define K 3
261 //
262 //unsigned int SEQUENCE[N] = {2, 5, 1}; /*2 5*/ 3
263 //#elif 0
264 //#define N 10
265 //#define K 3
266 //
267 //unsigned int SEQUENCE[N] = {2, 5, 1, 7, 90, 100, 3, 6, 8, 2}; /*2 5 7 6 8*/ 55
268 //#endif
269
270 int main(int argc, char *argv[])
271 {
272 #if !defined(TEST)
273 scanf("%d %d", &N, &K);
274
275 SEQUENCE = (unsigned int *)malloc(sizeof(unsigned int)*N);
276 memset(SEQUENCE, 0, sizeof(unsigned int)*N);
277 #else
278 clock_t start,finish;
279 start = clock();
280 N=5000;K=1; //20:524287(0.374) 21:1048575(0.765) 22:2097151(1.462) 23:4194303(3.064) 24:8388607(5.999) 25:16777215(16.201)
281 //20:19 100:99 1000:999 10000:
282 SEQUENCE = (unsigned int *)malloc(sizeof(unsigned int)*N);
283 for (i; i<N; i++)
284 {
285 *(SEQUENCE+N-(i+1)) = /*6;*/2*i+1; //4999,12497501
286 }
287 // *(SEQUENCE+10) = 8;
288 printf("starting...\n");
289 #endif
290
291 SEQ_DIG_FOUND = (char *)malloc(sizeof(char)*N);
292 memset(SEQ_DIG_FOUND, 0, sizeof(char)*N);
293
294 final_output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
295 memset(final_output_pos, 0, sizeof(unsigned int)*N);
296
297 output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
298
299 #if !defined(TEST)
300 for (; i<N; i++)
301 {
302 scanf("%d", SEQUENCE+N-(i+1));
303 }
304 #endif
305
306 for (i=0; final_output_len <= N-i && *(SEQ_DIG_FOUND+i) != '\1'; i++)
307 {
308 memset(output_pos, 0, sizeof(unsigned int)*N);
309
310 *output_pos = i;
311
312 output_len = 1+find(*(SEQUENCE+i), SEQUENCE+i+1, output_pos+1);
313
314 /* compare the found one for i with current longest one */
315 if (output_len >= final_output_len)
316 {
317 temp = final_output_pos;
318 final_output_pos = output_pos;
319 output_pos = temp;
320 final_output_len = output_len;
321 }
322 }
323
324 for (i=final_output_len;i>0;i--)
325 {
326 printf("%d ", *(SEQUENCE+*(final_output_pos+i-1)));
327 }
328
329 #ifdef TEST
330 finish = clock();
331 printf("\n%d %f", find_func_times, (double)(finish-start)/CLOCKS_PER_SEC);
332 #endif
333
334 return 0; /* return here, free will use cpu time */
335
336 free(SEQUENCE);
337 free(SEQ_DIG_FOUND);
338 free(final_output_pos);
339 free(output_pos);
340
341 return 0;
342 }
343 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
344 #elif 0
345 #include <stdio.h>
346 #include <memory.h>
347
348
349 /* define n and k */
350 #if 0
351 #define N 6
352 #define K 3
353
354 unsigned int SEQUENCE[N] = {2, 9, 7, 2, 5, 8}; /*9 7 5 8*/
355 //unsigned int SEQUENCE[N] = {9, 2, 5, 1, 1, 1}; /*2 1 1 1*/
356 //unsigned int SEQUENCE[N] = {9, 2, 5, 1, 4, 1}; /*2 5 4 1*/
357 #elif 0
358 #define N 3
359 #define K 3
360
361 unsigned int SEQUENCE[N] = {2, 5, 1}; /*2 5*/
362 #elif 0
363 #define N 10
364 #define K 3
365
366 unsigned int SEQUENCE[N] = {2, 5, 1, 7, 90, 100, 3, 6, 8, 2}; /*2 5 7 6 8*/
367 #endif
368
369 unsigned int get_output_len(unsigned int *output)
370 {
371 unsigned int j;
372
373 for (j=0;j<N;j++)
374 {
375 if (*(output+j) == 0)
376 break;
377 }
378
379 return j;
380 }
381
382 /* return out2's length if out1 shall be replaced with out2 */
383 unsigned int compareout(unsigned int *out1, unsigned int *out1_pos, unsigned int *out2, unsigned int *out2_pos)
384 {
385 unsigned int out1_len = get_output_len(out1);
386 unsigned int out2_len = get_output_len(out2);
387
388 if (out2_len>out1_len)
389 {
390 return out2_len;
391 }
392 else if (out2_len==out1_len)
393 {
394 unsigned int j;
395
396 for(j=out1_len;j>0;j--)
397 {
398 if(*(out2_pos+j-1) < *(out1_pos+j-1))
399 {
400 return out2_len;
401 }
402 }
403 }
404
405 return 0;
406 }
407
408 void printout(unsigned int *out)
409 {
410 unsigned int i;
411
412 for (i=0;(*(out+i)!=0 && i<N);i++)
413 {
414 printf("%d ", *(out+i));
415 }
416
417 printf("\n");
418 }
419
420 void find(unsigned int pre, unsigned int size, unsigned int k, unsigned int *input, unsigned int pos,
421 unsigned int *output, unsigned int *output_pos)
422 {
423 if (size == 0)
424 return;
425
426 if ((pre>k?(pre-k):0) <= *input && pre + k >= *input)
427 {/* a right digit is found */
428 unsigned int output_new[N];
429 unsigned int output_new_pos[N];
430 unsigned int output_new_len;
431
432 memset(output_new, 0, sizeof(output_new));
433 memset(output_new_pos, 0, sizeof(output_new_pos));
434
435 /* result of taking the digit into account */
436 *output = *input;
437 *output_pos = pos;
438 find(*output, size-1, k, input+1, pos+1, output+1, output_pos+1);
439
440 /* result of ignoring the digit*/
441 find(pre, size-1, k, input+1, pos+1, output_new, output_new_pos);
442
443 /* compare the output with the right digit and without */
444 output_new_len = compareout(output, output_pos, output_new, output_new_pos);
445 if (output_new_len > 0)
446 {
447 memcpy(output, output_new, sizeof(unsigned int)*output_new_len);
448 memcpy(output_pos, output_new_pos, sizeof(unsigned int)*output_new_len);
449 }
450 }
451 else
452 {/* not found */
453 find(pre, size-1, k, input+1, pos+1, output, output_pos);
454 }
455 }
456
457 int main(int argc, char *argv[])
458 {
459 unsigned int i;
460 unsigned int final_output[N];
461 unsigned int final_output_pos[N];
462 unsigned int *input;
463
464 memset(final_output, 0, sizeof(final_output));
465 memset(final_output_pos, 0, sizeof(final_output_pos));
466
467 for (i=0; i < N; i++)
468 {
469 unsigned int output_len = 0;
470 unsigned int output[N];
471 unsigned int output_pos[N];
472
473 memset(output, 0, sizeof(output));
474 memset(output_pos, 0, sizeof(output_pos));
475 input = SEQUENCE + i;
476 *output = *input;
477 *output_pos = i;
478
479 find(*output, N-(i+1), K, input+1, i+1, output+1, output_pos+1);
480
481 /* compare the found one for i with current longest one */
482 output_len = compareout(final_output, final_output_pos, output, output_pos);
483 if (output_len > 0)
484 {
485 memcpy(final_output, output, sizeof(unsigned int)*output_len);
486 memcpy(final_output_pos, output_pos, sizeof(unsigned int)*output_len);
487 }
488 }
489
490 printout(final_output);
491
492 return 0;
493 }
494 #elif 0
495 #include <stdio.h>
496 #include <stdlib.h>
497 #include <memory.h>
498
499 unsigned int N, K;
500 unsigned int *SEQUENCE;
501
502 unsigned int get_output_len(unsigned int *output)
503 {
504 unsigned int j;
505
506 for (j=0;j<N;j++)
507 {
508 if (*(output+j) == 0)
509 break;
510 }
511
512 return j;
513 }
514
515 /* return out2's length if out1 shall be replaced with out2 */
516 unsigned int compareout(unsigned int *out1, unsigned int *out1_pos, unsigned int *out2, unsigned int *out2_pos)
517 {
518 unsigned int out1_len = get_output_len(out1);
519 unsigned int out2_len = get_output_len(out2);
520
521 if (out2_len>out1_len)
522 {
523 return out2_len;
524 }
525 else if (out2_len==out1_len)
526 {
527 unsigned int j;
528
529 for(j=out1_len;j>0;j--)
530 {
531 if(*(out2_pos+j-1) < *(out1_pos+j-1))
532 {
533 return out2_len;
534 }
535 }
536 }
537
538 return 0;
539 }
540
541 void printout(unsigned int *out)
542 {
543 unsigned int i;
544
545 for (i=0;(*(out+i)!=0 && i<N);i++)
546 {
547 printf("%d ", *(out+i));
548 }
549
550 printf("\n");
551 }
552
553 void find(unsigned int pre, unsigned int size, unsigned int k, unsigned int *input, unsigned int pos,
554 unsigned int *output, unsigned int *output_pos)
555 {
556 if (size == 0)
557 return;
558
559 if ((pre>k?(pre-k):0) <= *input && pre + k >= *input)
560 {/* a right digit is found */
561 unsigned int *output_new;
562 unsigned int *output_new_pos;
563 unsigned int output_new_len;
564
565 output_new = (unsigned int *)malloc(sizeof(unsigned int)*N);
566 output_new_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
567 memset(output_new, 0, sizeof(unsigned int)*N);
568 memset(output_new_pos, 0, sizeof(unsigned int)*N);
569
570 /* result of taking the digit into account */
571 *output = *input;
572 *output_pos = pos;
573 find(*output, size-1, k, input+1, pos+1, output+1, output_pos+1);
574
575 /* result of ignoring the digit*/
576 find(pre, size-1, k, input+1, pos+1, output_new, output_new_pos);
577
578 /* compare the output with the right digit and without */
579 output_new_len = compareout(output, output_pos, output_new, output_new_pos);
580 if (output_new_len > 0)
581 {
582 memcpy(output, output_new, sizeof(unsigned int)*output_new_len);
583 memcpy(output_pos, output_new_pos, sizeof(unsigned int)*output_new_len);
584 }
585
586 free(output_new);
587 free(output_new_pos);
588 }
589 else
590 {/* not found */
591 find(pre, size-1, k, input+1, pos+1, output, output_pos);
592 }
593 }
594
595 int main(int argc, char *argv[])
596 {
597 unsigned int i;
598 unsigned int *final_output;
599 unsigned int *final_output_pos;
600 unsigned int *input;
601 unsigned int *output;
602 unsigned int *output_pos;
603
604 scanf("%d %d", &N, &K);
605
606 if(!(N>=1 && N<=100000))
607 return -1;
608
609 if(!(K>=1 && K<=100000))
610 return -2;
611
612 SEQUENCE = (unsigned int *)malloc(sizeof(unsigned int)*N);
613 memset(SEQUENCE, 0, sizeof(unsigned int)*N);
614
615 for (i=0; i<N; i++)
616 {
617 scanf("%d", SEQUENCE+i);
618 if (!(*(SEQUENCE+i)<=1000000000 && *(SEQUENCE+i)>0))
619 return -3;
620 }
621
622 final_output = (unsigned int *)malloc(sizeof(unsigned int)*N);
623 final_output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
624 memset(final_output, 0, sizeof(unsigned int)*N);
625 memset(final_output_pos, 0, sizeof(unsigned int)*N);
626
627 output = (unsigned int *)malloc(sizeof(unsigned int)*N);
628 output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
629
630 for (i=0; i < N; i++)
631 {
632 unsigned int output_len = 0;
633
634 memset(output, 0, sizeof(unsigned int)*N);
635 memset(output_pos, 0, sizeof(unsigned int)*N);
636
637 input = SEQUENCE + i;
638 *output = *input;
639 *output_pos = i;
640
641 find(*output, N-(i+1), K, input+1, i+1, output+1, output_pos+1);
642
643 /* compare the found one for i with current longest one */
644 output_len = compareout(final_output, final_output_pos, output, output_pos);
645 if (output_len > 0)
646 {
647 memcpy(final_output, output, sizeof(unsigned int)*output_len);
648 memcpy(final_output_pos, output_pos, sizeof(unsigned int)*output_len);
649 }
650 }
651
652 printout(final_output);
653
654 free(final_output);
655 free(final_output_pos);
656 free(output);
657 free(output_pos);
658
659 return 0;
660 }
661 #elif 0
662 #include <stdio.h>
663 #include <stdlib.h>
664 #include <memory.h>
665
666 unsigned int N = 0, K = 0;
667 unsigned int *SEQUENCE = NULL;
668
669 /* return out2's length if out1 shall be replaced with out2, otherwise return 0 */
670 unsigned int compareout(unsigned int *out1_pos, unsigned int *out2_pos)
671 {
672 unsigned int j = 0;
673 unsigned int len = 0;
674
675 for (;j<N;j++)
676 {
677 if (*(out1_pos+j) == 0)
678 {
679 if (*(out2_pos+j) != 0)
680 break;
681 else
682 {
683 /* unsigned int len = j;
684
685 for(;j>0;j--)
686 {
687 if(*(out2_pos+j-1) < *(out1_pos+j-1))
688 {
689 return len;
690 }
691 else if(*(out2_pos+j-1) > *(out1_pos+j-1))
692 {
693 return 0;
694 }
695 }
696
697 return 0; */
698 return len;
699 }
700 }
701 else
702 {
703 if(*(out2_pos+j)==0)
704 return 0;
705 else
706 {
707 if(*(out2_pos+j) < *(out1_pos+j))
708 {
709 len = j+1;
710 }
711 else if(*(out2_pos+j) > *(out1_pos+j))
712 {
713 len = 0;
714 }
715 else
716 {
717 if(len!=0)
718 len++;
719 }
720 }
721 }
722 }
723
724 for (j++;j<N;j++)
725 {
726 if (*(out2_pos+j) == 0)
727 return j;
728 }
729
730 return j;
731 }
732
733 void find(unsigned int pre, unsigned int size, unsigned int k, unsigned int *input, unsigned int pos,
734 unsigned int *output, unsigned int *output_pos)
735 {
736 if (size == 0)
737 return;
738
739 if ((pre>k?(pre-k):0) <= *input && pre + k >= *input)
740 {/* a right digit is found */
741 unsigned int output_new_len;
742
743 unsigned int *output_new = (unsigned int *)malloc(sizeof(unsigned int)*size);
744 unsigned int *output_new_pos = (unsigned int *)malloc(sizeof(unsigned int)*size);
745
746 memset(output_new, 0, sizeof(unsigned int)*size);
747 memset(output_new_pos, 0, sizeof(unsigned int)*size);
748
749 /* result of taking the digit into account */
750 *output = *input;
751 *output_pos = pos+1;
752 find(*output, size-1, k, input+1, pos+1, output+1, output_pos+1);
753
754 /* result of ignoring the digit*/
755 find(pre, size-1, k, input+1, pos+1, output_new, output_new_pos);
756
757 /* compare the output with the right digit and without */
758 output_new_len = compareout(output_pos, output_new_pos);
759 if (output_new_len > 0)
760 {
761 memcpy(output, output_new, sizeof(unsigned int)*output_new_len);
762 memcpy(output_pos, output_new_pos, sizeof(unsigned int)*output_new_len);
763 }
764
765 free(output_new);
766 free(output_new_pos);
767 }
768 else
769 {/* not found */
770 find(pre, size-1, k, input+1, pos+1, output, output_pos);
771 }
772 }
773
774 unsigned int i = 0;
775 unsigned int *final_output = NULL;
776 unsigned int *final_output_pos = NULL;
777 unsigned int *output = NULL;
778 unsigned int *output_pos = NULL;
779 unsigned int output_len = 0;
780 unsigned int final_output_len = 0;
781
782 int main(int argc, char *argv[])
783 {
784 scanf("%d %d", &N, &K);
785 /* no need to check, rule says "the program can assume that input data is always valid and consistent with specification given in the problem description"
786 if(!(N>=1 && N<=100000))
787 return -1;
788
789 if(!(K>=1 && K<=100000))
790 return -2;
791 */
792 SEQUENCE = (unsigned int *)malloc(sizeof(unsigned int)*N);
793 memset(SEQUENCE, 0, sizeof(unsigned int)*N);
794
795 for (i; i<N; i++)
796 {
797 scanf("%d", SEQUENCE+i);
798 /* no need to check, rule says "the program can assume that input data is always valid and consistent with specification given in the problem description" */
799 // if (!(*(SEQUENCE+i)<=1000000000 && *(SEQUENCE+i)>0))
800 // return -3;
801 }
802
803 final_output = (unsigned int *)malloc(sizeof(unsigned int)*N);
804 final_output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
805 memset(final_output, 0, sizeof(unsigned int)*N);
806 memset(final_output_pos, 0, sizeof(unsigned int)*N);
807
808 output = (unsigned int *)malloc(sizeof(unsigned int)*N);
809 output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
810
811 for (i=0; i < N && final_output_len < N - i; i++)
812 {
813 memset(output, 0, sizeof(unsigned int)*N);
814 memset(output_pos, 0, sizeof(unsigned int)*N);
815
816 *output = *(SEQUENCE + i);
817 *output_pos = i+1;
818
819 find(*output, N-(i+1), K, SEQUENCE+i+1, i+1, output+1, output_pos+1);
820
821 /* compare the found one for i with current longest one */
822 output_len = compareout(final_output_pos, output_pos);
823 if (output_len > 0)
824 {
825 memcpy(final_output, output, sizeof(unsigned int)*output_len);
826 memcpy(final_output_pos, output_pos, sizeof(unsigned int)*output_len);
827 final_output_len = output_len;
828 }
829 }
830
831 for (i=0;i<final_output_len;i++)
832 {
833 printf("%d ", *(final_output+i));
834 }
835
836 return 0; /* return here, free will use cpu time */
837
838 free(final_output);
839 free(final_output_pos);
840 free(output);
841 free(output_pos);
842
843 return 0;
844 }
845 #elif 0
846 #include <stdio.h>
847 #include <stdlib.h>
848 #include <memory.h>
849
850 #define COUNT_FIND /* UNDEFINE IT IN RELEASE VER */
851
852 unsigned int N = 0, K = 0;
853 unsigned int *SEQUENCE = NULL;
854
855 unsigned int *SEQ_DIG_FOUND = NULL;
856
857 #ifdef COUNT_FIND
858 unsigned int find_func_times = 0;
859 unsigned int compare_func_times = 0;
860 #endif
861
862 /* return out2's length if out1 shall be replaced with out2, otherwise return 0 */
863 unsigned int compareout(unsigned int *out1_pos, unsigned int *out2_pos)
864 {
865 unsigned int j = 0;
866 unsigned int len = 0;
867
868 #ifdef COUNT_FIND
869 compare_func_times++;
870 #endif
871
872 for (;j<N;j++)
873 {
874 if (*(out1_pos+j) == 0)
875 {
876 if (*(out2_pos+j) != 0)
877 break;
878 else
879 {
880 return len;
881 }
882 }
883 else
884 {
885 if(*(out2_pos+j)==0)
886 return 0;
887 else
888 {
889 if(*(out2_pos+j) < *(out1_pos+j))
890 {
891 len = j+1;
892 }
893 else if(*(out2_pos+j) > *(out1_pos+j))
894 {
895 len = 0;
896 }
897 else
898 {
899 if(len!=0)
900 len++;
901 }
902 }
903 }
904 }
905
906 for (j++;j<N;j++)
907 {
908 if (*(out2_pos+j) == 0)
909 return j;
910 }
911
912 return j;
913 }
914
915 void find(unsigned int pre, unsigned int size, unsigned int k, unsigned int *input, unsigned int pos,
916 unsigned int *output, unsigned int *output_pos)
917 {
918 #ifdef COUNT_FIND
919 find_func_times++;
920 #endif
921
922 // if (size == 0)
923 // return;
924
925 if ((pre>k?(pre-k):0) <= *input && pre + k >= *input)
926 {/* a right digit is found */
927 *output = *input;
928 *output_pos = pos+1;
929
930 *(SEQ_DIG_FOUND+pos) = 1; /* mark it found before */
931
932 if (size>1)
933 {
934 unsigned int output_new_len;
935
936 unsigned int *output_new = (unsigned int *)malloc(sizeof(unsigned int)*size);
937 unsigned int *output_new_pos = (unsigned int *)malloc(sizeof(unsigned int)*size);
938
939 memset(output_new, 0, sizeof(unsigned int)*size);
940 memset(output_new_pos, 0, sizeof(unsigned int)*size);
941
942 /* result of taking the digit into account */
943 find(*output, size-1, k, input+1, pos+1, output+1, output_pos+1);
944
945 /* result of ignoring the digit*/
946 find(pre, size-1, k, input+1, pos+1, output_new, output_new_pos);
947
948 /* compare the output with the right digit and without */
949 output_new_len = compareout(output_pos, output_new_pos);
950 if (output_new_len > 0)
951 {
952 memcpy(output, output_new, sizeof(unsigned int)*output_new_len);
953 memcpy(output_pos, output_new_pos, sizeof(unsigned int)*output_new_len);
954 }
955
956 free(output_new);
957 free(output_new_pos);
958 }
959 }
960 else
961 {/* not found */
962 if (size>1)
963 find(pre, size-1, k, input+1, pos+1, output, output_pos);
964 }
965 }
966
967 unsigned int i = 0;
968 unsigned int *final_output = NULL;
969 unsigned int *final_output_pos = NULL;
970 unsigned int *output = NULL;
971 unsigned int *output_pos = NULL;
972 unsigned int output_len = 0;
973 unsigned int final_output_len = 0;
974
975 int main(int argc, char *argv[])
976 {
977 scanf("%d %d", &N, &K);
978 /* no need to check, rule says "the program can assume that input data is always valid and consistent with specification given in the problem description"
979 if(!(N>=1 && N<=100000))
980 return -1;
981
982 if(!(K>=1 && K<=100000))
983 return -2;
984 */
985 SEQUENCE = (unsigned int *)malloc(sizeof(unsigned int)*N);
986 memset(SEQUENCE, 0, sizeof(unsigned int)*N);
987
988 SEQ_DIG_FOUND = (unsigned int *)malloc(sizeof(unsigned int)*N);
989 memset(SEQ_DIG_FOUND, 0, sizeof(unsigned int)*N);
990
991 for (i; i<N; i++)
992 {
993 scanf("%d", SEQUENCE+i);
994 /* no need to check, rule says "the program can assume that input data is always valid and consistent with specification given in the problem description" */
995 // if (!(*(SEQUENCE+i)<=1000000000 && *(SEQUENCE+i)>0))
996 // return -3;
997 }
998
999 final_output = (unsigned int *)malloc(sizeof(unsigned int)*N);
1000 final_output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
1001 memset(final_output, 0, sizeof(unsigned int)*N);
1002 memset(final_output_pos, 0, sizeof(unsigned int)*N);
1003
1004 output = (unsigned int *)malloc(sizeof(unsigned int)*N);
1005 output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
1006
1007 for (i=0; i < N && final_output_len < N - i && *(SEQ_DIG_FOUND+i) != 1; i++)
1008 {
1009 memset(output, 0, sizeof(unsigned int)*N);
1010 memset(output_pos, 0, sizeof(unsigned int)*N);
1011
1012 *output = *(SEQUENCE + i);
1013 *output_pos = i+1;
1014
1015 find(*output, N-(i+1), K, SEQUENCE+i+1, i+1, output+1, output_pos+1);
1016
1017 /* compare the found one for i with current longest one */
1018 output_len = compareout(final_output_pos, output_pos);
1019 if (output_len > 0)
1020 {
1021 memcpy(final_output, output, sizeof(unsigned int)*output_len);
1022 memcpy(final_output_pos, output_pos, sizeof(unsigned int)*output_len);
1023 final_output_len = output_len;
1024 }
1025 }
1026
1027 for (i=0;i<final_output_len;i++)
1028 {
1029 printf("%d ", *(final_output+i));
1030 }
1031
1032 #ifdef COUNT_FIND
1033 printf("\n%d %d", find_func_times, compare_func_times);
1034 #endif
1035
1036 return 0; /* return here, free will use cpu time */
1037
1038 free(SEQUENCE);
1039 free(SEQ_DIG_FOUND);
1040 free(final_output);
1041 free(final_output_pos);
1042 free(output);
1043 free(output_pos);
1044
1045 return 0;
1046 }
1047 #elif 0
1048 #include <stdio.h>
1049 #include <stdlib.h>
1050 #include <memory.h>
1051
1052 #define COUNT_FIND /* UNDEFINE IT IN RELEASE VER */
1053
1054 unsigned int N = 0, K = 0;
1055 unsigned int *SEQUENCE = NULL;
1056
1057 unsigned int *SEQ_DIG_FOUND = NULL;
1058
1059 #ifdef COUNT_FIND
1060 unsigned int find_func_times = 0;
1061 unsigned int compare_func_times = 0;
1062 #endif
1063
1064 /* return out2's length if out1 shall be replaced with out2, otherwise return 0 */
1065 unsigned int compareout(unsigned int *out1_pos, unsigned int *out2_pos)
1066 {
1067 unsigned int j = 0;
1068 unsigned int len = 0;
1069
1070 #ifdef COUNT_FIND
1071 compare_func_times++;
1072 #endif
1073
1074 for (;j<N;j++)
1075 {
1076 if (*(out1_pos+j) == 0)
1077 {
1078 if (*(out2_pos+j) != 0)
1079 break;
1080 else
1081 {
1082 return len;
1083 }
1084 }
1085 else
1086 {
1087 if(*(out2_pos+j)==0)
1088 return 0;
1089 else
1090 {
1091 if(*(out2_pos+j) < *(out1_pos+j))
1092 {
1093 len = j+1;
1094 }
1095 else if(*(out2_pos+j) > *(out1_pos+j))
1096 {
1097 len = 0;
1098 }
1099 else
1100 {
1101 if(len!=0)
1102 len++;
1103 }
1104 }
1105 }
1106 }
1107
1108 for (j++;j<N;j++)
1109 {
1110 if (*(out2_pos+j) == 0)
1111 return j;
1112 }
1113
1114 return j;
1115 }
1116
1117 void find(unsigned int pre, unsigned int size, unsigned int *input, unsigned int pos, unsigned int *output_pos)
1118 {
1119 #ifdef COUNT_FIND
1120 find_func_times++;
1121 #endif
1122
1123 if ((pre>K?(pre-K):0) <= *input && pre + K >= *input)
1124 {/* a right digit is found */
1125 *output_pos = pos+1;
1126
1127 *(SEQ_DIG_FOUND+pos) = 1; /* mark it found before */
1128
1129 if (size>1)
1130 {
1131 unsigned int output_new_len;
1132 unsigned int *output_new_pos = (unsigned int *)malloc(sizeof(unsigned int)*size);
1133
1134 memset(output_new_pos, 0, sizeof(unsigned int)*size);
1135
1136 /* result of taking the digit into account */
1137 find(*input, size-1, input+1, pos+1, output_pos+1);
1138
1139 /* result of ignoring the digit*/
1140 find(pre, size-1, input+1, pos+1, output_new_pos);
1141
1142 /* compare the output with the right digit and without */
1143 output_new_len = compareout(output_pos, output_new_pos);
1144 if (output_new_len > 0)
1145 {
1146 memcpy(output_pos, output_new_pos, sizeof(unsigned int)*output_new_len);
1147 }
1148
1149 free(output_new_pos);
1150 }
1151 }
1152 else
1153 {/* not found */
1154 if (size>1)
1155 find(pre, size-1, input+1, pos+1, output_pos);
1156 }
1157 }
1158
1159 unsigned int i = 0;
1160 unsigned int *final_output_pos = NULL;
1161 unsigned int *output_pos = NULL;
1162 unsigned int output_len = 0;
1163 unsigned int final_output_len = 0;
1164
1165 int main(int argc, char *argv[])
1166 {
1167 scanf("%d %d", &N, &K);
1168 /* no need to check, rule says "the program can assume that input data is always valid and consistent with specification given in the problem description"
1169 if(!(N>=1 && N<=100000))
1170 return -1;
1171
1172 if(!(K>=1 && K<=100000))
1173 return -2;
1174 */
1175 SEQUENCE = (unsigned int *)malloc(sizeof(unsigned int)*N);
1176 memset(SEQUENCE, 0, sizeof(unsigned int)*N);
1177
1178 SEQ_DIG_FOUND = (unsigned int *)malloc(sizeof(unsigned int)*N);
1179 memset(SEQ_DIG_FOUND, 0, sizeof(unsigned int)*N);
1180
1181 for (i; i<N; i++)
1182 {
1183 scanf("%d", SEQUENCE+i);
1184 /* no need to check, rule says "the program can assume that input data is always valid and consistent with specification given in the problem description" */
1185 // if (!(*(SEQUENCE+i)<=1000000000 && *(SEQUENCE+i)>0))
1186 // return -3;
1187 }
1188
1189 final_output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
1190 memset(final_output_pos, 0, sizeof(unsigned int)*N);
1191
1192 output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
1193
1194 for (i=0; i < N && final_output_len < N - i && *(SEQ_DIG_FOUND+i) != 1; i++)
1195 {
1196 memset(output_pos, 0, sizeof(unsigned int)*N);
1197
1198 *output_pos = i+1;
1199
1200 find(*(SEQUENCE + i), N-(i+1), SEQUENCE+i+1, i+1, output_pos+1);
1201
1202 /* compare the found one for i with current longest one */
1203 output_len = compareout(final_output_pos, output_pos);
1204 if (output_len > 0)
1205 {
1206 memcpy(final_output_pos, output_pos, sizeof(unsigned int)*output_len);
1207 final_output_len = output_len;
1208 }
1209 }
1210
1211 for (i=0;i<final_output_len;i++)
1212 {
1213 printf("%d ", *(SEQUENCE+*(final_output_pos+i)-1));
1214 }
1215
1216 #ifdef COUNT_FIND
1217 printf("\n%d %d", find_func_times, compare_func_times);
1218 #endif
1219
1220 return 0; /* return here, free will use cpu time */
1221
1222 free(SEQUENCE);
1223 free(SEQ_DIG_FOUND);
1224 free(final_output_pos);
1225 free(output_pos);
1226
1227 return 0;
1228 }
1229 #elif 0
1230 #include <stdio.h>
1231 #include <stdlib.h>
1232 #include <memory.h>
1233
1234 #define COUNT_FIND /* UNDEFINE IT IN RELEASE VER */
1235
1236 unsigned int N = 0, K = 0;
1237 unsigned int *SEQUENCE = NULL;
1238
1239 unsigned int *SEQ_DIG_FOUND = NULL;
1240
1241 #ifdef COUNT_FIND
1242 unsigned int find_func_times = 0;
1243 unsigned int compare_func_times = 0;
1244 #endif
1245
1246 unsigned int j = 0;
1247 unsigned int len = 0;
1248
1249 /* return out2's length if out1 shall be replaced with out2, otherwise return 0 */
1250 unsigned int compareout(unsigned int *out1_pos, unsigned int *out2_pos)
1251 {
1252 j = 0;
1253 len = 0;
1254
1255 #ifdef COUNT_FIND
1256 compare_func_times++;
1257 #endif
1258
1259 for (;j<N;j++)
1260 {
1261 if (*(out1_pos+j) == 0)
1262 {
1263 if (*(out2_pos+j) != 0)
1264 break;
1265 else
1266 {
1267 memcpy(out1_pos, out2_pos, sizeof(unsigned int)*len);
1268 return len;
1269 }
1270 }
1271 else
1272 {
1273 if(*(out2_pos+j)==0)
1274 return 0;
1275 else
1276 {
1277 if(*(out2_pos+j) < *(out1_pos+j))
1278 {
1279 len = j+1;
1280 }
1281 else if(*(out2_pos+j) > *(out1_pos+j))
1282 {
1283 len = 0;
1284 }
1285 else
1286 {
1287 if(len!=0)
1288 len++;
1289 }
1290 }
1291 }
1292 }
1293
1294 for (j++;j<N;j++)
1295 {
1296 if (*(out2_pos+j) == 0)
1297 {
1298 memcpy(out1_pos, out2_pos, sizeof(unsigned int)*j);
1299 return j;
1300 }
1301 }
1302
1303 memcpy(out1_pos, out2_pos, sizeof(unsigned int)*j);
1304 return j;
1305 }
1306
1307 //#if 0
1308 //#define N 6
1309 //#define K 3
1310 //
1311 //unsigned int SEQUENCE[N] = {2, 9, 7, 2, 5, 8}; /*9 7 5 8*/ 17 7
1312 //unsigned int SEQUENCE[N] = {3, 3, 3, 3, 3, 3}; /*3 3 3 3 3 3*/ 31 16
1313 //unsigned int SEQUENCE[N] = {9, 2, 5, 1, 1, 1}; /*2 1 1 1*/ 16 6
1314 //unsigned int SEQUENCE[N] = {2, 5, 6, 1, 1, 1}; /*2 1 1 1*/ 16 6
1315 //#elif 0
1316 //#define N 3
1317 //#define K 3
1318 //
1319 //unsigned int SEQUENCE[N] = {2, 5, 1}; /*2 5*/
1320 //#elif 0
1321 //#define N 10
1322 //#define K 3
1323 //
1324 //unsigned int SEQUENCE[N] = {2, 5, 1, 7, 90, 100, 3, 6, 8, 2}; /*2 5 7 6 8*/ 48 19
1325 //#endif
1326
1327 void find(unsigned int pre, unsigned int *input, unsigned int pos, unsigned int *output_pos)
1328 {
1329 #ifdef COUNT_FIND
1330 find_func_times++;
1331 #endif
1332
1333 if ((pre>K?(pre-K):0) <= *input && pre+K >= *input)
1334 {/* a right digit is found */
1335 *output_pos = pos+1;
1336 *(SEQ_DIG_FOUND+pos) = 1; /* mark it found before */
1337
1338 if ((N-pos)>1)
1339 {
1340 unsigned int *output_new_pos = (unsigned int *)malloc(sizeof(unsigned int)*(N-pos));
1341 memset(output_new_pos, 0, sizeof(unsigned int)*(N-pos));
1342
1343 /* result of taking the digit into account */
1344 find(*input, input+1, pos+1, output_pos+1);
1345
1346 /* result of ignoring the digit*/
1347 find(pre, input+1, pos+1, output_new_pos);
1348
1349 /* compare the output with the right digit and without */
1350 compareout(output_pos, output_new_pos);
1351
1352 free(output_new_pos);
1353 }
1354 }
1355 else
1356 {/* not found */
1357 if ((N-pos)>1)
1358 find(pre, input+1, pos+1, output_pos);
1359 }
1360 }
1361
1362 unsigned int i = 0;
1363 unsigned int *final_output_pos = NULL;
1364 unsigned int *output_pos = NULL;
1365 unsigned int output_len = 0;
1366 unsigned int final_output_len = 0;
1367
1368 int main(int argc, char *argv[])
1369 {
1370 scanf("%d %d", &N, &K);
1371 /* no need to check, rule says "the program can assume that input data is always valid and consistent with specification given in the problem description"
1372 if(!(N>=1 && N<=100000))
1373 return -1;
1374
1375 if(!(K>=1 && K<=100000))
1376 return -2;
1377 */
1378 SEQUENCE = (unsigned int *)malloc(sizeof(unsigned int)*N);
1379 memset(SEQUENCE, 0, sizeof(unsigned int)*N);
1380
1381 SEQ_DIG_FOUND = (unsigned int *)malloc(sizeof(unsigned int)*N);
1382 memset(SEQ_DIG_FOUND, 0, sizeof(unsigned int)*N);
1383
1384 for (i; i<N; i++)
1385 {
1386 scanf("%d", SEQUENCE+i);
1387 /* no need to check, rule says "the program can assume that input data is always valid and consistent with specification given in the problem description" */
1388 // if (!(*(SEQUENCE+i)<=1000000000 && *(SEQUENCE+i)>0))
1389 // return -3;
1390 }
1391
1392 final_output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
1393 memset(final_output_pos, 0, sizeof(unsigned int)*N);
1394
1395 output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
1396
1397 for (i=0; i < N && final_output_len < N - i && *(SEQ_DIG_FOUND+i) != 1; i++)
1398 {
1399 memset(output_pos, 0, sizeof(unsigned int)*N);
1400
1401 *output_pos = i+1;
1402
1403 find(*(SEQUENCE + i), SEQUENCE+i+1, i+1, output_pos+1);
1404
1405 /* compare the found one for i with current longest one */
1406 output_len = compareout(final_output_pos, output_pos);
1407 if (output_len > 0)
1408 {
1409 final_output_len = output_len;
1410 }
1411 }
1412
1413 for (i=0;i<final_output_len;i++)
1414 {
1415 printf("%d ", *(SEQUENCE+*(final_output_pos+i)-1));
1416 }
1417
1418 #ifdef COUNT_FIND
1419 printf("\n%d %d", find_func_times, compare_func_times);
1420 #endif
1421
1422 return 0; /* return here, free will use cpu time */
1423
1424 free(SEQUENCE);
1425 free(SEQ_DIG_FOUND);
1426 free(final_output_pos);
1427 free(output_pos);
1428
1429 return 0;
1430 }
1431 #elif 0
1432 #include <stdio.h>
1433 #include <stdlib.h>
1434 #include <memory.h>
1435
1436 #define COUNT_FIND /* UNDEFINE IT IN RELEASE VER */
1437
1438 unsigned int N = 0, K = 0;
1439 unsigned int *SEQUENCE = NULL;
1440
1441 char *SEQ_DIG_FOUND = NULL;
1442
1443 #ifdef COUNT_FIND
1444 unsigned int find_func_times = 0;
1445 #endif
1446
1447
1448 //#if 0
1449 //#define N 6
1450 //#define K 3
1451 //
1452 //unsigned int SEQUENCE[N] = {2, 9, 7, 2, 5, 8}; /*9 7 5 8*/ 19
1453 //unsigned int SEQUENCE[N] = {3, 3, 3, 3, 3, 3}; /*3 3 3 3 3 3*/ 31
1454 //unsigned int SEQUENCE[N] = {9, 2, 5, 1, 1, 1}; /*2 1 1 1*/ 19
1455 //unsigned int SEQUENCE[N] = {2, 5, 6, 1, 1, 1}; /*2 1 1 1*/ 15
1456 //#elif 0
1457 //#define N 3
1458 //#define K 3
1459 //
1460 //unsigned int SEQUENCE[N] = {2, 5, 1}; /*2 5*/ 3
1461 //#elif 0
1462 //#define N 10
1463 //#define K 3
1464 //
1465 //unsigned int SEQUENCE[N] = {2, 5, 1, 7, 90, 100, 3, 6, 8, 2}; /*2 5 7 6 8*/ 55
1466 //#endif
1467
1468 unsigned int find(unsigned int pre, unsigned int *input, unsigned int pos, unsigned int *output_pos)
1469 {
1470 unsigned int len = 0;
1471
1472 #ifdef COUNT_FIND
1473 find_func_times++;
1474 #endif
1475
1476 if ((pre>K?(pre-K):0) <= *input && pre+K >= *input)
1477 {/* a right digit is found */
1478 *output_pos = pos+1;
1479 *(SEQ_DIG_FOUND+pos) = '1'; /* mark it found before */
1480 len++;
1481
1482 if ((N-pos)>1)
1483 {
1484 unsigned int len_new = 0;
1485 unsigned int *output_new_pos = (unsigned int *)malloc(sizeof(unsigned int)*(N-pos));
1486 memset(output_new_pos, 0, sizeof(unsigned int)*(N-pos));
1487
1488 /* result of taking the digit into account */
1489 len += find(*input, input+1, pos+1, output_pos+1);
1490
1491 /* result of ignoring the digit*/
1492 len_new = find(pre, input+1, pos+1, output_new_pos);
1493
1494 /* compare the output with the right digit and without */
1495 if (len <= len_new)
1496 {
1497 memcpy(output_pos, output_new_pos, sizeof(unsigned int)*len_new);
1498 len = len_new;
1499 }
1500
1501 free(output_new_pos);
1502
1503 return len;
1504 }
1505 else
1506 return len;
1507 }
1508 else
1509 {/* not found */
1510 if ((N-pos)>1)
1511 return len + find(pre, input+1, pos+1, output_pos);
1512 else
1513 return len;
1514 }
1515 }
1516
1517 unsigned int i = 0;
1518 unsigned int *final_output_pos = NULL;
1519 unsigned int *output_pos = NULL;
1520 unsigned int output_len = 0;
1521 unsigned int final_output_len = 0;
1522 unsigned int *temp = NULL;
1523
1524 int main(int argc, char *argv[])
1525 {
1526 scanf("%d %d", &N, &K);
1527
1528 SEQUENCE = (unsigned int *)malloc(sizeof(unsigned int)*N);
1529 memset(SEQUENCE, 0, sizeof(unsigned int)*N);
1530
1531 SEQ_DIG_FOUND = (char *)malloc(sizeof(char)*N);
1532 memset(SEQ_DIG_FOUND, 0, sizeof(char)*N);
1533
1534 final_output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
1535 memset(final_output_pos, 0, sizeof(unsigned int)*N);
1536
1537 output_pos = (unsigned int *)malloc(sizeof(unsigned int)*N);
1538
1539 for (i; i<N; i++)
1540 {
1541 scanf("%d", SEQUENCE+N-(i+1));
1542 }
1543
1544 for (i=0; final_output_len <= N - i && *(SEQ_DIG_FOUND+i) != '1'; i++)
1545 {
1546 memset(output_pos, 0, sizeof(unsigned int)*N);
1547
1548 *output_pos = i+1;
1549
1550 output_len = 1 + find(*(SEQUENCE + i), SEQUENCE+i+1, i+1, output_pos+1);
1551
1552 /* compare the found one for i with current longest one */
1553 if (output_len >= final_output_len)
1554 {
1555 temp = final_output_pos;
1556 final_output_pos = output_pos;
1557 output_pos = temp;
1558 final_output_len = output_len;
1559 }
1560 }
1561
1562 for (i=final_output_len;i>0;i--)
1563 {
1564 printf("%d ", *(SEQUENCE+*(final_output_pos+i-1)-1));
1565 }
1566
1567 #ifdef COUNT_FIND
1568 printf("\n%d", find_func_times);
1569 #endif
1570
1571 return 0; /* return here, free will use cpu time */
1572
1573 free(SEQUENCE);
1574 free(SEQ_DIG_FOUND);
1575 free(final_output_pos);
1576 free(output_pos);
1577
1578 return 0;
1579 }
1580 #endif
 
  
Legend:
Removed 
Changed
 Added

[Add General Comment] to topic.