Tim Korb's Home Page

User Tools

Site Tools

Trace:
prelude_to_self-describing_sequence

Differences

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

Link to this comparison view

Next revision		Previous revision
prelude_to_self-describing_sequence [2011/09/20 06:11] – created jtkorbprelude_to_self-describing_sequence [2011/09/20 06:34] (current) – jtkorb
Line 1: Line 1:
 ===== Prelude to Self-describing Sequence ====== ===== Prelude to 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]].  The input format is the same.+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 the next run of identical values appears). 
 + 
 +  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 
 +  fr[n] 1   2   4   6   9  12  16   ... 
 + 
 +This array is a kind of run-length encoding of function ''f(n)''.
  
 ===== 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+
 </code> </code>
  
Line 25: 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