免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2005 | 回复: 1

请教hacker cup 之auction的算法 [复制链接]

论坛徽章:
0
发表于 2012-01-23 13:44 |显示全部楼层
这是原题:

Auction

    Download input file
    Submit answers
    Time Expired

You have encountered a new fancy online auction that offers lots of products. You are only interested in their price and weight. We shall say that product A is strictly preferred over product B if A costs less than B and is not heavier (they may be of equal weight) or if A weighs less and is not more expensive (they can have equal price).

We shall call a product A a bargain if there is no product B such that B is better than A. Similarly, we shall call a product C a terrible deal if there exists no product D such that C is better than D. Note that according to our definitions, the same product may be both a bargain and a terrible deal! Only wacky auctioneers sell such products though.

One day you wonder how many terrible deals and bargains are offered. The number of products, N, is too large for your human-sized brain though. Fortunately, you discovered that the auction manager is terribly lazy and decided to sell the products based on a very simple pseudo-random number generator.

If product i has price Pi and weight Wi, then the following holds for product i+1:

    Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N)
    Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N)

You carefully calculated the parameters for the generator (P1, W1, M, K, A, B, C and D). Now you want to calculate the number of terrible deals and bargains on the site.
Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with 9 space-separated integers: N, P1, W1, M, K, A, B, C and D.
Output

Output T lines, one for each test case. For each case, output "Case #t: a b", where t is the test case number (starting from 1), a is the number of terrible deals and b is the number of bargains.
Constraints

    1 ≤ T ≤ 20
    1 ≤ N ≤ 1018
    1 ≤ M, K ≤ 107
    1 ≤ P1 ≤ M
    1 ≤ W_1 ≤ K
    0 ≤ A,B,C,D ≤ 109

Example inputExample output

5
5 1 4 5 7 1 0 1 2
3 1 3 3 3 1 0 1 1
8 1 3 3 3 1 0 1 2
13 5 7 5 9 1 3 2 5
11 2 3 5 7 11 13 17 19

Case #1: 3 3
Case #2: 3 3
Case #3: 2 3
Case #4: 2 2
Case #5: 3 1


我写的程序算example的数据没有问题,但真正的input file却是:

20
34468440 999999 12347 9699690 9748872 378288879 843875938 672672191 643425609
81834165 9999991 1 9999991 9999989 389999650 169999844 799999121 149999837
918495108443110920 9999991 1 9999991 9999989 849999236 589999466 309999660 169999814
848937385843 8 7 17 19 0 5 6 2
567365141997043401 3960606 1985068 4125828 5630794 76825921 901167353 889742167 772908548
1783585506 9999987 1 10000000 999999 990000001 79999998 868999132 81999927
523223149082128364 158568 991720 2994044 1181676 376610494 650869357 336623539 620070320
967702028973969107 1 10000000 10000000 10000000 840000001 670000000 40000001 19999998
13 5 7 5 9 1 3 2 5
499587295797208700 3469541 1730417 5070929 1825598 855537260 882995491 898204830 34203727
1708396388 999999 12347 9699690 9748872 727477719 669281518 799407527 906645153
80933573 102400 15000 9699690 9748872 989369349 872975008 916394050 370457193
940978906345340844 759324 967048 10000000 9999999 810000001 650000000 59999995 259999974
991127410199121019 123456 557 9988776 1025 39955758 719192622 152456585 350827775
1606423995 9999909 9999991 9999949 10000000 499997451 929995254 810000001 970000002
960043019846431759 9999909 9999991 9999949 9999991 879995513 99999488 349999686 549999505
70413132 123 1 10000000 10000000 20000001 190000000 90000001 360000002
859373750084 8 7 17 19 1 16 6 2
3 1 3 3 3 1 0 1 1
1555193042 9999991 1 9999991 9999989 259999767 19999980 239999737 679999252


6分钟之内根本算不出来阿,请教要用什么算法?

论坛徽章:
0
发表于 2012-01-23 13:56 |显示全部楼层
918495108443110920 9999991 1 9999991 9999989 849999236 589999466 309999660 169999814
这一行就出不来了,lcm(9999991, 9999991)=99999800000099, 也忒恐怖了
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会

【架构革新 高效可控】2020年12月21日-23日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP