9 . 鹿不敷出

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

hank55663

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

46.2% (6/13)

Tags

ntucpc-challenge1

Description


角角購物台暢銷商品——角型印章盒

小鹿社的社團花費驚人，除了鹿仙貝的花費以外也經常需要進行社團辦公室的整修，為此她們開設了網路購物平台販售各種商品。為了跟上潮流，她們決定開始販賣鹿角福袋！

虎視虎子準備了 N 個角型印章盒以及 M 個鹿角娃娃準備要裝進鹿角福袋中。每個角型印章盒的重量皆為 A 公克，每個鹿角娃娃的重量皆為 B 公克。

每個鹿角福袋裡面裝著若干個角型印章盒及鹿角娃娃，兩種商品的數量不一定相同，也有可能只裝著一種商品。為了防止客人透過福袋的重量得知福袋中裝的商品，虎視虎子規定每一個福袋內的商品總重量必須要恰好是 K 公克。

由於社團辦公室空間寶貴，虎視虎子希望將盡量多的商品裝入福袋中，最小化剩下的角型印章盒及鹿角娃娃的總數。你能寫一支程式幫她算算，使用最佳的方法將商品分配進福袋後，剩下的商品總數最少可以是多少嗎？

Input Format

輸入的第一行為一整數 T，表示測試資料的數量。

每一筆測試資料僅一行，包含五個整數 N,M,A,B,K。

  • 1≤T≤1000
  • 1≤N,M,A,B≤1050
  • 1≤K≤2×10100

Output Format

對於每一筆測試資料，請輸出一行包含一個整數，表示可能剩下的最少商品總數。

Sample Input 1

8
10 8 2 3 12
3 3 2 2 8
1 3 2 2 10
6 6 3 5 16
341 329 5 6 741
727 521 18 9 576
290646493 622766369 133 76 578504001
285261289 308082376 109 3 922747797

Sample Output 1

3
2
4
0
120
28
2764179
5911117

Sample Input 2

5
18088424242579552518 7104691923183681339 44800271087456372342 73912720275978542088 3311309905175171864536816947645213124954
2391762016614507787945520815370272466319622 28600992478201072778186646252254164222566827 5608513952183650610 11040484300804766589 619207102399281797150320558480337195348
17668731365097358652906446897769904088811920637755 72894953696748801528422842559622566894251591568584 65766501545139653183 26131647443466988033 1718587031967816336397436635862698347072
86419753286419753286419753286419753286419753248763 56562565625656256562565625656256562565625656256562 123456789876543212345678987654321 987654321234567898765432123456789 121932632007315960006096855357413561957021002895878067367652796831
99999999999999999999999999999939202333720478371975 99999999999999999999999999999928218601401082500796 99999999999999983762738704940284173400254048986629 99999999999999971018796208805934772584415781810455 11871299136343488573286683183806021130812311398292498796910143828548074

Sample Output 2

25193116165763233857
31587700800821033267
64918824634504918103
490203648467396498476504295685902
39387603486681096136698976385793037716459839811599

Hints

在 Sample Input 1 的第一筆測資中，可以將 6 個鹿角印章盒裝進一個福袋中，將 4 個鹿角娃娃裝進另一個福袋中，再將 3 個鹿角印章盒及 2 個鹿角娃娃裝進另一個福袋中，最後剩下 1 個鹿角印章盒及 2 個鹿角娃娃。可以證明不存在分配方式能剩下 2 個或更少數量的商品。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~21 1≤N,M,A,B≤3×104,1≤K≤2×1018 30
3 0, 2~72 1≤N,M,A,B≤109,1≤K≤2×1018 30
4 0~99 無額外限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 3 4
1 1000 262144 65536 1 4
2 1000 262144 65536 2 3 4
3 1000 262144 65536 2 3 4
4 1000 262144 65536 2 3 4
5 1000 262144 65536 2 3 4
6 1000 262144 65536 2 3 4
7 1000 262144 65536 2 3 4
8 1000 262144 65536 2 3 4
9 1000 262144 65536 2 3 4
10 1000 262144 65536 2 3 4
11 1000 262144 65536 2 3 4
12 1000 262144 65536 2 3 4
13 1000 262144 65536 2 3 4
14 1000 262144 65536 2 3 4
15 1000 262144 65536 2 3 4
16 1000 262144 65536 2 3 4
17 1000 262144 65536 2 3 4
18 1000 262144 65536 2 3 4
19 1000 262144 65536 2 3 4
20 1000 262144 65536 2 3 4
21 1000 262144 65536 2 3 4
22 1000 262144 65536 3 4
23 1000 262144 65536 3 4
24 1000 262144 65536 3 4
25 1000 262144 65536 3 4
26 1000 262144 65536 3 4
27 1000 262144 65536 3 4
28 1000 262144 65536 3 4
29 1000 262144 65536 3 4
30 1000 262144 65536 3 4
31 1000 262144 65536 3 4
32 1000 262144 65536 3 4
33 1000 262144 65536 3 4
34 1000 262144 65536 3 4
35 1000 262144 65536 3 4
36 1000 262144 65536 3 4
37 1000 262144 65536 3 4
38 1000 262144 65536 3 4
39 1000 262144 65536 3 4
40 1000 262144 65536 3 4
41 1000 262144 65536 3 4
42 1000 262144 65536 3 4
43 1000 262144 65536 3 4
44 1000 262144 65536 3 4
45 1000 262144 65536 3 4
46 1000 262144 65536 3 4
47 1000 262144 65536 3 4
48 1000 262144 65536 3 4
49 1000 262144 65536 3 4
50 1000 262144 65536 3 4
51 1000 262144 65536 3 4
52 1000 262144 65536 3 4
53 1000 262144 65536 3 4
54 1000 262144 65536 3 4
55 1000 262144 65536 3 4
56 1000 262144 65536 3 4
57 1000 262144 65536 3 4
58 1000 262144 65536 3 4
59 1000 262144 65536 3 4
60 1000 262144 65536 3 4
61 1000 262144 65536 3 4
62 1000 262144 65536 3 4
63 1000 262144 65536 3 4
64 1000 262144 65536 3 4
65 1000 262144 65536 3 4
66 1000 262144 65536 3 4
67 1000 262144 65536 3 4
68 1000 262144 65536 3 4
69 1000 262144 65536 3 4
70 1000 262144 65536 3 4
71 1000 262144 65536 3 4
72 1000 262144 65536 3 4
73 1000 262144 65536 4
74 1000 262144 65536 4
75 1000 262144 65536 4
76 1000 262144 65536 4
77 1000 262144 65536 4
78 1000 262144 65536 4
79 1000 262144 65536 4
80 1000 262144 65536 4
81 1000 262144 65536 4
82 1000 262144 65536 4
83 1000 262144 65536 4
84 1000 262144 65536 4
85 1000 262144 65536 4
86 1000 262144 65536 4
87 1000 262144 65536 4
88 1000 262144 65536 4
89 1000 262144 65536 4
90 1000 262144 65536 4
91 1000 262144 65536 4
92 1000 262144 65536 4
93 1000 262144 65536 4
94 1000 262144 65536 4
95 1000 262144 65536 4
96 1000 262144 65536 4
97 1000 262144 65536 4
98 1000 262144 65536 4
99 1000 262144 65536 4
Submit
Back to Top