DCP-342: Marvel’s Smartest Back to All Problems

Medium Divide and Conquer > Dynamic Programming

**Amedeus Cho** helped **Bruce Banner** survive a radiation explosion and in the process he was exposed to the gamma radiation, becoming the “Totally Awesome Hulk”. Amedeus , with the help of his genious sister Madame Cho, roams in New York and fights crime with a chilled mood, turning into a jolly yet gruesome Hulk. Amedues is ranked as the 8th smartest person in the Marvel Universe, behind Hank Pym, Moon Girl, Bruce Banner, Tony Stark, Hank McCoy, Dr.Doom, T’Chala. But Madame Cho thinks her brother is naive and not smarter than her. To test Amedeus’s intelligence, she thought of a mathematical question. And here she is, Madame Cho, asking him the question, “ Let us call a **n-digit** number (n is an integer , **1<=n<=100000**) a Meme-number if it consists of digits from **0,1,2,3,4** and the difference between any two consecutive digit in the number is exactly two. How many n-digit numbers are there who are Meme-numbers?” Input: ------ Input will consist of N+1 lines in separate line ( **1<=N <=100000**) First line will contain N, the number of values of **n**. Next N line will contain one integer each denoting the value of n. Output: ------- For each n, print the number of n-digit numbers which are Meme-numbers. You should print the answer modulo **10^9+7**. Sample Input ------------ 2 1 2 Sample Output ------------- 5 6 Explanation: There are 2 inputs: n=1,2 For n=1, possible Meme-numbers are { 0, 1, 2, 3, 4}=>5 For n=2, possible Meme-numbers are {20, 31, 02, 42,13, 24}=>6

Problem Setter:

Mir Imtiaz Mostafiz

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats




# User Language Timing
01 swapnilsaha Cpp14 0.00s
02 prodipdatta7 Cpp14 0.00s
03 moshiur_cse15 Cpp14 0.00s
04 kissu_pari_na Cpp 0.00s
05 Morass Cpp14 0.00s
06 prateepm Cpp14 0.01s
07 feodorv C 0.01s
08 mno123 Cpp 0.01s
09 ittehad Cpp 0.01s
10 emrul Cpp14 0.01s
11 sazal_dev Cpp 0.01s
12 Double_O Cpp14 0.01s
13 robin_aust Cpp 0.01s
14 nasif2587 Cpp14 0.01s
15 ssavi Cpp14 0.01s
16 shaft Cpp 0.01s
17 as_couple Cpp14 0.02s
18 Mahmudul_Tushar Cpp 0.02s
19 nafiz0080 Cpp14 0.02s
20 ksohan Cpp 0.02s
21 Zeronfinity Cpp14 0.02s
22 dmehrab06 Cpp14 0.02s
23 njrafi Cpp14 0.02s
24 alttlprgrmmng Cpp 0.02s
25 Ishrak Cpp 0.02s
26 AlaminJust Cpp14 0.02s
27 Islam_Rafat Cpp14 0.02s
28 Sarwar05 Cpp 0.03s
29 vatsalsharma376 Cpp14 0.03s
30 nasib_mbstu Cpp 0.03s
31 Masum_ice Cpp14 0.03s
32 Foysol_Ahmed Cpp 0.03s
33 tariqiitju Cpp14 0.03s
34 mahbubcseju Cpp14 0.03s
35 I_See_You Cpp14 0.03s
36 haasib Cpp 0.03s
37 rayhan50001 Cpp 0.04s
38 clkjwdhc Cpp 0.05s

Your feedback is our precious!

Or call +88 02 9853138 for support