近來閒閒無事，就利用點時間復習一下程式語言，有時候去 ACM UVa online judge 網站找題目來練習，有時候則是自己想題目給自己寫（像是解數獨）；所以，最近我腦子裡充滿了 recursion、stack 、queue 等等，我想，我將來會很懷念這種沒有程式比賽的壓力，僅僅是為了好玩及鍛鍊自己而寫程式的單純日子。

Problem solved:

**Volume I**

- 100 - The 3n + 1 problem
- 101 - The Blocks Problem
- 102 - Ecological Bin Packing
- 103 - Stacking Boxes
quick sort + topological sort

- 104 - Arbitrage
All pair shortest path 的變形版

- 106 - Fermat vs. Pythagoras
利用畢氐定理的通解

- 107 - The Cat in the Hat
- 108 - Maximum Sum
暴力解是O(n

^{4}); 把問題 reduce 成 1D array 可以得到 O(n^{3}) 的解 - 111 - History Grading
題目很簡單, 唯一要注意的是不能直接拿 input 作Longest Common Subsequence

- 112 - Tree Summing
節點的數字可能是負數，要小心!

- 113 - Power of Cryptography
- 116 - Unidirectional TSP
Dynamic Programming 填表格

- 119 - Greedy Gift Givers
- 128 - Software CRC
- 136 - Ugly Numbers
第二次 submit 時使用大絕招，直接 printf 印出答案，結果還是需要 0.004 秒，不知道那些 0.000 秒的神人是怎麼辦到的...

- 138 - Street Numbers
- 146 - ID Codes
The output is actually the next lexicographical permutation of the input string. Just use a small piece of code for Problem 195.

- 151 - Power Crisis
apply the solution for The Joseph Problem.

- 160 - Factors and Factorials
- 193 - Graph Coloring
圖論的題目比我預期的還難搞....囧。UVa toolkit網頁上的輸出還和我的程式不同，一度以為自己寫錯，拚命在找 Bug, 更囧。

- 195 - Anagram
Generate all permutations. The algorithm can be found in The Art of Computer Programming, Section 7.2.1.2.

**Volume II**

- 200 - Rare Order
topological sort

- 231 - Testing the CATCHER
Longest increasing subsequence. The test case is not big so the O(n^2) DP is enough.

- 238 - Jill's Bike
Find the shortest path in a directed graph. Perhaps the most difficult part is to parse the input and understand the problem description rather than finding the shortest path.

- 256 - Quirksome Squares
- 264 - Count on Cantor
- 270 - Lining Up
First sort the points based on their x-coordinates (primary key) and y-coordinates (secondary key). For each point p[i], use p[i] as the anchor and find the slopes between p[i] and p[i+1..n], sort the slopes to find the number of co-linear points.

- 272 - TEX Quotes
- 280 - Vertex
Graph Traversal

- 291 - The House Of Santa Claus
A simple recursion can solve the problem.

- 294 - Divisors
- 299 - Train Swapping
count the number of pairs (x[i], x[j]) such that x[i] ＞ x[j]

**Volume III**

- 305 - Joseph
- 307 - Sticks
- 315 - Network
Use DFS traversal to decide whether a node is an articulation point.

- 324 - Factorial Frequencies
implement simple big integer arithmetics.

- 369 - Combinations
- 389 - Basically Speaking
remember to handle input 0.

- 392 - Polynomial Showdown
- 371 - Ackermann Functions
The same as Problem 100.

- 374 - Big Mod
- 382 - Perfection
Let n = p1^k1 * p2^k2*...*pm^km. The sum of n's divisors is (1 + p1 + p1^2 + ... + p1^k1) * (1 + p2 + ... + p2^k2) * ... * (1 + pm + ... + pm^km) - n.

**Volume IV**

- 400 - Unix ls
number of columns = 62 / (2 + max{strlen(fn[i]) | 0 &le i &le n-1})

- 406 - Prime Cuts
Just do what the problem asks for,

- 408 - Uniform Generator
Good choice if and only if GCD = 1.

- 412 - Pi
- 424 - Integer Inquiry
big integer addition

- 443 - Humble Numbers
Repeatedly generate humble numbers

- 445 - Marvelous Mazes
- 458 - The Decoder
For each input char except for the newline '\n', minus 7 from that char and print it.

- 459 - Graph Connectivity
Use any graph traversal algorithm like BFS or DFS. The answer is the number of traversal needed to visit every vertex.

- 465 - Overflow
- 474 - Heads / Tails Probability
Almost identical to Prob 545, but the rounding is different. (I hate fighting with precision).

- 482 - Permutation Arrays
- 483 - Word Scramble
- 485 - Pascal's Triangle of Death
- 488 - Triangle Wave
A simple loop solves the problem. I test the low-level IO function write() to see how it speeds up the running time. The difference was significant. The running time drops from 0.348s (using printf) to 0.056s (using write).

- 494 - Kindergarten Counting Game
- 495 - Fibonacci Freeze

**Volume V**

- 507 - Jill Rides Again
This is to find the longest interval that has the maximum sum. When the sum is negative, the interval is reset. When the sum equals to 0, I set up a flag to see if the current interval can be extended or not.

- 514 - Rails
- 524 - Prime Ring Problem
- 530 - Binomial Showdown
This problem is simple, but a trivial implementation is prone to exceed time limit. Rather than using the methods recommended by UVa forum, I use tsearch() in ANSI C to maintain binomial coefficients discovered for avoiding redundant computation.

- 531 - Compromise
string version for the longest common subsequence problem

- 532 - Dungeon Master
BFS search

- 534 - Frogger
BFS search

- 536 - Tree Recovery
- 541 - Error Correction
- 543 - Goldbach's Conjecture
- 545 - Heads
- 558 - Wormholes
DFS traversal with root node 0. For each back edge, check if a negative cycle is form.

- 562 - Dividing coins
Set up an array of 50001 elements, if some set of coins add up to s, set the corresponding element to 1, otherwise 0. Output the answer based on this array.

- 572 - Oil Deposits
DFS or BFS traversal

- 573 - The Snail
- 575 - Skew Binary
Do as the problem asks

- 579 - ClockHands
- 568 - Just the Facts
- 583 - Prime Factors
- 587 - There's treasure everywhere!
- 591 - Box of Bricks
- 594 - One Little, Two Little, Three Little Endians
Use union in C

**Volume VI**

- 612 - DNA Sorting
- 623 - 500!
- 636 - Squares (III)
- 640 - Self Numbers
- 673 - Parentheses Balance

**Volume VII**

- 713 - Adding Reversed Numbers
- 729 - The Hamming Distance Problem
Initially, set up a string of 0s and 1s that satisfies the required Hamming distance. Then find all the lexicographical permutation of this string.

- 748 - Exponentiation
- 763 - Fibinary Numbers
My method involves three stages. The first stage is find c = a + b with no carry digits (c[i] = a[i] + b[i]). The second stage is a while loop that smooths out c so that c has no digit &ge 2. The third stage is another while loop that reduces c to the form required by the problem.

- 825 - Walking on the Safe Side
- 834 - Continued Fractions
- 855 - Lunch in Grid City
Find the (2D) median. (This problem is similar to Vito's Family)

- 884 - Factorial Factors
- 895 - Word Problem
- 897 - Anagrammatic Primes
There are only 22 anagrammatic primes satisfying the conditions set by the problem.

- 10000 - Longest Paths
Modify the topological sort algorithm to get answer.

- 10004 - Bicoloring
- 10006 - Carmichael Numbers
Method 1: Google for Carmichael numbers. Method 2: test just prime numbers below 65000.

- 10007 - Count the Trees
The number of trees that contain n vertices is called Catalan number C

_{n}= C(2n, n) / (n + 1), where C(2n, n) is a binomial coefficient. Because each vertex is labeled by a unique id, the output of this problem is n! * C_{n}. - 10008 - What's Cryptanalysis?
An easy problem for practicing sort algorithms.

- 10010 - Where's Waldorf?
- 10013 - Super long sums
Use char arrays to do big integer addition.

- 10018 - Reverse and Add
- 10023 - Square root
Java's BigInteger and binary search can be accepted within the time limit.

- 10026 - Shoemaker's Problem
sort based on finish_time/fine.

- 10034 - Freckles
Minimum spanning tree

- 10035 - Primary Arithmetic
- 10038 - Jolly Jumpers
- 10041 - Vito's Family
找出 median 後，答案就呼之欲出了；第一次用 qsort 找 median，時間 0.028 秒，第二次利用 quick sort 的 partition procedure 直接找 median，時間 0.024 秒，第三次用 radix sort 找 median，但跑得比第二次慢；目前最好的成績是 0.020秒，排名 70。

- 10044 - Erdos Numbers
- 10050 - Hartals
- 10055 - Hashmat the Brave Warrior
- 10056 - What is the Probability ?
Use high-school mathematics to find out the equation of the answer. Remember: never divide by 0.

- 10062 - Tell me the frequencies!
call qsort to find the answer, and notice the array index range as well as the output format. A blank line is also considered as a test case.

- 10066 - The Twin Towers
LCS

- 10070 - Leap Year or Not Leap Year and ...
The year is represented by a long string. I implement a simple big integer module function to solve this problem.

- 10071 - Back to High School Physics
The answer is 2*v*t

- 10079 - Pizza Cutting
Find the formula of the solution

- 10082 - WERTYU
- 10094 - Place the Guards
- 10098 - Generating Fast
The algorithm can be found in The Art of Computer Programming, section 7.2.1.2. Note that you should print a blank line after the last test case.

- 10099 - The Tourist Guide
A little similar to the maximum flow problem, but this one is much easier. Take care the case that the starting city and the destination is the same.

- 10104 - Euclid Problem
The test data set seems large. Using recursive version will get TLE. I got my program accepted after revising it into loop version.

- 10105 - Polynomial Coefficients
- 10106 - Product
- 10107 - What is the Median?
實作一個簡單的 binary search tree, insert 和 query 的 average time 都是 O(log n), 排名 42/5389。

- 10110 - Light, more light
Interesting Problem

- 10125 - Sumsets
- 10127 - Ones
Use a simple loop to simulate the division (without involving big integer arithmetics) The inputs 0 and 1 are special cases, the corresponding outputs are 0 and 1.

- 10131 - Is Bigger Smarter?
- 10139 - Factovisors
find the prime factors

- 10183 - How Many Fibs?
- 10189 - Minesweeper
- 10192 - Vacation
- 10194 - Football (aka Soccer)
- 10200 - Prime Time
Use a binary array of 10001 elements, the element n is 1 iff f(n) is prime. Then find the prefix sum of this array to to handle queries.

- 10222 - Decode the Mad man
The chars qwaszx map to {};'./ respectively.

- 10252 - Common Permutation
Find the occurrence of each characters.

- 10258 - Contest Scoreboard
- 10276 - Hanoi Tower Troubles Again!
UVa forum has a recursive equation.

- 10281 - Average Speed
- 10282 - Babelfish
Use a hash table

- 10299 - Relatives
Euler's totient function

- 10341 - Solve It
Bisection method

- 10347 - Medians
題目說 print -1時，實際上要 print -1.000，要不然會得到 Wrong answer(好鳥的題目描述) ；另外，要使用 double，而不是 float

- 10363 - Tic Tac Toe
- 10386 - Circles in Triangle
S8 = 2* r * (sqrt(3) + 1 + sqrt(11/3))

S11 = 2 * r * (sqrt(3) + 2 + 4/sqrt(6)) - 10420 - List of Conquests
- 10608 - Friends
Union-Find

- 10611 - The Playboy Chimp
Binary search

- 10622 - Perfect P-th Powers
The input contains negative numbers, be careful.

- 10633 - Rare Easy Problem
- 10642 - Can You Solve It?
Find the formula for the index of a point according to the problem description.

- 10650 - Determinate Prime
The problem description is not very clear. For input pair 251 and 263, the program should output nothing (because a proper subset of {251 257 263 269} is prohibited). Another key point is that inputs are not necessarily increasing. When given a input pair 269 251, the program should output 251 257 263 269.

- 10653 - Bombs! NO they are Mines!!
Implement a shortest path algorithm.

- 10656 - Maximum Sum (II)
Just output the numbers ＞ 0; if none, output 0.

- 10664 - Luggage
There may be no luggage(empty line). In this case the program outputs YES.

- 10678 - The Grazing Cow
- 10679 - I Love Strings!!
- 10673 - Play with Floor and Ceil
- 10680 - LCM
- 10683 - The decadary watch
- 10684 - The jackpot
This problem can be solved in linear time

- 10689 - Yet another Number Sequence
- 10696 - f91
- 10699 - Count the factors
- 10700 - Camel trading
- 10701 - Pre, in and post
Recursively find the root node label, the preorder of the left tree and the inorder of the right subtree to construct the original tree structure.

- 10702 - Travelling Salesman
DP

- 10703 - Free spots
The input may not give x1, x2, y1, y2 based on the sorted order, so swap x1, x2 and y1, y2 if necessary.

- 10714 - Ant
Forget the problem description, the answers depend on only four numbers.

- 10719 - Quotient Polynomial
Just use an array to simulate the polynomial division. Note that there is an empty line following ``every'' set of output.

- 10720 - Graph Construction
At first, I tried to solve this problem by checking simple conditions that a simple graph never holds, but received Wrong answer. Only until using Erdos and Gallai theorem (see http://mathworld.wolfram.com/GraphicSequence.html) that my program got accepted.

- 10721 - Bar Codes
A good example of DP

- 10725 - Triangular Square
Use pen and paper to find the solution. When coding the program, I first sort the three sides and let C be the angle corresponding to the longest side. One case is that angle C &le 90 degrees (cos C &ge 0). Another case is that angle C ＞ 90 degree.

- 10730 - Antiarithmetic?
- 10732 - The Strange Research
- 10733 - The Colored Cubes
Burnside's lemma

- 10742 - The New Rule in Euphomia
Find prime numbers and then apply binary search

- 10745 - Dominant Strings
Find the occurrence of each characters for each string, and then decide whether a string is dominated by another string.

- 10763 - Foreign Exchange
Divide the inputs into two groups, sort the two groups, and check if they match each other.

- 10773 - Back to Intermediate Math
Special cases: v &ge u, v=0 and u=0, in those cases output "can't determine".

- 10776 - Determine The Combination
Sort the sequence, find the number of occurrence for each character. Then run a recursive call to find all the combinations (In my program, I also maintain a variable for the length of the suffix string for avoiding unnecessary recursive calls).

- 10784 - Diagonal
- 10789 - Prime Frequency
- 10791 - Minimum Sum LCM
Be careful with 1.

- 10780 - Again Prime? No Time.
Take care of the case n = 1.

- 10783 - Odd Sum
- 10793 - The Orc Attack
Just do what the problem asks. Note that, as the problem description already states, an edge may appear several times in the input.

- 10806 - Dijkstra, Dijkstra
This is an interesting problem. Please refer the Uva forum to the general idea.

- 10812 - Beat the Spread!
- 10814 - Simplifying Fractions
Java is my good friend when dealing with big integer arithmetics.

- 10815 - Andy's First Dictionary
- 10816 - Travel in Desert
I used a two-stage approach. The first stage finds the minimum temperature t from the source to the destination. The second stage finds the shortest path, where the temperature of each path is &le t. Both stages finds a shortest path by using the BFS approach.

Note: there may be multiple edges from a node u to another node v. The multiple edges represent different routes (in terms of temperature and distance), so the degree of a node may exceed N. At first I didn't notice that and got a few Runtime Error.

- 10820 - Send a Table
Apply the Euler Totient Function

- 10842 - Traffic Flow
Construct "maximum" spanning tree

- 10843 - Anne's game
This is equivalent to finding the number of spanning trees in a complete graph K

_{n}. The answer is n^{n-2}. The proof can be found in A Course in Combinatorics. - 10844 - Bloques
This is actually a set partition problem and the answer is known as Bell numbers. By taking advantage of the Bell number triangle my program use only addition operations. Due to the strict time limit, I use an array of long long to implement big integer arithmetics and the base of the big integer is 10

^{18}.Materials about Bell numbers can be found in The Art of Computer Programming, Section 7.2.1.5.

- 10852 - Less Prime
- 10862 - Connect the Cable Wires
Fibonacci numbers and big integer arithmetics.

- 10878 - Decode the tape
The symbols "o" and space represent 1 and 0, respectively. Each row (except for the first and the last) in the tape maps to an ASCII code. Find the code and output the character.

- 10879 - Code Refactoring
- 10887 - Concatenation of Languages
Be careful that the input may have empty lines (which represent empty strings).

- 10896 - Known Plaintext Attack
- 10903 - Rock-Paper-Scissors Tournament
- 10905 - Children's Game
Apply a sorting algorithm smartly. Be careful that a input number can have length more than 100. I received a few WA until I figured out what was going on.

- 10912 - Simple Minded Hashing
Consider only the cases L <= 351 and C <= 26

- 10916 - Factstone Benchmark
To decide the largest n such that n! &le 2^k for a given k, a simple method is applying log operation to both sides. That is, log(n) + log(n-1) + ... + log2 &le k.

- 10918 - Tri Tiling
S[i] = 4*S[i-1] - S[i-2] for i &ge 3

- 10921 - Find the Telephone
An practical example of hash function in our daily life.

- 10922 - 2 the 9s
- 10924 - Prime Words
- 10928 - My Dear Neighbours
- 10929 - You can say 11
- 10935 - Throwing cards away I
Just simulate the Joseph Problem.

- 10940 - Throwing cards away II
This is a variant of the well-known Joseph Problem. Just Manipulate the ouput of the original Joseph Problem a little bit and you will get the answer.

- 10943 - How do you add?
num[k][n] = sum(num[k-1][n-i]) for 0 &le i &le n

- 10945 - Mother bear
- 10948 - The primary problem
- 10931 - Parity
- 10954 - Add All
Always pick up the two smallest numbers to add. I use a min heap to make the process fast.

- 10957 - So Doku Checker
Very similar to problem #989. Just use the same old method to solve it.

- 10970 - Big Chocolate
- 10976 - Fractions Again?!
The range of y is k + 1 &le y &le 2*k. Use this property to find x.

- 10986 - Sending email
I use exhaustive BFS to approach this problem. Again, online judge gave WA to my ANSI-C code, which is accepted by choosing C++ as the programming language.

- 10991 - Region
Area of the triangle ABC is sqrt(s(s-a)(s-b)(s-c)), where a, b, c is the length of the three sides with respect to angles A, B, and C, and s = (a + b + c)/2. Using the formula, cosC = (a^2 + b^2 - c^2)/2*a*b, the angle of C can be found by using acos() function and so does angles of A and B.

- 10994 - Simple Addition
This problem is more difficult than it looks. Getting TLE is guaranteed if you just run a simple loop. I treat the summation from p to q as (summation from 1 to q) minus (summation from 1 to p - 1). Then I divide p into groups of 10 elements, and use the recursive function f(p) = 45*p/10 + f(p/10) for p &ge 10. The base case for f(p) can be found by using a simple loop. The final answer would be f(p) - f(q - 1). The answer should be represented by a 64-bit integer for avoiding overflow.

- 11000 - Bee
DP

- 11044 - Searching for Nessy
- 11049 - Basic wall maze
Shortest path + back trace. It is not a difficult problem, simply follow the problem description to find out the answer.

- 11054 - Wine trading in GergoviaGreedy method
- 11057 - Exact Sum
Sort and use binary search. Like Sample 1, take care of the case that there may be two books such that their selling price equals to the budget.

- 11064 - Number Theory
- 11067 - Little Red Riding Hood
- 11069 - A Graph Problem
Use DP to solve this problem. The DP rule is very simple.

- 11321 - Sort! Sort!! and Sort!!!
use standard library qsort() might be the best strategy. Because the input number could be as large as 2

^{31}Don't use *(int *)a - *(int *)b in the comparison function for avoiding integer overflow/underflow. - 11137 - Ingenuous Cubrency
- 11150 - Cola
- 11151 - Longest Palindrome
- 11152 - Colourful Flowers
- 11172 - Relational Operator
- 11185 - Ternary
0 is a special case.

- 11192 - Group Reverse
- 11223 - O: dah dah dah!
- 11250 - Working with Small Numbers
&Sigma

_{1 &le i &le n}1/(i(i+1)(i+2)(i+3)) = n(n^{2}+ 6n+ 11)/(18(n+1)(n+2)(n+3)) - 11309 - Counting Chaos
- 11310 - Delivery Debacle
- 11313 - Gourmet Games
- 11326 - Laser Pointer
The value of B depends on the number of times (even or odd) for the beam to reflect before reaching the exit. Note that θ be may 0, in that case the program should output 1.000.

- 11331 - The Joys of Farming
Try to find if the field is 2-colorable. If yes, then assign bulls/cows based on the 2-coloring.

- 11332 - Summing Digits --- A simple loop can solve it
- 11340 - Newspaper
output format is something like 2.10$ instead of 2.1$

- 11342 - Three-square
Pre-compute a table of perfect square numbers. Use the table to decide to speed up the program by avoiding multiplication and square root calculation.

- 11344 - The Huge One
- 11353 - A Different Kind of Sorting
If n is composite, find the first prime factor p, and let nFactor(n) = nFactor(n/p) + 1. Then sort the sequence based on the problem specification.

- 11364 - Parking
2*(max - min)

- 11385 - Da Vinci Code
- 11386 - Triples
Use 64-bit integer for the input sequence. Sort the numbers first, find their occurrence and use the combination (number, occurrence) to find the answer. Because the test data set is enormous, it is very likely to receive TLE if adopting trivial solutions.

- 11387 - The 3-Regular Graph
If the sum of vertex degrees is odd, output "impossible". Otherwise, output a symmetric 3-regular graph. Note that n = 1, 2, 3 are special cases.

- 11388 - GCD LCM
Interesting problem; input is output.

- 11401 - Triangle Counting
DP, try to find the relation between the number of triangles between inputs n and n-1.

- 11407 - Squares
I am tempted to use greedy approach at first. But later I found that it was a wrong direction and used DP to solve it (Consider 12 as an example, the correct output is 3, but the greedy approach outputs otherwise).

- 11408 - Count DePrimes
Initially set all prime sum to 0. Then for each prime p, add p to the prime sum to 2*p, 3*p,... up to 5000000 until we have all the prime sums for [2..5000000]. Then, a number n is a Deprim if primeSum[primeSum[n]] = primeSum[n]. By this property we can construct an array deprime[1..5000000], whose values are either 0(non-deprime) or 1(deprime). Next, calculate the prefix sum for this array and answer each query in O(1) time.

- 11417 - GCD
- 11428 - Cubes
Brute force method

- 11436 - Cubes - EXTREME!!!
x^3 - y^3 = (x-y)*(x^2 + xy + y^2), and (x - y) &le cbrt(N)

- 11444 - Sum
The idea is to prepare 21 arrays of prefix sum to handle queries. I maintain a table of binomial coefficients C(k, *) and i

^{k}for k &le 20 and 0 &le i &le 100000. Then, I calculate 20 arrays of prefix sum &Sigma seq(i)*i^{k}for each possible k. When dealing with a query, use binomial theorem to expand (i + (1-a))^{k}, reducing the query equation to a series of prefix sums. - 11448 - Who said crisis?
- 11455 - Behold my quadrangle
- 11461 - Square Numbers
- 11462 - Age Sort
Counting sort

- 11466 - Largest Prime Divisor
The input may contain negative numbers, call abs() or labs() before calculating the answer.

- 11479 - Is this the easiest problem?
- 11483 - Code Creator
- 11494 - Queen
- 11496 - Musical Loop
- 11498 - Division of Nlogonia
- 11517 - Exact Change
Dynamic programming

- 11526 - H(n)
我的作法要 O(sqrt(n)) 的時間，剛好排到第 99 名，不知道有沒有更快的解；順道一提，n有可能是負數或 0，遇到這種 case 要 print 0。

- 11530 - SMS Typing
- 11541 - Decoding
- 11547 - Automatic Answer
- 11565 - Simple Equations
The same as Prob. 11571, but simpler.

- 11567 - Moliu Number Generator
If n is even, then divide n by 2. If n is odd,then check if INC is a better move than DEC.

- 11571 - Simple Equations - Extreme!!
This problems asks us to find the three roots of a cubic function x^3 + b*x^2 + c*x + d = 0, where b = -A, c = (A^2 - C)/2, and d = -C. The basic idea is using Newton's method to find a root α, and find another two roots β and γ by the quadratic function β + γ = A - α, β * γ = B/α.

If the range [-B^(1/3) .. B^(1/3)] contains odd number of roots, then apply Newton's method on this range to find α. Otherwise, find the positions p and q that have local minimum/maximum (p and q are the roots of 3*x^2 + 2b*x + c = 0). . The range [p..q] must contain one and only one root α, so we can use Newton's method to find it.

In this problem, precision is a big issue. I use data type long long and long double to avoid overflow. When running Newton's method, we are actually concerned about the signage of f(p) instead of its actual value. I calculate the signage of f(p) by 1 + b/p + c/p^2 + d/p^3 rather than p^3 + b*p^2 + c*p + d. If p is smaller than 0, negate the sign.

Newton's method not necessarily returns the precise value of α (I am not a competent programmer). So I double check the result, seeing if some of the seven values from α - 3 to α + 3 is a root of the cubic function.

Note: The problems states that x, y and z are different. If the roots are not different, the program should output No solution.

Remarks: fooling around with precision issue is really tedious.

- 11572 - Unique Snowflakes
The problem description is vague at the first glance. Maybe it can be rephrased as follows: Given an array A[1..n], find the sub-array of maximum length such that each element in the sub-array is unique. For example, A[] = {1 4 2

**8 7 4 3 2**4 5 }, the output is 5.I used ANSI-C tsearch function as a hash table. It is not a fast solution, but simple.

- 11577 - Letter Frequency
- 11579 - Triangle Trouble
- 11582 - Colossal Fibonacci Numbers!
- 11586 - Train Tracks
Just count the number of Ms and Fs. Special case: the number of pieces can be 0 or 1, in this case the program should output NO LOOP

- 11597 - Spanning Subtree
n/2

- 11608 - No Problem
No problem, indeed.

- 11609 - Teams
n*2

^{n-1}mod 1000000007 - 11614 - Etruscan Warriors Never Play Chess
(-1 + sqrt(1 + 8*n))/2

- 11615 - Family Tree
Find the depth for the two brothers in the tree, use the depth to find the number of their ancestors, pick up the smaller one, minus it from 2

^{n}- 1. - 11616 - Roman Numerals
- 11621 - Small Factors
Use the formula to generate all possible numbers (not may), and then use binary search to find the answer.

- 11628 - Another lottery
Just calculate the probability of winning the last round.

- 11631 - Dark roads
Build a minimum spanning tree

- 11634 - Generate random numbers
I use tsearch() in ANSI-C to build a hash table. When a new value is calculated and that value appears in the hash table, we find a cycle.

- 11636 - Hello World!
&lfloor log N &rfloor

- 11646 - Athletics Track
A simple math problem. It is better to use pen and paper to work out the math formula before coding.

- 11648 - Divide The Land
This problem takes more time on paper/pen than on computer. Let DE: AE = 1 : x. Use triangle similarity to find the value of x, which depends on only AB and CD. And output the answer based on x, AD and BC.

- 11650 - Mirror Clock
Amplify the angle of a circle from 360 to 10800 in order to avoid floating-point calculation.

- 11661 - Burger Time?
- 11666 - Logarithms
The equations in the problem description are a big hint.

Use double as the data type of floating points.

- 11677 - Alarm Clock
- 11686 - Pick up sticks
Topological sort

- 11687 - Digits
Note that 0 is a special case.

- 11689 - Soda Surpler
A simple loop can solve this problem.

- 11690 - Money Matters
For each connected component, check the sum of the debts is 0 or not.

- 11692 - Rain Fall
There are three cases for the output: (1) L < H (2) L = H and (3) L > H. The maximum/minimum heights for Cases (1) and (3) are the same.

- 11703 - sqrt log sin
- 11713 - Abstract Names
- 11714 - Blind Sorting
- 11715 - Car
- 11716 - Digital Fortress
- 11727 - Cost Cutting
- 11734 - Big Number of Teams will Solve This
- 11764 - Jumping Mario
- 11804 - Argentina
Sort the input based on the problem description.

- 11805 - Bafana Bafana
- 11824 - A Minimum Land Price
- 11827 - Maximum GCD
- 11830 - Contract Revision
- 11834 - Elevator
Put one cylinder against the upper/left walls and another one against the lower/right walls. Calculate the distance between the centers.

- 11838 - Come and Go
Run BFS traversal n times.

- 11839 - Optical Reader
- 11847 - Cut the Silver Bar
- 11849 - CD
- 11850 - Alaska
- 11854 - Egypt
- 11875 - Brick Game
- 11876 - N + NOD (N)
- 11877 - The Coco-Cola Store
- 11878 - Homework Checker
- 11879 - Multiple of 17
No need for bigNumber calculation, just a simple string manipultation. The input string has to be manipulated until its length is <= 2.

- 11889 - Benefit
Factor A and C to find B.

- 11900 - Boiled Eggs
- 11904 - One Unit Machine
- 11908 - Skyscraper
interval scheduling problem

- 11909 - Soya Milk
simple math.

- 11910 - Closest Fractions
When a input is smaller than 0, the output is the same as those of 0 (but be careful, the output is a 10-char string, with one minus sign and 9 digits). Similarly, input that is greater than 1000 is treated like 1000. For each input number, I ran a loop for y = 1 to 1000, calculate x = input * y, find 5 numbers (x-2)/y, (x-1)/y, x/y, (x+1)/y, and (x+2)/y. Then, Sorted those numbers based on the difference between the number and the input. Finally produce the outputs.

- 11917 - Do Your Own Homework

## 沒有留言:

張貼留言