Submit | All submissions | Best solutions | Back to list |
TMB - Thousands ByteMan March |
Leo invited all his friends to a giant meeting for peace in byteland. All people came in bus which were all full. Last year, they were only 4 people : A, B, C, D. As Leo likes structured things, he thought to form groups. All the ways to form homogeneous teams were :
{{A,B,C,D}} : one team of 4 (one way), {{A}, {B}, {C}, {D}} : four 'teams' of 1 (one way more), {{A,B}, {C,D}} or {{A,C}, {B,D}} or {{A,D}, {B,C}} : two teams of 2 (3 ways more).
for a total of 5 ways. But this year many people are awaited.
Input
The input begins with the number T of test cases in a single line. In each of the next T lines there are two integers : N, K. N is the quantity of bus that came to the meeting. K is the common capacity of each bus.
Output
For each test case, your task is to calculate the number of ways people can form homogeneous teams. The answer can be a big number and could not fit in a 64bit container.
Example
Input: 3 2 2 1 6 2 3 Output: 5 27 27
Explanations
With lower letters, here are 27 ways for 2×3 people.
{{a,c,e},{b,d,f}}, {{a,c,d},{b,e,f}}, {{a,b},{c,e},{d,f}}, {{a,f},{b,e},{c,d}}, {{a,b,f},{c,d,e}}, {{a,c},{b,f},{d,e}}, {{a,e},{b,f},{c,d}}, {{a,b},{c,d},{e,f}}, {{a,e},{b,d},{c,f}}, {{a,e,f},{b,c,d}}, {{a,b,e},{c,d,f}}, {{a,d,e},{b,c,f}}, {{a,d},{b,e},{c,f}}, {{a,d},{b,c},{e,f}}, {{a,d},{b,f},{c,e}}, {{a,c,f},{b,d,e}}, {{a,b,c},{d,e,f}}, {{a},{b},{c},{d},{e},{f}}, {{a,b,c,d,e,f}}, {{a,c},{b,d},{e,f}}, {{a,c},{b,e},{d,f}}, {{a,b},{c,f},{d,e}}, {{a,f},{b,d},{c,e}}, {{a,f},{b,c},{d,e}}, {{a,e},{b,c},{d,f}}, {{a,d,f},{b,c,e}}, {{a,b,d},{c,e,f}}
Constraints
0 < T ≤ 100 0 < K ≤ 100 0 < N ≤ 100
Uniform-random input in the range. Basic 1/6kB Python code can get AC under 1.5s, around 0.18s using PIKE (quite my first PIKE code), (timings edited 2017-02-11 after compiler changes).
Added by: | Francky |
Date: | 2013-03-03 |
Time limit: | 2.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own problem |
hide comments
2020-05-20 14:56:22
@Francky: Very nice problem! Sorry I've solved it somewhat strightforwardly. I'd like to know the intended solution :) =(Francky)=> Congrats, you got it ;-) Only minors improvements I think. It was a 3 lines of Python for me at start, few more to speed up a bit... I'm glad you enjoyed the problem. Last edit: 2020-05-20 20:28:35 |
|
2018-10-23 21:03:44
Amazing one. As usual with Francky's problems, the concept alone is not trivial, but once figured out, still have to reduce. Feels fantastic to get AC, or rather not to get WA, as to be honest I've been getting lost on my way to the solution. Writing this was like listening to wife when stoned, you fully comprehend every word she's saying, but by the end of the sentence, you don't remember how it all began ;) Just noticed I've got a pretty good time, which is surprising as it feels there's still a lot to optimize. Will enjoy spending some more time looking into this beauty. Thanks! =(Francky)=> Congrats, and thanks for your appreciation ;-) Last edit: 2018-10-24 00:47:23 |
|
2013-12-18 20:56:42 Apoorv Jindal
@Francky Good problem!How can I optimize my python 2.7 code? Any suggestions? --ans(francky)--> It's always a good idea to try to sieve something, but the code will be harder to write. Yet a nice job. Edit(apoorv)--> Thanks for replying, i'll think about it. Last edit: 2013-12-19 15:24:54 |