## Problem A Second-price Auction

#### Code

```#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> P;
P v[110];

int main() {
int T; cin >> T;
while(T--) {
int n; cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> v[i].first;
v[i].second = i;
}
sort(v + 1, v + n + 1);
cout << v[n].second << " " << v[n-1].first << endl;
}
return 0;
}
```

## Problem B Light Bulb

#### Code

```#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-7;
double H, h, D;
double lim;

double solve(double i) {
if(i >= lim) {
double d = D - i;
return d * h / H;
}
double m = (D*h - i*H) / (H - h);
return i + H * m / (D + m);
}

int main()
{
int T; scanf("%d", &T);
while(T--) {
scanf("%lf%lf%lf", &H, &h, &D);
lim = D * h / H;
double L = 0, R = D;
for(int i = 0; i < 100; ++i) {
double mid1 = L + (R - L) / 3.0;
double mid2 = R - (R - L) / 3.0;
if(solve(mid1) > solve(mid2)) {
R = mid2;
} else {
L = mid1;
}
}
printf("%.3f\n", solve(L));
}
return 0;
}
```

## Problem C Connect them

#### Code

```#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

struct Edge {
int from, to, cost;
Edge(int from, int to, int cost):
from(from), to(to), cost(cost) {}
bool operator < (const Edge & rhs) const {
if(cost != rhs.cost) return cost < rhs.cost;
if(from != rhs.from) return from < rhs.from;
}
};
const int maxn = 110;
vector<Edge> e;
vector<P> res;
int n, pa[maxn];

void Init(int n) { for(int i = 0; i <= n; ++i) pa[i] = i; }
int Find(int x) { return pa[x] == x ? x : pa[x] = Find(pa[x]); }

void Kruskal() {
sort(e.begin(), e.end());
res.clear();
int cnt = 0;
Init(n);
for(int i = 0; i < e.size(); ++i) {
int rx = Find(e[i].from);
int ry = Find(e[i].to);
if(rx != ry) {
pa[rx] = ry;
res.push_back(P(e[i].from, e[i].to));
++cnt;
if(cnt >= n - 1)
break;
}
}
}

int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d", &n);
e.clear();
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
int len; scanf("%d", &len);
if(len) e.push_back(Edge(i, j, len));
}
}
Kruskal();
if(res.size() < n-1) {
puts("-1");
} else {
sort(res.begin(), res.end());
for(int i = 0; i < res.size(); ++i) {
printf("%d %d%c", res[i].first, res[i].second, i==res.size()-1 ? '\n' : ' ');
}
}
}
return 0;
}
```

## Problem F 80ers’ Memory

#### Code

```#include <bits/stdc++.h>
using namespace std;

set<string> s;

int main() {
int n; cin >> n;
for(int i = 0; i < n; ++i) {
string cur; cin >> cur;
s.insert(cur);
}
cin >> n;
while(n--) {
int m, cnt = 0; cin >> m;
while(m--) {
string cur; cin >> cur;
if(s.count(cur)) ++cnt;
}
cout << cnt << endl;
}
return 0;
}
```

## Problem I A Stack or A Queue?

### Mean

#### Code

```#include <bits/stdc++.h>
using namespace std;

vector<int> a, b;

int main() {
int T; cin >> T;
while(T--) {
int n; cin >> n;
a.clear(); b.clear();
for(int i = 0; i < n; ++i) {
int x; cin >> x;
a.push_back(x);
}
for(int i = 0; i < n; ++i) {
int x; cin >> x;
b.push_back(x);
}
bool ok1 = false;
bool ok2 = false;
if(a == b) ok1 = true;
reverse(a.begin(), a.end());
if(a == b) ok2 = true;
if(ok1 && ok2) {
cout << "both" << endl;
} else if(ok1 && !ok2) {
cout << "queue" << endl;
} else if(!ok1 && ok2) {
cout << "stack" << endl;
} else {
cout << "neither" << endl;
}
}
return 0;
}
```

## Problem J Dream City

#### Code

```#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

const int maxn = 300;
int n, m, dp[maxn][maxn];
P v[maxn];

int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%d", &v[i].first);
for(int i = 1; i <= n; ++i)
scanf("%d", &v[i].second);
sort(v+1, v+n+1, [](const P &a, const P& b) { return a.second < b.second; });
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + v[j].first + (i-1)*v[j].second);
}
}
printf("%d\n", dp[m][n]);
}
return 0;
}
```

## Problem K K-Nice

#### Code

```#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

const int maxn = 300;
int n, m, dp[maxn][maxn];
P v[maxn];

int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%d", &v[i].first);
for(int i = 1; i <= n; ++i)
scanf("%d", &v[i].second);
sort(v+1, v+n+1, [](const P &a, const P& b) { return a.second < b.second; });
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + v[j].first + (i-1)*v[j].second);
}
}
printf("%d\n", dp[m][n]);
}
return 0;
}
```