XMAS2014 - Help Santa Claus to Pack the Toys
English | Indonesian |
One day, at the north pole there is a huge factory that produce many awesome toys. Santa Claus, who own this factory want to deliver this toys as a gift to many children who want some gift on christmas day using flying reindeer, because for each year number of toy increase and his flying reindeer get older, he want his load to be as light as possible.
Fortunately this christmas (December 2014) he invent a new technology that can store infinite amount of toys using 4th space dimension, he call it "magical box", so every item/toys in magical box will weightless, very impressive! He invent that magical box on 23 December 2014, there still 2 days remaining before christmas, so he want to speed up the loading process.
There are many toys to load in short time and his magical box can't absorb many obcect to 4th space dimension in short time, so he decided to split the work in parallel because he has many magical box available. For example if the toys numbered from 1 to n first magical box absorb toy 2 to toy 5, ... , last magical box absorb toy n-7 to n-1. Note that it's possible that Santa's magical box can't absorb all toys in his factory on time even if he use parallel technique, so some toy maybe left in the factory for next christmas.
Because his magical box still in "beta version" it still has a bug, it can only absorb consecutive toys only, so if toys 3 and toys 5 absorbed to same magical box, toy 4 will be accidentally absorbed to that magical box too. Since the problem become too complex, Santa want to rest and he left the factory to feed and tell his flying reindeer a good news that he invent the magical box so his flying reindeer will not carrying heavy load again like previous year. He also planning how he pack the toys to magical box. Because Santa is perfection, he want each box if used contains at least d toys.
Now he wonder how many ways he can load the toys into his magical box if number of his magical box and number of toys in his factory is same. It's not necessary to use all his magical box, he want to use at least one of his magical box. Can you help him count how many ways he can do it?
Input
On the first line there is one integer c, denoting case type. For details about case type, see "Constraints".
Each next line untill EOF there are three integers d, n, and m
- d = Minimal number of toys Santa want to put on each magical box
- n = Number of toys available at the Santa's factory
- m = Modulo, since the answer is very large, Santa will understand, he just need the answer modulo m.
Output
For each answer you get, output two numbers, d and the answer modulo m in one line separated by a space.
Constraints
2014 cases.
1 ≤ c ≤ 3
1 ≤ d ≤ 2014 (d will be unique on each input file, no two cases with same d)
1 ≤ m ≤ 109
Type1: 0 ≤ n < 2×d; Score = 1 for each correct answer.
Type2: 0 ≤ n ≤ max(d2,2×d); Score = 10 for each correct answer.
Type3: 0 ≤ n < 264; Score = 100 for each correct answer.
Scoring
Your final score will be sum of score from test type1 to test type3.
If you print all correct answers on test case type3 you'll get bonus score.
Bonus score will be = floor{(25.0-[your time on test 3])*8056.0}
Example 1
Input:
1
1 1 1000
2 3 1000
3 5 1000
4 7 1000
Output:
1 1
2 3
3 6
4 10
Score:
Because this is input type 1, so each correct case worth 1 point.
For this example score=4*1=4.
Example 2
Input:
2
1 2 1000
2 4 1000
3 6 1000
4 8 1000
Output:
1 4
4 16
2 7
Score:
Note that you can put your answer in any order,
because there are 3 correct answers and this is input type 2 (each test case worth 10 points),
for this example score=3*10=30.
Example 3
Input:
2
1 2 1000
2 4 1000
3 6 1000
4 8 1000
Output:
1 4
3 10
4 16
2 7
Score:
For this example you'll get "Wrong Answer".
That's because for d=3 and n=6 and m=1000 answer should be 11, but output is 10.
Better not output "3 10" like in example 2, than output wrong answer.
For this example score = N/A.
Example 4
Input:
3
1 11 1000
2 11 1000
Output:
Score:
Because user don't output anything score=0.
Be careful, you'll get WA if sum of your score on test type1 to type3=0
Example 5
Input:
3
1 12345678987654321 1000
2 11 1000
Output:
2 23
Score:
Because this is input type 3, so each correct case worth 100 points.
For this example score=1*100=100
Example 6
Input:
3
1 3 5
2 4 6
Output:
1 2
2 1
1 2
Score:
All answer are correct, but no duplicate d allowed,
so for this example it will be judged as WA.
Score for this example = N/A
Example 7
Input:
3
1 3 1000000000
2 4 1000000000
Output:
1 12
2 7
Score:
200
Explanation for "Example 7"
Here is 12 ways to pack 3 toys using 1 or more magical box and each magical box must contain minimal 1 toy.
Here is 7 ways to pack 4 toys using 1 or more magical box and each magical box must contain minimal 2 toys.
Additional Information
All input (n and m) are generated with random uniform distribution in the range.
My score at the time publication of this problem is 66554, Will it be hard to beat this(?)
Update: [2014-12-24 13:42:56] Congratulations to Min_25, first user who break my record in this problem.
If some user has perfect score (223554) I'll not increase constraints or change test data, I'll change the scoring system (taking running time into account), but... will it happen?
Update: It happen! [2015-01-02 22:38:52] Congratulations to Min_25!
hide comments
(Tjandra Satria Gunawan)(曾毅昆):
2015-01-02 23:42:05
Wow!
|
|
Min_25:
2015-01-02 23:40:47
@Francky
|
|
Francky:
2015-01-02 23:15:04
Big congrats to Min_25 !!!!!!! |
|
(Tjandra Satria Gunawan)(曾毅昆):
2015-01-02 23:15:04
@Flago: Yes, I agree, by looking your code, I see how hard your work to beat Mitch for now :p btw, Min_25's points is about 80% of perfect score. There's high probability that someday it become perfect so I should start thinking about new scoring formula.
@Anubhav Balodhi: Thank you ^^ Btw, I notice two minor bug in my master_judge 1) If you get "TLE" with zero sum of points, it will be judged as "Wrong Answer". 2) If your code judged as "Time Limit Exceeded" the judge not print details on each test data because there are some typo/unwanted '\n' in my master_judge code. Of course it just "minor" bug and not fatal. I'll fix this when I change scoring system (If Min_25 or someone has perfect score). |
|
Flago:
2015-01-02 23:15:04
Trying to get some points to beat Mitch is depressive when you see Min_25 having 100*more points ! (Min_25 too strong ! Should get malus !! :D) |
|
Anubhav Balodhi :
2015-01-26 19:59:28
I must say, very nice problem and good explanation ^_^ |
|
Flago:
2015-01-02 23:15:04
Good one, no quite sure tho where i'm missing something... Type 2, d is 2 10³ as max, so n is 4 10⁶... I should be able to n² without having problems with php max int...
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2015-01-02 23:15:04
@californiagurl: I'll explain the image, the blue color on specific cell means the toy is absorbed to magical box, and white color means it left in the factory, if all the color is blue then all toys is absorbed into magical box, |12|3| (all blue) and |1|23| (all blue) in the image is different, |12|3| means toy 1 and toy 2 are absorbed into same magical box while toy 3 is absorbed into other magical box, and |1|23| means toy 2 and 3 is absorbed into same magical box while toy 1 is absorbed into other magical box.
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2015-01-02 23:15:04
@Min_25:
|
|
californiagurl:
2015-01-02 23:15:04
i dont understand the explanation for example 7. |
Added by: | Tjandra Satria Gunawan |
Date: | 2014-12-23 |
Time limit: | 25s |
Source limit: | 12014B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own Problem |