text:
Print My Block Schedule
My high school, and many others implement a type of schedule called a Rotating Block Schedule. This is a way for people to have 8 classes, but on have 6 periods in a school day.
There are four days in a block schedule that repeat over and over, and have nothing to do with the actual days of the week. Each are assigned a number [1-4].
The way the schedule works is that you list all your morning classes, periods 1-4: [1, 2, 3, 4]. This is your schedule for the first day, or Day 1. The rest of the days just rotate the list: [2, 3, 4, 1] , [3, 4, 1, 2], [4, 1, 2, 3].
However, the last period in the morning is "dropped" and you don't see that teacher that day. Hence the days are: [1, 2, 3], [2, 3, 4], [3, 4, 1], [4, 1, 2].
The afternoon is the same, except that it uses periods 5-8 instead: [5, 6, 7], [6, 7, 8], [7, 8, 5], [8, 5, 6].
Your task
All this rotating is hard to keep track of, so you have to write a program to print out my schedule given what day it is as input. Your code has to place Homeroom and Lunch in the correct spots. Here is the exact output your code needs to have for inputs 1-4:
Homeroom    Homeroom    Homeroom    Homeroom
Period 1    Period 2    Period 3    Period 4
Period 2    Period 3    Period 4    Period 1
Period 3    Period 4    Period 1    Period 2
Lunch       Lunch       Lunch       Lunch
Period 5    Period 6    Period 7    Period 8
Period 6    Period 7    Period 8    Period 5
Period 7    Period 8    Period 5    Period 6

But Wait - One more thing!
Sometimes, on the first day of school, or on other special days, my school has a "Day 0". This just means that I will have all my classes that day along with homeroom and lunch. Your code will have to deal with Day 0's. Here is the output for a Day 0:
Homeroom
Period 1
Period 2
Period 3
Period 4
Lunch
Period 5
Period 6
Period 7
Period 8

This is code-golf so shortest code in bytes wins!

Are there 4 days in the week? Or would the first Friday loop back to  1, 2, 3, 5, 6, 7?

@ZachGates only 4 days in the *week*. The block schedule would be out of sync with the actual school week.

When are "Day 0"s used? How do we know which week we're picking from, and how many "Day 0"s have occurred so far?

@ZachGates Isn't that irrelevant? You just have to supply one output for one input. There are only 5 distinct outputs.

Does the schedule restart weekly, or does it keep looping from the previous week? Can you provide a sample input/output? Is the input a single integer?

@ZachGates There are 5 possible inputs. The 5 outputs that correspond to them are listed verbatim in the challenge.

Snowman 1.0.2, 190 bytes
}vg10sB*:#NdE*!1*"Homeroom
"sP0vn3nR:|%+#nA4NmO'"Period "sP'!#nAtSsP"
"sP|%;ae|"Lunch
"sP5*|ae;:"Homeroom
"sP0vn4nR*#:`"Period "sP`NiNtSsP"
"sP;aE"Lunch
"sP#:`"Period "sP`5nAtSsP"
"sP;aE;#bI

That leftmost column actually looks pretty nice, doesn't it?
...
... who am I kidding, I'd rather program in PHP than this.
"Readable" version:
}vg10sB*   // store day # in permavar
// big if statement coming up, depending on whether the input (n) is 0 or not

// THE FOLLOWING BLOCK IS FOR N != 0
:

#NdE*      // decrement number (because we like 0-based indeces) and re-store
!1*        // store the number 1 in permavar ! for later
"Homeroom
"sP        // print "Homeroom"
0vn3nR     // generate [0 1 2]
// for each element in this array...
:
    |%            // shuffle around some variables so we have room
    +#nA          // add day number (in permavar +)
    4NmO          // modulo by 4
    '"Period "sP  // print "Period "
    '!#nAtSsP     // add whatever is in permavar ! and print
    "
"sP               // print a newline
    |%            // return variables to their original state
;ae
// this is a rare occasion in which we use "ae" instead of "aE"
// we use non-consume mode here because we need the block again
// since we've used a permavar ! to determine what to add to the period number,
//   we can set the permavar to 4 more than it used to be and run the same
//   exact block
|"Lunch
"sP        // print "Lunch"
5*         // store the number 5 in permavar !, as described above
|ae        // run the same block over the same array again

;

// THE FOLLOWING BLOCK IS FOR N == 0

:

// after much frustration, I have determined that the easiest way to go about
//   this is to simply code the "day 0" separately
// yes, snowman is *that* bad
"Homeroom
"sP           // you know the drill
// for each number in [0 1 2 3]
0vn4nR*#:
    `"Period "sP
    `NiNtSsP  // increment and print
    "
"sP
;aE
"Lunch
"sP           // same stuff from here
// only interesting thing is we saved the range from before with *#, so we can
//   get it back easily
#:`"Period "sP`5nAtSsP"
"sP;aE

;

#bI

Thoughts and musings:

Firstly, I definitely need to implement a prettier way of printing newlines. Because strings with newlines in an indented block are super ugly.
I like my trick with ae—you rarely see the ae operator without the E capitalized in real Snowman code. (You also rarely see Snowman code that's not written by me, but that's besides the point.)
For the uninitiated, Snowman has two ways to call operators. "Consume" mode, and "non-consume" mode. "Consume" mode will call the operator with the variables requested and then discard the variables. Non-consume mode will call the operator and still leave the variables intact.
Which is usually not what you want with ae (array-each), because the block you're calling on each element will stay there and get in your way, using up a precious one of the eight variables.
However, this is a rare situation in which ae is actually what we want (see the comments in the code for further explanation).
I'm really, really starting to think that Snowman needs more than two modes, other than just "consume" and "do-not-consume." For example, with aa (basically array indexing), you only get two ways to call it:
["foo" 0] -> ["f"]
["foo" 0] -> ["foo" 0 "f"]

(Snowman doesn't use a stack/array structure, but that's simply being used for clarity here.)
It's pretty common that you want ["foo" "f"] (i.e. consume the index variable, but not the original one). It's a super convoluted process to get rid of that annoying 0 if you use "do-not-consume" mode.
A similar thing happens when you call "array-each" in "do-not-consume" mode, as is done here. The array and the block stick around, even during the execution of said block. Which is... really, really weird.
Then again, the design goal of Snowman is to be as confusing as possible, so I'm not sure whether this is a problem at all.

CJam, 65 55 bytes
ri_5,m<0-_W<\?_4f+]"HomeroomLunch"8/.{N@{"Period "\N}%}

Try it online in the CJam interpreter.

Python 3, 193 192 182 168 165 bytes
u=int(input())
print('Homeroom')
r=['Period '+i for i in("123567234678341785412856"[(u-1)*6:u*6]if u else"12345678")]
r.insert(len(r)//2,'Lunch')
for i in r:print(i)

Just a quick solution.
Python 2, 161 bytes
u=int(input())
print'Homeroom'
r=['Period '+i for i in("123567234678341785412856"[(u-1)*6:6*u]if u else"12345678")]
r.insert(len(r)//2,'Lunch')
print'\n'.join(r)

You can save by replacing the for loop with a "\n".join

It's the same amount of bytes in Python 3, but it would help in Python 2. @Maltysen I'll add it though. :P

144 char: def f(u):  r=['Homeroom']+['Period '+i for i in"1123422341334124567856785678567"[u::5]+'8'*(u<1)]  r.insert(4+(u<1),'Lunch')  return'\n'.join(r)

Can further contract "1123422341334124567856785678567"[u::5]+'8'*(u<1) to ("112342234133412456"+'7856'*3)[u::5]+'78'*(u<1) but that only saves one byte

Pyth, 51 bytes
"Homeroom"j"Lunch
"c2jb+L"Period "+J?QP.<S4tQS4+L4J


text:
Make me a hamburger!
The hamburger joint maHburger has hired you to write a program for them.
It is simple: make an ASCII hamburger, using the key. Sounds simple right? Well these customers are super picky, but one thing is for sure, they do love onions.
Write a program that accepts the customer's orders, and prints a hamburger with as many onions as possible.
Key
O=Onions
P=Pickles
M=Mustard
K=Ketchup
#=Bread
.=Sesame Seed
&=Meat
_=Nothing

Input
Through stdin, or closest alternative, your program will receive the customer's order.
Arguments: (number of patties) (Condiments preference) (number of pickles) (number of sesame seeds)
Condiments preference:

M: more mustard (above 50% below 80%)
K: more ketchup (above 50% below 80%)
NM: nu mustard
NK: no ketchup
NMK: no condiments
E: Ketchup and Mustard (between 40% and 60% each)

Rules

Pickles:

Size: 7-21
There must be a pickle that is at least 14 characters, if one or more pickles were ordered.

Mustard:

Size: 2-7
No mustard may be touching Ketchup.

Ketchup:

Size: 2-7
No ketchup may be touching Mustard.

Onions:

If a onion is touching two M's, K's or P's It is considered an M, K, or P as well.
An onion may not be touching an M and an K at the same time.
An onion may not be at the edge of the hamburger.
Only up to 2 onions in and 5 character space.

Sesame seeds are on the top bun only, and may not be touching each other.
Nothing: only up to 10 per patty.
Patties: Customers always order at least 2.

Example:
2 E 3 16

Means 2 patties, Normal condiments, 3 pickles, 16 sesame seeds
and could produce:
                  ###.##########
              ###.#############.####
          ##########.###################
       ###.######.######.######.######.####
     #######.#############.##################
   ###########################.################
  #################.#################.##########
 ###############.#############.##################
##################################################
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
_KKKKKK__MMMMMMMOPPPOPOP_O_PPPPPPOPPPPOPPPPPPPPPOP
##################################################
##################################################
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
KKKKKK_OMMMMMOMO_KOKPPOPPPPPO_MMMMMMMO_OKKKK__OO__
##################################################
##################################################
##################################################

Code Golf
This is code golf, so the shortest code wins.
There are bonuses for the amount of onions your code produces, for the following test cases:
"2 E 3 16"      -5 bytes per onion
"8 M 25 17"     -1 byte per 5 onions
"2 NMK 5 13"    -8 bytes per onion
"2 NK 100 500" -20 bytes if your program prints "No maHburger for you!" for impossible hamburgers.

The bonuses may change.
Format
# Language name, x bytes
How many onions your program produced, and the hamburgers the program created.
code
explanation (if needed)

ASCII
Any whitespace that doesn't affect the ASCII art is fine.
                  ##############
              ######################
          ##############################
       ####################################
     ########################################
   ############################################
  ##############################################
 ################################################
##################################################

Is the top bun
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

Line of Condiments (50 char long)
##################################################
##################################################

for every patty
Standard Loopholes apply.
This is my first Code Golf Challenge! Yay!
This challenge was inspired by this.

No mustard may be touching Mustard....

Oops, forgot to change that to ketchup when I copied and pasted that.

@minxomat Fixed.

"There must be a pickle that is at least 14 characters, if one or more pickles were ordered." - however, I can't see such long sequence of P letters in the sample hamburger?

The onion counts as a P when it is surrounded by P's (onion rule 1)

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Digital River (Shortest And Fastest Solution)
This is my first question, so I hope it goes well.
Background:
It's not the rivers that you might be thinking about. The question revolves around the concept of digital rivers. A digital river is a sequence of numbers where the number following n is n plus the sum of its digits.
Explanation:
12345 is followed by 12360 since 1+2+3+4+5=15 and so 12345 + 15 gives
12360. similarly 145 is followed by 155. If the first number of a digital river is M we will call it river M.
For e.g: River 480 is the sequence beginning {480,492,507,519....}, and river 483 is the sequence beginning {483,498,519,....}. Normal streams and rivers can meet, and the same is true for digital rivers. This happens when two digital rivers share some of the same values.
Example:
River 480 meets river 483 at 519. River 480 meets river 507 at 507 and never meets river 481. Every digital river will eventually meet river 1, river 3 or river 9.
Write a program that can determine for a given integer n the value where river n first meets one of these three rivers.
Input
The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n (1 <= n <= 16384). A test case with value of 0 for n terminates the input and this test case must not be processed.
Output
For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then on a separate line output the line "first meets river x at y". Here y is the lowest value where river n first meets river x (x = 1 or 3 or 9). If river n meets river x at y for more than one value of x, output the lowest value. Print a blank line between two consecutive test cases.
Test case
Input:
86
12345
0

Output:
Case #1

first meets river 1 at 101

Case #2

first meets river 3 at 12423

Scoring:
The fastest algorithm wins. In case of tie. The one with shorter code will win.
Thanks to mbomb007 for pointing out my error.
p.s: I want to have the fastest solution rather than the smallest one.
I also have a solution of mine which is slow. For that look here.
Note:
I will be using this for code testing. And performance checking.

I'm not sure that you can score that way. What if someone's code is O(log(log n))? You can't cover them all, so you need to just say that the fastest algorithm wins, but in case of a tie, shortest code wins, and first posted wins in case both are the same length.

Yeah, thanks for that advice. @mbomb007

Just wanted it that way..

mbomb007 you can edit it for the looks. If you want

I can't find anything on copyright or usability of old ACM-ICPC challenges, but I can find this challenge on the archive site. Is it permissible to use here?

@Geobits. I have solution of the code. But it is not fast enough. I asked it on codereview. No answer there.So thought in golfing people will find dun to find the fastest solution

That has nothing to do with copyright. If in doubt, the easiest thing is normally to email the site owner(s) and ask.

And i have found this question in a competition i was participating. I have clearly stated, in the link i have given.

The convention here for fastest code challenges is usually to post the specs of the machine you will test everything on. That info might be helpful.

this is fastest algorithm.And then implemented in code

"If the last digit of a digital river is M we will call it river M" doesn't make sense for two reasons: firstly, if a river is an infinite sequence of numbers then it doesn't have a last digit; and secondly, in the next paragraph river M means the river starting at number M.

From the linked CR.SE question, it seems like a river is whichever number started with in the series, but here's it's the last digit. Which is correct?

@Geobits Ah, that explains why the question was formatted that way. It was mostly pasted, with some parts changed.

That question was also asked by me in CR SE. Long ago. So directly copied and pasted the old question

With the 1 ≤ n ≤ 16384 restriction, what prevents using a large lookup table?

@LegionMammal978 your own decency

Would lookup tables for, say, rivers 1, 3, and 9 be allowed?

Well, Its not stated to not use a lookup table. But i highly don't appreciate the use of lookup table

C, 320 294 bytes
Compile with -std=c99
#include<stdio.h>
int s(int i){for(int j=i;j;j/=10)i+=j%10;return i;}int main(){int c=0,i;while(scanf("%d",&i)){c++;if(!i)continue;int j,o[]={1,3,9},p[]={1,3,9};Q:for(j=0;j<3;j++){if(o[j]==i)goto D;else if(o[j]<i){o[j]=s(o[j]);goto Q;}}i=s(i);goto Q;D:printf("Case #%d\n\nfirst meets river %d at %d\n\n",c,p[j],o[j]);}}

Ungolfed:
#include <stdio.h>

int s(int i)
{
    for(int j = i; j; j /= 10)
        i += j % 10;
    return i;
}

int main()
{
    int c = 0, i;
    while(scanf("%d", &i))
    {
        c++;
        if(!i)
            continue;
        int j,o[]={1,3,9},p[]={1,3,9};
        Q: for(j = 0; j < 3; j++)
        {
            if(o[j] == i)
                goto D;
            else if(o[j] < i)
            {
                o[j] = s(o[j]);
                goto Q;
            }
        }
        i = s(i);
        goto Q;
        D: printf("Case #%d\n\nfirst meets river %d at %d\n\n", c, p[j], o[j]);
    }
}

Try it out!
Essentially, the "target" rivers are increased until they're greater than the river we're testing against, and afterwards the test river is increased. This is repeated until the test river is equal to some other river.
I'm not reading parameters from the command line in this program, and I'm not sure if you're supposed to. Now you can pass parameters to STDIN. You can terminate by passing a non-numeric input.
Also darn, beaten by half an hour.

I am working on test cases for now. Only 3 input test cases wont be much suitable.

please would you mind taking input from stdin.

JavaScript (ES6)
This is a quite fast answer using a quite slow language. Really, executing time should not be a problem using any language with hash tables.
All my tests under 100 ms.
Anonymous method with the list of test case as input parameter.

F=cases=>{
  var t0 = +new Date
  var result = 0
  var spots = []
  var top=[,1,3,,9]
  var rivers=[,1,3,1,9,1,3,1]
  cases.forEach((n,i)=>{
    var found = result = spots[n]
    for (;!found;)
    {
      found = top.some((v,i)=>{
        for(;spots[v] |= i, v<n; top[i] = v)
          [...v+''].forEach(d=>v-=-d)
        return result = v-n ? 0 : i;
      }) || (
        [...n+''].forEach(d=>n-=-d),
        result = spots[n]
      )
    }
    console.log(`Case #${i+1}\nfirst meets river ${rivers[result]} at ${n}`)
  })
  return 'Time (ms) ' + (new Date-t0)
}

console.log(F([86, 12345, 123, 456, 789, 16384]))

Java 7, 519 505  bytes
import java.util.*;String c(int i){if(i<=0)return"";ArrayList<Long>r=f(1),s=f(3),t=f(9),x=f(i);String z="first meets river ";for(int j=0;j<r.size();j++){long u=r.get(j),v=s.get(j),w=t.get(j);if(x.contains(u))return z+1+" at "+u;if(x.contains(v))return z+3+" at "+v;if(x.contains(w))return z+9+" at "+w;}return"";}ArrayList f(long i){ArrayList<Long>l=new ArrayList();l.add(i);for(long j=0,x;j<9e4;j++){x=l.get(l.size()-1);for(char c:(x+"").toCharArray())x+=new Long(c+"");l.add(x);if(x>16383)return l;}return l;}

Yes, it's long, ugly and can without a doubt be completely changed to code-golf it more.. I'm both distracted and tired, so perhaps I should just delete it again..
It was a pretty hard challenge to be honest.. But at least you have your first answer.. ;) (Which might even be longer than your original ungolfed C++ program.. xD)
Ungolfed & test cases:
Try it here.
import java.util.*;
class M{
  static String c(int i){
    if(i <= 0){
      return "";
    }
    ArrayList<Long> r = f(1),
                    s = f(3),
                    t = f(9),
                    x = f(i);
    String z = "first meets river ",
           y = " at ";
    for(int j = 0; j < r.size(); j++){
      long u = r.get(j),
           v = s.get(j),
           w = t.get(j);
      if(x.contains(u)){
        return z+1+y+u;
      }
      if(x.contains(v)){
        return z+3+y+v;
      }
      if(x.contains(w)){
        return z+9+y+w;
      }
    }
    return "";
  }

  static ArrayList f(long i){
    ArrayList<Long> l = new ArrayList();
    l.add(i);
    for(long j = 0, x; j < 9e4; j++){
      x = l.get(l.size() - 1);
      for(char c : (x + "").toCharArray()){
        x += new Long(c+"");
      }
      l.add(x);
      if(x > 16383){
        return l;
      }
    }
    return l;
  }

  public static void main(String[] a){
    System.out.println(c(86));
    System.out.println(c(12345));
    System.out.println(c(0));
  }
}

Output:
first meets river 1 at 101
first meets river 3 at 12423
(empty output)

I will compare yours program with mine. I am also going to post my solution too. Why to use a slow language. Use any fast language.

I only noticed the fastest-algorithm tag later on.. I always post Java 7 code-golf answers here.. It's defintely not going to win in either shortest or fastest though.. Btw, your rextester gives errors when it should only give warnings for lack of casts / type-initializes.. It works on ideone (and in Eclipse IDE).

ok. let me see. rextester gives compile time and execution time. So i used it

well thats a problem here. I will look for other online compiler which gives the compile time and execution time

@KishanKumar I've added the casts in my code, which shouldn't affect time a.f.a.i.k. Here is the working rextester code with the result: Compilation time: 0.62 sec, absolute running time: 0.14 sec, cpu time: 0.11 sec, memory peak: 22 Mb, absolute service time: 0,77 sec for me locally. So yeah, it's pretty slow..

U're supposed to be taking input from stdin. mate.

http://rextester.com/HEWSPP46345 my code is a lil bit faster than this

Scala, 774 bytes
Fiddle: http://scalafiddle.net/console/4ec96ef90786e0f2d9f7b61b5ab0209b
I don't feel like golfing it. It finds a solution to the posed problem within 50ms
Usage may not be exactly what you want:
scala river.scala
Now you can continuously input numbers followed by an enter. And terminate the program with 0. The result will be printed as soon as you hit enter.
io.Source.stdin.getLines.map(_.toInt)
  .takeWhile(_ != 0)
  .map(stream(_).takeWhile(_ < 16383))
  .zipWithIndex
  .map { cur =>
    Seq(1, 3, 9).map { i =>
      val s = stream(i).takeWhile(_ < 16383)
      (cur._2+1, i, s.intersect(cur._1).headOption)
    }
  }.foreach { opts =>
    val options = opts.filterNot(_._3.isEmpty)

    if(options.isEmpty) {
      println("No result")
    } else {
      val opt = options(0)
      println(s"Case #${opt._1}\n\nfirst meets ${opt._2} at ${opt._3.get}\n\n")
    }
  }

def stream(i:Int): Stream[Int] = {
  def sub: Int => Stream[Int] = {
    i => i #:: sub(a(i))
  }
  sub(i)
}

def a(i:Int): Int = i + i.toString.map{_.asDigit}.sum

I don't know much about Scala. So please could you modify the code which will according to http://rextester.com/l/scala_online_compiler

I tried to put it in there but it timed out while compiling.

ok @AmazingDreams

@KishanKumar even the default one times out so the site seems to be broken for scala

@KisthanKumar Use this one http://scalafiddle.net/console/4ec96ef90786e0f2d9f7b61b5ab0209b it does not support stdin though so I had to change some minor things.

C, 228 283 300 bytes
This is a mod of Yakov's code to take advantage of the river patterns.  This makes it ~3x faster.  Also, unsigned integers avoid the cltod penalty on 64-bit machines, so it's a few bytes longer but fractionally faster.
#define sum(z) for(y=z;y;y/=10)z+=y%10;
n,x;main(){unsigned i,j,y;while(scanf("%d",&i)){if(i){j=x=1+!(i%3)*2+!(i%9)*6;do{while(j<i)sum(j)}while(j^i&&({sum(i)i;}));printf("Case #%u\n\nfirst meets river %u at %u\n\n",++n,x,i);}}}

Ungolfed:
#define sum(z) for(y=z;y;y/=10)z+=y%10;
n, x;
main() {
    unsigned i, j, y;
    while(scanf("%d", &i)) {
        if(i){
            j = x = 1 + !(i%3)*2 + !(i%9)*6;
            do{
                while (j < i) sum(j)
            }
            while(j^i&&({sum(i)i;}));
            printf("Case #%u\n\nfirst meets river %u at %u\n\n", ++n, x, i);
        }
    }
}

Explanation:
j = x = 1 + !(i%3)*2 + !(i%9)*6;

This selects the correct river.  River 1 meets every other river, so we use this as the fall-back case.  If 3 is the greatest common divisor of the test river, we select river 3 (1 + !(i%3)*2).  If 9 is the greatest common divisor of the test river, we override the previous values and select river 9.
Why does this work? River 9 goes 9, 18, 27, 36, etc.  This steps by a multiple of 9 each time thus it will always be the shortest route to a sister river.  River 3 will step by a multiple of 3 each time: 3, 6, 12, 15, 21, etc.  While rivers that are a multiple of 9 are also a multiple of 3, we choose them as river 9 first, leaving only the multiples of 3.  The remainder will meet river 1 first: 1, 2, 4, 8, 16, 23, 28, etc.
Once we have selected our correct river, we step the two rivers until they meet.

Python 3, 144 bytes
r,a,b,c,i={int(input())},{1},{3},{9},1
while i:
  for x in r,a,b,c:t=max(x);x|={sum(int(c)for c in str(t))+t}
  if r&(a|b|c):i=print(*r&(a|b|c))

C
Very simple, it just looks that long because I unrolled all the 3 rivers. It first generates the 3 rivers up to RIVER_LENGTH (which I hope is big enough), and then for each step on N it does a binary search on all three streams to see if it is in any of them. This works because the streams are already sorted, so we can do the contains check in log(n) time.
#include <stdio.h>

#define RIVER_LENGTH 10000

int main() {
    int num_cases;
    scanf("%d", &num_cases);
    int cases[num_cases];
    int N;
    int s1[RIVER_LENGTH] = {1};
    int s3[RIVER_LENGTH] = {3};
    int s9[RIVER_LENGTH] = {9};
    int i;
    int temp;

    for (i = 1; i < RIVER_LENGTH; i++) {
        s1[i] = temp = s1[i-1];
        while (temp) {
            s1[i] += temp % 10;
            temp /= 10;
        }
    }

    for (i = 1; i < RIVER_LENGTH; i++) {
        s3[i] = temp = s3[i-1];
        while (temp) {
            s3[i] += temp % 10;
            temp /= 10;
        }
    }

    for (i = 1; i < RIVER_LENGTH; i++) {
        s9[i] = temp = s9[i-1];
        while (temp) {
            s9[i] += temp % 10;
            temp /= 10;
        }
    }

    int start;
    int end;
    int pivot;

    for (i=1; i <= num_cases; i++) {
        scanf("%d", &cases[i]);
    }

    for (i=1; i <= num_cases; i++) {
        printf("Case #%d\n\n", i);
        N = cases[i];

        while (1) {

            temp = N;
            while (temp) {
                N += temp % 10;
                temp /= 10;
            }

            start = 0;
            end = RIVER_LENGTH;
            pivot = 1;

            while (end != start && pivot != RIVER_LENGTH - 1) {
                pivot = start + ((end - start) >> 1);
                if (s1[pivot] == N) {
                    printf("first meets river 1 at %d\n\n", N);
                    goto case_done;
                } else if (N < s1[pivot]){
                    end = pivot;
                } else {
                    start = pivot+1;
                }
            }

            start = 0;
            end = RIVER_LENGTH;
            pivot = 1;

            while (end != start && pivot != RIVER_LENGTH - 1) {
                pivot = start + ((end - start) >> 1);
                if (s3[pivot] == N) {
                    printf("first meets river 3 at %d\n\n", N);
                    goto case_done;
                } else if (N < s3[pivot]){
                    end = pivot;
                } else {
                    start = pivot+1;
                }
            }

            start = 0;
            end = RIVER_LENGTH;
            pivot = 1;

            while (end != start && pivot != RIVER_LENGTH - 1) {
                pivot = start + ((end - start) >> 1);
                if (s9[pivot] == N) {
                    printf("first meets river 9 at %d\n\n", N);
                    goto case_done;
                } else if (N < s9[pivot]){
                    end = pivot;
                } else {
                    start = pivot+1;
                }
            }
        }

        case_done:;

    }
}

It takes a number for the number of cases first, instead of using 0 to delimit the end of the inputs, because you know, C. This is just for convenience and doesn't really affect anything, so I hope its okay.

This program hits a time limit exceeded on ideone on inputs 86,12345,0

http://ideone.com/mHCeef here is the link. And it gives a kill signal output on rextester

@KishanKumar It takes a number for the number of cases first, instead of using 0 to delimit the end of the inputs, because you know, C. This is just for convenience and doesn't really affect anything, so I hope its okay.

@KishanKumar try this one instead: http://rextester.com/XRJK89444

its ok. No problem. But i will have to write an extra script for your program. As i have to take average time of all the input range.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Can you help Tony Stark become an Ironman?
Tony Stark is, as we know Ironman (that super awesome guy in metal suit and loads of weapons). However, without the metal suit, he can't claim that title. Tony Stark, having a great ego, wants to finish Norseman, which is considered to be the hardest triathlon in the world (for distances equivalent to those of an Ironman race), to prove that he's a mean machine, even when he leaves the iron at home.
Tony has a predefined schedule / time plan for each part of the competition.
That means for every location in the race (i.e. distance from start), there's an expected time he should arrive there based on the schedule.
He also has a watch that tells the time spent and the total distance covered.
Your task is: Given those two values as input, tell Tony how much he is ahead of, or behind schedule. The input will be a time on the format hh:mm:ss (or (optional) h:mm:ss if it's been less than 10 hours) and a decimal number telling how far he has come (in km).
The distances for each of the three disciplines are:
Swim: 3.8 km
Bike: 180 km
Run: 42 km
Total distance: 225.8 km   // Input will never exceed 225.8

The estimated times for each part (i.e. the schedule):
Swim: 1:20:00
Transition 1: 0:12:00
Bike: 7:10:00
Transition 2: 0:05:00
Run: 4:50:00
Total: 13:37:00

Both distances, and the estimated times are given before the race, and can therefore be hardcoded. The transition zone is just a place where he changes clothes and equipment, so he's not moving during transition.
Input can be comma-separated, a string, two separate arguments or whatever is most convenient in your language. He want the output on the format +/-mm:ss, not hours (assume he's never more than one hour too slow or too fast. If he's in transition, you can assume he just got there.
Examples and explanations (apologies for the length of it):
Input: 04:32:20 93.8
Output: +34:40 / 34:40

At 93.8 km, he has finished the swim, been through transition and has finished half of the bike leg. According to the schedule, this should have taken him: 1:20:00 + 0:12:00 + (0.5 * (07:10:00)) = 5:07:00. If he has used 4:32:20, then he's 34:40 ahead of schedule.

Input: 1:20:00 3.8
Output: +00:00 / +0:00 / 00:00 / 0:00 / -00:00 / -0:00

Assuming the distance is 3.8, you can assume he has just got into the first transition zone. The estimated time here was 1:20:00, so for the input above, he's on time.

If the time is 1:25:00, then he's 5 minutes behind schedule, thus:
Input: 1:25:00 3.8
Output: -05:00 / -5:00

Another example, explained in detail:
Input: 10:33:46 198.14

So, a distance of 198.14 km has been covered. That means he has finished the swim (3.8), the bike leg (180 km) and 14.34 km of the running, and he has been through both transitions. According to the schedule, he should have started the run after: 1:20:00 + 0:12:00 + 07:10:00 + 0:05:00 = 8:47:00. 42 km of running should take 4:50:00, thus 14.34 km should take: 4:50:00 * (14.34 / 42) = 1:39:01. So, according to the plan, 198.14 km should take: 8:47:00 + 1:39:01 = 10:26:01. He has used 10:33:46, which is 07:45 more than planned.
Output: -07:45 / -7:45

The plus sign is optional, but there has to be a minus sign if he's behind schedule.
The output should have exactly the same format as the examples above, but trailing spaces, newlines etc. are OK.
This is code golf, so the shortest code in bytes win.

CJam, 91
r~[0_80 3.8_92 43dI183.8 527 290d42]4/{1$a<},W=(@\-\~/@*+60*r':/:i60b-i_gs);\60b2Te[':*)Amd

Try it online. Note: it takes the distance first.


text:
Outputting a base-proof expression
Background
In some possible futures, the world will convert their numerical systems from decimal (base 10 or b10) to some other base (binary b2, octal b8, hexadecimal b16, or even unary b1, in which case we're screwed!). Thus, in preparation for this possible world-changing event, you decide to base-proof all of your programs. This can be done by using only singular 0s and 1s in conjunction with operators to replace the existing number constants.
However, there's just one problem: You have a ton of programs to change, and manually converting each number to an expression would take weeks! Thus, you decide to write a program (or function) to decide for you what expression should replace each number.
Input
The input will be a positive integer. Your code must be able to handle any integer up to 1000.
(If your code supports decimals and/or negative inputs, see Scoring below.)
Output
Your code must output an expression that evaluates to the input in at least one language. This may be any language; it does not have to be the same one your program or function is written in. Also, this expression does not need to be a full program or function.
For clarity, the output may contain any of these operations:

increment / decrement
add / sum
subtract / negate
multiply / double (only if it doesn't directly involve the number 2!)
divide / modulo
exponents / logarithms
square / sqrt (again, only if these don't directly involve the number 2!)
bitwise operations (bOR, bAND, bNOT, bXOR, bit-shifts)
setting / getting variables
stack manipulation

You may not use eval() or any similar functions in the output. You may also not use in the output any functions that perform an action(s) other than the ones mentioned above.
Oh, and one more thing: since we want the output to be valid in as many bases as possible, the only number constants it may contain are 0 and 1. Numbers such as 10 (ten) are disallowed, unless the language interprets it as a 1 and a 0. Using strings to contain numbers is not allowed either, as is using characters such as CJam's A-K (which represent 10-20).
Test-cases
(All outputs are in JavaScript, but may work in other languages.)
Input 1:
2

Possible output 1:
1+1

Input 2:
13

Possible output 2:
(a=1+1+1)*a+a+1

Input 3:
60

Possible output 3:
(b=(a=1+1+1+1)*a)*a-a

Input 4:
777

Possible output 4:
(c=(b=((a=1+1+1+1)*a-a+1)*a)*a+b)+c+c-a+1

Input 5:
1000

Possible output 5:
Math.pow((a=1+1+1)*a+1,a)

Scoring
The goal of this challenge is to shorten your code's output as much as possible. Your score will be calculated in this way:

Base score: The average byte-count of all outputs for integers 1 to 1000.
Decimal score: If your code supports at least 3 decimal places, this is the average byte-count of all outputs of the sequence of numbers starting at 0.001 and ending at 1000, increasing by 1.001 each time. 0.001, 1.002, 2.003...998.999, 1000.000 Then take 50% off of this score.
Negative score: If your code supports negative numbers and zero, this is the average byte-count of the outputs of all integers from -1000 to 0. Then take 10% off of this score.

(The easiest way to calculate these would likely be a loop with your program/function inside.)
Your final score is the average of whichever of the above formulas apply.
If the output is non-deterministic (i.e. somewhat random; multiple runs with the same input produces multiple unique outputs), then the score for each input is determined by the largest output over ten runs on my CPU.
Also, as you don't know how precious computer data will be in the future, the byte-count of your generator code must be less than 512 bytes.
Lowest score in two weeks (on Sep 30) will be declared the winner. Congratulations to your winner, @ThomasKwa!

Leaderboard

var QUESTION_ID=58084,OVERRIDE_USER=42545;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[3],language:a[1]+'/'+a[2],lang2:a[2],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size.toFixed(3)).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/S?1:E<S?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size.toFixed(3)).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,])\/([^\n,]*[^\s,]),.*?([\.\d]+)(?=[^\n\.\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\.\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Languages	Score

Winners by Output Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

To make sure your answer shows up correctly, please start it with this header:
# Language name/Other language name, X points

Where X is the score of your answer. Example:
# CJam/Pyth, 25.38 points

If you have any questions or suggestions, please let me know. Good luck!

Can I use variables that hold 0 or 1 by default?

@Dennis I don't see any problem with that, so go ahead!

I'm assuming I can't do base conversion between base 2 and the default base.

@muddyfish Nope, no base conversion allowed in the output.

I guess we also are not allowed to use something like Integer.parseInt("1000", 1+1+1+1+1+1+1+1+1+1)? I'm pretty sure parseInt uses only the allowed operations ;-)

@PaŭloEbermann No, that would go against this rule, or at least the main intention of it: "Numbers such as 10 (ten) are disallowed, unless the language interprets it as a 1 and a 0." I'll edit to make this more clear.

Are the constants allowed to contain loops? For example Beam '''>\++++++++)` = 24

@MickyT Loops are OK, at least in that case, as Beam does not have built-in multiplication.

@ETHproductions Is the 512B limit for the generating or the generated code?

@minxomat For the generating.

@ETHproductions The negative score uses one step more than the base score ({-1000..0} > {1..1000}). Intended?

@minxomat Yes, this is to score the 0 case. Although now that I think about it, it may be better to include 0 in the base score instead. (Also, I keep reading your username as min-mix-o-mat. ;) )

Are bit shift operations on h also illegal?

@ThomasKwa Bit-shifts are OK, as long as a) it's only a shift by 1 bit (also known as doubling/halving), or b) the number of bits it is shifted by is calculated the same way as regular numbers.

The z80's "shift left logical" instruction shifts a 1 into bit 0.

@ThomasKwa Thanks for the info. I believe that's still alright; it's not too much different from the default behavior.

Which of these single instructions are legal (provided they do not contain literals other than 0 and 1: Pyth's y (double), a hypothetical left trit-shift by 1 on a ternary computer, a left bit shift by 2 implemented by adding a number to itself twice, square (implemented by multiplying a number by itself), cube, square root, cube root, "push a number of 1s given by the number on top of the stack", sum of all numbers from 1 to n, sum of all numbers on the stack, increment twice, add hl to the stack pointer?

@ThomasKwa Doubling is fine; you're already using that in your answer () add hl, hl). I'm gonna say squares, square and cube roots, sum entire stack, and "push a number of 1s given by the number on top of the stack" are fine as well. I'm not sure what you mean by "add hl to the stack pointer"; it would be great if you could elaborate. None of the others are allowed, including "a hypothetical left trit-shift by 1 on a ternary computer", which is exactly the same as tripling.

The z80 has a stack pointer sp; when a register pair is pushed it decrements twice to point to the top of the stack, and when a register pair is popped it increments twice. I was thinking of using push de and add hl,sp to subtract 3 from hl.

@ThomasKwa Alright, I guess that's OK. IMHO, it's actually a pretty clever solution to subtract 3 in 2 bytes. May I ask what push de is referring to?

push de pushes the register pair de onto the stack.

@ThomasKwa Well yeah, I guess I figured that. I should learn more about z80 machine code. Also, congratulations on your win! :)

Python/Zilog Z80 machine code, 11.653 11.488
import math,numpy as np
def R(n):
    if n==0:return []
    if n<0:return -R(-n)
    e=int(math.log(n,2))
    if n >= 5/3 * 2**e:
        return np.append(2**(e+1),-R(2**(e+1)-n))
    return np.append(2**e,R(n-2**e))

def strR(n):
    b = R(n)
    s = ""
    if n==0:return s
    e=max(abs(b))
    while e:
        if e in b:s+="#"
        elif -e in b:s+="+"
        s+=")"
        e//=2
    return s[:-1]

Bonuses: Negative numbers.
Assumes that the hl register pair initially holds 0, and returns the result in hl.
Only these three instructions are used:
ASCII   Hex    Instruction
--------------------------
#       23     inc hl
)       29     add hl,hl
+       2B     dec hl

We use a small modification of the minimum-weight balanced binary representation BBR2. Since BBR2 minimizes the weight (number of nonzero digits), but we want to minimize the weight plus the number of bit shifts, we change a constant in the algorithm from 3/2 to 5/3.
To compute the score and verify, use this code:
def verify(n):
v = 0
for c in strR(n):
    if c=="#":v += 1
    elif c=="+":v -= 1
    else: v *= 2
return v==n

print(0.5*(sum([len(strR(n)) for n in range(1,1001)])/1000 + \
           sum([len(strR(n)) for n in range(-1000,1)])/1001 * 0.9))

print(all([verify(n) for n in range(-1000,1001)]))

Example output:
strR(486)
         '#)))))+)+))+)'

Or in assembly:
inc hl \ add hl,hl \ add hl,hl \ add hl,hl \ add hl,hl \ add hl,hl \ dec hl \ add hl,hl \ dec hl \ add hl,hl \ add hl,hl \ dec hl \ add hl,hl

More example programs:
-256  +))))))))
-255  +))))))))#
-254  +)))))))#)
-253  +)))))))#)#
-252  +))))))#))
-251  +))))))#))#
-250  +))))))#)#)
-249  +)))))#)))+
-248  +)))))#)))
-247  +)))))#)))#
-246  +)))))#))#)
-245  +)))))#))#)#
-244  +)))))#)#))
-243  +)))))#)#))#
-242  +))))#)))+)
-241  +))))#))))+

  -5  +))+
  -4  +))
  -3  +)+
  -2  +)
  -1  +
   0
   1  #
   2  #)
   3  #)#
   4  #))
   5  #))#

Possible optimizations: OP rules that the inc h and dec h instructions, which directly change the upper byte of hl, are illegal, but sla h and the undocumented sl1 h (left bit shifts by 1 on h that shift in a 0 and 1 respectively) are permitted. sla h and sl1 h are two bytes each, but they can sometimes shorten the output.

Very nice, the lowest so far! I guess this is one instance where pure machine code comes in handy. ;)

+1 this is probably unbeatable. Also for the genius of using machine code (on a cpu with a largely 8 bit instruction set and some 16 bit registers.)

It's weird how + translates to dec. I keep reading the negative examples wrong.

CJam/CJam, 143.263 42.713 28.899 23.901 21.903 20.468
ri
[
    ['X\2b1>e`{~{"1)*)"*}{_({(')*1\"m<"}{"1)*"*}?}?}/]s
    "X1)*"/"1)"*
    "1)1)*"/"1)))"*
    "X1)m<"/"1)))"*
    _"1)"/("1):Y"+\'Y*+
]
{,}$0=

No bonuses apply.
Try it online: sample run | score calculator | verification
Example runs
   1 X
   2 1)
   3 1))
   4 1)))
   5 1))))
   6 1))1)*
   7 1))1)*)
   8 X1))m<
   9 1)))1)*)
  10 1))))1)*
  11 1))))1)*)
  12 1))1)m<
  13 1))1)*1)*)
  14 1))1)*)1)*
  15 1))1)*)1)*)
  16 X1)))m<
  17 X1))m<1)*)
  18 1)))1)*)1)*
  19 1)))1)*)1)*)
  20 1))))1)m<

 981 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*Y*)
 982 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*)Y*
 983 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*)Y*)
 984 1):Y)Y*)Y*)Y*Y*)Y*)Y)m<
 985 1):Y)Y*)Y*)Y*Y*)Y*)Ym<Y*)
 986 1):Y)Y*)Y*)Y*Y*)Y*)Y*Y*)Y*
 987 1):Y)Y*)Y*)Y*Y*)Y*)Y*Y*)Y*)
 988 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Ym<
 989 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*Y*)
 990 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*)Y*
 991 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*)Y*)
 992 1):Y)Y*)Y*)Y*)Y)))m<
 993 1):Y)Y*)Y*)Y*)Y))m<Y*)
 994 1):Y)Y*)Y*)Y*)Y)m<Y*)Y*
 995 1):Y)Y*)Y*)Y*)Y)m<Y*)Y*)
 996 1):Y)Y*)Y*)Y*)Ym<Y*)Ym<
 997 1):Y)Y*)Y*)Y*)Ym<Y*)Y*Y*)
 998 1):Y)Y*)Y*)Y*)Ym<Y*)Y*)Y*
 999 1):Y)Y*)Y*)Y*)Ym<Y*)Y*)Y*)
1000 1):Y)Y*)Y*)Y*)Y*Y*)Y)m<

My word, that was fast! The links don't work in Firefox, though.

Since this isn't code golf, I replaced each % with a longer expression. The links should work now.

Input 34 gives 1. On which input does it work better

@KishanKumar The verification tests all 1000 possible inputs. Output 1 indicates that the comparison was successful.

Could you add some example outputs?

Ceylon/Ceylon, 49.86 40.95 points
The third version uses Ceylon 1.2 for the generator and 509 bytes of code:
import ceylon.language{S=String,I=Integer,e=expand}S q(I n)=>n==0then"0"else(n<0then"-"+p(-n,"-")else p(n,"+"));variable Map<[I,S],S>c=map{};S p(I n,S s){S v=c[[n,s]]else(n<8then s.join([1].repeat(n)))else(let(a="+-".replace(s,""))e(e{for(x in 2..8)let(l=(n^(1.0/x)).integer){for(r in l:2)if(r>1)let(w=r^x){if(w-n<n)"("+p(r,"+")+")^("+p(x,"+")+")"+(w<n then s+p(n-w,s)else(n<w then a+p(w-n,a)else""))}}}).reduce<S>((x,y)=>x.size<y.size then x else y))else"";c=[n,s]in c then c else map{[n,s]->v,*c};return v;}
It gets down to 35.22 points, but I won't put this in the title line because Celyon 1.2 only was published at october 29. I don't think I would be able to implement this algorithm in Ceylon 1.1 in this size.). More details down there, here I'll describe the second version. (The first version can be seen in the history – it supported only positive numbers, but did fit into 256 bytes.)
Second version
Now the second version, which supports negative integers (and 0), and generally creates a bit shorter output by using in addition -.
(This version actually uses the permitted length, the first one tried to stay under 256 bytes instead of 512.)
String proof(Integer n) {
    if (n == 0) { return "0"; }
    if (n < 0) { return "-" + p(-n, "-"); }
    return p(n, "+");
}
String p(Integer n, String sign) {
    if (n < 9) {
        return sign.join([1].repeat(n));
    }
    value anti = (sign == "+") then "-" else "+";
    value root = ((n^0.5) + 0.5).integer;
    return "(" + p(root, "+") + ")^(1+1)" +
       ( (root^2 < n) then sign + p(n - root^2, sign) else
         ((n < root^2) then anti + p(root^2 - n, anti) else ""));
}

Code has length 487, so there is still some space for more optimizations later. (There are also lots of reserves in form of whitespace and long variable names.)
The scoring:
Total positive: 42652
Average positive:42.652
Total negative: 43653
Average negative: 43.60939060939061
With bonus:39.24845154845155
Overall score: 40.95022577422577

Some sample outputs:
   27:  21: (1+1+1+1+1)^(1+1)+1+1
   28:  23: (1+1+1+1+1)^(1+1)+1+1+1
   29:  25: (1+1+1+1+1)^(1+1)+1+1+1+1
   30:  27: (1+1+1+1+1)^(1+1)+1+1+1+1+1
   31:  29: (1+1+1+1+1+1)^(1+1)-1-1-1-1-1
   32:  27: (1+1+1+1+1+1)^(1+1)-1-1-1-1
   33:  25: (1+1+1+1+1+1)^(1+1)-1-1-1
   34:  23: (1+1+1+1+1+1)^(1+1)-1-1

  -27:  22: -(1+1+1+1+1)^(1+1)-1-1
  -28:  24: -(1+1+1+1+1)^(1+1)-1-1-1
  -29:  26: -(1+1+1+1+1)^(1+1)-1-1-1-1
  -30:  28: -(1+1+1+1+1)^(1+1)-1-1-1-1-1
  -31:  30: -(1+1+1+1+1+1)^(1+1)+1+1+1+1+1
  -32:  28: -(1+1+1+1+1+1)^(1+1)+1+1+1+1
  -33:  26: -(1+1+1+1+1+1)^(1+1)+1+1+1
  -34:  24: -(1+1+1+1+1+1)^(1+1)+1+1

  993:  65: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1+1)^(1+1)+1+1+1+1+1
  994:  63: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1-1-1
  995:  61: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1-1
  996:  59: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1
  997:  57: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1
  998:  55: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1
  999:  53: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)
 1000:  55: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)+1

 -993:  66: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1+1)^(1+1)-1-1-1-1-1
 -994:  64: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1+1+1
 -995:  62: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1+1
 -996:  60: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1
 -997:  58: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1
 -998:  56: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1
 -999:  54: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)
-1000:  56: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)-1

    1:   1: 1
    2:   3: 1+1
    3:   5: 1+1+1
    4:   7: 1+1+1+1
    5:   9: 1+1+1+1+1
    6:  11: 1+1+1+1+1+1
    7:  13: 1+1+1+1+1+1+1
    8:  15: 1+1+1+1+1+1+1+1
    9:  13: (1+1+1)^(1+1)
   10:  15: (1+1+1)^(1+1)+1

    0:   1: 0
   -1:   2: -1
   -2:   4: -1-1
   -3:   6: -1-1-1
   -4:   8: -1-1-1-1
   -5:  10: -1-1-1-1-1
   -6:  12: -1-1-1-1-1-1
   -7:  14: -1-1-1-1-1-1-1
   -8:  16: -1-1-1-1-1-1-1-1
   -9:  14: -(1+1+1)^(1+1)
  -10:  16: -(1+1+1)^(1+1)-1

As you can see, the negative ones are always one byte (the leading -) longer than the corresponding positive ones.
The base idea is the same as the previous program: find a square near our target number, and represent its root and the remainder recursively.
But now we allow our square being also some larger than the target number, which then makes the remainder negative.
(The +0.5 can be changed to a different constant to tweak the algorithm, but it seems that I already did hit the optimum here – both 0.4 and 0.6 give worse results.)
To make negative values negative (and otherwise have the same structure as the positive ones, we pass the operator sign to our recursive function p – that is either "+" or "-". We can use that for the joiner in the trivial cases (i.e. n < 9) as well as for the remainder if it's positive, and use the opposite sign for the remainder if it is negative.
The proof function handles the initial sign (with a special case for 0), the p function does the actual work, with recursion.
Third version, for Ceylon 1.2
import ceylon.language { S=String, I=Integer,e=expand }

// output a base-proof Ceylon expression for an integer
// (i.e. using only 0 and 1 as digits).
//
// Question: http://codegolf.stackexchange.com/q/58084/2338
// My Answer:  http://codegolf.stackexchange.com/a/58122/2338
//
// The goal is to produce an expression as short as possible, with
// the code staying under 512 bytes in length.
//
// This approach is to represent a positive integer as a square
// of a positive integer plus some remainder (where the remainder
// can be negative), and for negative integers replace the + on the
// outer level by -.

S q(I n) =>
        n == 0 then "0"
        else (n < 0 then "-" + p(-n, "-")
            else p(n, "+"));

// cache for values of p
variable Map<[I, S],S> c = map { };

// Transforms a positive number into a base-proof term, using
// the given sign for the summation on the outer level.
S p(I n, S s) {
    S v =
    // look into the cache
            c[[n, s]] else (
        // hard-code small numbers
        n < 8 then s.join([1].repeat(n)))
            else
    // do the complicated stuff
    (let (a = "+-".replace(s,""))
            e(e {
                    for (x in 2..8) // try these exponents
                        let (l = (n ^ (1.0 / x)).integer) // \[ sqrt[exp]{n} \] in LaTeX
                            { for (r in l:2) // lowerRoot, lowerRoot + 1
                                    if (r > 1)
                                        let (w = r ^ x)
                                            { if (w-n < n) // avoid recursion to larger or same number
                                                    // format the string as  r^x + (n-w)
                                                    "(" + p(r, "+") + ")^(" + p(x, "+") + ")" +
                                                            (w < n then s + p(n - w, s)
                                                                else (n < w then a + p(w - n, a)
                                                                    else ""))
                                            } } })
            // and now find the shortest formatted string
                .reduce<S>((x, y) => x.size < y.size then x else y))
    // this should never happen, but we can't tell the compiler
    // that at least some of the iterables are non-empty due to the if clause.
            else "";

    // this builds a new cache in each step – quite wasteful,
    // as this also happens when the value was found in the cache,
    // but we don't have more characters remaining.
    //// c = map { [n, s] -> v, *c };
    ///better way:
     c = [n,s] in c then c else map{[n,s]->v, *c};
    return v;
}

The golfed version (i.e. comments and whitespace removed) is posted at the top, at exactly 509 bytes of code.
This uses the same base principle as the second version, but instead of just squares, it also tries to use higher powers of numbers (trying exponents from 2 to 8), and uses the shortest result. It also caches the results, as otherwise this would be unacceptably slow for larger numbers with many recursive calls.
Scoring:
Total positive: 36622
Average positive: 36.622
Total negative: 37623
Average negative: 37.58541458541458
With bonus:33.826873126873124
Overall score: 35.22443656343656

The big indented construct in the middle are three nested iterable comprehensions, the inner two inside a let expression. These are then unnested using the expand function twice, and the reduce function finds the shortest of those strings.
I've filed a feature request to be able to do this in a single comprehension.
Inside the comprehension, we are building a string from the root r, the exponent x and the remainder (n-w or w-n).
The let expression and the map function are new in Ceylon 1.2. map could have been replaced by HashMap (which would have needed more characters for the import, although it would probably be even faster, as I wouldn't build the map new for each new entry). The let expressions like let (w = r ^ x) could have been replaced by using an if clause like if(exists w = true then r ^ x) (and then I wouldn't have needed the two expand calls either), but this would still be a bit longer, not fitting inside the 511 allowed bytes.
Here the sample outputs corresponding to those selected above, all of them except the really small numbers are shorter:
   27:  15: (1+1+1)^(1+1+1)
   28:  17: (1+1+1)^(1+1+1)+1
   29:  19: (1+1+1)^(1+1+1)+1+1
   30:  21: (1+1)^(1+1+1+1+1)-1-1
   31:  19: (1+1)^(1+1+1+1+1)-1
   32:  17: (1+1)^(1+1+1+1+1)
   33:  19: (1+1)^(1+1+1+1+1)+1
   34:  21: (1+1)^(1+1+1+1+1)+1+1

  -27:  16: -(1+1+1)^(1+1+1)
  -28:  18: -(1+1+1)^(1+1+1)-1
  -29:  20: -(1+1+1)^(1+1+1)-1-1
  -30:  22: -(1+1)^(1+1+1+1+1)+1+1
  -31:  20: -(1+1)^(1+1+1+1+1)+1
  -32:  18: -(1+1)^(1+1+1+1+1)
  -33:  20: -(1+1)^(1+1+1+1+1)-1
  -34:  22: -(1+1)^(1+1+1+1+1)-1-1

  993:  39: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1-1-1
  994:  37: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1-1
  995:  35: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1
  996:  33: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1
  997:  31: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1
  998:  29: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1
  999:  27: ((1+1+1)^(1+1)+1)^(1+1+1)-1
 1000:  25: ((1+1+1)^(1+1)+1)^(1+1+1)

 -993:  40: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1+1+1
 -994:  38: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1+1
 -995:  36: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1
 -996:  34: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1
 -997:  32: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1
 -998:  30: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1
 -999:  28: -((1+1+1)^(1+1)+1)^(1+1+1)+1
-1000:  26: -((1+1+1)^(1+1)+1)^(1+1+1)

    1:   1: 1
    2:   3: 1+1
    3:   5: 1+1+1
    4:   7: 1+1+1+1
    5:   9: 1+1+1+1+1
    6:  11: 1+1+1+1+1+1
    7:  13: 1+1+1+1+1+1+1
    8:  13: (1+1)^(1+1+1)
    9:  13: (1+1+1)^(1+1)
   10:  15: (1+1+1)^(1+1)+1

    0:   1: 0
   -1:   2: -1
   -2:   4: -1-1
   -3:   6: -1-1-1
   -4:   8: -1-1-1-1
   -5:  10: -1-1-1-1-1
   -6:  12: -1-1-1-1-1-1
   -7:  14: -1-1-1-1-1-1-1
   -8:  14: -(1+1)^(1+1+1)
   -9:  14: -(1+1+1)^(1+1)
  -10:  16: -(1+1+1)^(1+1)-1

For example, now we have 1000 = (3^2 + 1)^3, instead of 1000 = (6^2-4)^2-5^2+1.

I did wrongly remember the program restriction as 256 bytes ... in 512 quite a bit more can be done. Will try that later.

Nah, it says less than 512. Sou you can use a max. of 511 bytes ;)

How have I never heard of this language?!? :O But seriously, excellent explanation! I love to understand the techniques others use in their answers. +1

@ETHproductions I also only read of it about two weeks ago here on the site, and started to like it. So to get to know it better, I try to answer questions here using Ceylon.

ß/BrainFuck, 34.201 points
ß source (194B):
E='++[------>+<]>++'°\c[1]<0°{E&='.'µA=ß"-ß°°c[1]),'')µE&='+++'°/B=1°(A[0]°\A[B]='.'°{µE&='--.++'°]E&=ß~A'+',A[B])&'.'&ß~A'-',A[B])°}°)°'ß"&E,'+-')+ß"&E,'-+')>0µE=ß"'ß"'E,'-+',''),'+-','')°!€E)

If someone is interested, I'll add an explanation. The BF output is pretty optimized already, but I guess I could use the remaining 318B of ß code to implement

a loop-nesting-optimization,
more 8bit overflow shortcuts,
operator collision removal.

Samples:
Running in windows:
$ sharps encode.ss 42
++[------>+<]>+++++++++.--.--

$ sharps encode.ss -42
++[------>+<]>++.+++++++.--.--

$ sharps encode.ss 1.427
++[------>+<]>++++++.---.++++++.--.+++++.-------

$ sharps encode.ss -946.427
++[------>+<]>++.++++++++++++.-----.++.--------.++++++.--.+++++.-------

Running in linux:
$ WINEDEBUG=-all wine sharps source.ss -4.72
++[------>+<]>++.+++++++.------.+++++++++.-----.--

Validate in the online BF interpreter.
Scores:

Base average = 37.495.
Decimal average = 60.959 * 0.5 = ~30.48.
Negative avg. = 38.4765234765235 * 0.9 = ~34.629
Avg of the above, final score = (37.495 + 30.48 + 34.629)/3 = 34.201.

I always like to see the new languages folks have created. :) Thanks for the score breakdown! I'd like to put more of a bonus on the decimal portion, so I've changed the deduction from 40% to 50%.

@ETHproductions Yeah, I'll try setting up an online interpreter for this. There are about 435 highly abstract operators, additional 9,9k can be defined ;-) . I've corrected the calculation (hopefully).

Ruby/Ruby, 29.77885
31.873*0.9 (negative) 30.872 (positive).
Basic strategy is symmetrical base 3 representation ("balanced ternary"), ie when the digits are -1,0,1 instead of 0,1,2
#function
f=->n{m=n
  a='0'
  7.times{|i|
    r=m%3;r-=r/2*3
    m=(m-r)/3
    #produce expression: replace 0 with (0*x+-1)
    #only add 0*x if there are higher base 3 digits to follow.
    #only add (..+-1) if the current base 3 digit is nonzero.
    a.sub!('0',['','(','('][r]+(m.abs>0?'0*x':'')+['','+1)','-1)'][r])
  }
  #tidy up expression
  a.sub!('(-1)*','-')          #remove internal (-1)*
  a.sub!('(+1)*','')           #remove internal (+1)*
  a[-1]==')' && a=a[1..-2]     #remove unnecessary global brackets
  a.sub!('x','(x=1+1+1)')      #find the first x and define it as 1+1+1=3
  #special cases for small numbers
  n.abs<8 && a=n==0?'0':['','1'+'+1'*(n-1).abs,'-1'*n.abs][n<=>0]
  a
}

#call like this
(1..1000).each{|p|
b=f.call(p)
puts b

Here's the output from 0 to 40 before cleanup
(+1)
((+1)*x-1)
(+1)*x
((+1)*x+1)
(((+1)*x-1)*x-1)
((+1)*x-1)*x
(((+1)*x-1)*x+1)
((+1)*x*x-1)
(+1)*x*x
((+1)*x*x+1)
(((+1)*x+1)*x-1)
((+1)*x+1)*x
(((+1)*x+1)*x+1)
((((+1)*x-1)*x-1)*x-1)
(((+1)*x-1)*x-1)*x
((((+1)*x-1)*x-1)*x+1)
(((+1)*x-1)*x*x-1)
((+1)*x-1)*x*x
(((+1)*x-1)*x*x+1)
((((+1)*x-1)*x+1)*x-1)
(((+1)*x-1)*x+1)*x
((((+1)*x-1)*x+1)*x+1)
(((+1)*x*x-1)*x-1)
((+1)*x*x-1)*x
(((+1)*x*x-1)*x+1)
((+1)*x*x*x-1)
(+1)*x*x*x
((+1)*x*x*x+1)
(((+1)*x*x+1)*x-1)
((+1)*x*x+1)*x
(((+1)*x*x+1)*x+1)
((((+1)*x+1)*x-1)*x-1)
(((+1)*x+1)*x-1)*x
((((+1)*x+1)*x-1)*x+1)
(((+1)*x+1)*x*x-1)
((+1)*x+1)*x*x
(((+1)*x+1)*x*x+1)
((((+1)*x+1)*x+1)*x-1)
(((+1)*x+1)*x+1)*x
((((+1)*x+1)*x+1)*x+1)

And after cleanup
0
1
1+1
1+1+1
1+1+1+1
1+1+1+1+1
1+1+1+1+1+1
1+1+1+1+1+1+1
(x=1+1+1)*x-1
(x=1+1+1)*x
(x=1+1+1)*x+1
((x=1+1+1)+1)*x-1
((x=1+1+1)+1)*x
((x=1+1+1)+1)*x+1
(((x=1+1+1)-1)*x-1)*x-1
(((x=1+1+1)-1)*x-1)*x
(((x=1+1+1)-1)*x-1)*x+1
((x=1+1+1)-1)*x*x-1
((x=1+1+1)-1)*x*x
((x=1+1+1)-1)*x*x+1
(((x=1+1+1)-1)*x+1)*x-1
(((x=1+1+1)-1)*x+1)*x
(((x=1+1+1)-1)*x+1)*x+1
((x=1+1+1)*x-1)*x-1
((x=1+1+1)*x-1)*x
((x=1+1+1)*x-1)*x+1
(x=1+1+1)*x*x-1
(x=1+1+1)*x*x
(x=1+1+1)*x*x+1
((x=1+1+1)*x+1)*x-1
((x=1+1+1)*x+1)*x
((x=1+1+1)*x+1)*x+1
(((x=1+1+1)+1)*x-1)*x-1
(((x=1+1+1)+1)*x-1)*x
(((x=1+1+1)+1)*x-1)*x+1
((x=1+1+1)+1)*x*x-1
((x=1+1+1)+1)*x*x
((x=1+1+1)+1)*x*x+1
(((x=1+1+1)+1)*x+1)*x-1
(((x=1+1+1)+1)*x+1)*x
(((x=1+1+1)+1)*x+1)*x+1

I believe it's called "balanced ternary".

@ThomasKwa edited in, thanks

Ruby/dc, 20.296 18.414 16.968
Dynamic programming! Defines a list of functions that, given a dc instruction, return a new expression and the numeric value of that expression. Then, starting with 1 prefined, it builds a list of all reachable values up to and including the wanted value.
edit:
Added a function for n-1 and made it run the algorithm through multiple passes. It seems to need 7 passes to stabilize. Had to shorten some variable names to stay within 512 bytes.
edit 2:
Added functions for n(n-1), n(n+1) and n^3 while I was at it. Shortened the code some more, landing at exactly 512 bytes.
N = gets.to_i

fns = [
  ->(n,s){[n-1,   s+'1-']},
  ->(n,s){[n+1,   s+'1+']},
  ->(n,s){[n*2,   s+'d+']},
  ->(n,s){[n*3,   s+'dd++']},
  ->(n,s){[n*~-n, s+'d1-*']},
  ->(n,s){[n*n,   s+'d*']},
  ->(n,s){[n*-~n, s+'d1+*']},
  ->(n,s){[n*n*n, s+'dd**']},
]

lst = []*(N+1)
lst[0..2] = %w[0 1 1d+]

loop do
  prev = lst.dup

  (1..N).each do |n|
    fns.each do |f|
      m,s = f[n, lst[n]]
      lst[m] = s if m <= N && (lst[m].nil? || lst[m].size > s.size)
    end
  end

  break if lst == prev
end

puts lst[N]

Generated numbers:
Output consists entirely of five different characters: 1 pushes the value 1 on the stack; d duplicates the top of the stack; +, -, and *  pops the two top values and pushes their sum, difference, and product, respectively. Each generated expression adds only one value to the stack after execution.
   1: 1
   2: 1d+
   3: 1dd++
   4: 1d+d+
   5: 1d+d+1+
   6: 1d+dd++
   7: 1d+dd++1+
   8: 1d+dd**
   9: 1dd++d*
  10: 1d+d+1+d+
  11: 1d+d+1+d+1+
  12: 1dd++d1+*
  13: 1dd++d1+*1+
  14: 1d+dd++1+d+
  15: 1d+d+d*1-
  16: 1d+d+d*
  17: 1d+d+d*1+
  18: 1dd++d*d+
  19: 1dd++d*d+1+
  20: 1d+d+d1+*
  21: 1d+d+d1+*1+
  22: 1d+d+1+d+1+d+
  23: 1d+dd**dd++1-
  24: 1d+dd**dd++
  25: 1d+d+1+d*

...
 989: 1d+d+d*d+d1-*1-1-1-
 990: 1d+d+d*d+d1-*1-1-
 991: 1d+d+d*d+d1-*1-
 992: 1d+d+d*d+d1-*
 993: 1d+d+d*d+d1-*1+
 994: 1d+d+d*d+d1-*1+1+
 995: 1d+d+d*d+d1-*1+1+1+
 996: 1d+d+1+dd**d+1-d+d+
 997: 1d+d+1+d+dd**1-1-1-
 998: 1d+d+1+d+dd**1-1-
 999: 1d+d+1+d+dd**1-
1000: 1d+d+1+d+dd**

Pretty good, beating everything but z80 machine code so far (even Dennis' CJam!). Do you think you might be able to add in a - operator while staying within the byte count?

@ETHproductions How's that? ;) It shouldn't be hard to add negative numbers now, either.

Python 2.6, 78.069 - 66.265 points
Submitting my answer for what it's worth (not a lot in this case ... but clearly demonstrating that for this challenge it's not enough to simply think of composing the output as a sum of bit-shifted values; when taken into account that no digits outside of 0 or 1 may  appear in the output). I might come back later with a different way of generating output.
The code itself is not too long (176 characters):
def f(a):return'+'.join(('(1<<%s)'%['0','+'.join('1'*x)][x>0]).replace('(1<<0)','1')for x in[i for i,e in enumerate(bin(a)[::-1][:-2])if int(e)])
print"".join(f(int(input())))

It generates correct but verbose output:
17
1+(1<<1+1+1+1)

800
(1<<1+1+1+1+1)+(1<<1+1+1+1+1+1+1+1)+(1<<1+1+1+1+1+1+1+1+1)

Snippet that calculates the score:
def f(a):return'+'.join(('(1<<%s)'%['0','+'.join('1'*x)][x>0]).replace('(1<<0)','1')for x in[i for i,e in enumerate(bin(a)[::-1][:-2])if int(e)])
print sum(len("".join(f(i)))for i in range(1000))


text:
Crazy Librarian's Amazing Sorting System
It's back to school season! So for a part-time job, you're helping out at the school's library. The problem is, the head librarian has never even heard the words "Dewey Decimal," let alone implemented that system. Instead, the sorting system in use has grown "organically" as the library has expanded...
In an effort to keep your sanity, you've elected to write a program to help you sort books as they're returned, because woe unto you if you sort the books wrong. (The head librarian is VERY strict.)
Input / Output

The input will be a list of (hypothetical) book titles, one per line, from STDIN / language equivalent.
You can assume no more than 100 books input at a time (you can only carry so many around the library at once).
Books can have multiple words in their titles, and these words may be separated by spaces or other punctuation (e.g., a colon:, a dash-, etc.).
For ease of calculation, assume all titles are UTF-8.

Output is the same titles, sorted according to the below rules, again one per line, to STDOUT / language equivalent.
The Sorting Rules
Books are sorted numerically based on their average character value (i.e., cumulative character value divided the number of characters in the book title), counted by the following rules:

All characters count for determining the number of characters in a title.
Lowercase letters are counted by their position in the alphabet. (a=1,b=2,...z=26)
If the title contains capital letters, those count for 1.5 their lowercase value (A=1.5,B=3,...Z=39). ("Capital letters are important!" says the librarian.)
Each punctuation mark / symbol in this list !@#$%^&*()-=_+[]\{}|;':",./<>?~ counts -1 from the cumulative value before averaging. ("Grandiose titles are not!")
If the title contains a number, written in Arabic numerals, that number is subtracted from the average value before sorting. Multiple consecutive digits are treated as one number (e.g., 42 would subtract 42, not subtract 4 and then subtract 2). Individual digits don't count for the cumulative value (i.e., each digit contributes 0), but DO count for number of characters. Note that this may result in a negative value and should be treated appropriately. (Rumor has it, the librarian has had a crush on a math instructor for several years, now.)
If the title contains two separate words that start with an R, the book gets a score of "infinity" and is dumped into a pile in the corner (i.e., randomly arranged at the end of the list). (The librarian was once dumped by a person with those initials, or so you've heard.)
Spaces don't count for the cumulative character value (i.e., they contribute 0), but DO contribute to the number of characters in a title.
Characters that don't fit the above rules (e.g, a ÿ) don't count for the cumulative character value (i.e., they contribute 0), but DO contribute to the number of characters in a title.
For example, a hypothetical book ÿÿÿÿÿ would have a "score" of (0+0+0+0+0) / 5 = 0, but a hypothetical book ÿÿyÿÿ would have a "score" of (0+0+25+0+0) / 5 = 5.
Two books that happen to "score" the same can be Output in your choice of order. (They're on the same shelf, anyway)

Example Input 1
War and Peace
Reading Rainbow: The Best Unicorn Ever
Maus
Home for a Bunny

Example Output 1 (with "scores" in parentheses to show reasoning - you don't need to print them)
War and Peace (8.5)
Home for a Bunny (10.125)
Maus (15.125)
Reading Rainbow: The Best Unicorn Ever (infinity)

Example Input 2
Matthew
Mark
Luke
John
Revelations

Example Output 2 (with "scores" in parentheses to show reasoning - you don't need to print them)
Mark (12.375)
John (13)
Revelations (13.545454...)
Luke (13.75)
Matthew (~13.786)

Example Input 3
42
9 Kings
1:8
7th

Example Output 3 (with "scores" in parentheses to show reasoning - you don't need to print them)
42 (-42)
1:8 (-9.3333...)
9 Kings (~0.36)
7th (2.3333...)

Other restrictions

This is Code-Golf, because you need to keep the program secret from the ever-watching eyes of the librarian, and the smaller the program, the easier it is to hide.
Standard loophole restrictions apply
Don't let the librarian catch you slacking off by spending all your time on PPCG.

What if two books score exactly the same. i.e i Have Reading Rainbow and Ruby Rails

@KishanKumar In that specific instance, "randomly arranged at the end of the list" since they're both double-R. In other words, take your pick. In the general case, if two words score the same, they can appear in any order relative to each other. I'll add a bullet to clarify that.

You need an A word so your system has an acronym name. I recommend Crazy Librarian's Amazing Sorting System :D

@Geobits Do you have CLASS?

Numbers are just decimal numbers? What if there are several ones, are all of them subtracted separately?

@PaŭloEbermann Strictly speaking, they're Integers, as the . is considered punctuation and handled separately. Yes, if there are multiple numbers in the input they are each subtracted, as in the 1:8 in the 4th example -- (0+-1+0)/3 - (1+8) = -9.333....

But only integers in decimal notation using the digits 0 to 9, not octal, hexadecimal or strange Chinese characters, right?

@PaŭloEbermann Yes, Arabic numerals (what Unicode would call "European digits") only. Other characters should be handled as the ÿ example. I've edited the numbers portion for clarification.

Also, 9 Kings is (-9 + 0 + 1,5*11 + 9 + 14 + 7 + 19)/7 = ~8,07, 7th = (-7+20+8)/3 = 7 and 1:8 = (-1 + 0 - 8)/3 = -3

@Zereges No - integer values are subtracted after you average and before you sort, not as part of the averaging. The digits count as zero. For 7th that means (0+20+8)/3 - 7 = 2.333. for example. I expanded out the 1:8 example three comments up. Let me know if that's still not clear.

Can you confirm that the symbols (scoring -1) are all the ASCII printable characters (ascii code 32 to 126) except alphanumeric, space (32), backslash (92) and backtick (92) ?

@edc65 You're correct, excepting that backslash (92) is included in the symbols list on this challenge. The backtick (96) is not included in the symbols list on this challenge. However, do note that this challenge is anticipating Unicode input/output.

Right ... the backslash was eaten when I ported the string in javascript code. Thanks

Can we assume a maximum title lenght?

@fschmengler Sure. I'm not picky on that, so choose something reasonable (e.g., 50+) if it impacts your code length. None of the private tests that I have should get anywhere close to overflowing a buffer or suffering from wrapping an int or the like.

Can I expect no title to have two capital R's in one word?

@Padarom Like a CamelCase word? I don't have a test case that explicitly tests that one way or the other, but you should ensure that your algorithm doesn't match any capital R, just those that are at the beginning of the words.

Okay, that's what I was trying to find out, thanks!

It would be so awesome to have an Ook! entry here...

APL (132)
{⎕ML←3⋄⍵[⍋{2='R'+.=↑¨⍵⊂⍨⍵≠' ':!99⋄↑(+/⍎¨'0',⍵⊂⍨⍵∊⎕D)-⍨((+/∊1.5 1×(⍳×∊⍨)∘⍵¨G)-+/⍵∊(⎕UCS 32+⍳94)~'`',⎕D,∊G←(⊂⎕A),⊂⎕UCS 96+⍳26)÷⍴⍵}¨⍵]}

Since everyone else is doing the same thing, this too is a function that takes an array of titles and returns it sorted, e.g.:
      titles
┌─────────────┬──────────────────────────────────────┬────┬────────────────┬───────┬────┬────┬────┬───────────┬──┬───────┬───┬───┐
│War and Peace│Reading Rainbow: The Best Unicorn Ever│Maus│Home for a Bunny│Matthew│Mark│Luke│John│Revelations│42│9 Kings│1:8│7th│
└─────────────┴──────────────────────────────────────┴────┴────────────────┴───────┴────┴────┴────┴───────────┴──┴───────┴───┴───┘

      {⎕ML←3⋄⍵[⍋{2='R'+.=↑¨⍵⊂⍨⍵≠' ':!99⋄↑(+/⍎¨'0',⍵⊂⍨⍵∊⎕D)-⍨((+/∊1.5 1×(⍳×∊⍨)∘⍵¨G)-+/⍵∊(⎕UCS 32+⍳94)~'`',⎕D,∊G←(⊂⎕A),⊂⎕UCS 96+⍳26)÷⍴⍵}¨⍵]}titles
┌──┬───┬───────┬───┬─────────────┬────────────────┬────┬────┬───────────┬────┬───────┬────┬──────────────────────────────────────┐
│42│1:8│9 Kings│7th│War and Peace│Home for a Bunny│Mark│John│Revelations│Luke│Matthew│Maus│Reading Rainbow: The Best Unicorn Ever│
└──┴───┴───────┴───┴─────────────┴────────────────┴────┴────┴───────────┴────┴───────┴────┴──────────────────────────────────────┘

Explanation:

⎕ML←3: set ⎕ML to 3 (for ⊂)
⍵[⍋{...}¨⍵]: sort the input by the values returned from the inner function

↑¨⍵⊂⍨⍵≠' ': get the first character of each word
2='R'+.=: see if two of these are 'R'.
:!99: if so, return 99! (≈ 9.3×10155). This is not quite infinity, but it'll do: a title can never have a score more than 38 times its length (ZZZZ...), so as long as no single title is bigger than about 2×10130 yottabytes, it is guaranteed that these will be at the end.
⋄: otherwise:
(...)÷⍴⍵: divide the score by the length of ⍵ after calculating it:

G←(⊂⎕A),(⎕UCS 96+⍳26): store in G the uppercase and lowercase letters
(⎕UCS 32+⍳94)~'`',⎕D,∊G: the printable ASCII characters, except letters, digits, spaces and '`', which are the characters for which a point is subtracted. (This is shorter than writing them all out, because G is used later on.)
+/⍵∊: count the amount of these characters in ⍵
-: subtract this from:
+/∊1.5 1×(⍳×∊⍨)∘⍵¨G: the sum of 1.5 × the scores for the capitals, and 1 × the scores for the lowercase letters.

-⍨: afterwards, subtract the total of the numbers in ⍵:

⍵⊂⍨⍵∊⎕D: find the groups of digits in ⍵
'0',: add '0', to prevent the list being empty
⍎¨: evaluate each string
+/: find the sum

Instead of !99 you could use ⌊/⍬

I love looking at long code in APL. It makes me feel like the world is so much large than I. And I like symbols.

Lua 5.3, 366 364 Bytes
r={}for i,s in ipairs(arg)do n=0 s:gsub("%l",function(a)n=n+(a:byte()-96)end):gsub("%u",function(a)n=n+(a:byte()-64)*1.5 end):gsub("%p",function(a)n=n-1 end):gsub("^R?.- R.- ?R?",function()n=math.huge end)m=n/utf8.len(s)s:gsub("%d+",function(a)m=m-a end)table.insert(r,{s=s,n=m})end table.sort(r,function(a,b)return a.n<b.n end)for i,v in ipairs(r)do print(v.s)end

This code only works in Lua 5.3 because it needs to deal with Unicode characters. If you don't care about Unicode, then replace "utf8" with "string" and it will work fine with Lua 5.2 or 5.1.
It takes its inputs from command-line arguments, so either run it from the command line or put this code above my answer:
arg = {"Title 1", "Title 2", "Title 3"}

I don't have Lua 5.3 on my machine, but I followed your suggestion to swap utf8 with string on Ideone and got no output.

@TimmyD see my edit

Good. Gravy. And (arg) is sitting there staring me in the face. This question has apparently fried my brain. Have a +1.

With MoonScript, this is 266 bytes: http://pastebin.com/wr4qVs5h.

JavaScript (ES6), 210 218 251
As a function with an array argument, returned sorted.

f=L=>(S=s=>([...s].map(c=>t-=(a=s.charCodeAt(l++))>32&a<48|a>57&a<65|a>90&a<96|a>122&a<127?1:a>64&a<123?96-(a<96?a*1.5:a):0,l=t=0),s.split(/\D/).map(n=>t-=n,t/=l),t/!s.split(/\bR/)[2]),L.sort((a,b)=>S(a)-S(b)))

//TEST

test1=['War and Peace','Reading Rainbow: The Best Unicorn Ever','Maus','Home for a Bunny']
test2=['Matthew','Mark','Luke','John','Revelations']
test3=['42','9 Kings','1:8','7th']

;O.innerHTML=f(test1)+'\n\n'+f(test2)+'\n\n'+f(test3);

// The comparing function used to sort, more readable

Sort=s=>(
  t = 0, // running total
  l = 0, // to calc the string length avoiding the '.length' property
  [...s].map(c=>{
    a=s.charCodeAt(l++);
    t-=a>32&a<48|a>57&a<65|a>90&a<96|a>122&a<127
      ? 1 // symbols (ASCII char except space, alphanumeric and backtick)
      : a>64&a<123
        ? 96-(a<96?a*1.5:a) // alphabetic both upcase and lowcase, and backtick
        // lowcase: 96-a, upcase (64-a)*1.5=>96-a*1.5, backtick is 96 and 96-96 == 0
        : 0 // else space, non ASCII, and numeric : 0
  }),
  t = t/l, // average
  s.split(/\D/).map(n=>t-=n), // sub number values
  f = s.split(/\bR/)[2], // split at words starting with R, if less then 2 f is undefined
  t/!f // dividing by not f I can get the infinity I need
)

Nicely done. For reference to anyone else reading this answer, I had to change O.innerHTML to this.InnerHTML in Firefox's console.

Mathematica, 253 216 bytes (214 chars)
r=RegularExpression;c=ToCharacterCode;f=SortBy[Tr@Flatten@Reap[StringCases[#,
{r@"(\\bR.*)+"->∞,r@"\\d+":>0Sow@-FromDigits@"$0",r@"[a-z]":>c@"$0"-96,
r@"[A-Z]":>1.5c@"$0"-96,r@"[!-/:-@[-_{-~]"->-1}]/StringLength@#]&]

Call the function like f[{"42", "9 Kings", "1:8", "7th"}]; it will return a sorted list of the inputs.
Just barely made it!  Mathematica's pattern matching is not as concise when strings are involved, and I just get killed by those long names.  The extra two bytes are for the Infinity unicode character.
(Let me know if I've fallen afoul of any Standard Loopholes.)
Update
Looking a little closer at edc65's answer, it looks like the OP will accept a function that sorts a list of strings.  With that in mind we can use the curried form of SortBy (which Mathematica calls the "operator form"); with one argument (the function applied to the list elements to determine their order) it behaves like a function that takes one argument, returning the sorted form of the input; that is, SortBy[list, f] is equivalent to (SortBy[f])[list].
Ungolfed
Function[{titles},
  SortBy[titles, Function[{str}, (* sort by function value *)
    Total[Flatten[Reap[ (* total up all the parts *)
      StringCases[str, {
        RegularExpression["(\\bR.*){2}"] -> Infinity
          (* matches R at the start of a word twice, adds infinity to the total *),
        RegularExpression["\\d+"] :> 0 * Sow[-FromDigits["$0"]]
          (* matches a number, Sows it for Reap to collect, then multiplies by zero
                                                          to not affect the average *),
        RegularExpression["[a-z]"] :> ToCharacterCode["$0"] - 96
          (* matches a lowercase letter and returns its value *),
        RegularExpression["[A-Z]"] :> 1.5 ToCharacterCode["$0"] - 96
          (* matches an uppercase letter and returns 1.5 its value *),
        RegularExpression["[!-/:-@[-_{-~]"] -> -1
          (* matches a 'grandiose' symbol and returns -1 *)
      }] / StringLength[#] (* averages character values *)
    ]]]
  ]]
]

Nice answer, and you get an Internet Cookie for literally using "infinity" in your calculations ;-).

@TimmyD The beauty of symbolic math processing =)

Probably you mean 214 chars, 216 bytes. Well done, I tried to compete but no way

C#, 352 349 Bytes
Due to the magic of linq:

class A{static void Main(string[]a){foreach(var x in a.OrderBy(b=>{var s="0";int j=0;return Regex.Split(b,@"[^\w]+").Count(l=>l[0]=='R')==2?(1/0d):b.Aggregate(0d,(d,e)=>{if(e>47&e<58){s+=e;return d;}d+=(e>64&e<91)?(e-64)*1.5:(e>96&e<123)?e-96:e>32&e<127&e!=96?-1:0;j+=int.Parse(s);s="0";return d;})/b.Length-j-int.Parse(s);}))Console.WriteLine(x);}}

Could have saved another 6 bytes if backtick would be included in the punctuation list!

class A
{
    static void Main(string[] a)
    {
        foreach (var x in a.OrderBy(b =>
            {
                var s = "0";
                int j = 0;
                return Regex.Split(b, @"[^\w]+").Count(l => l[0] == 'R') == 2
                    ? (1 / 0d)
                        : b.Aggregate(0d, (d, e) =>
                        {
                            if (e > 47 & e < 58) { s += e; return d; }
                            d += (e > 64 & e < 91) ? (e - 64) * 1.5 : (e > 96 & e < 123) ? e - 96 : e > 32 & e < 127 & e != 96 ? -1 : 0;
                            j += int.Parse(s);
                            s = "0";
                            return d;
                        }) / b.Length - j - int.Parse(s);
            }))
            Console.WriteLine(x);
    }

}

Go, 755 Bytes
package main
import("os"
"fmt"
"math"
"bufio"
"regexp"
"sort"
"strconv")
type F float64
type T []F
func(t T)Swap(i,j int){t[i],t[j],S[i],S[j]=t[j],t[i],S[j],S[i]}
func(t T)Len()int{return len(t)}
func(t T)Less(i,j int)bool{return t[i]<t[j]}
var S []string
func main(){var t T
for{b:=bufio.NewReader(os.Stdin)
w,_,_:=b.ReadLine()
if len(w)==0{break}
u:=string(w)
var v F
for _,c:=range u{if 96<c&&c<123{v+=F(c)-F(96)}else
if 64<c&&c<91{v+=(F(c)-64)*1.5}else
if (48>c&&c>32)||(c>57&&c<127){v-=1}}
a:=v/F(len(w))
r,_:=regexp.Compile("[0-9]+")
n:=r.FindAllString(string(w),-1)
for _,x:=range n{y,_:=strconv.Atoi(x);a-=F(y)}
if m,_:=regexp.Match("((^| )R.*){2}",w);m{a=F(math.Inf(1))}
S=append(S,u)
t=append(t,a)}
sort.Sort(t)
for _,o:=range S{fmt.Println(o)}}

The formatted version:
package main

import (
    "bufio"
    "fmt"
    "math"
    "os"
    "regexp"
    "sort"
    "strconv"
)

type F float64
type T []F

func (t T) Swap(i, j int)      { t[i], t[j], S[i], S[j] = t[j], t[i], S[j], S[i] }
func (t T) Len() int           { return len(t) }
func (t T) Less(i, j int) bool { return t[i] < t[j] }

var S []string

func main() {
    var t T
    for {
        b := bufio.NewReader(os.Stdin)
        w, _, _ := b.ReadLine()
        if len(w) == 0 {
            break
        }
        u := string(w)
        var v F
        for _, c := range u {
            if 96 < c && c < 123 {
                v += F(c) - F(96)
            } else if 64 < c && c < 91 {
                v += (F(c) - 64) * 1.5
            } else if (48 > c && c > 32) || (c > 57 && c < 127) {
                v -= 1
            }
        }
        a := v / F(len(w))
        r, _ := regexp.Compile("[0-9]+")
        n := r.FindAllString(string(w), -1)
        for _, x := range n {
            y, _ := strconv.Atoi(x)
            a -= F(y)
        }
        if m, _ := regexp.Match("((^| )R.*){2}", w); m {
            a = F(math.Inf(1))
        }
        S = append(S, u)
        t = append(t, a)
    }
    sort.Sort(t)
    for _, o := range S {
        fmt.Println(o)
    }
}

Implementing a custom sort interface made it longer than expected. The program reads from STDIN until end of input o a blank line is entered.

PHP, 362 367 Bytes
<?for(;$w=fgets(STDIN);$S[]=$w){for($l=$i=mb_strlen($w);$i--;){$c=array_sum(unpack("C*",mb_substr($w,$i,1)));96<$c&&$c<123 and $v+=$c-96 or 64<$c&&$c<91 and $v+=1.5*$c-96 or 48<$c&&$c>32||$c>57&&$c<127 and $v-=1;}$v/=$l;preg_match_all("/\d+/",$w,$m);$v-=array_sum($m[0]);preg_match("/((^| )R.*){2}/",$w)&&$v=INF;$t[]=$v;}array_multisort($t,$S);echo join("
",$S);

Formatted version:
<?php
for (; $w = fgets(STDIN); $S[] = $w) {
    for ($l = $i = mb_strlen($w); $i--;) {
        $c = array_sum(unpack("C*", mb_substr($w, $i, 1)));
        96 < $c && $c < 123 and $v += $c - 96
        or 64 < $c && $c < 91 and $v += 1.5 * $c - 96
        or 48 < $c && $c > 32 || $c > 57 && $c < 127 and $v -= 1;
    }
    $v /= $l;
    preg_match_all("/\d+/", $w, $m);
    $v -= array_sum($m[0]);
    preg_match("/((^| )R.*){2}/", $w) && $v = INF;
    $t[] = $v;
}
array_multisort($t, $S);
echo join("
", $S);

Interesting lines:
$c = array_sum(unpack("C*", mb_substr($w, $i, 1)));

Converts a single UTF-8 character to its byte values and sums them, so that we get the real value for ASCII characters and a value higher than 127 for multibyte characters.
96 < $c && $c < 123 and $v += $c - 96
or 64 < $c && $c < 91 and $v += 1.5 * $c - 96
or 48 < $c && $c > 32 || $c > 57 && $c < 127 and $v -= 1;

Makes use of low operator precedence of and and or to assign the character value in a single statement without if.

Perl 5, 190 bytes
sub p{$_=pop;chomp;$c=-y/A-Za-z0-9 \\`//c;map$c+=(32&ord$_?1:1.5)*(31&ord),/[a-z]/gi;$c/=length;map$c-=$_,/\d+/g;$c}say(sort{$y=$b=~/\bR.*\bR/;($x=$a=~/\bR.*\bR/)||$y?$x-$y:(p($a)<=>p$b)}<>)

Try it online!


text:
Drop of Chaos (Constructing a Minimally Aperiodic Sequence)
The idea here is to produce an almost repeating pattern. That is, the sequence being constructed changes at the last moment to avoid a repetition of some subsequence. Subsequences of the type AA and ABA are to be avoided (where B is no longer than A).
Examples:
I'll go ahead and start by listing all of the small examples to make my description clearer. Let's start with 0.
Valid:   0

Invalid: 00    (AA pattern)
Valid:   01

Invalid: 010   (ABA pattern)
Invalid: 011   (AA pattern)
Valid:   012

Valid:   0120
Invalid: 0121  (ABA pattern)
Invalid: 0122  (AA pattern)

Invalid: 01200 (AA pattern)
Invalid: 01201 (ABA pattern; 01-2-01)
Invalid: 01202 (ABA pattern)
Valid:   01203

Now, I strongly believe that a 4 is never needed, though I do not have a proof, because I have easily found sequences of hundreds of characters long that use only 0123. (It's probably closely related to how only three characters are needed to have infinite strings that do not have any AA patterns. There's a Wikipedia page on this.)
Input/Output
Input is a single, positive, non-zero integer n. You may assume that n <= 1000.
Output is an n-character sequence with no subsequences that match either prohibited pattern (AA or ABA).
Sample inputs and outputs

>>> 1
0

>>> 2
01

>>> 3
012

>>> 4
0120

>>> 5
01203

>>> 50
01203102130123103201302103120132102301203102132012

Rules

Only the characters 0123 are allowed.
B is no longer than A. This is to avoid the situation where 012345 has to be followed by 6 because 0123451 has this: 1-2345-1. In other words, the sequence would be trivial and uninteresting.
n may be inputted through any method desired, except hard-coding.
Output may be either a list or a string, depending on which is easier.
No brute force; the run time should be on the order of minutes, at most an hour on a really slow machine, for n=1000. (This is intended to disqualify solutions that just loop through all n-length permutations of {0,1,2,3}, so that trick and similar tricks are disallowed.)
Standard loopholes are disallowed, as usual.
Scoring is in bytes. This is code-golf, so the shortest entry wins (probably - see bonus).
Bonus: pick the lowest allowed digit at each step. If 1 and 3 are possible choices for the next digit in the sequence, pick 1. Subtract 5 bytes from your score. However, take note of the note below.

Note!
Dead-ends are possible. Your program or function must avoid these. Here's an example:

Stump: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012310213012031023013203123021320123102130120
Stump: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012310213012031023013203123021320123102130123
Stump: 012031021301231032013021031201321023012031021320123021031201302310320123021320310230120321023120130210312301320310213012032102301320312302103201231021301203102301320312302132012310320
Stump: 012031021301231032013021031201321023012031021320123021031201302310320123021320310230120321023120130210312301320310213012032102301320312302103201231021301203102301320312302132012310321301203102130

Each of these sequences cannot be extended any further (without using a 4). But also note that there is a crucial difference between the first two and the second two. I'll replace the shared initial subsequence with an X to make this clearer.

Stump: X2130120
Stump: X2130123
Stump: X320
Stump: X321301203102130

The last two digits of X are 10, so the only possible choices for the next digit are 2 and 3. Choosing 2 leads to a situation where the sequence must terminate. The greedy algorithm will not work here. (Not without backtracking, anyway.)

Can one use a brute force strategy of testing every possible string, even if it will not give an output in realistic time? Do you know there to be a solution for all n? If someone gives a heuristic semi-greedy algorithm, how will you check that it does not run into problems for a very large length? The general problem is an interesting one, and I haven't been able to find anything on pattern avoidance where we restrict the length of part of the pattern. If someone can produce a general recipe, I expect that to be the best approach.

I believe I disallowed brute force in the rules. I should probably highlight that. I do not have a proof that there exists a solution for all n, but given that the stumps my program finds tend to get longer by an average of 10 digits each time, I'm very sure that an infinite sequence exists. I'm not sure how a semi-greedy algorithm could be tested for arbitrarily large sequences. I could restrict the requirement to n=1000 and just not worry about higher n.

I suppose AA is really type ABA where B is empty.  This could perhaps help to streamline some solutions.

Retina, 86 bytes - 5 = 81
$
_
(r`^(?<-2>.)+_((.)+)\b$
$1!
\b$
0
3#
#
0#
1
1#
2
2#
3
)r`\1(?<-2>.)*((.)+)$
$0#
!
<empty>

Where <empty> represents an empty trailing line. You can run the above code from a single file with the -s flag.
The input should be given in unary, e.g. 111111. I haven't tested it for output on the order of thousands yet - two of the regexes might get a bit slow after a while - but it can easily handle a couple of hundred in a few seconds.
Explanation
This is a simple backtracking solution.

Append a 0.
While the current sequence is invalid, remove all trailing 3s and increment the last non-3.
Repeat until we have a valid sequence of the desired length.

This backtracking is implemented by a loop of regex substitutions which aborts once the string remains unchanged through one iteration.
$
_

This appends a _ to the input, which is used to separate the unary input from the sequence we're building.
(r`^(?<-2>.)+_((.)+)\b$
$1!

This is the first substitution in the loop (indicated by the leading ().  The regex matches if a) there is a word character (i.e. a digit) at the end the string (which means the string is valid - we'll see below that invalid sequences are marked with a trailing #) and b) there are at least as many characters in the sequence as in the input (this is checked using balancing groups). If that's the case, we remove the input and append a !. This ! serves to make all regexes in the loop fail, such that it terminates.
\b$
0

If there is a word character at the end (i.e. the sequence is valid, and the loop wasn't terminated by the previous step), append a 0.
3#
#

If (instead) the sequence had been marked invalid and ended in 3, we remove that 3 (but leave the sequence as invalid, because there's no possible continuation for the current prefix... so the next character needs to be backtracked as well).
0#
1
1#
2
2#
3

If the sequence is marked invalid and any digit other than 3 is at the end, we increment the digit and remove the marker.
)r`\1(?<-2>.)*((.)+)$
$0#

The last substitution in the loop (as indicated by the )). It checks whether the string ends in ABA (where B is not longer than A but potentially empty). The relative lengths of A and B are again checked using balancing groups, and the repetition of A is checked with a simple backreference.
If this regex matches, we mark the sequence invalid by appending #.
!
<empty>

Once the loop terminates, all we need to do is remove the ! and are then left with the desired output.

Python 2, 175 - 5 = 170 bytes
n=input();s='';u=j=-1
while n>len(s):
 while u>2:u=int(s[0]);s=s[1:]
 u+=1;t=`u`+s;m=c=0
 while t[c:]*0**m:c+=1;i=t[c:].find(t[:c]);m=j<i<=c
 if c>=len(t):s=t;u=j
print s[::j]

This is the greedy algorithm with backtracking.  I wish it were shorter.  I hope it's correct (see below).
It builds the string one digit at a time. Given a string of d digits that it has found already, it tries to append a 0 as the (d+1)st digit.  If that doesn't work, then it tries a 1, then a 2, then a 3.  If none of these works, then it goes back to the dth digit and increments it (if less than 3) or removes it (if equal to 3, in which case it increments the previous one, etc.).
The check for validity is the line with .find in it.  In case anyone decides to read my code, I should say that this program is  actually storing the string backwards, meaning that it's adding digits to the front.  So the check involves looking for places where the first c digits appear again later on in the string (anyplace after the first c digits), and if there are any such places, whether the intervening length is at most c.
(Of course it reverses the string before printing.)
It could also easily be faster; I originally had it exiting various loops early for efficiency, but that cost precious bytes.  It still does OK in the range of n=1000, though.
Anyway, the program does seem to exhibit a preference for the smaller digits, but it's not a very strong preference.  For example, running it with n=2000 gave me a string with 523 zeros, 502 ones, 497 twos and 478 threes, ending in 30210312013021.  So if anyone else is working on a greedy algorithm, maybe they can confirm this result.  Or with n=1000 I got [263, 251, 248, 238] for the counts by digit.
Finally, I would mention that these counts are sort of suggestive of symmetry, almost (though not exactly) as if we had started with a uniform distribution and then converted some of the 3's to 0's and a few of the 2's to 1's.  But obviously that could just be coincidence. I have no idea!

Haskell, 115 (120 bytes − 5 bonus)
x?_|or[t x==t(drop i x)|i<-[1..length x],t<-[take$div(i+1)2]]=[]
x?0=[x]
x?n=(?(n-1)).(:x)=<<"0123"
f=reverse.head.([]?)

Run online at Ideone
Example run:
*Main> f 40
"0120310213012310320130210312013210230120"