{"id":"51cc1d22-954d-4044-8aa7-297923f0e8ce","name":"Paint Fence","description":"1. You are given a number n and a number k in separate lines, representing the number of fences and number of colors.\r\n2. You are required to calculate and print the number of ways in which the fences could be painted so that not more than two consecutive fences have same colors.","inputFormat":"A number n\r\nA number k","outputFormat":"A number representing the number of ways in which the fences could be painted so that not more than two fences have same colors.","constraints":"1 &lt;= n &lt;= 10\r\n1 &lt;= k &lt;= 10","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n\nusing namespace std;\n\n int main() {\n int n ;\n cin>>n ;\n int k ;\n cin>>k ;\n \n //write your code here\n }"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n\r\n }\r\n}"},"python":{"code":"def numWays(n: int, k: int):\n #write your code here\n \nn=int(input())\nk=int(input())\n\nprint(numWays(n,k))"}},"points":10,"difficulty":"easy","sampleInput":"8\r\n3","sampleOutput":"3672","questionVideo":"https://www.youtube.com/embed/ju8vrEAsa3Q?end=56","hints":[],"associated":[{"id":"88b63233-f30a-4ed2-8800-a3ec3deea633","name":"What will happen when we don't handle base case in recursive DP approach?","slug":"what-will-happen-when-we-don-t-handle-base-case-in-recursive-dp-approach","type":4},{"id":"98feb3a1-4353-449c-8545-2c4e77a73a5c","name":"if we are maintaining 2 dp-table of size n, the time complexity will be:","slug":"if-we-are-maintaining-2-dp-table-of-size-n-the-time-complexity-will-be","type":4},{"id":"bb5bb0c6-7cba-4186-809c-4564a3a2569d","name":"DP optimizes the solution by taking advantage of which of the following:","slug":"dp-optimizes-the-solution-by-taking-advantage-of-which-of-the-following","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"52d62581-1313-45fb-aaf0-1d72a45f6a50","name":"Dynamic Programming And Greedy For Beginners","slug":"dynamic-programming-and-greedy-for-beginners","type":0},{"id":"d6d73b61-71ce-4d98-9a3f-64beeeb66b0a","name":"Paint Fence","slug":"paint-fence","type":1}],"next":{"id":"34405f41-0f24-4d14-b3a3-f767e8cbccc9","name":"Paint Fence","type":3,"slug":"paint-fence"},"prev":{"id":"05abd83c-e89d-4861-952f-965118bc3dbb","name":"Paint House-Many Colors","type":3,"slug":"paint-house-many-colors"}}}

Paint Fence

1. You are given a number n and a number k in separate lines, representing the number of fences and number of colors. 2. You are required to calculate and print the number of ways in which the fences could be painted so that not more than two consecutive fences have same colors.

{"id":"51cc1d22-954d-4044-8aa7-297923f0e8ce","name":"Paint Fence","description":"1. You are given a number n and a number k in separate lines, representing the number of fences and number of colors.\r\n2. You are required to calculate and print the number of ways in which the fences could be painted so that not more than two consecutive fences have same colors.","inputFormat":"A number n\r\nA number k","outputFormat":"A number representing the number of ways in which the fences could be painted so that not more than two fences have same colors.","constraints":"1 &lt;= n &lt;= 10\r\n1 &lt;= k &lt;= 10","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n\nusing namespace std;\n\n int main() {\n int n ;\n cin>>n ;\n int k ;\n cin>>k ;\n \n //write your code here\n }"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n\r\n }\r\n}"},"python":{"code":"def numWays(n: int, k: int):\n #write your code here\n \nn=int(input())\nk=int(input())\n\nprint(numWays(n,k))"}},"points":10,"difficulty":"easy","sampleInput":"8\r\n3","sampleOutput":"3672","questionVideo":"https://www.youtube.com/embed/ju8vrEAsa3Q?end=56","hints":[],"associated":[{"id":"88b63233-f30a-4ed2-8800-a3ec3deea633","name":"What will happen when we don't handle base case in recursive DP approach?","slug":"what-will-happen-when-we-don-t-handle-base-case-in-recursive-dp-approach","type":4},{"id":"98feb3a1-4353-449c-8545-2c4e77a73a5c","name":"if we are maintaining 2 dp-table of size n, the time complexity will be:","slug":"if-we-are-maintaining-2-dp-table-of-size-n-the-time-complexity-will-be","type":4},{"id":"bb5bb0c6-7cba-4186-809c-4564a3a2569d","name":"DP optimizes the solution by taking advantage of which of the following:","slug":"dp-optimizes-the-solution-by-taking-advantage-of-which-of-the-following","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"52d62581-1313-45fb-aaf0-1d72a45f6a50","name":"Dynamic Programming And Greedy For Beginners","slug":"dynamic-programming-and-greedy-for-beginners","type":0},{"id":"d6d73b61-71ce-4d98-9a3f-64beeeb66b0a","name":"Paint Fence","slug":"paint-fence","type":1}],"next":{"id":"34405f41-0f24-4d14-b3a3-f767e8cbccc9","name":"Paint Fence","type":3,"slug":"paint-fence"},"prev":{"id":"05abd83c-e89d-4861-952f-965118bc3dbb","name":"Paint House-Many Colors","type":3,"slug":"paint-house-many-colors"}}}
plane

Editor

Loading...

Paint Fence

easy

1. You are given a number n and a number k in separate lines, representing the number of fences and number of colors. 2. You are required to calculate and print the number of ways in which the fences could be painted so that not more than two consecutive fences have same colors.

Constraints

1 <= n <= 10 1 <= k <= 10

Format

Input

A number n A number k

Output

A number representing the number of ways in which the fences could be painted so that not more than two fences have same colors.

Example

Sample Input

8 3

Sample Output

3672

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode