10400 - Game Show Math
I know that from the problem description, the maximum possible combination of the solution is 4^100, which is impossible to calculate. However, I've tried that backtracking with efficient pruning is enough to pass the time limit. Prune when: current value is > 32.000 or < -32.000, or when that value already reached (which means your DFS create cycles...) 10404 - Bachet's Game Working forwards from n to 0 is not recommended since the search space is extremely too big. Instead, works backward. If you know that if n==0 and it's Ollie's turn, then Stan obviously win, because Stan has just reached 0 previously. If n == 1, 3 or 8, the set of legal moves is {1,3,8}, and it's again Stan's turn then Stan will win because his next step will reach state when n == 0 and Ollie's turn. If n == 2, the set of legal moves is {1,3,8}, and it's Stan's turn, then Stan will lose since he can only move to state when n == 1 and Ollie's turn. Ollie will then use her turn to win the game. Works this reasoning backwards, up to N. Apply Dynamic Programming by using table to store the intermediate values. 10405 - Longest Common Subsequence Refer to my programming page, Dynamic Programming section, regarding LCS. 10407 - Simple division The idea is to find GCD of multiple numbers. Example from sample input 1: The value d = 179 can divide the set of integers { 701 1059 1417 2312 }, leaving the same remainder r = 164. Value d can be calculated by finding the GCD of = GCD (1059-701, 1417-701, 2312-701) = GCD (358, 716, 1611) = 179 Since GCD (179) will exactly divides 358, 716, 1611 without any remainders..., then all the original numbers {701 1059 1417 2312} will have remainder of exactly 701 mod 179 = 164. Since the input is in increasing order, the first number in the set will definitely be the smallest and in overall this algorithm will output the biggest d. 10408 - Farey sequences I know that there is a simpler pattern to solve this problem. However, I've tried that using brute force can pass the time limit. First, generate all possible (i,j) pairs where 1 <= i,j <= n, and gcd(i,j) == 1... (this implies an O(n^2) algorithm), then sort them using quick sort based on their fraction values. After that simply get the k'th index and print it. 10409 - Die Game Very easy, just simulate, total brute force... 10415 - Eb Alto Saxophone Player Another simulation, use Boolean array to store pressed/un-pressed state. Number of presses increased if and only if that finger is currently in un-pressed state and now you pressed it. A lot of 'switches' and 'ifs' is required here. 10420 - List of Conquests This problem is a simple frequency counting. There are many ways to do this, the simplest is to sort the country names (you can ignore all the girls' names...), then count how many time these countries appears. 10422 - Knights in FEN A simple backtracking will do. The depth limit is 11 moves, if you do it carefully, you should be able to pass the time limit. There must be a faster way... (I see some of you can get Accepted with less than 1 sec), however I don't know the trick yet... 10424 - Love Calculator Simply the value of 2 given string as given in problem description (digit sum), then compare the ratio... remember that ratio can't be greater than 100%, therefore you must select the smaller between the 2 numbers as numerator and the larger as denominator :) 10432 - Polygon Inside A Circle First, to avoid stupid precision error, define pi = 2*acos(0.0) !!! Then to calculate the area of the polygon, simply divide them into n smaller triangles. Based on the given radius r, you can get the height and width of this small triangles by trigonometry relation. Finally, calculate the total area of this n triangles :) 10440 - Ferry Loading II Greedy works. I will not give the proof here, I don't like proofing. However the logical thought are as follows: For optimality the last ferry must take the last n cars... correct? Then... the 1st ferry must take the 1st car (car 0) up to car m%n if => m%n != 0
or up to car n if m%n == 0... (otherwise last ferry won't take n cars...)
Now for each ferry trip, last car carried by this ferry trip's time + 2*t is the time this ferry return (for subsequent cars...). If any subsequent car arrives before this, they have to wait. Shift all car arrival timings accordingly. (i.e. if ferry returns at time 50, all cars that arrive < 50 must wait at least until time 50). Then, time the last car + t (one trip to the other side) is the time last car arrive at destination, the completion time. Done :D 10443 - Rock, Scissors, Paper This problem is really about manipulating array content (which is a bit hard to debug in my opinion). Prepare two grid arrays (yes, you need 2!!!), then update the new array content based on the content of the old array content + Rock, Scissors, Paper rule. 10450 - World Cup Noise (explanation taken from Message Board) From the problem description, we must find the number of all binary-strings of length n that don't have consecutive ones. Let f(n) = number of binary-strings of length n that don't have consecutive ones. We can split f(n) into two: 1. f0(n) : number of strings that start with '0'. 2. f1(n) : number of strings that start with '1'. Let's consider f1(n) If the string starts with '1', clearly the next digit has to be '0', so, the strings are fixed to "10????...". Starting from s[2] until s[n-1], the values are chosen so there is no consecutive ones. That means it is the same as calculating f(n-2). f0(n) starts with '0', the next digit can be either '0' or '1' ... The strings are only fixed to pattern "0????..." and the rest should be chosen in such a way so that no consecutive ones are found. It's the same as recursively calculating f(n-1). We can see that f(n) = f(n-2) + f(n-1) ... which is Fibonacci sequence. 10451 - Ancient Village Sports This problem is basically a twisted problem 10432 (see above), if you know the formula to solve 10432, then you'll be able to derive similar (but a bit different) formula to solve this. 10452 - Marcus, help! The issue of whether the God "IEHOVA" exist or not is another issue. In this problem, use DFS to correctly choose the step to reach the destination. Note that this path is definitely exist (see problem description), so your output should always be 7 steps... 10465 - Homer Simpson I know the problem description seems unclear. However after some contemplation, I realize that this is just a standard DP problem. Create two arrays, maxBurger[1..T] and beer[1..T], then use the following derivation: Base case, from time t, from 1 to min(m,n) - 1: The number of burger that Homer can take is 0, i.e. maxBurger[t] = 0; Homer must drink t litres of beer, i.e. beer[t] = t; General case, from time min(m,n) to T: The number of burger that Homer can take is max(maxBurger[t-n],maxBurger[t-m]) + 1 But, in this problem, we must consider another criteria, take those burger if the number of beer needed is smaller. I'll leave this to you to figure out how to handle this :) 10466 - How Far? A simple trigonometry problem. I'm sure you already know this formula from high school, that in right triangle: length_of_x = cos(degree) * radius and length_of_y = sin(degree) * radius. This problem just ask you to calculate them... 10469 - To Carry or not to Carry Use unsigned long, and then simply XoR them :) 10473 - Simple Base Conversion Base number conversion is popular topic, refer to math books if you don't know how to do this. 10474 - Where is the Marble? Read the input, sort them, then search the query element using binary search. Don't forget to find the first element that is matched with the query instead of the one that returned by binary search. 10487 - Closest Sums Read the input, sort them, and then do O(n^2) pairing..., if the sum has the closest match to the query, output it. Purely brute force :p 10489 - Boxes of Chocolates (By: Niaz) A very simple problem. You will be given a sequence of box descriptions. Just multiply the elements with each other and finally MOD by number of friends and the remainder will be the result. But there is a big problem. If you do it this way, your value will overflow. To avoid this, we will take the help of modular operation. According to modular operation we can do MOD just after each multiplication. Example: input 1 5 1 3 2 3 4 output 4 Calculation for this input: R = 1 R = (R * 2) % 5 R = (R * 3) % 5 R = (R * 4) % 5 Now R will holds 4. For large value this method will help you to avoid overflow. NOTE: In case of more than one line, take the sum for each line and finally MOD it with number of friends. 10490 - Mr. Azad and his Son!!!!! You can count it yourself, after that pre-calculate the answers. First 10 primes <= 31 are {2,3,5,7,11,13,17,19,23,29,31}; n == 11 || n == 23 || n == 29 are prime but not perfect, exclude them. For the rest, just calculate 2^(k-1) * (2^k - 1) 10491 - Cows and Cars (Derivation by: Victor Loh) The solution for this problem is: (1.0*(ncows*ncars+ncars*(ncars-1))/(ncows+ncars-nshow-1))/(ncows+ncars)); Derivation: P(winning a car) = P(car 1st & change to another car) + P(cow 1st & change to car) P(car 1st & change to another car) = ncar/(ncar + ncow) * (ncar-1)/(ncar + ncow - nshow - 1) P(cow 1st & change to car) = ncow/(ncar + ncow) * ncar/(ncar + ncow - nshow - 1) Simplifying and we get your formula, and further simplification gives you: ncar * (ncow + ncar - 1) ----------------------------------------- (ncow+ncar) * (ncow + ncar - nshow - 1) 10496 - Collecting Beepers A simple backtracking problem. Simply enumerate all possible paths that Karel may take. Prune the search tree as necessary (when current length is already exceed best known shortest path length). 10499 - The Land of Justice Okay, just follow this derivation: 1. Do you know that 4 * area of circle = area of sphere (their diameter must be the same) 2. Every cut that you do, will create 2 * 1/2 * area of circle + 1/N * area of sphere 3. If you have N cuts, you will have: N * (2 * 1/2 * area of circle + 1/ N * area of sphere) 4. The formula can be simplified to: N * area of circle + area of sphere 5. Substitute area of circle == 1/4 area of sphere 6. Our formula is now: N/4 area of sphere + area of sphere 7. We want to know our profit: which is: area of all cuts / area of original sphere 8. (1 + N/4) area of sphere / area of sphere == 1 + N/4, our profit is N/4. 9. Since we want it to be displayed in percentage, profit: N/4 * 100 ==> N * 25.
10. Finished... BUT... don't forget the special case: if N == 1, you don't have any profit!!!
I know that from the problem description, the maximum possible combination of the solution is 4^100, which is impossible to calculate. However, I've tried that backtracking with efficient pruning is enough to pass the time limit. Prune when: current value is > 32.000 or < -32.000, or when that value already reached (which means your DFS create cycles...) 10404 - Bachet's Game Working forwards from n to 0 is not recommended since the search space is extremely too big. Instead, works backward. If you know that if n==0 and it's Ollie's turn, then Stan obviously win, because Stan has just reached 0 previously. If n == 1, 3 or 8, the set of legal moves is {1,3,8}, and it's again Stan's turn then Stan will win because his next step will reach state when n == 0 and Ollie's turn. If n == 2, the set of legal moves is {1,3,8}, and it's Stan's turn, then Stan will lose since he can only move to state when n == 1 and Ollie's turn. Ollie will then use her turn to win the game. Works this reasoning backwards, up to N. Apply Dynamic Programming by using table to store the intermediate values. 10405 - Longest Common Subsequence Refer to my programming page, Dynamic Programming section, regarding LCS. 10407 - Simple division The idea is to find GCD of multiple numbers. Example from sample input 1: The value d = 179 can divide the set of integers { 701 1059 1417 2312 }, leaving the same remainder r = 164. Value d can be calculated by finding the GCD of = GCD (1059-701, 1417-701, 2312-701) = GCD (358, 716, 1611) = 179 Since GCD (179) will exactly divides 358, 716, 1611 without any remainders..., then all the original numbers {701 1059 1417 2312} will have remainder of exactly 701 mod 179 = 164. Since the input is in increasing order, the first number in the set will definitely be the smallest and in overall this algorithm will output the biggest d. 10408 - Farey sequences I know that there is a simpler pattern to solve this problem. However, I've tried that using brute force can pass the time limit. First, generate all possible (i,j) pairs where 1 <= i,j <= n, and gcd(i,j) == 1... (this implies an O(n^2) algorithm), then sort them using quick sort based on their fraction values. After that simply get the k'th index and print it. 10409 - Die Game Very easy, just simulate, total brute force... 10415 - Eb Alto Saxophone Player Another simulation, use Boolean array to store pressed/un-pressed state. Number of presses increased if and only if that finger is currently in un-pressed state and now you pressed it. A lot of 'switches' and 'ifs' is required here. 10420 - List of Conquests This problem is a simple frequency counting. There are many ways to do this, the simplest is to sort the country names (you can ignore all the girls' names...), then count how many time these countries appears. 10422 - Knights in FEN A simple backtracking will do. The depth limit is 11 moves, if you do it carefully, you should be able to pass the time limit. There must be a faster way... (I see some of you can get Accepted with less than 1 sec), however I don't know the trick yet... 10424 - Love Calculator Simply the value of 2 given string as given in problem description (digit sum), then compare the ratio... remember that ratio can't be greater than 100%, therefore you must select the smaller between the 2 numbers as numerator and the larger as denominator :) 10432 - Polygon Inside A Circle First, to avoid stupid precision error, define pi = 2*acos(0.0) !!! Then to calculate the area of the polygon, simply divide them into n smaller triangles. Based on the given radius r, you can get the height and width of this small triangles by trigonometry relation. Finally, calculate the total area of this n triangles :) 10440 - Ferry Loading II Greedy works. I will not give the proof here, I don't like proofing. However the logical thought are as follows: For optimality the last ferry must take the last n cars... correct? Then... the 1st ferry must take the 1st car (car 0) up to car m%n if => m%n != 0
or up to car n if m%n == 0... (otherwise last ferry won't take n cars...)
Now for each ferry trip, last car carried by this ferry trip's time + 2*t is the time this ferry return (for subsequent cars...). If any subsequent car arrives before this, they have to wait. Shift all car arrival timings accordingly. (i.e. if ferry returns at time 50, all cars that arrive < 50 must wait at least until time 50). Then, time the last car + t (one trip to the other side) is the time last car arrive at destination, the completion time. Done :D 10443 - Rock, Scissors, Paper This problem is really about manipulating array content (which is a bit hard to debug in my opinion). Prepare two grid arrays (yes, you need 2!!!), then update the new array content based on the content of the old array content + Rock, Scissors, Paper rule. 10450 - World Cup Noise (explanation taken from Message Board) From the problem description, we must find the number of all binary-strings of length n that don't have consecutive ones. Let f(n) = number of binary-strings of length n that don't have consecutive ones. We can split f(n) into two: 1. f0(n) : number of strings that start with '0'. 2. f1(n) : number of strings that start with '1'. Let's consider f1(n) If the string starts with '1', clearly the next digit has to be '0', so, the strings are fixed to "10????...". Starting from s[2] until s[n-1], the values are chosen so there is no consecutive ones. That means it is the same as calculating f(n-2). f0(n) starts with '0', the next digit can be either '0' or '1' ... The strings are only fixed to pattern "0????..." and the rest should be chosen in such a way so that no consecutive ones are found. It's the same as recursively calculating f(n-1). We can see that f(n) = f(n-2) + f(n-1) ... which is Fibonacci sequence. 10451 - Ancient Village Sports This problem is basically a twisted problem 10432 (see above), if you know the formula to solve 10432, then you'll be able to derive similar (but a bit different) formula to solve this. 10452 - Marcus, help! The issue of whether the God "IEHOVA" exist or not is another issue. In this problem, use DFS to correctly choose the step to reach the destination. Note that this path is definitely exist (see problem description), so your output should always be 7 steps... 10465 - Homer Simpson I know the problem description seems unclear. However after some contemplation, I realize that this is just a standard DP problem. Create two arrays, maxBurger[1..T] and beer[1..T], then use the following derivation: Base case, from time t, from 1 to min(m,n) - 1: The number of burger that Homer can take is 0, i.e. maxBurger[t] = 0; Homer must drink t litres of beer, i.e. beer[t] = t; General case, from time min(m,n) to T: The number of burger that Homer can take is max(maxBurger[t-n],maxBurger[t-m]) + 1 But, in this problem, we must consider another criteria, take those burger if the number of beer needed is smaller. I'll leave this to you to figure out how to handle this :) 10466 - How Far? A simple trigonometry problem. I'm sure you already know this formula from high school, that in right triangle: length_of_x = cos(degree) * radius and length_of_y = sin(degree) * radius. This problem just ask you to calculate them... 10469 - To Carry or not to Carry Use unsigned long, and then simply XoR them :) 10473 - Simple Base Conversion Base number conversion is popular topic, refer to math books if you don't know how to do this. 10474 - Where is the Marble? Read the input, sort them, then search the query element using binary search. Don't forget to find the first element that is matched with the query instead of the one that returned by binary search. 10487 - Closest Sums Read the input, sort them, and then do O(n^2) pairing..., if the sum has the closest match to the query, output it. Purely brute force :p 10489 - Boxes of Chocolates (By: Niaz) A very simple problem. You will be given a sequence of box descriptions. Just multiply the elements with each other and finally MOD by number of friends and the remainder will be the result. But there is a big problem. If you do it this way, your value will overflow. To avoid this, we will take the help of modular operation. According to modular operation we can do MOD just after each multiplication. Example: input 1 5 1 3 2 3 4 output 4 Calculation for this input: R = 1 R = (R * 2) % 5 R = (R * 3) % 5 R = (R * 4) % 5 Now R will holds 4. For large value this method will help you to avoid overflow. NOTE: In case of more than one line, take the sum for each line and finally MOD it with number of friends. 10490 - Mr. Azad and his Son!!!!! You can count it yourself, after that pre-calculate the answers. First 10 primes <= 31 are {2,3,5,7,11,13,17,19,23,29,31}; n == 11 || n == 23 || n == 29 are prime but not perfect, exclude them. For the rest, just calculate 2^(k-1) * (2^k - 1) 10491 - Cows and Cars (Derivation by: Victor Loh) The solution for this problem is: (1.0*(ncows*ncars+ncars*(ncars-1))/(ncows+ncars-nshow-1))/(ncows+ncars)); Derivation: P(winning a car) = P(car 1st & change to another car) + P(cow 1st & change to car) P(car 1st & change to another car) = ncar/(ncar + ncow) * (ncar-1)/(ncar + ncow - nshow - 1) P(cow 1st & change to car) = ncow/(ncar + ncow) * ncar/(ncar + ncow - nshow - 1) Simplifying and we get your formula, and further simplification gives you: ncar * (ncow + ncar - 1) ----------------------------------------- (ncow+ncar) * (ncow + ncar - nshow - 1) 10496 - Collecting Beepers A simple backtracking problem. Simply enumerate all possible paths that Karel may take. Prune the search tree as necessary (when current length is already exceed best known shortest path length). 10499 - The Land of Justice Okay, just follow this derivation: 1. Do you know that 4 * area of circle = area of sphere (their diameter must be the same) 2. Every cut that you do, will create 2 * 1/2 * area of circle + 1/N * area of sphere 3. If you have N cuts, you will have: N * (2 * 1/2 * area of circle + 1/ N * area of sphere) 4. The formula can be simplified to: N * area of circle + area of sphere 5. Substitute area of circle == 1/4 area of sphere 6. Our formula is now: N/4 area of sphere + area of sphere 7. We want to know our profit: which is: area of all cuts / area of original sphere 8. (1 + N/4) area of sphere / area of sphere == 1 + N/4, our profit is N/4. 9. Since we want it to be displayed in percentage, profit: N/4 * 100 ==> N * 25.
10. Finished... BUT... don't forget the special case: if N == 1, you don't have any profit!!!
