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”.
Input
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
Output T lines, each containing the required answer modulo 10^9+7.
Constraints
1 <= T <= 1000
1 <= N <= 10^9
1 <= min_a <= max_a <= 10^9
1 <= min_b <= max_b <= 10^9
1 <= min_c <= max_c <= 10^9
Example
Input: 1 3 1 1 1 1 1 1 Output: 1
hide comments
|
Sushovan Sen:
2023-01-18 07:07:09
What is the answer when N is less than 3? |
|
nadstratosfer:
2019-07-13 17:52:09
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. |
|
aspro:
2016-05-21 20:39:34
great question....just take care while using combination and modulo together. |
|
Smriti Vashisth:
2014-06-08 16:32:30
can anyone give some more test cases, I'm getting WA after running 5th case |
|
Rishav Goyal:
2014-03-28 13:30:38
@D: Great Idea.. !!! |
|
Deepak:
2014-02-24 21:10:02
As easy as they come... |
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-09-28 11:37:26
My Math Formula give me perfect time 0.00s ;-) |
|
:D:
2012-07-02 07:00:16
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 |
|
Gaurav Mittal:
2012-06-28 06:15:54
i understand but please answer my ques., because brute force is not the solution for my problem |
|
|
:D:
2012-06-27 10:06:10
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.
|
| Added by: | dce coders |
| Date: | 2012-04-30 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
| Resource: | Own Problem |
RSS