Hello Akash, I think the approach is simple. You just need to figure out a way to count all the numbers where 3 follows 1, and those numbers should be less than N.
And the number of configurations will be N - (count of numbers where 3 follows 1) - 1. The last subtraction with 1 in the end is for dish number 0. Eg. In case of N=1113, no. of configurations is 1064 because The count of numbers where 3 follows 1 is 48. The numbers are as follows: 13, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 103, 113, 123, 143. 153, 163, 173, 183,193, 213, 313, 413, 513, 613, 713, 813, 913, 1013, 1023, 1033, 1043, 1053, 1063, 1073, 1083, 1093, 1030, 1031, 1032, 1033, 1034, 1035, 1036, 1037, 1038, 1039, 1113 So, 1113 - 48 - 1 = 1064 -- The subtraction with 1 denotes consideration of dish 0. The numbers above show a pattern that can be used to find the count of such numbers. But now the task is to find and use an efficient data structure that can help us achieve that. I could come up with only this solution now and I know its not an efficient one but can be considered as a rough approach.(A food for thought)! On 3/5/11, Akash Mukherjee <akash...@gmail.com> wrote: > Hi, > > I need some help. I am still a nube so if this is too easy, plz don't flame. > I cannot understand how to approach the problem. Would appreciate any help. > > At CodeChef, The Chef can make 10 types of dishes numbered 0 through 9. He > can however only make dishes one after another. Suppose The Chef made dishes > 1, 4, 2, 1, 2, 1 on a given day, the number configuration that day would be > 142121. On a given day, he makes any number of dishes as long as: > > 1. The number configuration for that day is greater than zero(0) and less > than or equal to 'N'. > 2. Dish 3 is never made *after* dish 1 has been made. > 3. Dish 0 is never the first dish of the day, to be prepared. > > > How many such unique number configurations exist for a given 'N'? > > Examples: > > - 1 is a valid configuration > - 52 is a valid configuration > - 12 is a valid configuration > - 32 is a valid configuration > - 321 is a valid configuration > - 3231 is a valid configuration > - 120 is a valid configuration > - 012 is not a valid configuration > - 123 is not a valid configuration > - 32123 is not a valid configuration > > The first line of the input will contain a number T (1 ≤ T ≤ 1000) > containing the number of test cases. Each line that follows is a separate > test case which has exactly 1 integer 'N' (1 ≤ N < 1018). For each case, > output a single line containing the number of configurations possible for > that 'N'. > *Sample Input:* > > 5 > 10 > 15 > 115 > 1113 > 123456789 > > *Sample Output:* > > 10 > 14 > 112 > 1064 > 92470733 > > Thanks > Akash > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
