●●● ●●●● ●●●●● ●●●● ●●0●● How many pieces of land? ●●●0 ●●●● Input The first line of the input file contains one integer s(0 s< 3500), which indicates how many sets of input are there. The next s lines contain S sets of input Each input contains one integer N (0<=N<231) Output Sample input Sample output For each set of input you should output in a single line the maximum number pieces of land possible to get for the value of N 41234
How many pieces of land? ⚫ Input ⚫ The first line of the input file contains one integer S (0 < S < 3500), which indicates how many sets of input are there. The next S lines contain S sets of input. Each input contains one integer N (0<=N<2^31). ⚫ Output ⚫ For each set of input you should output in a single line the maximum number pieces of land possible to get for the value of N. 16 Sample Input: 4 1 2 3 4 Sample Output: 1 2 4 8
●●● ●●●● ●●●●● ●●●● ●●0●● Analysis ●●●0 ●●●● Denote the solution by f(n), so f(1)=1, f(2)=2, etc What's the relationship between f(n)and f(n-1)? Assume we have a maximum number of pieces for n-1 points, Which is f(n-1) o Now we add the nth point. We can connect this point to other n-1 points. So we have n-1 new lines ● Each line wil‖ lead to more pieces
Analysis ⚫ Denote the solution by f(n), so f(1) = 1, f(2) = 2, etc. ⚫ What’s the relationship between f(n) and f(n-1)? ⚫ Assume we have a maximum number of pieces for n-1 points, which is f(n-1). ⚫ Now we add the nth point. We can connect this point to other n-1 points. So we have n-1 new lines. ⚫ Each line will lead to more pieces. 17
●●● ●●●● ●●●●● ●●●● ●●0●● Analysis(Cont ●●●0 ●●●● i nodes on the left k Consider adding a new line n-2-i nodes on the right between node n and k The new line will intersect with i(n-2- number of lines So, the new line will be divided into i(n-2-1)+1 segments Each segment means a new plece f()=/(n-1)+∑(n-2-1)+1 0
Analysis (Cont.) 18 n k i nodes on the left Consider adding a new line n-2-i nodes on the right between node n and k. The new line will intersect with i(n-2-i) number of lines. So, the new line will be divided into i(n-2-i)+1 segments. Each segment means a new piece! 1 0 ( ) ( 1) [ ( 2 ) 1] n i f n f n i n i − = = − + − − +
●●● ●●●● ●●●●● ●●●● ●●0●● Practice 2: Counting ●●●0 ●●●● http://acm.uva.es/p/v101/10198.html Gustavo knows how to count, but he is now learning how write numbers. as he is a very good student, he already learned 1, 2 3 and 4. But he didn 't realize yet that 4 is different than 1, so he thinks that 4 is another way to write 1. Besides that, he is having fun with a little game he created himself: he make numbers(with those four digits) and sum their values. For instance 132=1+3+2=6 112314=1+1+2+3+1+1=9(remember that Gustavo thinks that 4 After making a lot of numbers in this way gustavo now wants to know how much numbers he can create such that their sum is a number n For instance, for n =2 he noticed that he can make 5 numbers: 11, 14, 41, 44 and 2 (he knows how to count them up but he doesn't know how to write five). However, he cant figure it out for n greater than 2. So, he asked you to help him
Practice 2: Counting ⚫ http://acm.uva.es/p/v101/10198.html ⚫ Gustavo knows how to count, but he is now learning how write numbers. As he is a very good student, he already learned 1, 2, 3 and 4. But he didn't realize yet that 4 is different than 1, so he thinks that 4 is another way to write 1. Besides that, he is having fun with a little game he created himself: he make numbers (with those four digits) and sum their values. For instance: ⚫ 132 = 1 + 3 + 2 = 6 ⚫ 112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (remember that Gustavo thinks that 4 = 1) ⚫ After making a lot of numbers in this way, Gustavo now wants to know how much numbers he can create such that their sum is a number n. For instance, for n = 2 he noticed that he can make 5 numbers: 11, 14, 41, 44 and 2 (he knows how to count them up, but he doesn't know how to write five). However, he can't figure it out for n greater than 2. So, he asked you to help him. 19