Pango Silliness

September 24, 2010 at 17:50 (silly)

Next time you need to buy your friend a birthday present, save money by getting them a deluxe 0-sized Pango board!

Permalink Leave a Comment

Frobenius Numbers – Round Robin Algorithm

September 20, 2010 at 14:50 (algorithm, java, math.NT)

Frobenius numbers are solutions to the coin problem. Let \displaystyle 0<a_1<\cdots<a_n be coin denominations; what is the smallest sum of money that cannot be obtained using these coins? More formally, define the Frobenius number \displaystyle g(a_1,\,\ldots\,,a_n) as the greatest number that is not a linear combination \sum_{i=1}^n x_ia_i with \displaystyle 0 \le x_i \in \mathbb{Z} . The Frobenius number exists if and only if \displaystyle a_1 > 1 and \displaystyle \gcd(a_1,\,\ldots\,,a_n)=1 . A special case of Frobenius numbers involves the interestingly named McNugget numbers, and there is a well-known formula when \displaystyle n=2 given by \displaystyle g(a_1,a_2)=a_1a_2-a_1-a_2 sometimes known as the Chicken McNugget Theorem.

Read the rest of this entry »

Permalink Leave a Comment

SPOJ, ideone, and TEST

September 14, 2010 at 05:53 (computer language, tutorial)

Background: I introduced SPOJ in a previous post.

ideone is an excellent tool that allows you to write and execute code in many languages, all online. It’s basically a pastebin with added functionality, making it an online mini-IDE. It is based on the SPOJ engine but supports some languages that SPOJ does not.

I’m mainly writing this post to report a useful discovery regarding ideone and the first SPOJ problem, TEST. If you happen to know a language like JavaScript and would like to submit a solution to TEST but can’t figure out how I/O is supposed to work, there is an easy solution through ideone. Simply go there, set the language to say JavaScript (rhino) and use the link to insert sample that appears above the textarea. A basic solution to TEST in the given language will magically appear, complete with sample input. This seems to work for just about any language on the list (even Whitespace!), and could come in handy when there is no corresponding thread in the SPOJ forums.

Permalink Leave a Comment

How To: SPOJ TEST Using JAR File

September 12, 2010 at 07:39 (java, tutorial)

Background: Sphere Online Judge (SPOJ) is an online judge system accepting a wide variety of programming languages. It’s a great way to test your skills as a programmer, and can be quite addictive if you like a good challenge.

While browsing the SPOJ forums, I did not find a thread detailing how to successfully submit a JAR for the first problem, TEST. So, here’s a quick guide. I’m using Windows, but there should be little difference with other operating systems since everything is done through the command line. I will assume you already have the JDK installed and paths set up such that if you type java, javac, or jar from the command line the appropriate programs will be executed.

Read the rest of this entry »

Permalink 3 Comments