#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
using namespace std;
int main() {
int n;
while (cin >> n) {
if (n == 0)
break;
map<string, int> mp;
map<string, int>::iterator it, ans;
int MAX = 0;
for (int i = 0; i < n; i ++ ) {
string str;
cin >> str;
it = mp.find(str);
if (it != mp.end())
mp[str] ++ ;
else
mp[str] = 1;
}
for (it = mp.begin(); it != mp.end(); it ++ ) {
if (it->second > MAX) {
MAX = it->second;
ans = it;
}
}
cout << ans->first << endl;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
using namespace std;
const int N = 40;
char a[N];
int main() {
while (cin >> a) {
if (!strcmp(a, "#"))
break;
int n = strlen(a);
int cnt = 0;
for (int i = 0; i < n - 1; i ++ ) {
cout << a[i];
if (a[i] == '1')
cnt ++ ;
}
if (a[n - 1] == 'e' && cnt % 2 == 0)
cout << '0';
else if (a[n - 1] == 'e' && cnt % 2 == 1)
cout << '1';
else if (a[n - 1] == 'o' && cnt % 2 == 0)
cout << '1';
else if (a[n - 1] == 'o' && cnt % 2 == 1)
cout << '0';
puts("");
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int w[N];
int f[N][N];
int main() {
while (cin >> n && n) {
for (int i = 1; i <= n; i ++ )
cin >> w[i];
cin >> m;
sort(w + 1, w + 1 + n);
int MAX = w[n];
if (m < 5) {
cout << m << endl;
continue;
}
m -= 5;
memset(f, 0, sizeof f);
for (int i = 1; i < n; i ++ )
for (int j = 0; j <= m; j ++ ) {
f[i][j] = f[i - 1][j];
if (j >= w[i])
f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + w[i]);
}
cout << m + 5 - MAX - f[n - 1][m] << endl;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
using namespace std;
const int N = 510, M = 5010;
struct node {
int p, q, v;
} a[N];
int f[M];
bool cmp(node A, node B) {
return A.q - A.p < B.q - B.p;
}
int main() {
int n, m;
while (cin >> n >> m) {
for (int i = 1; i <= n; i ++ )
cin >> a[i].p >> a[i].q >> a[i].v;
sort(a + 1, a + 1 + n, cmp);
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= a[i].p; j -- )
if (j >= a[i].q)
f[j] = max(f[j], f[j - a[i].p] + a[i].v);
cout << f[m] << endl;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int N = 10;
struct point {
int x, y;
bool check() {
if (x >= 0 && x < 8 && y >= 0 && y < 8)
return true;
return false;
}
};
struct node {
point p[4];
int step;
} st, ed;
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int g[N][N];
char vis[8][8][8][8][8][8][8][8];
bool cmp(point A, point B) {
if (A.x != B.x)
return A.x < B.x;
else
return A.y < B.y;
}
bool Tb_OK(point s) {
if (g[s.x][s.y])
return true;
return false;
}
char get_vis(node s) {
return vis[s.p[0].x][s.p[0].y][s.p[1].x][s.p[1].y][s.p[2].x][s.p[2].y][s.p[3].x][s.p[3].y];
}
bool bfs() {
node One, next;
memset(vis, 0, sizeof vis);
vis[st.p[0].x][st.p[0].y][st.p[1].x][st.p[1].y][st.p[2].x][st.p[2].y][st.p[3].x][st.p[3].y] = '1';
vis[ed.p[0].x][ed.p[0].y][ed.p[1].x][ed.p[1].y][ed.p[2].x][ed.p[2].y][ed.p[3].x][ed.p[3].y] = '2';
st.step = ed.step = 0;
queue<node> p, q;
p.push(st), q.push(ed);
while (p.size() || q.size()) {
if (p.size()) {
One = p.front();
p.pop();
memset(g, 0, sizeof g);
g[One.p[0].x][One.p[0].y] = 1, g[One.p[1].x][One.p[1].y] = 1;
g[One.p[2].x][One.p[2].y] = 1, g[One.p[3].x][One.p[3].y] = 1;
if (One.step >= 4)
continue;
for (int i = 0; i < 4; i ++ )
for (int j = 0; j < 4; j ++ ) {
next = One;
next.step ++ ;
next.p[j].x += dx[i], next.p[j].y += dy[i];
if (!next.p[j].check())
continue;
if (Tb_OK(next.p[j])) {
next.p[j].x += dx[i], next.p[j].y += dy[i];
if (!next.p[j].check())
continue;
}
sort(next.p, next.p + 4, cmp);
if (get_vis(next) == '1')
continue;
else if (get_vis(next) == '2')
return true;
vis[next.p[0].x][next.p[0].y][next.p[1].x][next.p[1].y][next.p[2].x][next.p[2].y][next.p[3].x][next.p[3].y] = '1';
p.push(next);
}
}
if (q.size()) {
One = q.front();
q.pop();
memset(g, 0, sizeof g);
g[One.p[0].x][One.p[0].y] = 1, g[One.p[1].x][One.p[1].y] = 1;
g[One.p[2].x][One.p[2].y] = 1, g[One.p[3].x][One.p[3].y] = 1;
if (One.step >= 4)
continue;
if (get_vis(One) == '1')
return true;
for (int i = 0; i < 4; i ++ )
for (int j = 0; j < 4; j ++ ) {
next = One;
next.step ++ ;
next.p[j].x += dx[i], next.p[j].y += dy[i];
if (!next.p[j].check())
continue;
if (Tb_OK(next.p[j])) {
next.p[j].x += dx[i], next.p[j].y += dy[i];
if (!next.p[j].check())
continue;
}
sort(next.p, next.p + 4, cmp);
if (get_vis(next) == '1')
return true;
else if (get_vis(next) == '2')
continue;
vis[next.p[0].x][next.p[0].y][next.p[1].x][next.p[1].y][next.p[2].x][next.p[2].y][next.p[3].x][next.p[3].y] = '2';
q.push(next);
}
}
}
return false;
}
int main() {
while (cin >> st.p[0].x >> st.p[0].y) {
for (int i = 1; i < 4; i ++ )
cin >> st.p[i].x >> st.p[i].y;
for (int i = 0; i < 4; i ++ )
cin >> ed.p[i].x >> ed.p[i].y;
for (int i = 0; i < 4; i ++ ) {
st.p[i].x --, st.p[i].y -- ;
ed.p[i].x --, ed.p[i].y -- ;
}
sort(st.p, st.p + 4, cmp);
sort(ed.p, ed.p + 4, cmp);
bool flag = bfs();
if (flag)
puts("YES");
else
puts("NO");
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 70;
int n, a[N];
bool flag, st[N];
int MAX;
bool cmp(int a, int b) {
return a > b;
}
void dfs(int res, int v) {
// 找到答案,返回
if (flag)
return;
// 如果所有都被选择 flag置true,表示找到
if (v == n) {
flag = true;
return;
}
// 如果res = 0 且并非所有都被选择,则继续将MAX dfs
if (res == 0 && v < n)
dfs(MAX, v);
for (int i = 0; i < n; i ++ ) {
if (!flag && !st[i] && a[i] <= res) {
st[i] = true;
dfs(res - a[i], v + 1);
st[i] = false;
// 这个去掉 +40MS
if (res == a[i])
return;
// 这个去掉,TLE。。
if (res == MAX)
return;
// 这个剪枝去掉了,+100MS
while (a[i] == a[i + 1])
i ++ ;
}
}
}
int main() {
while (cin >> n && n) {
int sum = 0;
for (int i = 0; i < n; i ++ ) {
cin >> a[i];
sum += a[i];
}
sort(a, a + n, cmp);
MAX = a[0];
// 剪枝:如果最长的长度大于剩余所有长度和,则答案就是他们的和
//(这个去掉了也可以,耗时没有变化 = 。=,就是说不写也可以)
if (MAX > sum - MAX) {
cout << sum << endl;
continue;
}
flag = false;
while (!flag) {
// 剪枝: 如果所有长度总和 对 目标长度 取模不为0 ,则目标长度一定不是答案,这个必须有
// 这个如果去掉,耗时增多不说,对后面剪枝影响,会导致WA
while (sum % MAX != 0)
MAX ++ ;
memset(st, false, sizeof st);
dfs(MAX, 0);
if (flag)
break;
MAX ++ ;
}
cout << MAX << endl;
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 3e3 + 10, INF = 0x3f3f3f3f;
typedef long long LL;
int n, m, Q;
LL ans;
int g[N][N];
int f[N][N];
bool st[N];
int dist[N];
vector<int> v[N];
int p[N];
void prim(int x) {
ans = 0LL;
for (int i = 0; i < n; i ++ )
dist[i] = g[x][i], p[i] = x, st[i] = false, v[i].clear();
st[0] = true, p[0] = -1, dist[0] = INF;
for (int i = 1; i < n; i ++ ) {
int t = 0;
for (int j = 0; j < n; j ++ ) {
if (!st[j] && dist[t] > dist[j])
t = j;
}
st[t] = true;
if (p[t] != -1) {
v[t].push_back(p[t]);
v[p[t]].push_back(t);
}
ans += (LL)dist[t];
for (int j = 0; j < n; j ++ ) {
if (!st[j] && dist[j] > g[t][j]) {
dist[j] = g[t][j];
p[j] = t;
}
}
}
}
int dfs(int u, int fa, int root) {
int res = INF;
for (int i = 0; i < v[u].size(); i ++ ) {
int j = v[u][i];
if (j == fa)
continue;
int temp = dfs(j, u, root);
res = min(res, temp);
f[u][j] = f[j][u] = min(f[u][j], temp);
}
if (root != fa)
res = min(res, g[root][u]);
return res;
}
int main() {
while (~scanf("%d%d", &n, &m)) {
if (n == 0 && m == 0)
break;
memset(g, 0x3f, sizeof g);
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= m; i ++ ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
prim(0);
for (int i = 0; i < n; i ++ )
dfs(i, -1, i);
LL sum = 0LL;
scanf("%d", &Q);
for (int i = 1; i <= Q; i ++ ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (p[a] != b && p[b] != a)
sum += ans;
else
sum += (ans - g[a][b] + min(c, f[a][b]));
}
printf("%.4lf\n", 1.0 * sum / Q);
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
using namespace std;
const int N = 110;
#define INF 0x3f3f3f3f
int n, m;
int g[N][N];
int level[N];
bool st[N];
int dist[N];
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
for (int i = 1; i <= n; i ++ )
dist[i] = g[0][i];
for (int i = 1; i <= n; i ++ ) {
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
for (int j = 1; j <= n; j ++ )
if (!st[j] && g[t][j])
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
return dist[1];
}
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++ ) {
int q;
cin >> g[0][i] >> level[i] >> q;
while (q -- ) {
int ver, price;
cin >> ver >> price;
g[ver][i] = price;
}
}
int ans = INF;
for (int i = 1; i <= n; i ++ ) {
int MAX = level[i];
for (int j = 1; j <= n; j ++ ) {
if (level[j] > MAX || MAX - level[j] > m)
st[j] = true;
else
st[j] = false;
}
int min_price = dijkstra();
if (min_price < ans)
ans = min_price;
}
cout << ans << endl;
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int N = 10;
int casei;
int main() {
int p, e, i, d;
int lcm = 21252; // lcm(23, 28, 33)
while (cin >> p >> e >> i >> d && (~p || ~e || ~i || ~d)) {
int ans = (5544 * p + 14421 * e + 1288 * i - d + lcm) % lcm;
if (ans == 0)
ans = lcm;
printf("Case %d: the next triple peak occurs in %d days.\n", ++ casei, ans);
}
return 0;
}
#include <iostream>
#include <cmath>
using namespace std;
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
int main() {
int a, b, c;
while (cin >> a >> b >> c) {
if (a == 0 && b == 0 && c == 0)
break;
int x, y;
int d = exgcd(a, b, x, y);
int _x = x * (c / d), _y = y * (c / d);
int x1, y1;
x1 = (_x % (b / d) + (b / d)) % (b / d);
y1 = (c - a * x1) / b;
int x2, y2;
y2 = (_y % (a / d) + (a / d)) % (a / d);
x2 = (c - b * y2) / a;
if (abs(x1) + abs(y1) >= abs(x2) + abs(y2))
printf("%d %d\n", abs(x2), abs(y2));
else
printf("%d %d\n", abs(x1), abs(y1));
}
return 0;
}