User Tools

Site Tools


prelude_to_self-describing_sequence

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
prelude_to_self-describing_sequence [2011/09/20 06:24] jtkorbprelude_to_self-describing_sequence [2011/09/20 06:34] (current) jtkorb
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 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                      10  11  12 13 14 15 16   n                      10  11  12 13 14 15 16
   f(n)  1                        6  6  6  7   f(n)  1                        6  6  6  7
-  fr[n] 1          12  16+  fr[n] 1          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 Nfollowed by N*(N-1)/2 additional numbers.+Input consists of a sequence of integers, one per line.  The last entry is a 0which 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)/2followed 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 -1 -2 1 0 -1 1 0 -1 +
-5 79950 79936 79942 79962 79954 79972 79960 79968 79924 79932+
 </code> </code>
  
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+
 </code> </code>
prelude_to_self-describing_sequence.txt · Last modified: 2011/09/20 06:34 by jtkorb