Given a string consist just of the letter 'u' ,if we can consider every two adjacent 'u' -->' w' and every u can be used only once in how many ways the string can appear ?
example : uuu can be uuu or wu or u w so the answer is 3 .
I am asking this question because at the last contest I was trying to solve this problem https://codeforces.net/contest/1245/problem/C and I claim the solution is every continuous 'u' or 'n' I save in how many ways it can appear in a vector and then multiply all the numbers and this is the answer .
Trace if you have 2,3,4,5 consecutive u or n and will observe the right pattern
It will be Fibonacci series at the end.
Could you please tell the reason behind this fibonacci Pattern
It_Wasnt_Me Thanks
Let say F(n) is the amount of ways the string uuu...uu (n times) can appear. We can do two things: (1) Keep the last character as 'u': then, there are remaining n-1 characters. (2) Use the last two characters as 'w': then, there are remaining n-2 characters. Therefore: F(n) = F(n-1) + F(n-2) for n > 2. F(1) = 1, because you can't change a single 'u'. F(2) = 2, because 'uu' can be 'uu' or 'w'
aniervs Thanks
Beautiful!
It can be generalized as, if 'uu...'(m times) is replace by 'w'.
Then, F(n) = ̷F̷(̷n̷-̷1̷)̷ ̷+̷ ̷F̷(̷n̷-̷2̷)̷ ̷+̷ ̷.̷.̷.̷ ̷+̷ ̷F̷(̷n̷-̷m̷)̷;
Edit : — F(n) = F(n-1) + F(n-m), look at aniervs comment below.
If 'uuu...u' (m times) is replaced by 'w'. Then we can: (1) Keep last character as 'u': there are remaining n-1 characters. (2) Use the last m characters as 'w': then, there are n-m characters. Therefore: F(n) = F(n-1) + F(n-m)