DCP-174: Troubles With Germs Back to All Problems

Hard Divide and Conquer > Dynamic Programming

The laboratory of Microbiology department has been attacked by several robbers recently. They robbed and stole many valuable samples of viruses, bacteria, microorganisms. While being in hurry, they broke a tube. The tube contained sample of one of the most dangerous germs called Dangerm. The tube contained exactly one sample of each of the three species (namely Clu, Tron, Flynn) of Dangerm. During the research and test on the day before robbery, our students managed to discover that everyday each Clu turns into 12 Dangerms (3 Clus, 4 Trons and 5 Flynns), each Tron turns into 21 Dangerms (6 Clus, 7 Trons and 8 Flynns) and each Flynn turns into 30 Dangerms (9 Clus, 10 Trons and 11 Flynns). As Dangerm is very dangerous, scientists have set out a meeting and are planning to invent something called Dangkill to destroy all the Dangerms. They are expecting that the invention of Dangkill will take n days and for every thousand Dangerms, one Dangkill is needed. So to know how many Dangkills need to be prepared, scientists need to know how many Dangerms there will be on the nth day. Can you help them? Input: ------ Input starts with an integer T (T ≤ 1000) denoting the number of test cases. Each case contains a single integer n (1 ≤ n ≤ 1 000 000 000). Output: ------- For each case, print the number of Dangerms that will exist on the nth day modulo 1 000 000 009. Sample Input ------------ 4 1 2 3 1000 Sample Output ------------- 3 63 1377 358121526

Problem Setter:

Ariful Hoque Maruf

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# 3.00
Go 3.00
Java 3.00
JavaScript 3.00
Objective-C 3.00
Perl 3.00
PHP 3.00
Python 3.00
Python3 3.00
Ruby 3.00
VB.Net 3.00

Problem Stats




# User Language Timing
01 nmunim Cpp14 0.00s
02 nasif2587 Cpp14 0.00s
03 Protap_Ghose Cpp14 0.00s
04 Robbinb1993 Cpp14 0.00s
05 shaft Cpp14 0.01s
06 Knight_King Cpp14 0.01s
07 Masum_ice Cpp14 0.01s
08 Sopto Cpp14 0.01s
09 ksohan Cpp14 0.01s
10 MazedRupok Cpp14 0.01s
11 eltonrawn Cpp14 0.01s
12 Reayz Cpp14 0.01s
13 SKL12 Cpp14 0.01s
14 tariqiitju Cpp14 0.01s
15 Double_O Cpp14 0.01s
16 saiful130104 Cpp14 0.01s
17 feodorv Cpp14 0.01s
18 mamun4122 Cpp14 0.01s
19 Dariwala Cpp14 0.01s
20 imranziad Cpp14 0.01s
21 alhelal_cse Cpp14 0.01s
22 CLown1331 Cpp14 0.01s
23 sahedsohel Cpp14 0.01s
24 Tanmoy1228 Cpp14 0.01s
25 Zeronfinity Cpp14 0.02s
26 BishalG Cpp14 0.02s
27 akazad_cse13_ruet Cpp14 0.02s
28 dmehrab06 Cpp14 0.02s
29 PKP_007 Cpp14 0.02s
30 ssavi Cpp14 0.02s
31 n999 Cpp14 0.03s
32 AlirezaNa Cpp14 0.03s
33 Rajib_119 Cpp14 0.03s
34 adamantium Cpp14 0.04s
35 Tanmoy_Datta Cpp14 0.04s
36 Morass Cpp14 0.05s
37 ISMAIL_HOSSAIN Cpp14 0.05s
38 _dipu Cpp14 0.07s
39 sayedgkm Cpp14 0.08s
40 seyedssz Cpp14 0.18s

Your feedback is our precious!

Or call +88 02 9853138 for support