Chef attic windowProblem code: WINDOW |
All submissions for this problem are available.
Chef lives in a big house. Almost all is perfect in it except for one thing. Chef has an attic, but there is no window in it. Now, he wants to build a window there.
The attic wall has the form of a right triangle. We can imagine it as a triangle on a coordinate plane with vertices (0; 0), (N; 0), (N; N * A / B), where N, A, B are some positive integers.
As a modern guy Chef want to build a modern (L, K)-window on the attic wall. A modern (L, K)-window is made up of L+1 vertical lines and K+1 horizontal lines such that all their intersections lie on the attic wall. Here L, K are positive integers.
Formally he can choose L+1 integers 0 <= x[0] < x[1] < ... < x[L] <= N and K+1 integers 0 <= y[0] < y[1] < ... < y[K] <= N*A/B such that all points (x[i], y[j]) lie on the wall. Then, rectangular grid with all these points as nodes is required window.
Chef is interested in knowing how many ways he can choose the window. But since this number can be very large he wants to find it modulo 900000011. Help him.
Input
The first line contains a single positive integer T <= 50, the number of test cases. T test cases follow. The only line of each test case contains five positive integers N, A, B, K, L, where N, A, B <= 10^18 and K, L <= 10.
Output
For each test case, output a single line containing the number of ways to choose a window modulo 900000011.
Example
Input: 3 4 2 3 1 1 4 3 2 2 2 1001 101 97 3 2 Output: 5 4 579415965
Explanation
In the first case we need calculate the number of rectangles which lie in triangle with vertices (0; 0), (4; 0), (4; 8/3). There exist 5 such rectangles. Among them 3 have size 1 x 1. One has size 2 x 1 and one have size 1 x 2.In the second case we have two rectangles 2 x 2 and one rectangle 2 x 3 where we can choose middle horizontal segment in two ways. So we have in total 4 possible choices.
| Author: | anton_lunyov |
| Date Added: | 10-12-2010 |
| Time Limit: | 5 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Can you be more precise in
Can you be more precise in the definition of one of these windows? I can't figure out what they should look like from the problem statement at all.
There are many such choices of L+1 vertical lines and H+1 horizontal lines which don't have all of the x and y coordinates increasing, so that definition doesn't help at all. The second definition doesn't define rectangular grid at all (at least not a standard definition) - in fact, the only way I can possibly see the sample explanation working is if in fact there are two windows for a given set of x and y coordinates, whereas the definition seems to imply the coordinates give a unique window.. I'm lost.
You can forget about
You can forget about windows.
Just find the number of (K+L+2) tuples (x[0],x[1],...,x[L],y[0],y[1],...,y[K]) that satisfying second definition.
Hi, could you tell what is
Hi, could you tell what is second definition?
(L,K) is the exact window size or minimum window size that chef wants to build?
In first example output, all possible rectangles are considered which are equal or greater than size of (1,1)
In second example output, the possible rectangles whcih are equal or greater than size of (2,2) are two 2x2 rectangles and one 2x3 rectangle. so total possibel ways should be 3 only. but you mentioned that we can choose middle horizontal segment in two ways.. what do you mean by that? pls help.. thanks..
You need to count the number
You need to count the number of ways of choosing 0 <= x[0] < x[1] < .. < x[L] <= N, 0 <= y[0] < .. < y[K] <= N*A/B such that (x[i],y[j]) is within the wall for any i and j.
In the second example, the 4 solutions are:
2,3,4, 0,1,2
2,3,4, 1,2,3
2,3,4, 0,1,3
2,3,4, 0,2,3
17:30 hrs, 5th January, 2011
17:30 hrs, 5th January, 2011 (IST): The time limits for all test cases in this contest problem are now set to 5 seconds.
My submisson should get TLE
My submisson should get TLE but it is giving wrong answer. It says it ran for 0.04 seconds but it was running for more than 30 seconds.
Please read the FAQ for
Please read the FAQ for details on how your program is tested. What you have described is perfectly logical behaviour.
The message of the update
The message of the update seems to be a little misleading: it appears the time limit is set to 5 seconds "per input file" instead of "per test case".