Search found 34 matches

by shuniu
Thu Jun 17, 2004 4:57 pm
Forum: Volume 106 (10600-10699)
Topic: 10670 - Work Reduction
Replies: 10
Views: 7693

Greedy is the right way to go, couple things to watch for though: Notice the output format, eg "Case 1, Case 2" the name can be more than 1 character the output order should be sorted by name if costs are equal watch out for cases where A or B equals 0, then you could get into trouble for dividing b...
by shuniu
Wed Jun 16, 2004 6:49 pm
Forum: Volume 106 (10600-10699)
Topic: 10604 - Chemical Reaction
Replies: 24
Views: 15047

When I used DFS, without memorization I got TLE, with memorization I got MLE. Then I changed to BFS, and got AC with pretty good time and mem. At each loop, I record only the possible configurations for the current and next step and its minimum heat values. Take the first sample input for example. O...
by shuniu
Wed Jun 16, 2004 6:55 am
Forum: Volume 106 (10600-10699)
Topic: 10603 - Fill
Replies: 19
Views: 8806

I used DFS to solve the problem, had to use approx 20000 of memory. I see on the ranklist alot of people got it with 64 mem and almost 0 time. This question seems to be quite large to send in precalc results, so is there a much better approach then searching through all configurations?
by shuniu
Tue Jun 15, 2004 11:16 pm
Forum: Volume 106 (10600-10699)
Topic: 10601 - Cubes
Replies: 9
Views: 5238

I believe this problem is meant to be solved by backtracking and then send the precalc result, which is already quite difficult. Otherwise it would rely too much on the knowledge of a specific theorem. (Or... there is another very smart approach) People here seem to knock on the concept of sending i...
by shuniu
Mon Jun 14, 2004 4:32 pm
Forum: Volume 106 (10600-10699)
Topic: 10648 - Chocolate Box
Replies: 15
Views: 7530

thanks, misof, i get AC after i fix that mistake.
btw, i was just trying to be extra careful on the boundary case (0 box), cause the problem never mentioned m>0, and you know how alot of problems try to screw people on such cases.
by shuniu
Fri Jun 11, 2004 11:05 pm
Forum: Volume 106 (10600-10699)
Topic: 10648 - Chocolate Box
Replies: 15
Views: 7530

I used double in my Java program, got WA, I wonder if there is precision error. Here are some of my IO, please tell me if there are errors. Input: 100 0 100 5 100 6 100 7 100 10 100 20 100 30 100 40 100 50 100 59 100 60 100 61 100 70 100 80 100 90 100 100 -1 Output: 0.0000000 0.0000000 0.0000001 0.0...
by shuniu
Thu Jun 10, 2004 7:27 pm
Forum: Java
Topic: Java BigInt Implementation
Replies: 0
Views: 3474

Java BigInt Implementation

Here is my "Big Number" implementation in Java. Adapted from the book "Programming Challenges". Hope it helps! [java]class BigInt implements Comparable { int PLUS = 1; int MINUS = -1; int MAXDIGITS = 500; char[] digits; int signbit; int lastdigit; private BigInt() { digits = new char[MAXDIGITS]; sig...
by shuniu
Wed Jun 09, 2004 6:02 pm
Forum: Volume 106 (10600-10699)
Topic: 10664 - Luggage
Replies: 20
Views: 14124

Input: 16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 2 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 1 2 3 5 7 11 13 17 23 1 2 3 5 7 11 13 17 23 29 1 2 3 5 7 11 13 17 23 29 31 1 2 3 5 7 11 13 17 23 29 31 37 10 20 30 40 50 50 1...
by shuniu
Wed Jun 09, 2004 12:21 am
Forum: Volume 106 (10600-10699)
Topic: 10663 - Non-Powerful Subsets
Replies: 27
Views: 7036

If multiset is allowed, then {1,1,1,1} (sums to 4) is a subset of {1}, so {1} is not a solution.
by shuniu
Tue Jun 08, 2004 10:28 pm
Forum: Java
Topic: Stack over flow...
Replies: 1
Views: 1757

If it says stack overflow, it most likely means your recursion doesnt terminate. You may want to print some debuging message at each loop to see where it got stuck.
by shuniu
Tue Jun 08, 2004 7:09 pm
Forum: Volume 106 (10600-10699)
Topic: 10655 - Contemplation - Algebra
Replies: 42
Views: 10726

After countless tries, I finally got AC, it certainly has alot of traps, I ended up with a whole list of if statements to catch each of the traps in my program... Need to catch the following n==0 p==0 && q==0 p==1 && q==0 p==0 && q==1 p==2 && q==1 Input 0 0 0 0 0 1 0 0 200000000 1 3 0 999999 999999 ...
by shuniu
Fri Jun 04, 2004 11:08 pm
Forum: Volume 106 (10600-10699)
Topic: 10644 - Floor Tiles
Replies: 25
Views: 11433

A faster way than drawing it on paper is to write a program to draw it. First set 2x3, 3x2, 5x9, 9x5 to be the possible tiled rectangles. Then use dynamic programming to determine the rest (eg a rectangle can be tiled iff it can be cut into 2 tilable rectangles). Unfortunately, this method takes mor...
by shuniu
Fri Jun 04, 2004 9:22 pm
Forum: Volume 106 (10600-10699)
Topic: 10653 - Bombs! NO they are Mines!!
Replies: 36
Views: 18346

My solution in Java got AC in 9.953s, talking about cutting it close!!! I think these kind of long input questions are really discriminating to the Java users. Java programs are about 5-10x slower (or even more) than the C, C++, Pascal programs. Even a System.out.println("") takes 0.006s, eg it can ...
by shuniu
Wed May 26, 2004 5:08 pm
Forum: Volume 1 (100-199)
Topic: 196 - Spreadsheet
Replies: 42
Views: 10339

Try using columns AA, BB.. ZZZ to see if u are calculating them correctly. Input: 1 30 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 =AA2 =AA1+B2+AC2 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600...
by shuniu
Mon May 17, 2004 10:53 pm
Forum: Volume 106 (10600-10699)
Topic: 10633 - Rare Easy Problem
Replies: 37
Views: 19013

Here is a proof that finds the answers mathematically, N = original number M = N with last digit chopped off B = the chopped off digit So that, N = 10M + B where (0<=B<=9) N-M = (10M+B)-M = 9M+B We can calculate (N-M)%9 = (9M+B)%9 = (9M)%9 + (B)%9 = B%9 If B%9==0, then B can be either 0 or 9, B=0 im...

Go to advanced search