### Site Tools

prelude_to_self-describing_sequence

# Differences

This shows you the differences between two versions of the page.

 prelude_to_self-describing_sequence [2011/09/20 06:24]jtkorb prelude_to_self-describing_sequence [2011/09/20 06:34] (current)jtkorb Both sides previous revision Previous revision 2011/09/20 06:34 jtkorb 2011/09/20 06:28 jtkorb 2011/09/20 06:26 jtkorb 2011/09/20 06:26 jtkorb 2011/09/20 06:25 jtkorb 2011/09/20 06:24 jtkorb 2011/09/20 06:24 jtkorb 2011/09/20 06:11 jtkorb created Next revision Previous revision 2011/09/20 06:34 jtkorb 2011/09/20 06:28 jtkorb 2011/09/20 06:26 jtkorb 2011/09/20 06:26 jtkorb 2011/09/20 06:25 jtkorb 2011/09/20 06:24 jtkorb 2011/09/20 06:24 jtkorb 2011/09/20 06:11 jtkorb created Line 3: Line 3: First, start by reading the problem statement for [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=33&​page=show_problem&​problem=990|Self-describing Sequence]]. First, start by reading the problem statement for [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=33&​page=show_problem&​problem=990|Self-describing Sequence]]. - For this prelude, create an array, ''​fr'',​ that contains the index of each place in ''​f(n)''​ where ''​f(n)''​ changes values (that is, where a next run of identical values appears). + For this prelude, create an array, ''​fr'',​ that contains the index of each place in ''​f(n)''​ where ''​f(n)''​ changes values (that is, where the next run of identical values appears). n     ​1 ​  ​2 ​  ​3 ​  ​4 ​  ​5 ​  ​6 ​  ​7 ​  ​8 ​  ​9 ​ 10  11  12 13 14 15 16 n     ​1 ​  ​2 ​  ​3 ​  ​4 ​  ​5 ​  ​6 ​  ​7 ​  ​8 ​  ​9 ​ 10  11  12 13 14 15 16 f(n)  1   ​2 ​  ​2 ​  ​3 ​  ​3 ​  ​4 ​  ​4 ​  ​4 ​  ​5 ​  ​5 ​  ​5 ​  ​6 ​ 6  6  6  7 f(n)  1   ​2 ​  ​2 ​  ​3 ​  ​3 ​  ​4 ​  ​4 ​  ​4 ​  ​5 ​  ​5 ​  ​5 ​  ​6 ​ 6  6  6  7 - fr[n] 1   ​2 ​  ​4 ​  ​6 ​  ​9 ​ 12  16 + fr[n] 1   ​2 ​  ​4 ​  ​6 ​  ​9 ​ 12  16   ... This array is a kind of run-length encoding of function ''​f(n)''​. This array is a kind of run-length encoding of function ''​f(n)''​. Line 13: Line 13: ===== Input ===== ===== Input ===== - Like Pairsumonious Numbers, the input is a sequence of test cases, one per line.  The first number on the line is N, followed by N*(N-1)/2 additional numbers. + Input consists of a sequence of integers, one per line.  The last entry is a 0, which should not be processed. ===== Output ===== ===== Output ===== - Print a line of output for each line of input.  The first number on the line is N*(N-1)/2, followed by the N*(N-1)/2 input numbers in sorted order, from lowest ​to highest. + For each non-zero ​input value, ''​k'',​ print the value of ''​n''​ where ''​f(n)''​ changes ​to ''​k''​. ===== Sample Input ===== ===== Sample Input ===== <​code>​ <​code>​ - 3 1269 1160 1663 + 7 - 3 1 1 1 + 0 - 5 226 223 225 224 227 229 228 226 225 227 + - 5 216 210 204 212 220 214 222 208 216 210 + - 5 -1 0 -1 -2 1 0 -1 1 0 -1 + - 5 79950 79936 79942 79962 79954 79972 79960 79968 79924 79932 + ​ Line 33: Line 29: <​code>​ <​code>​ - 3 1160 1269 1663 + 16 - 3 1 1 1 + - 10 223 224 225 225 226 226 227 227 228 229 + - 10 204 208 210 210 212 214 216 216 220 222 + - 10 -2 -1 -1 -1 -1 0 0 0 1 1 + - 10 79924 79932 79936 79942 79950 79954 79960 79962 79968 79972 +