DCEPC702 - NOS
Find the number of strings of length “N” made up of only 3 characters – a, b, c such that “a” occurs at least “min_a” times and at most “max_a” times, “b” occurs at least “min_b” times and at most “max_b” times and “c” occurs at least “min_c” times and at most “max_c” times. Note that all permutations of same string count as 1, so “abc” is same as “bac”.
First line gives T, the number of test cases.
Each test case has an integer “N” on first line.
Next line contains 2 integers, min_a and max_a.
Next line contains 2 integers, min_b and max_b.
Next line contains 2 integers, min_c and max_c.
Output T lines, each containing the required answer modulo 10^9+7.
1 1Output: 1
Hit the wall in what seemed to be the easy part of the computation but rather than postponing until I can look at it again with a fresh mind, produced a massive overkill about 50 lines too long, with an extra log factor to boot, that took an hour to debug, and dragged this convoluted mess past the finish line. Even a broken clock gives the right time twice a day, lol. Cool problem though.
great question....just take care while using combination and modulo together.
can anyone give some more test cases, I'm getting WA after running 5th case
@D: Great Idea.. !!!
As easy as they come...
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
My Math Formula give me perfect time 0.00s ;-)
Nonsense! Testing with values in range (1;1000) will find pretty much all issues you can have with your program on problem like this. What could be left, is checking for proper usage of data types (long long/int). In fact, I'm pretty sure your program fails on some cases where a,b,c<=10.Last edit: 2012-07-02 14:09:34
i understand but please answer my ques., because brute force is not the solution for my problem
You can easily write a brute force checker and analyze some smaller cases on your own. Just check all ordered "abc" strings separately to see if they meet constraints. It will be only O(N^2) and you will be able to check pretty big test cases with it.
Is the output for
|Added by:||dce coders|
|Cluster:||Cube (Intel G860)|
|Languages:||ASM32-GCC MAWK BC C-CLANG C C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET|