Problem 7: The Grand Farm-off [Haitao Mao, 2009]
Farmer John owns 3*N (1 <= N <= 500,000) cows surprisingly numbered
0..3*N-1, each of which has some associated integer weight W_i (1 <=
W_i <= d). He is entering the Grand Farm-off, a farming competition
where he shows off his cows to the greater agricultural community.
This competition allows him to enter a group of N cows. He has given
each of his cows a utility rating U_i (1 <= U_i <= h), which
represents the usefulness he thinks that a particular cow will have
in the competition, and he wants his selection of cows to have the
maximal sum of utility.
There might be multiple sets of N cows that attain the maximum
utility sum. FJ is afraid the competition may impose a total weight
limit on the cows in the competition, so a secondary priority is
to bring lighter weight competition cows.
Help FJ find a set of N cows with minimum possible total weight
among the sets of N cows that maximize the utility, and print the
remainder when this total weight is divided by M (10,000,000 <= M
<= 1,000,000,000).
Note: to make the input phase faster, FJ has derived polynomials
which will generate the weights and utility values for each cow.
For each cow 0 <= i < 3*N,
W_i = (a*i^5+b*i^2+c) mod d
and U_i = (e*i^5+f*i^3+g) mod h
with reasonable ranges for the coefficients (0 <= a <= 1,000,000,000;
0 <= b <= 1,000,000,000; 0 <= c <= 1,000,000,000; 0 <= e <=
1,000,000,000; 0 <= f <= 1,000,000,000; 0 <= g <= 1,000,000,000;
10,000,000 <= d <= 1,000,000,000; 10,000,000 <= h <= 1,000,000,000).
The formulae do sometimes generate duplicate numbers; your algorithm
should handle this properly.
PROBLEM NAME: farmoff
INPUT FORMAT:
* Line 1: Ten space-separated integers: N, a, b, c, d, e, f, g, h, and
M
SAMPLE INPUT (file farmoff.in):
2 0 1 5 55555555 0 1 0 55555555 55555555
INPUT DETAILS:
The functions generate weights of 5, 6, 9, 14, 21, and 30 along
with utilities of 0, 1, 8, 27, 64, and 125.
OUTPUT FORMAT:
* Line 1: A single integer representing the lowest sum of the weights
of the N cows with the highest net utility.
SAMPLE OUTPUT (file farmoff.out):
51
OUTPUT DETAILS:
The two cows with the highest utility are cow 5 and 6, and their combined
weight is 21+30=51.
【中文翻譯】
問題描述:
農夫約翰擁有 3*N(1 <= N <= 500,000)只牛，它們的編號爲0..3*N-1，每隻牛都有一個體重 W_i(1 <= W_i <= d)。約翰參加了一個叫做 Farm-off 的盛大競賽活動，在這個活動上他可以在整個農業界炫耀他的牛。
這個競賽約翰可以派出一隊共 N 頭牛參賽，他的每頭牛都有一個效率值 U_i (1 <= U_i <= h)，這個值用來描述他認爲在這個競賽中每頭牛的有用值。約翰想讓他選擇的一羣牛有一個最大的效率總值。
可能有很多種 N 頭牛的集合可以達到這個最大的效率總值。農夫約翰爲了防止競賽中的欺騙行爲，對牛的體重加以限制。所以第二個要考慮的因素便是參加競賽的牛的體重。
幫助約翰從所有以N頭牛組合而得的效率總值最大的集閤中，找到一個最小體重的組合。 並且打印出體重總值被M (10,000,000 <= M <= 1,000,000,000)整除後的餘數。
注意：爲了儘快地輸入，約翰找到一個能夠表示出每頭牛體重及效率值的多項式：
對於每頭牛 0 <= i < 3*N，
W_i = (a*i^5+b*i^2+c) mod d
U_i = (e*i^5+f*i^3+g) mod h
合理的係數範圍：
0 <= a <= 1,000,000,000;
0 <= b <= 1,000,000,000;
0 <= c <= 1,000,000,000;
0 <= e <= 1,000,000,000;
0 <= f <= 1,000,000,000;
0 <= g <= 1,000,000,000;
10,000,000 <= d <= 1,000,000,000;
10,000,000 <= h <= 1,000,000,000.
公式有時會產生一些重複的數字，你的算法應該能夠適應這種情況。
PROBLEM NAME: farmoff
輸入格式：
第一行：用空格隔開的10個數字：N, a, b, c, d, e, f, g, h,M
輸入樣例：(file farmoff.in):
2 0 1 5 55555555 0 1 0 55555555 55555555
根據公式計算出來的 W_i 分別是：5, 6, 9, 14, 21,30；計算出來的U_i分別是：0, 1, 8, 27, 64,125
輸出格式：
第一行：一個單獨的整數用來描述：N頭牛的淨效率總值最大的條件下的最小體重總值。
輸出樣例（farmoff.out）：
51
兩隻牛的組閤中效率最大的是牛5和牛6，它們的體重總值爲：21+30=51
【分析】
本題並不是很難，因為沒有用到很難的算法。
因為數據很大，當然可以用高精度算法來實現。
但是高精度算法不僅代碼複雜度高，而且時間複雜度也不低。
所以，我們可以通過餘數定理來實現把大數據變小，變到long long的範圍（2^63-1）之內。
=======================================
[餘數定理]
a：兩數的和除以m的餘數等於這兩個數分別除以m的餘數和。
實例：7÷3=…1，5÷3=…2，這樣（7+5）÷3的餘數就等於1+2=3，所以餘0。
b: 兩數的差除以m的餘數等於這兩個數分別除以m的餘數差。
實例：8÷3=…2，4÷3=…1，這樣（8-4）÷3的餘數就等於2-1=1，所以餘1。
如果是（7-5）÷3呢? 會出什麼問題？
c: 兩數的積除以m的餘數等於這兩個數分別除以m的餘數積。
實例：7÷3=…1，5÷3=…2，這樣（7×5）÷3的餘數就等於1×2=2，所以餘2。
attention:
對a，餘數和應再對m取次餘
對b，餘數差應加上m後再對m取次餘
========================================
然後 ，本題剩下的部分就是利用編程語言中的快速排序(qsort)，對結構體進行二級排序即可。
【我的代碼】
（在記憶體為512MB，CPU為1.6GHz的評測機上，10組測試數據共運行4.813秒。）
#include <iostream>#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
long long a,b,c,D,e,f,g,H;
long long M;
long long S=0;
long long tt;
class COW
{
public:
long long W;
long long U;
}C[1500001];
int cmp(const void *a,const void *b)
{
class COW *c=(class COW *)a;
class COW *d=(class COW *)b;
if(c->U!=d->U)
return d->U-c->U;
return c->W-d->W;
}
long long pl(long long num,long long level,long long moder)
{
long long temp=1;
while (level)
{
temp=(temp*num)%moder;
level--;
}
return(temp);
}
void init()
{
cin>>N;
cin>>a>>b>>c>>D>>e>>f>>g>>H;
cin>>M;
long long w,u;
for (int i=0;i<3*N;i++)
{
w=((((a%D)*pl(i,5,D))%D+((b%D)*pl(i,2,D))%D)+c%D)%D;
u=((((e%H)*pl(i,5,H))%H+((f%H)*pl(i,3,H))%H)+g%H)%H;
C[i].W=w;
C[i].U=u;
}
qsort(C,3*N,sizeof(C[0]),cmp);
for (int i=0;i<N;i++)
{
S+=C[i].W;
S%=M;
}
cout<<S<<endl;
}
int main()
{
freopen("farmoff.in","r",stdin);
freopen("farmoff.out","w",stdout);
init();
return 0;
}
沒有留言:
張貼留言