Our current solutions to the problems in this volume are below. If a problem is not shown here, then we have not posted a solution yet.

#300 - Maya Calendar

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
Solution Description: First, determine how many days have passed since the beginning of time. This is of course year*365 + month*20 + day. Call this quantity X.

The Tzolkin date is:

Year - X / 260
Month - X % 20
Day - (X % 13) + 1

There's an extra one on the day because the days are 1-indexed in Tzolkin, but 0-indexed in Haab.


#305 - Joseph

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:brute force
Solution Description: Use an ArrayList and simulate the 'game'. Record the results from 1 to 13, and hard code them back in. Output.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
simulation
Solution Description: As there are only 13 possible input values, it's easy to brute force the solutions and then write code that just outputs them.

For each k, fill a dynamic array of characters with k 'G's and k 'B's for good guys and bad guys respectively. Then, keep incrementing an m variable and running the simulation. When you find an m that kills all the bad guys first, output it.

In C++ you may be able to get away with actually submitting the brute force code, but it takes about 2 seconds to test all cases in Java, so you should just write a program that outputs the correct answers.


#311 - Packets

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: You'll need a variable to hold space for one's left over, one to hold space for two's left over, and a total count of packages.

When you look at each of the product sizes, it turns out that:

Packaging a 6x6 yields count++
Packaging a 5x5 yields count++, ones+=11 * #of5x5s
Packaging a 4x4 yields count++, twos+= 5* #of4x4s

You can carry on in this fashion for 3's, although you have to handle a little trickiness, since 4 3x3's fit into one package.

Once you hit the twos, you know how many spots in the previous packages there are to fit twos. Subtract the spots available from the 2x2s you have to package. What's left over can go to extra spots for the ones.

Output count

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:greedy
Solution Description: This problem takes a bit of repetitive coding, but it isn't as bad as some of the simulations out there.

Greedily fit the largest packets possible into each box. So first, you need one box for each 6x6 packet. Then, for each 5x5 packet, you can fit up to 11 1x1 packets in the same box. For 4x4 packets you can fit up to 5 2x2 packets as well, and if you run out of 2x2 packets, fill the extra with 1x1 packets. Continue in this manner until you've used up all of your packets.


#315 - Network

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
other graph
Solution Description: This problem is about finding articulation points (or cut vertices) in a graph. An articulation point is a vertex that, if removed, increases the number of connected components.

The simplest way of searching for articulation points is to remove each vertex i from 1 to n, and then run DFS starting from the (i+1)th vertex. If any nodes are found to be unreachable, then i is an articulation point.

This algorithm runs O(EV), which is good enough for this problem, but there exists a better algorithm that runs O(E+V) which is worth knowing. See my solution for problem 10199.

See Also:
- Problem 10199 (Tourist Guide)


#320 - Border

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Keep an array 32x32 of booleans and run the simulation. Each movement - NSEW - will set a certain tile relative to your current x and y as true. Make sure you remember, your x and y values are IN BETWEEN the tiles.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: Keep an array of characters, a[32][32] where all characters are initially '.' Remember that the path follows the lines, but your array is holding the grid squares.

x and y are your current grid co-ordinates. When you move north, set a[x][y] to 'X' and increment y. When you move west, set a[x-1][y] to 'X', and decrement x. Do similarly for east and south. At the end, just output your array.

Make sure you have a blank line after *each* case, not just between cases.


#324 - Factorial Frequencies

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:math
strings
Solution Description: Pregenerate the factorials. The rest is just formatting your output.

Doable in 50 lines.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Pregenerate an array of BigIntegers where f[i] = i! Also, create an array of integers where a[i][j] is the number of times the digit j appears in i! Convert each BigInteger to a string and count the digits.

Then, it's just one or two for loops for the output. Never mind the comment about the output not needing to be exact. You should make it look exactly as it does in the sample.


#325 - Identifying Legal Pascal Real Constants

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Let Java do a bunch of the work for you.

Make a boolean named legal, that starts off true.

Use a try catch block, and try converting the trimmed line into a double. If you get an exception, it's illegal.

There are only a couple extra things you have to add now, since Java is more forgiving than the problem desc is.

If there's a period at the beginning or end of the trimmed line, or the trimmed line doesn't contain a ., e, or E, then its illegal.

Lastly, if there's a period next to an e, or an E, it's illegal.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: For each string, make sure to trim the whitespace off at both sides. Then, iterate through it looking for the following things for every character c:

- c must be in the set {0123456789eE+-.}

- If c is + or -, it must be at the beginning or directly following e or E. It also must be followed by a digit

- If c is e or E, it must not be at the beginning or end. It must also be preceded by a digit, and be followed by a digit or + or -

- If c is . it must not be at the beginning or end. It also must be preceded and followed by a digit

The last thing to check is that your number has either a . or e or E, and that it has no more than one of either, and that if it has both, the . comes before the e or E.

If all of these conditions are met, then the constant is legal. Otherwise, it's illegal.


#326 - Extrapolation Using a Difference Table

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a really nice, simple, and easy to understand DP problem. They almost set you up to see the DP right away.

Look at the difference table, and take notice of the bottom diagonal line of numbers. When you calculate the next number in the sequence, you only ever use those last numbers, and so you only need to keep track of those n numbers.

Make an integer array prev, and another named next. Populate prev with the bottom diagonal row of the initial difference table/triangle. You can do this iteratively with a temporary array and two for loops.

Then, just run:

for k
-----next[0] = prev[0]
-----for x from 1 to n-1
----------next[x] = next[x-1]+prev[x]
-----prev = next
output prev[n-1]

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
math
Solution Description: From the first column given, calculate the bottom row of numbers in the difference table. Store these numbers in an array, a[].

Now, for k iterations, extrapolate the next row with a[i] = a[i] + a[i+1] for all numbers in the array except for the last. After k iterations, a[0] is your answer.

Don't worry about the upper bound of k. It doesn't appear to be large, and 32-bit integers (even signed) will suffice.


#332 - Rational Numbers from Repeating Fractions

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Split the number into two components, a and b, where a is the non-repeating part, and b is the repeating part. So for instance, in the first sample input:

2 0.318

a = 3
b = 18

Now, let len(a) and len(b) be the lengths of a and b respectively, including any leading zeroes. The input can be decomposed into a sum of two fractions:

a / 10^len(a)
b / (10^len(b) - 1) * 10^len(a)

Add these fractions to get the fraction that needs to be outputted. Keep the numerator and denominator in separate variables, and reduce them by dividing each by gcd(numerator,denominator).

You may need to handle the case of j = 0 separately, so watch out for it.


#333 - Recognizing Good ISBNs

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Fairly straightforward. Make sure you check all the conditions... work with a trimmed string.

To clear up some grey areas:

the X can only appear as the last character
a completely blank line should still be shown as " is incorrect."

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: For each line, trim the whitespace off of both sides. Then, iterate through each character. If any character is invalid (ie, not of the set {0123456789X-}) then the strin gis invalid. Append all valid characters to a temporary string, except for hyphens which should just be discarded.

In your temporary string, confirm that it is 10 characters long, and that no more than 1 X appears, and that if one appears, it's in the final position. Then, confirm that the sum of sums is divisible by 11. If all these conditions are met, the string is valid.

Watch out for blank lines. They should be processed and marked incorrect.

This problem does not appear to run in time in Java, even with BufferedReader and all the optimizations I can manage.


#336 - A Node Too Far

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:other graph
Solution Description: This is just a BFS problem, but a little bit more difficult than the average because you need to use hash tables to map the names of nodes to indicies. Also, you must use a sparse graph BFS algorithm, so one that runs in O(V + E) rather than O(V^2).

Other than that, the problem isn't too difficult, but remember that the graph need not be connected!


#337 - Interpreting Control Sequences

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
strings
Solution Description: Keep a 10x10 array of characters to manipulate, initially all spaces. Also keep a boolean for marking what mode you're in, and then two variables for the current row and column of the cursor.

Iterate through each line. When you encounter any non-circumflex (^) character and you're in overwrite mode, just write the character to the current cursor position and increment the column. When you're in insert mode, iterate from the end of the row to the current cursor position shifting everything to the right. Then put the character down and increment the column as normal.

There isn't anything particularly tricky about the control characters. Just make sure that when you read the characters past the circumflex, you increment the loop counter to show that they've already been read. Otherwise, you'll double-read the characters, once as a control character, and once as a regular character.

Past that, make sure the cursor stays on the screen and you should be good to go.


#340 - Master-Mind Hints

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:
Solution Description: The core of this problem is very similar to Problem 296 (Safebreaker), so look at my solution for that problem to see how to compare a guess with an answer and determine how many strong and weak matches there are.

"Correct" and "misplaced correct" in Problem 296 correspond to "strong" and "weak" respectively in this problem.


#341 - Non-Stop Travel

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dijkstra
Solution Description: Pretty standard Dijkstra problem. Keep an array p[] where p[i] is the "parent" of node i. That is, the node before i in the path. Whenever you update the distance to node i, set p[i] to whatever node you're currently expanding. Use p[] at the end to reconstruct the path by working backwards from the end.


#343 - What Base Is This?

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
math
strings
Solution Description: First, determine the smallest possible base for each number. For instance, 1392 must be at least base 10 because it has a 9 in it, and ABCD must be at least base 14 because it has a D.

Then, just brute force all combinations of bases for the two numbers and see if they're equal. Use BigInteger when calculating the value of each number, as they can get quite large. In Java you can actually pass a string and a base to the BigInteger constructor and it'll do the base conversion for you.

Two things to note:

- There is no base less than 2 even though the problem says the bases go from 1 to 36. So if the input is 0 0, output base 2, not base 1.
- There can any sort of whitespace between numbers, including blank lines, even though the problem says there will be two integers on each line.


#344 - Roman Digititis

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Hardcode two arrays of strings, one for the ones digit and one for the tens digit:

ones[0] = "";
ones[1] = "i";
ones[2] = "ii";
ones[3] = "iii";
ones[4] = "iv";
ones[5] = "v";
ones[6] = "vi";
ones[7] = "vii";
ones[8] = "viii";
ones[9] = "ix";

tens[0] = "";
tens[1] = "x";
tens[2] = "xx";
tens[3] = "xxx";
tens[4] = "xl";
tens[5] = "l";
tens[6] = "lx";
tens[7] = "lxx";
tens[8] = "lxxx";
tens[9] = "xc";

Then for each number, add up the letters in the appropriate strings. For instance, if you get 43, add "xl" and "iii" for 4 (tens) and 3 (ones). For the special case of 100, just add one 'c'.

Iterate through all numbers from 1 to n (the input value), and at the end, output the total quantity of each letter.


#346 - Getting Chorded

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:brute force
strings
Solution Description: Keep an array of three integers where a[i] is the numerical value of the ith note in the input. By this I mean, A = 0, A# = 1, B = 2, ... , G# = 11.

Now, brute force all 6 permutations of the sequence. For each one, calculate a[1] - a[0] and a[2] - a[1]. If the value is negative, wrap-around by adding 12. If the values are 4 and 3 respectively, the chord is major. If the values are 3 and 4, then the chord is minor.

This problem can become a little unwieldly code-wise, but you should be able to keep it within 150 lines. Most of it is just copy and paste.

Make sure that you never output the name of the chord with a flat sign (b). Only use sharps (#) (if necessary).


#348 - Optimal Array Multiplication Sequence

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:dynamic programming
strings
Solution Description: Let a[i][j] be the optimal number of multiplications for the sequence of matrices (i * i+1 * ... * i+j).

Initially, a[i][0] is 0 for all i. Iterate through increasing j updating a[i][j]. This will be a triangular matrix, as it's meaningless to have something like a[2][4] when there are only 5 matrices. You can't go four matrices beyond the second.

For the DP itself... let's say j = 3. So we're going to make the seqeunces (0*1*2*3), (1*2*3*4), ...

For (0*1*2*3) we consider all possible midpoints. That is,

0 * (1*2*3)
(0*1) * (2*3)
(0*1*2) * 3

These are all values we've computed before, so we take the minimum across each one. That is, the minimum sum of:

1) The amount of multiplications in the left-hand side
2) The amount of multiplications in the right-hand side
3) The amount of multiplications necessary to put the two halves together

To get the output string, I create a second array, s[][] that parallels a[][]. s[i][j] is the string that represents the optimal arrangment of matrices for (i * i+1 * ... i+j).

Initially, s[i][0] = "Ai" for all i. Whenever you update a[][], put "(s1 * s2)" into s[][] where:

s1 = the string from the first half
s2 = the string from the second half


#350 - Pseudo-Random Numbers

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Make a HashSet and an ArrayList.

Keep adding the numbers generated to both, until the HashSet detects a duplicate.

Output HashSet.size() - ArrayList.indexOf(duplicate)

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:simulation
Solution Description: Keep an array of 10000 integers where a[i] is the iteration that i first appears in the sequence of numbers.

Keep simulating the process of generating numbers, and where l is the next number, mark a[l] with the current iteration. If a[l] is greater than 0, then stop, as you've found a cycle. Output (current iteration - a[l]).


#352 - The Seasonal War

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: Take your input into an array of characters.

Iterate through the entire grid, and whenever you find a '1', increment a counter and flood fill from that point (essentially doing a breadth first search that changes grid values if you're unfamiliar with flood fill).

Output the counter.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: This is a simple floodfill problem. Store the input in an array of characters, and then iterate through it row by row. Whenever you encounter a 1, increment a running count, and floodfill all adjacent 1's with 0's. At the end, output the running count.


#353 - Pesky Palindromes

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Use string buffers, and check for every length of substring, in every position, if the substring = substring.reverse.

Add every time that happens, and use a HashSet to ensure no duplicates. That is, every time you count something, add it to the hash set. And only count something if the hashset doesn't contain it already.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
strings
Solution Description: Iterate through every substring of the input to see whether or not it's a palnidrome. Whenever you find a new palindrome, increment a running total and add it to an array of previously found palindromes (this should be about 10,000 large). Output the running total at the end.

Note: It isn't explicitly stated, but the input is case sensitive.


#355 - The Bases Are Loaded

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Use a string to map the letters and numbers to eachother. Something like:

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

That way you can simply use indexOf to get the value of a character, or charAt to get the character of a value.

Unfortunately the bounds are as such that you cannot use Integer.parse int, and you have to use longs. This means that we get to manually convert both ways.

Going the first way, from a to base 10 is easy. Just iterate from the right of the input string to the left, adding (valueHere)*(a^indexFromRight) to a counter.

Going the other way, you have to setup a while loop:

while(counter != 0)
----add counter%b to the output
----counter %= b

Lastly, make sure to handle the case where your input to convert it zero.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Convert each number into base 10, and then convert it into the final base. Check for invalid characters, which may be things like lowercase letters or punctuation. Basically, check that only the characters in the set {0123456789ABCDEF} are used, and that the number is legal in the given base.

If you're using Java, you can use Long.parseLong to do the base conversion, and you can catch NumberFormatExceptions, which indicate that the number contains invalid characters.

Note that you must use longs as ints are too small for some of the inputs.


#356 - Square Pegs And Round Holes

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
Solution Description: As the shape is symmetrical vertically and horizontally, it suffices to calculate a quarter of the shape and then multiply by 4.

The first quadrant is probably the most intuitive. For each square, check whether the lower left and upper right corners are within the circle. If both are, then the square is entirely in the cirlce. If just the lower left is inside, then the square contains a segment of the circle. Add all of these up, and then multiply by 4.


#357 - Let Me Count The Ways

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is the most basic of coin change DPs. Make an array where d[i] is the value of the ith coin (1-indexed), so d[1] = 1, d[2] = 5, etc.

Let a[i][j] be the number of ways to make change for j cents with coins up to i. Make a[][] and array of longs as the output grows quite quickly.

The coin change recurrence:

a[0][j] = 0 (j >= 1)
(There are no ways to make change with no coins)

a[i][0] = 1
(There is always one way to make 0 cents: use no coins)

a[i][j] = a[i-1][j] (d[i] > j)
(If the coin can't be used, then don't use it)

a[i][j] = a[i-1][j] + a[i][j-d[i]] (d[i] <= j)
(If the coin can be used, then either use it or don't)

Output a[5][n] for any input n.


#362 - 18,000 Seconds Remaining

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:medium
Algorithms Used:simulation
Solution Description: OH MY GOD. I think this is has got to be my LEAST favourite problem right now. I'd rather me stabbing myself repeatedly than having anything more to do with this CRAP.

Do what the problem does, and:

-MAKE SURE YOU PAY FULL ATTENTION TO ROUNDING AND DOUBLES, ESPECIALLY THE:
remainSecond = (5*(double)remainingpackets)/(double)receivedpackets;

-Use a stringbuffer to hold your output, and then print it all at once

-MAKE SURE THERE'S A NEW LINE AFTER EACH LINE

-Have somebody else double check the formatting of your output, before your brain explodes, like mine did.

I have this damn problem done in 15 minutes, and spent OVER AN HOUR trying to get to AC. MY GOD.

*Stroke*

I give this a MEDIUM because I've checked the UVa forums, and THIS IS A HORRIBLE PROBLEM.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: For every input n, keep reading numbers while n > 0. Keep a running sum of how many bytes have been transferred. Every 5 seconds, output a time remaining line, and then reset this counter. Don't forget to round up when you print the time remaining.

In Java you'll have to use BufferedReader. And don't forget to put a blank line after *every* case.


#369 - Combinations

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: I considered reducing the factorials and all of that... but then I realized that I could just pregenerate all the factorials up to 100!, and then use BigIntegers to output the result.

Runs in time with Java!

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Pregenerate an array of BigIntegers where f[i] is f!

For each input n and m, just output f[n] / (f[m]*f[m-n]).


#371 - Ackermann Functions

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
math
Solution Description: Keep an array of integers, where a[i] is the cycle length of i. Whenever you need to calculate a cycle length, do it brute force, and then store the result in the array. If you're asked for it again, just read it from the array.

You will never be asked for numbers higher than 10,000,000.

Note the special case for 1. Its cycle length should be 3, not 0, as seen in the problem description.


#374 - Big Mod

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Use BigIntegers to solve the problem.

You need to use the BigInteger.modPow function to have this run in time, since using BigInteger.pow, then BigInteger.mod will TLE.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: As the problem name would suggest, just use BigIntegers to do the calculation.


#377 - Cowculations

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
sorting
Solution Description: One of those simple problems shrouded by a convoluted problem description.

The important thing to notice from the addition table is that the symbols correspond to numbers:

V = 0
U = 1
C = 2
D = 3

It's also apparent from the addition table that the cow numbers are in base 4 (because of the carries).

So, just make a function that converts cow numbers to base 10 numbers. Then, for each of the operations:

A - Add num1 to num2
R - Divide num2 by 4
L - Multiply num2 by 4

At the end, check if num2 is equal to the base 10 representation of the 8 digit number.


#378 - Intersecting Lines

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
math
Solution Description: This is a pretty simple analytical problem. Find the slope and y-intercept of each line, and then solve the following system:

y = m1x + b1
y = m2x + b2

...to get...

x = (b1 - b2) / (m2 - m1)

Substitute back into the previous equations to get y.

Watch out for vertical lines, and handle them separately!


#382 - Perfection

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Hold an answer array, with each element initializaed at 0.

Iterate from 1 to 60000/2, and for each i, iterate up from i*2 - adding i each time.

For each input, output deficient, perfect, or abundant if ans[input] < input, == input, or > input repectively.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: For each input n, iterate i from 1 to n-1. If n % i = 0, then add i to a running sum. At the end, check whether the sum is greater than, less than, or equal to n.


#386 - Perfect Cubes

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:brute force
Solution Description: Seeing as how this problem has no input, you can always be really cheap and just precalculate all the output and make a program that just dumps it out. But, we're here to learn, right? :D

As it turns out, the "real" solution isn't actually that hard. You can do brute force with pruning at it runs really quickly:

for a = 2 to 200
for b = 2 to 200
for c = b to 200
for d = c to 200
--- if(b^3 + c^3 + d^3 > a^3)
------ break


#389 - Basically Speaking

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
Solution Description: Just convert the numbers into the new bases. Make sure that you don't miss the input "0".


#392 - Polynomial Showdown

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: You're going to have to use a LOT of nested if statements and else's... it's really just be careful about covering every case, and not being too broad with your ifs. Some cases to consider:

0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1
-1 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0

It's annoying.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Keep a boolean, initially true. Iterate through the input from the highest degree to the lowest. When you encounter a non-zero value for the first time, set the boolean to false. When the boolean is false, append " + " or " - " beforehand as necessary. When the boolean is true, only append "-" if necessary.

Then, append the absolute value of the exponent (unless it's 1), and append "x^y" where y is the degree (or nothing if y = 1).

Remember to not output the constant term if it's 0, unless *all* the terms are 0.

In Java, use BufferedReader and StringBuffer to make this run in time.





Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By PHPGraphLib - Click For Official Site