KRSU May Training Contest
Сабж прошел сегодня на задачах школьного чемпионата, что означало простые и короткие задачи. Победил renatm без единого бревна через 43 минуты после начала. Я финишировал 4-м (внезапно сеть стала говорить Reply from 81.20.20.4: TTL expired in transit.).
А трусишка udpn предпочел смотреть мультики.
A
Найти минимальное число квадратов натуральных чисел, дающих в сумме N.
Задача на ДП. Кроме того, можно вспомнить теорему Гильберта-Варинга, которая, в частности, утверждает, что любое натуральное число можно представить в виде суммы не более 4 квадратов.
const int M = 2010;
int dp[M];
memset(dp, 0, sizeof(dp));
for (int i = 1; i * i < M; ++i) dp[i * i] = 1;
for (int i = 2; i <= 4; ++i) {
for (int j = 1; j < M; ++j) if (dp[j] == i-1) {
for (int k = 1; k * k + j < M; ++k) {
if (dp[k * k + j] == 0) {
dp[k * k + j] = i;
}
}
}
}
int n;
cin >> n;
cout << dp[n] << endl;
B
В клеточном квадрате 2009x2009 в ячейке (x;y) завелся вирус, который может перемещаться только в окрестности фон Неймана (4 клетки) и не может дважды посещать одну ячейку. Найти минимальное число клеток, которые он посетит, прежде чем будет обездвижен.
Немного порисовав, можно понять, что уголок будет выглядеть примерно так:
688888
688888
678888
567888
486788
645666
и написать соответствующий ему код. Если код будет не соответствовать, можно получить +3, как у меня.
const int M = 2009;
int x, y;
cin >> x >> y;
x = min(x, M-x+1);
y = min(y, M-y+1);
if (x == 1 && y == 2 || x == 2 && y == 1) cout << 4;
else if (x == 1 && y == 3 || y == 1 && x == 3) cout << 5;
else if (x == 1 || y == 1 || x + y == 5) cout << 6;
else if (x + y == 6) cout << 7;
else cout << 8;
cout << endl;
C
Даны числа 1..N. Игрок А ходом забирает любое простое число, игрок Б любой палиндром. Если один игрок не может сделать ход, другой забирает все оставшиеся. Сколько заберет А при оптимальной игре с обоих сторон?
Оптимальной стратегией с обеих сторон является брать сначала простые палиндромы. Выигрыш зависит от того, кому дольше хватит чисел. Достаточно посчитать количество простых палиндромов, просто простых чисел и просто палиндромов, после чего выписать ответ.
Функции ispali и isprime не приводятся ввиду их очевидности.
int n;
cin >> n;
int pp = 0, pr = 0, pa = 0;
for (int i = 1; i <= n; ++i) {
bool prime = isprime(i), pali = ispali(i);
if (prime && pali) ++pp;
else if (prime) ++pr;
else if (pali) ++pa;
}
if (pp / 2 + pa < pp / 2 + pp % 2 + pr) cout << n - (pp / 2 + pa) << endl;
else cout << (pp / 2 + pp % 2 + pr) << endl;
D
Координатами углов (≤2009) заданы два целочисленных прямоугольника 1 и 2. Найти площадь 1−2.
Небольшие значения координат позволяют решить задачу тупым моделированием.
char a[2010][2010];
const int M = 2009;
memset(a, 0, sizeof(a));
int xl1, xr1, yl1, yr1, xl2, xr2, yl2, yr2;
cin >> xl1 >> xr1 >> yl1 >> yr1 >> xl2 >> xr2 >> yl2 >> yr2;
for (int i = xl1; i < xr1; ++i) for (int j = yl1; j < yr1; ++j) a[i][j] = 1;
for (int i = xl2; i < xr2; ++i) for (int j = yl2; j < yr2; ++j) a[i][j] = 2;
int res = 0;
for (int i = xl1; i < xr1; ++i) for (int j = yl1; j < yr1; ++j) if (a[i][j] == 1) ++res;
cout << res;
E
Из N монет (5 ≤ N ≤ 1000) K лежат решкой вверх. За шаг можно перевернуть любые 5. Можно ли повернуть все монеты одной стороной вверх?
Можно подумать, а можно реализовать простое ДП [решек] = шагов.
int n, k;
cin >> n >> k;
vector dp(n + 1);
dp[k] = 1;
bool was = true;
for (int step = 2; was; ++step) {
was = false;
for (int i = 0; i <= n; ++i) if (dp[i] == step - 1) {
for (int j = 0; j <= 5; ++j) {
if (i >= j && n - i >= 5 - j) {
int newk = i - j + 5 - j;
if (dp[newk] == 0) {
dp[newk] = step;
was = true;
}
}
}
}
}
if (dp[0] || dp[n]) cout << "YES" << endl;
else cout << "NO" << endl;
F
В N! (N > 5, не больше 100 цифр) одна цифра заменена символом ?. Написать это число без ?.
Простейшее решение - наглый хардкод. Легко догадаться, что все N! при N>5 отличаются длиной, а сам список факториалов без труда выдаст Maple.
string s[] = { /* Хардкод */ };
string a;
cin >> a;
int i;
for (i = 0; a.length() != s[i].length(); ++i);
cout << s[i] << endl;
G
Найти минимальное число разрезов, нужных для разделения прямоугольника NxM на отдельные клетки (прямоугольники можно перемещать).
Просто сумма округленных вверх двоичных логарифмов.
int n, m;
cin >> n >> m;
cout << int(ceil(log((double) n) / log(2.0)) + ceil(log((double) m) / log(2.0))) << endl;
А если кто-то еще не успел ознакомиться с потрясающим Wolfram Alpha (хочу у них работать, хнык) или с изумительной 4K PC демкой elevated by Rgba [web] & TBC (видео, потому что машина нужна беспощадно суровая) - самое время это сделать.
А трусишка udpn предпочел смотреть мультики.
A
Найти минимальное число квадратов натуральных чисел, дающих в сумме N.
Задача на ДП. Кроме того, можно вспомнить теорему Гильберта-Варинга, которая, в частности, утверждает, что любое натуральное число можно представить в виде суммы не более 4 квадратов.
const int M = 2010;
int dp[M];
memset(dp, 0, sizeof(dp));
for (int i = 1; i * i < M; ++i) dp[i * i] = 1;
for (int i = 2; i <= 4; ++i) {
for (int j = 1; j < M; ++j) if (dp[j] == i-1) {
for (int k = 1; k * k + j < M; ++k) {
if (dp[k * k + j] == 0) {
dp[k * k + j] = i;
}
}
}
}
int n;
cin >> n;
cout << dp[n] << endl;
B
В клеточном квадрате 2009x2009 в ячейке (x;y) завелся вирус, который может перемещаться только в окрестности фон Неймана (4 клетки) и не может дважды посещать одну ячейку. Найти минимальное число клеток, которые он посетит, прежде чем будет обездвижен.
Немного порисовав, можно понять, что уголок будет выглядеть примерно так:
688888
688888
678888
567888
486788
645666
и написать соответствующий ему код. Если код будет не соответствовать, можно получить +3, как у меня.
const int M = 2009;
int x, y;
cin >> x >> y;
x = min(x, M-x+1);
y = min(y, M-y+1);
if (x == 1 && y == 2 || x == 2 && y == 1) cout << 4;
else if (x == 1 && y == 3 || y == 1 && x == 3) cout << 5;
else if (x == 1 || y == 1 || x + y == 5) cout << 6;
else if (x + y == 6) cout << 7;
else cout << 8;
cout << endl;
C
Даны числа 1..N. Игрок А ходом забирает любое простое число, игрок Б любой палиндром. Если один игрок не может сделать ход, другой забирает все оставшиеся. Сколько заберет А при оптимальной игре с обоих сторон?
Оптимальной стратегией с обеих сторон является брать сначала простые палиндромы. Выигрыш зависит от того, кому дольше хватит чисел. Достаточно посчитать количество простых палиндромов, просто простых чисел и просто палиндромов, после чего выписать ответ.
Функции ispali и isprime не приводятся ввиду их очевидности.
int n;
cin >> n;
int pp = 0, pr = 0, pa = 0;
for (int i = 1; i <= n; ++i) {
bool prime = isprime(i), pali = ispali(i);
if (prime && pali) ++pp;
else if (prime) ++pr;
else if (pali) ++pa;
}
if (pp / 2 + pa < pp / 2 + pp % 2 + pr) cout << n - (pp / 2 + pa) << endl;
else cout << (pp / 2 + pp % 2 + pr) << endl;
D
Координатами углов (≤2009) заданы два целочисленных прямоугольника 1 и 2. Найти площадь 1−2.
Небольшие значения координат позволяют решить задачу тупым моделированием.
char a[2010][2010];
const int M = 2009;
memset(a, 0, sizeof(a));
int xl1, xr1, yl1, yr1, xl2, xr2, yl2, yr2;
cin >> xl1 >> xr1 >> yl1 >> yr1 >> xl2 >> xr2 >> yl2 >> yr2;
for (int i = xl1; i < xr1; ++i) for (int j = yl1; j < yr1; ++j) a[i][j] = 1;
for (int i = xl2; i < xr2; ++i) for (int j = yl2; j < yr2; ++j) a[i][j] = 2;
int res = 0;
for (int i = xl1; i < xr1; ++i) for (int j = yl1; j < yr1; ++j) if (a[i][j] == 1) ++res;
cout << res;
E
Из N монет (5 ≤ N ≤ 1000) K лежат решкой вверх. За шаг можно перевернуть любые 5. Можно ли повернуть все монеты одной стороной вверх?
Можно подумать, а можно реализовать простое ДП [решек] = шагов.
int n, k;
cin >> n >> k;
vector
dp[k] = 1;
bool was = true;
for (int step = 2; was; ++step) {
was = false;
for (int i = 0; i <= n; ++i) if (dp[i] == step - 1) {
for (int j = 0; j <= 5; ++j) {
if (i >= j && n - i >= 5 - j) {
int newk = i - j + 5 - j;
if (dp[newk] == 0) {
dp[newk] = step;
was = true;
}
}
}
}
}
if (dp[0] || dp[n]) cout << "YES" << endl;
else cout << "NO" << endl;
F
В N! (N > 5, не больше 100 цифр) одна цифра заменена символом ?. Написать это число без ?.
Простейшее решение - наглый хардкод. Легко догадаться, что все N! при N>5 отличаются длиной, а сам список факториалов без труда выдаст Maple.
string s[] = { /* Хардкод */ };
string a;
cin >> a;
int i;
for (i = 0; a.length() != s[i].length(); ++i);
cout << s[i] << endl;
G
Найти минимальное число разрезов, нужных для разделения прямоугольника NxM на отдельные клетки (прямоугольники можно перемещать).
Просто сумма округленных вверх двоичных логарифмов.
int n, m;
cin >> n >> m;
cout << int(ceil(log((double) n) / log(2.0)) + ceil(log((double) m) / log(2.0))) << endl;
А если кто-то еще не успел ознакомиться с потрясающим Wolfram Alpha (хочу у них работать, хнык) или с изумительной 4K PC демкой elevated by Rgba [web] & TBC (видео, потому что машина нужна беспощадно суровая) - самое время это сделать.