2010/11/03

[Life] 溫故知新

近來閒閒無事,就利用點時間復習一下程式語言,有時候去 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(n4); 把問題 reduce 成 1D array 可以得到 O(n3) 的解

  • 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 Cn = 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! * Cn.

  • 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 Kn. The answer is nn-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 1018.

    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 Gergovia

    Greedy 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 231 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

    &Sigma1 &le i &le n 1/(i(i+1)(i+2)(i+3)) = n(n2 + 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 ik for k &le 20 and 0 &le i &le 100000. Then, I calculate 20 arrays of prefix sum &Sigma seq(i)*ik 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*2n-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 2n - 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

沒有留言: