USACO终于升到金组了。本来该满分的，但是。。。
有一道题，无解应该输出’NONE’，我输出’NONE.’，其实在比赛结束前就发现了的。不过我重传文件是可能传错了，所以WA一个点，总分960。
还有，WSC也升金组了，他也是960，同一个点WA，不过他是在无解的时候不输出。
一点点遗憾。
![USACO[Elite 2010 March Competition]解题报告 - 天之骄子 - 天之骄子的家](https://blog.boleyn.su/wp-content/uploads/2010/03/5688046329369509421.jpg "USACO[Elite 2010 March Competition/silver]解题报告 - 天之骄子 - 天之骄子的家")
题目有点水，我觉得就只有第二题有意思点。
下面是我打的注释：
![USACO[Elite 2010 March Competition/silver]解题报告 - 天之骄子 - 天之骄子的家](https://blog.boleyn.su/wp-content/uploads/2010/03/5688046329369509455.jpg "USACO[Elite 2010 March Competition/silver]解题报告 - 天之骄子 - 天之骄子的家")
第一行是最先打的，我们猜guess个为true，那么保证得分min{abs{guess-t[i]-N}}，而要做的就是最大化它。即答案为max{min{abs{guess-t[i]-N},i=1 to K},guess=0 to N}。此时时间复杂度是O(K*N)。
太慢了，于是我写下了第二行和第三行注释。令d[i]=N-t[i]，那么要求的变成max{min{abs{guess-d[i]},i=1 to K},guess=0 to N}，其实这一步是没有多大用的，不过本人很喜欢abs(guess-d[i])，因为它有几何意义。即在数轴上guess到d[i]的距离。
然后,看图：
![USACO[Elite 2010 March Competition/silver]解题报告 - 天之骄子 - 天之骄子的家](https://blog.boleyn.su/wp-content/uploads/2010/03/5688046329369509543.jpg "USACO[Elite 2010 March Competition/silver]解题报告 - 天之骄子 - 天之骄子的家")
显然，无论guess在数轴的哪个位置，min{abs{guess-d[i]}一定等于离guess最近的两个点（或一个点）到guess的距离的最小值。所以我们只要把d[]排序一下下，就OK了。O(∩_∩)O~
下面贴代码（有改动，现在可以全部AC）。
CODE:
/*
PROG: rocks
LANG: C++
ID: boleyn.2
*/
/*
TITLE: The Rock Game [Tom Conerly, 2010]
CONTENT:
Before the cows head home for rest and recreation, Farmer John wants
them to get some intellectual stimulation by playing a game.
The game board comprises N (1 <= N <= 15) identical holes in the
ground, all of which are initially empty. A cow moves by either
covering exactly one hole with a rock, or uncovering exactly one
previously covered hole. The game state is defined by which holes
are covered with rocks and which aren’t. The goal of the game is
for the cows to reach every possible game state exactly once and
then return to the state with all holes uncovered.
The cows have been having a tough time winning the game. Below is
an example of one of their games:
Holes
time 1 2 3
—————–
0 O O O Initially all of the holes are empty
1 O O X The cow covers hole 3
2 X O X The cow covers hole 1
3 X O O The cow uncovers hole 3
4 X X O The cow covers hole 2
5 O X O The cow uncovers hole 1
6 O X X The cow covers hole 3
7 X X X The cow covers hole 1
Now the cows are stuck! They must uncover one hole and no matter
which one they uncover they will reach a state they have already
reached. For example if they remove the rock from the second hole
they will reach the state (X O X) which they already visited at
time 2.
Below is an example of a valid solution for N=3 holes:
Holes
time 1 2 3
—————–
0 O O O Initial state: all of the holes are empty
1 O X O The cow covers hole 2
2 O X X The cow covers hole 3
3 O O X The cow uncovers hole 2
4 X O X The cow covers hole 1
5 X X X The cow covers hole 2
6 X X O The cow uncovers hole 3
7 X O O The cow uncovers hole 2
8 O O O The cow uncovers the 1st hole
which returns the game board to the start having, visited each state once.
The cows are tired of the game and want your help. Given N, create
a valid sequence of states that solves the game. If there are
multiple solutions return any one.
PROBLEM NAME: rocks
INPUT FORMAT:
* Line 1: A single integer: N
SAMPLE INPUT (file rocks.in):
3
OUTPUT FORMAT:
* Lines 1..2^N+1: A string of length N containing only ‘O’ and ‘X’
(where O denotes a uncovered hole and X denotes a covered
hole). The jth character in this line represents whether the
jth hole is covered or uncovered in this state. The first and
last lines must be all uncovered (all O).
SAMPLE OUTPUT (file rocks.out):
OOO
OXO
OXX
OOX
XOX
XXX
XXO
XOO
OOO
*/
#include <fstream>
using std::ifstream;
using std::ofstream;
using std::endl;
#include <cstring>
using std::memset;
class Application
{
ifstream cin;
ofstream cout;
static const int MAXN=15;
int N;
bool print(int state)
{
for (int i=0;i<N;i++)
if ((1<<i)&state) cout<<‘X’;
else cout<<‘O’;
cout<<endl;
return true;
}
void dfs(int step,int state)
{
static bool visited[1<<MAXN];
static bool finished;
if (finished) return;
if (step==(1<<N)&&(!state))
{
finished=true;
print(state);
return;
}
if (!visited[state])
{
visited[state]=true;
for (int i=0;i<N;i++)
if (!finished) dfs(step+1,state xor (1<<i));
visited[state]=false;
}
if (finished) print(state);
}
public:
Application(char* input,char* output)
:cin(input),cout(output)
{
cin>>N;
}
~Application()
{
cin.close();
cout.close();
}
int run()
{
dfs(0,0);
return 0;
}
};
int main()
{
Application app(“rocks.in”,“rocks.out”);
return app.run();
}
/*
PROG: teststr
LANG: C++
ID: boleyn.2
*/
/*
TITLE: Test Taking [Tom Conerly, 2010]
CONTENT:
Farmer John has to take his annual farming license test. The test
comprises N (1 <= N <= 1,000,000) true/false questions. After FJ’s
dismal performance on last year’s test Bessie wishes to help him.
Bessie has inside information that the number of questions whose
answer is true will be one of t_1, t_2, t_3,…, or t_K (0 <= t_i
<= N; 0 <= K <= 10,000) — even though Bessie has no information
about any answer to any specific question. Bessie wants to know the
best score that FJ is guaranteed achieve by exploiting this information
carefully, even if he doesn’t know the actual answers to any test
questions.
To demonstrate Bessie’s idea, consider a license test with N=6
questions where Bessie knows that the number of questions with the
answer ‘true’ is either 0 or 3. FJ can always get at least 3 answers
correct using logic like this: If FJ answers ‘false’ on every
question and there are 0 questions with the answer ‘true’ then he
will get all 6 correct. If there are 3 questions with the answer
‘true’ then he will get 3 answers correct. So as long as he marks
every answer as ‘false’ he is guaranteed to get at least 3 correct
without knowing any answer to the test questions.
On the other hand, consider what happens if FJ chooses an inferior
strategy: he guesses that some 3 answers are ‘true’ and the other
3 are ‘false’. If it turns out that NO answers are ‘true’ then FJ
will get 3 answers correct, the ones he guessed were false. If 3
answers are ‘true’ then FJ could get as few as 0 answers correct.
If he answered incorrectly on all 3 of that answers for which he
guessed ‘true’, and the other 3 (for which he guessed ‘false’) are
true, then he gets 0 correct answers. Even though FJ could get 3
correct in this case by guessing ‘false’ every time, he can not
always guarantee even 1 correct by guessing some 3 answers as ‘true’,
so this strategy can not guarantee getting any answer correct. FJ
should use the previous paragraph’s strategy.
Given Bessie’s inside information, determine the number of answers
FJ can always get correct using this information assuming he uses
it optimally.
PROBLEM NAME: teststr
INPUT FORMAT:
* Line 1: Two space-separated integers: N and K
* Lines 2..K+1: Line i+1 contains a single integer: t_i
SAMPLE INPUT (file teststr.in):
6 2
0
3
OUTPUT FORMAT:
* Line 1: A single integer, the best score FJ is guaranteed to achieve
SAMPLE OUTPUT (file teststr.out):
3
*/
#include <fstream>
using std::ifstream;
using std::ofstream;
using std::endl;
#include <cstring>
using std::memset;
#include <algorithm>
using std::sort;
class Application
{
ifstream cin;
ofstream cout;
static const int MAXK=10000;
int N,K;
int t[MAXK+2];
inline int abs(int n)
{
return n>-n?n:-n;
}
public:
Application(char* input,char* output)
:cin(input),cout(output)
{
cin>>N>>K;
for (int i=1;i<=K;i++) cin>>t[i];
}
~Application()
{
cin.close();
cout.close();
}
int run()
{
//max{min{abs{guess+t[i]-N}}}
//d[i]=N-t[i]
//max{min{abs{guess-d[i]}}}
int d[MAXK+2];
for (int i=1;i<=K;i++)
d[i]=N-t[i];
sort(d+1,d+K+1);
int answer=0;
for (int i=1;i<=K;i++)
if (answer<(d[i+1]-d[i])/2) answer=(d[i+1]-d[i])/2;
if (answer<N-d[K]) answer=N-d[K];
if (answer<d[1]) answer=d[1];
cout<<answer<<endl;
/*
int answer=0;
for (int guess=0;guess<=N;guess++)
{
int min=N;
for (int i=1;i<=K;i++)
{
//cout<<guess<<“,”<<i<<“=abs(“<<guess<<“+”<<t[i]<<“-“<<N<<“) “<<abs(guess+t[i]-N)<<endl;
if (abs(guess+t[i]-N)<min) min=abs(guess+t[i]-N);
}
cout<<guess<<“min=”<<min<<endl;
if (min>answer) answer=min;
}
cout<<answer<<endl;
*/
return 0;
}
};
int main()
{
Application app(“teststr.in”,“teststr.out”);
return app.run();
}
/*
PROG: sboost
LANG: C++
ID: boleyn.2
*/
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-3-13
DESCRIPTION:
Need For Speed [Jeffrey Wang, 2007]
Bessie is preparing her race car for the upcoming Grand Prix, but
she wants to buy some extra parts to improve the car’s performance.
Her race car currently has mass M (1 <= M <= 1,000) and is able
to push itself forward with a force of F (1 <= F <= 1,000,000).
The Race Car Performance Store has N (1 <= N <= 10,000) parts
conveniently numbered 1..N. Bessie can buy as many or as few parts
as she wishes though the store stocks no more than one instance
of each part.
Part P_i adds force F_i (1 <= F_i <= 1,000,000) and has mass
M_i (1 <= M_i <= 1,000). Newton’s Second Law decrees that F =
MA, where F is force, M is mass, and A is acceleration. If Bessie
wants to maximize the total acceleration of her race car (and
minimize the mass otherwise), which extra parts should she choose?
Consider a race car with initial F=1500 and M=100. Four parts are
available for enhancement:
i F_i M_i
1 250 25
2 150 9
3 120 5
4 200 8
Adding just part 2, e.g., would result in an acceleration of
(1500+150)/(100+9) = 1650/109 = 15.13761.
Below is a chart of showing the acceleration for all possible
combinations of adding/not-adding the four parts (in column one,
1=part added, 0=part not added):
Parts Aggregate Aggregate
1234 F M F/M
0000 1500 100 15.0000
0001 1700 108 15.7407
0010 1620 105 15.4286
0011 1820 113 16.1062
0100 1650 109 15.1376
0101 1850 117 15.8120
0110 1770 114 15.5263
0111 1970 122 16.1475 <– highest F/M
1000 1750 125 14.0000
1001 1950 133 14.6617
1010 1870 130 14.3846
1011 2070 138 15.0000
1100 1900 134 14.1791
1101 2100 142 14.7887
1110 2020 139 14.5324
1111 2220 147 15.1020
Thus, the best additional part combination is parts 2, 3, and 4.
PROBLEM NAME: sboost
INPUT FORMAT:
* Line 1: Three space-separated integers: F, M, and N
* Lines 2..N+1: Line i+1 contains two space separated integers: F_i
and M_i
SAMPLE INPUT (file sboost.in):
1500 100 4
250 25
150 9
120 5
200 8
OUTPUT FORMAT:
* Lines 1..P: The index values of P extra parts, one per line, that
Bessie should add to her racecar. If she should not add any,
output ‘NONE’ (without quotes). The output should be given in
increasing order, so if the optimal set of parts is {2,4,6,7},
then the output should be in the order 2,4,6,7 and not, for
example, 4,2,7,6. Solutions will be unique.
SAMPLE OUTPUT (file sboost.out):
2
3
4
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <fstream>
using std::ifstream;
using std::ofstream;
using std::endl;
#include <sstream>
using std::stringstream;
#include <vector>
using std::vector;
#include <string>
using std::string;
#include <stack>
using std::stack;
#include <queue>
using std::queue;
#include <map>
using std::map;
using std::pair;
using std::make_pair;
#include <algorithm>
using std::sort;
#include <cassert>
//using std::assert;
struct Compare
{
bool operator()(const pair<int,pair<int,int> >& a,
const pair<int,pair<int,int> >& b)
{
return (long long int)(a.second.first)*(long long int)(b.second.second)
>
(long long int)(b.second.first)*(long long int)(a.second.second);
}
}compare;
class Application
{
ifstream cin;
ofstream cout;
int N;
pair<int,pair<int,int> > FM;
vector<pair<int,pair<int,int> > > fm;
public:
Application(char* input,char* output)
:cin(input),cout(output)
{
cin>>FM.second.first>>FM.second.second>>N;
fm.resize(N);
for (int i=0;i<N;i++)
{
cin>>fm[i].second.first>>fm[i].second.second;
fm[i].first=i+1;
}
}
int run()
{
sort(fm.begin(),fm.end(),compare);
int i=0;
while (compare(fm[i],FM)&&(i<fm.size()))
{
FM.second.first+=fm[i].second.first;
FM.second.second+=fm[i].second.second;
i++;
}
fm.resize(i);
if (i)
{
sort(fm.begin(),fm.end());
for (int i=0;i<fm.size();i++)
cout<<fm[i].first<<endl;
}
else cout<<“NONE”<<endl;
return 0;
}
};
int main()
{
Application app(“sboost.in”,“sboost.out”);
return app.run();
}