DCP-130: K-Perfect Number Back to All Problems

Medium Divide and Conquer > Dynamic Programming

Shin Chan is no longer a kid now. Rather he has become a very good programmer as well as mathematician. He loves inventing new properties of numbers. He has invented a new special kind of number called K-Perfect number. He calls a positive integer N as K-Perfect if N contains **only** the integers 1 to K in an arbitrary order and each integer from 1 to K appears **exactly once**. It’s very easy to generate K-Perfect number. Shin Chan takes an array and then adds K integers (1 to K) in the array and then shuffles it. After that he takes a blank string and then concatenates the elements of array one after another with the string. The resulting string is a K-Perfect number. Look at the following samples: ![Image about explaining K-Perfect number][1] We do not know what will be the K-Perfect number generated by Shin Chan as it is dependent on the order of shuffling. But it is obvious that for any K, there exists exactly **K!** (factorial of K) K-perfect numbers. Anyways, Shin Chan is tensed because recently Himawari just attacked his laptop and Shin Chan has no idea whether Himawari has messed up with his code of K-Perfect number generator. So to check whether his code is okay, can you help him? Input: ------ Input starts with an integer **T (T ≤ 30)** denoting the number of test cases. Each case gives you an integer **K (1 ≤ K ≤ 18)** and a positive integer **N** in separate lines. The number of digits in **N** does not exceed **50**. Output: ------- For each case, print **“YES”** if the given number is K-Perfect and **“NO”** otherwise without the quotes. Sample Input ------------ 4 4 4132 5 425132 12 112345678910112 12 123456781901112 Sample Output ------------- YES NO YES NO [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/59cf8e45-26e7-ca7c-9038-08d3d31d8bbc_ceed666a6ce24995b4c70222ab31393f_W634xH108.png

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 Robbinb1993 Cpp14 0.00s
02 Morass Cpp14 0.01s
03 feodorv C 0.01s
04 Double_O Cpp14 0.25s
05 prodipdatta7 Cpp14 0.31s
06 sakib_muhit Cpp14 0.40s
07 eltonrawn Cpp14 0.42s
08 Mahmudul_Tushar Cpp14 0.43s
09 evan Cpp14 0.43s
10 as_couple Cpp14 0.43s
11 SONNET_N Cpp14 0.48s
12 jayanto Cpp14 0.48s
13 anowar1112 Cpp14 0.49s
14 sahedsohel Cpp14 0.50s
15 alhelal_cse Cpp14 0.50s
16 mamun4122 Cpp14 0.55s
17 tariqiitju Cpp14 0.61s
18 mahbubcseju Cpp14 0.68s
19 kitorp Cpp14 0.78s

Your feedback is our precious!

Or call +88 02 9853138 for support