Барабанная дробь и разбор готов! (✷‿✷) SRound #1
[problem:447021A]
- Идея: Ilya_Is2022
- Разработка: Ilya_Is2022
Для решения данной задачи достаточно было проверять введённый пинг на принадлежность к 4 числовым отрезкам, а именно:
- Если $$$n \in [0, 21)$$$, то выводить amazing!.
- Иначе если $$$n \in [21,\ 51)$$$, то выводить good!.
- Иначе если $$$n \in [51,\ 151)$$$, то выводить bad!.
- В противном случае $$$n \in [51,\ 1001)$$$, тогда нужно вывести very bad!.
Итоговая асимптотика решения: $$$\mathcal{O}(1)$$$
n = int(input())
if n < 21:
print("amazing!")
elif n < 51 and n > 20:
print("good!")
elif n < 151 and n > 50:
print("bad!")
else:
print("very bad!")
[problem: 447021B]
- Идея: Ilya_Is2022
- Разработка: Ilya_Is2022
Способов решения данной задачи существует очень много, поэтому разберем самое оптимальное.
В условии указано, что нужно найти любой интересный подотрезок, длина которого $$$\le n - 1$$$. Тогда не сложно догадаться, что достаточно вывести отрезок из $$$1$$$ элемента — максимума массива $$$a$$$, что будет удовлетворять условию задачи.
Итоговая асимптотика решения: $$$\mathcal{O}(n)$$$
n = int(input())
print(max(list(map(int, input().split()))))
[problem: 447021C]
Вычисление по данной формуле напрямую, скорее всего, не получится, так как $$$n$$$ может достигать $$$10^9$$$ и числа будут огромными. Но можно заметить, что $$$4 = 2 \times 2$$$, $$$21 = 3 \times 7$$$, $$$14 = 2 \times 7$$$, $$$15 = 3 \times 5$$$, $$$6 = 2 \times 3$$$. Используя стандартные правила работы со степенями, можно представить числитель и знаменатель в виде произведения простых чисел 2, 3, 5, 7 в некоторых степенях. При делении $$$a$$$ на $$$b$$$ число $$$n$$$ везде сократится и останется только число 200. То есть, $$$\cfrac{a}{b} = 200$$$. Значит $$$\cfrac{a \times n}{b} = 200 \times n$$$, значит, для решения задачи необходимо просто считать число $$$n$$$ и вывести $$$200 \times n$$$. Также стоит заметить, что при больших значениях $$$n$$$ в некоторых языках программирования ответ может не помещаться в 32-битный целочисленный тип данных, поэтому необходимо использовать 64-битный тип данных.
Итоговая асимптотика решения: $$$\mathcal{O}(1)$$$
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
cout << 200ll * n << "\n";
return 0;
}
n = int(input())
print(n * 200)
[problem: 447021D]
- Идея: Ilya_Is2022
- Разработка: Ilya_Is2022
Для решения данной версии задачи достаточно было перебрать все возможные числа, которые мог загадать Илья. Таким образом, для каждого обратного $$$i$$$-го числа нужно проверять его на соответствие сумм чисел на четных и нечетных позициях, а также количества нулей, для предложенного $$$j$$$-го тестового набора входных данных. Так как перебираемые числа довольно малы, то асимптотикой их проверки можно пренебречь. В случае успешного нахождения загаданного числа нужно вывести для $$$j$$$-го набора входных данных ответ YES, в противном случае, если такое число при заданных Ильей значениях $$$a$$$, $$$b$$$ и $$$k$$$ не существует или является больше, чем $$$10^4$$$, ответ NO.
Итоговая асимптотика решения: $$$\mathcal{O}(t \cdot n)$$$, где $$$n$$$ ($$$1 \le n \le 10^4$$$) — число, загаданное Ильей.
for _ in range(int(input())):
a, b, k = map(int, input().split())
answer = False
for i in range(1, 10 ** 4 + 1):
s = str(i)[::-1]
a_s = 0
b_s = 0
k_s = 0
for j in range(len(s)):
if j % 2 == 0:
b_s += int(s[j])
if s[j] == '0':
k_s += 1
else:
a_s += int(s[j])
if s[j] == '0':
k_s += 1
if a == a_s and b == b_s and k == k_s:
print("YES")
answer = True
break
if not answer:
print("NO")
[problem: 447021E]
- Идея: vika1310
- Разработка: Ilya_Is2022
- Разбор: nekstas
В начале давайте найдём все простые числа от в диапазоне [1, 100]. Это можно сделать вручную, с помощью алгоритмов, например, решета Эратосфена, перебором или любым другим способом. Мы получим 25 простых чисел от 1 до 100.
Можно понять, что нет смысла делать запрос с числом $$$x$$$, если в его разложении на простые числа есть числа больше 100 или степень какого-либо из простых чисел превосходит 1.
Заметим, что так как $$$n$$$ — простое число, то если мы хотим проверить, является ли число $$$n$$$ каким-то простым числом $$$x$$$ или $$$y$$$, мы можем проверить, делится ли число $$$x \times y$$$ на $$$n$$$. Если оно делится, то $$$n$$$ является либо числом $$$x$$$, либо числом $$$y$$$. Таким образом, за один запрос мы можем узнавать информацию, является ли $$$n$$$ числом $$$x$$$ сразу для нескольких чисел $$$x$$$.
Перейдём к самому решению. Давайте расположим все 25 простых чисел от 1 до 100 в порядке возрастания. А дальше можно применить бинпоиск. Изначально считаем, что число $$$n$$$ находится в отрезке от первого простого числа до последнего (из нашего списка). Возьмём число $$$x$$$ равное произведению первой половины нашего отрезка простых чисел. Проверим с помощью запроса, входит ли число $$$n$$$ в эту половину отрезка. Если входит, сдвинем правую границу в середину отрезка, иначе левую. И будем уменьшать отрезок постоянно в 2 раза, пока у нас не останется лишь одно число. Это число и будет ответом.
Может показаться, что $$$x$$$ в некотором запросе может стать больше $$$10^{18}$$$, но это не так: произведение первой половины чисел равно $$$7420738134810$$$, что меньше $$$10^{18}$$$. Если мы сдвинем границы влево, то произведение больше не станет. Если сдвинем вправо, то получим произведение $$$15805487167$$$, что тоже подходит под ограничения. Соответственно, отрезки, лежащие внутри тоже подходят, а справа произведение равно $$$19657257924641$$$, и оно тоже меньше $$$10^{18}$$$, а значит произведение всех последующих отрезков чисел тоже меньше $$$10^{18}$$$.
Значит, решение работает и сделает около $$$\log_2 25 $$$ запросов, то есть не больше $$$5$$$ запросов.
Итоговая асимптотика решения: $$$\mathcal{O}(1)$$$.
#include <bits/stdc++.h>
// #include "testlib.h"
using namespace std;
#define ll long long
#define vec vector
const ll INF = 1e9 + 7;
const ll NOT_INF = 1e9 + 7;
const string YES = "YES";
const string NO = "NO";
void rec(vec<int> v){
ll L = 1;
for(int i = 0; i < v.size() / 2 + v.size() % 2; i++){
L *= v[i];
}
cout << "? " << L << '\n';
cout.flush();
int n; cin >> n;
if (n){
if (L == v[0]){ cout << "!" << " " << L; return;}
else {
vec<int> v4;
for(int i = 0; i < v.size() / 2 + v.size() % 2; i++){
v4.push_back(v[i]);
}
rec(v4);
return;
}
}else {
if (L == v[0]) { cout << "!" << " " << v[1];}
else {
vec<int> v4;
for(int i = v.size() / 2 + v.size() % 2; i < v.size(); i++){
v4.push_back(v[i]);
}
rec(v4);
return;
}
}
}
void test_case(){
vector<int> v1 {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43
}, v2 {
47, 53, 59, 61, 67, 71, 73, 79
}, v3 {
83, 89, 97
};
ll L = 1;
for(auto i: v1){
L *= i;
}
cout << "? " << L << '\n';
cout.flush();
int n; cin >> n;
if (n){
rec(v1);
}else {
L = 1;
for (auto i: v2) {
L *= i;
}
cout << "? " << L << '\n';
cout.flush();
cin >> n;
if (n) {
rec(v2);
} else {
rec(v3);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t-->0){
test_case();
}
}
from functools import reduce
l, r, p = 0, 25, [*map(int, '2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97'.split())]
while r - l > 1:
m = (l + r) // 2
print('?', reduce(lambda x, y: x * y, p[l:m]))
if input() == '1':
r = m
else:
l = m
print('!', p[l])
[problem: 447021F]
- Идея: Ilya_Is2022
- Разработка: Ilya_Is2022
Во входных данных мы имеем остановки и для каждой из них расписание некоторого $$$P$$$-го автобуса. Тогда давайте заведем словарь $$$a$$$, в котором мы будем хранить расписание для каждой $$$i$$$-й остановки, гдк ключём будет являться название остановки, а значением — массив $$$a[i]$$$, который будет состоять из чисел, обозначающих значения расписания в минутах (для удобства использования данных в дальнейшем).
После преобразования в удобный вид использования входных данных нам нужно ответить на $$$t$$$ запросов, для которых ответом является нахождение ближайшего следующего рейса $$$P$$$-го автобуса для $$$t_i$$$ остановки в заданное время.
Очевидно, что из-за возможного большого количества данных для каждой из остановок, перебирать и сравнивать заданное время с значениями расписания для текущей $$$t_i$$$ остановки отнюдь не оптимально, тогда на помощь к нам приходит двоичный поиск!
Для того, чтобы реализовать быстрое нахождение ближайшего рейса $$$P$$$-го автобуса, нам потребуется для каждой заданной $$$i$$$-й остановки изначально отсортировать значения их расписаний. После чего, отвечая на $$$t_i$$$ запрос, мы можем реализовать поиск ближайшего следующего рейса в массиве $$$a_{t_i}$$$ при помощи двоичного поиска, а именно применив алгоритм бинпоиске по массиву upper_bound, который будет возвращать ссылку на значение в минутах нужного нам рейса $$$P$$$-го маршрута. В случае, если значение полученного результата принадлежит $$$a_{t_i}$$$, тогда останется вывести модуль разности между заданным и полученным временем. В противном случае вывести :(.
Итоговая асимптотика решения: $$$\mathcal{O}(n \cdot q \cdot log \cdot q + t \cdot log \cdot q)$$$
#include <bits/stdc++.h>
//#include "testlib.h"
using namespace std;
#define ll long long
#define vec vector
const ll INF = 1e9 + 7;
const ll NOT_INF = 1e9 + 7;
const string YES = "YES";
const string NO = "NO";
void test_case(){
ll n;
cin >> n;
map<string, vec<ll>> a;
ll p = (ll)pow(10, 5);
for(int i = 0; i < n; i++){
string name; ll q;
cin >> name >> q;
while(q--){
ll h, m;
cin >> h >> m;
a[name].push_back(h * p + m);
}
}
for(auto &i: a){
sort(i.second.begin(), i.second.end());
}
// for(auto &i: a){
// cout << i.first << " ! ost\n";
// for(auto j: i.second){
// cout << "Schedule: " << j.h << " h. " << j.m << " m.\n";
// }
// }
int t; cin >> t;
while(t-->0){
string name; ll h, w;
cin >> name >> h >> w;
auto mx = upper_bound(a[name].begin(), a[name].end(), h * p + w);
if (mx != a[name].end()){
// cout << *mx << ' ' <<h * p + w<< '\n';
cout << abs(*mx - (h * p + w)) << '\n';
}else
cout << ":(" << '\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test_c = 1;
//cin >> test_c ;
while(test_c-->0){
test_case();
}
}
[problem: 447021G]
- Идея: Ilya_Is2022
- Разработка: Ilya_Is2022
Первое, что требовалось понять — это удобный принцип рассмотрения станций. Не сложно было догадаться, что одним из возможных вариантов оптимальных решений являлось движение от станции с наименьшим значением загруженности к наибольшей. Таким образом, достаточно было отсортировать массив $$$a$$$ для проведения последующих действий... (Также отметим, что в начальный момент времени {по условию} сумма степеней возмущенности равна $$$0$$$)
Далее, для полного решения задачи, необходимо иметь решения ее подзадач. Заведем для этих целей массив $$$dp$$$, в котором мы будем хранить наименьшее значение возмущенности Ильи после посещения $$$i$$$-й станции метрополитена. Также введём обозначение:
Разберём ситуацию для $$$n\ =\ 1$$$, тогда совсем не сложно осознать, что Илья посетит только одну станцию и соответственно степень возмущённости будет равна единице. Тогда наименьшая сумма степеней будет равняться единице. ($$$dp[1] = 1$$$)
Разберём ситуацию для $$$n\ =\ 2$$$, тогда мы рассмотрим два случая изменения степени возмущённости Ильи, а именно:
- Если модуль разности значений загруженности станций $$$a_1$$$ и $$$a_2$$$ не больше, чем значение параметра $$$k$$$ ($$$|a_1 - a_2| \le k $$$), то после посещения данных пунктов метрополитена суммарная степень возмущённости для этих станций будет равна единице. Тогда наименьшая сумма степеней возмущённости будет равна единице. ($$$dp[2] = 1$$$)
- В противном случае для каждой из станций степень возмущённости будет равна единице. Тогда после посещения двух станций степень возмущённости будет равняться двум. ($$$dp[2] = 2$$$)
Разберём ситуацию для $$$n\ =\ 3$$$, тогда мы рассмотрим три случая изменения степени возмущения Ильи, а именно:
- Если разность максимального и минимального значения отрезка $$$b\ =\ [a_1, a_2, a_3]$$$ не превышает значения параметра $$$d$$$ ($$$b_{max} - b_{min} \le d$$$), то после посещения трёх пунктов метрополитена суммарная степень возмущённости этих станций будет равна $$$1$$$. Тогда наименьшая сумма степеней будет равняться единице. ($$$dp[3] = 1$$$)
- Иначе, если модуль разности значений загруженности станций $$$a_2$$$ и $$$a_3$$$ не больше, чем значение параметра $$$k$$$ ($$$|a_2 - a_3| \le k $$$), то после посещения данных пунктов метрополитена суммарная степень возмущённости этих станций будет равно единице. Тогда наименьшая сумма степеней будет равняться двум ($$$dp[3] = 2 $$$), так как получится следующее разбиение на комбинации:
- В противном случае значение степени возмущённости увеличится на единицу и будет равняться $$$dp[3] = dp[2] + 1$$$. (Так как мы рассматриваем еще и значение $$$dp[2]$$$, которое получилось при рассмотрении первых двух элементов отсортированного массива $$$a$$$, исходя из предыдущего пункта). Тогда мы получаем следующую комбинацию:
Для решения каждой последующей подзадачи, для которых $$$n > 3$$$, мы спокойно можем воспользоваться значениями $$$dp[1],\ dp[2],\ dp[3]$$$ по умолчанию. Таким образом, для определения наименьшей суммы степеней возмущённости каждой последующей $$$i$$$-й подзадачи, нам нужно рассматривать следующие эффективные комбинации получения наименьшей суммы степеней:
Если разность максимального и минимального значения отрезка $$$b\ =\ [a_{i - 2}, a_{i - 1}, a_i]$$$ (посещение трех последних станций) не превышает значения параметра $$$d$$$ ($$$b_{max} - b_{min} \le d$$$), тогда рассмотрим две последние посещённые станции:
-
- Если модуль разности значений загруженности станций $$$a_{i - 1}$$$ и $$$a_{i}$$$ не больше, чем значение параметра $$$k$$$ ($$$|a_{i - 1} - a_i| \le k $$$), то значение степени возмущённости для этих пунктов метрополитена будет равна единице, а наименьшая сумма степеней для помещенных станций будет равна $$$dp[i] = min(dp[i - 2] + 1, dp[i - 3] + 1)$$$.
-
- В противном случае для этих пунктов метрополитена степень возмущённости будет равняться единице, а наименьшая сумма степеней для посещённых станций будет равна $$$dp[i] = dp[i - 3] + 1$$$ (Изменять значение степени возмущённости для каждой станции по отдельности для данного случая не имеет смысла). Получается следующее комбинирование станций при измерении степеней:
- Иначе, если модуль разности значений загруженности станций $$$a_{i - 1}$$$ и $$$a_{i - 2}$$$ не больше, чем значение параметра $$$k$$$ ($$$|a_{i - 1} - a_{i - 2}| \le k $$$), то для этих пунктов метрополитена суммарная степень возмущённости будет равна единице, а наименьшее значение суммы степеней для текущей подзадачи равно $$$dp[i] = dp[i - 2] + 1$$$. Таким образом получаем следующее комбинирование:
- В противном случае мы рассматриваем $$$i$$$-ю станцию отдельно и значение степени возмущённости для неё будет равно единственное, следовательно наименьшее значение суммы степеней для текущей подзадачи равно $$$dp[i] = dp[i - 1] + 1$$$. Таким образом получаем следующее комбинирование:
После рассмотрения конечной посещённой станции итоговым ответом будет являться значение $$$dp[n]$$$.
Итоговая асимптотика решения: $$$\mathcal{O}(t \cdot (n \cdot log \cdot n + n))$$$
#include <bits/stdc++.h>
//#include "testlib.h"
using namespace std;
#define ll long long
#define vec vector
const ll INF = 1e9 + 7;
const string YES = "YES";
const string NO = "NO";
void test_case(int argc, char *argv[]){
ll n, k, d; cin >> n >> k >> d;
vec<ll> a(n);
vec<ll> dp(n);
cin >> a[0];
for(int i = 1; i < n; i++){
cin >> a[i];
}
sort(a.begin(), a.end());
dp[0] = 1;
if (n >= 2){
if (abs(a[0] - a[1]) <= d){
dp[1] = 1;
}else {
dp[1] = 2;
}
}
if (n >= 3){
if (abs(max(a[0], max(a[1], a[2])) - min(a[0], min(a[1], a[2]))) <= k){
dp[2] = 1;
}else if (abs(a[1] - a[2]) <= d){
dp[2] = 2;
}else {
dp[2] = dp[1] + 1;
}
}
if (n > 3){
for(int i = 3; i < n; i++){
if (max(a[i], max(a[i - 1], a[i - 2])) - min(a[i], min(a[i - 1], a[i - 2])) <= k){
if (abs(a[i - 1] - a[i]) <= d) {
dp[i] = min(dp[i - 2] + 1, dp[i - 3] + 1);
}else {
dp[i] = dp[i - 3] + 1;
}
}else if (abs(a[i - 1] - a[i]) <= d) {
dp[i] = dp[i - 2] + 1;
}else {
dp[i] = dp[i - 1] + 1;
}
}
}
cout << dp[n - 1] << '\n';
}
int main(int argc, char *argv[]){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1; cin >> t;
while(t-->0){
test_case(argc, argv);
}
}
[problem: 447021H]
Более формально, в задаче необходимо найти все натуральные числа $$$n = 2 \times k^2 + 1$$$, где $$$k$$$ — натуральное число, и $$$n$$$ является палиндромом. Можно предположить, что таких чисел существует не очень много, и попробовать запустить поиск таких чисел.
Перебор числа $$$n$$$ будет выполняться слишком долго, так как $$$n$$$ может достигать $$$10^{18}$$$. Нужно придумать способ оптимальнее. Заметим, что так как $$$n \le 10^{18}$$$, то $$$k \le \sqrt{\cfrac{10^{18} - 1}{2}}$$$, то есть $$$k$$$ не превосходит $$$10^9$$$. Значит, можно перебирать число $$$k$$$ вместо $$$n$$$, вычислять $$$n$$$ и проверять его, является ли оно палиндромом.
Асимптотика перебора: $$$\mathcal{O}(\sqrt{N} \log{N})$$$, где $$$N$$$ — максимально возможное $$$n$$$, в нашем случае $$$N = 10^{18}$$$. (Будем считать, что проверка, является ли число палиндромом, выполняется за его длину, то есть за $$$\mathcal{O}(\log{N})$$$)
Может показаться, что этот перебор будет выполняться довольно долго, но на практике достаточно от 40 секунд до 15 минут, в зависимости от языка программирования и реализации алгоритма.
В результате перебора можно понять, что подходящих под условие задачи чисел всего 21: $$$3$$$, $$$9$$$, $$$33$$$, $$$99$$$, $$$393$$$, $$$969$$$, $$$38211283$$$, $$$91044019$$$, $$$95855859$$$, $$$357727753$$$, $$$10284648201$$$, $$$91637373619$$$, $$$93323232339$$$, $$$100083380001$$$, $$$3119172719113$$$, $$$100540454045001$$$, $$$302791646197203$$$, $$$982885848588289$$$, $$$9188622002268819$$$, $$$150434127721434051$$$, $$$355553961169355553$$$.
Теперь мы знаем все подходящие числа и то, что их не так много. Значит, мы можем записать все эти числа в виде массива в коде программы и потом с ними работать, не пытаясь их посчитать при каждом запуске.
На запросы можно отвечать разными способами. Можно искать с помощью бинпоиска индекс минимального числа, которое не меньше $$$l$$$ и индекс минимального числа, которое больше $$$r$$$. И тогда ответ — это разность этих индексов. Тогда асимптотика решения будет $$$\mathcal{O}(t \log{B})$$$, где $$$B$$$ — это количество подходящих чисел, $$$B = 21$$$.
Но можно поступить и проще, так как у нас всего 21 число, для каждого запроса можно перебирать каждое число и проверять, лежит ли оно в необходимом диапазоне. Тогда асимптотика решения будет $$$\mathcal{O}(tB)$$$, где $$$B$$$ — это количество подходящих чисел, $$$B = 21$$$.
Вероятно, должны существовать способы оптимизировать перебор чисел, чтобы можно было перебирать их прямо в решении, перед ответом на запросы, или даже найти их все без перебора, но задача предполагает решение описанным способом.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll max_n = 1'000'000'000'000'000'000ll;
bool is_palindrome(ll x) {
ll y = 0;
for (ll t = x; t > 0; t /= 10) {
y = 10 * y + t % 10;
}
return x == y;
}
int main() {
for (ll x = 1, d = 3; 2 * x + 1 <= max_n; x += d, d += 2) {
ll n = 2 * x + 1;
if (is_palindrome(n)) {
cout << n << "\n";
}
}
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> nums = {
3ll, 9ll, 33ll, 99ll, 393ll, 969ll, 38211283ll, 91044019ll, 95855859ll,
357727753ll, 10284648201ll, 91637373619ll, 93323232339ll, 100083380001ll,
3119172719113ll, 100540454045001ll, 302791646197203ll, 982885848588289ll,
9188622002268819ll, 150434127721434051ll, 355553961169355553ll
};
void solve() {
ll l, r, ans = 0;
cin >> l >> r;
for (ll x: nums) {
if (l <= x && x <= r) {
ans++;
}
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll t = 1;
cin >> t;
for (ll i = 0; i < t; ++i) {
solve();
}
}
For D2, in testcase: $$$a=0, b=1,k=1$$$, or testcase $$$a=1, b=0,k=1$$$ your model solution is wrong. Note that in one of these cases, your model solution assumes it can put a leading zero in a natural number. But this is wrong.
One way of noticing this, is trying to plug these cases into the solution of D1 (note that any solution with these low values of a,b,k would fit in numbers $$$\leq 10000$$$.
The notification said that the inverse numbers can start from zero...
Therefore, one of the models will output YES, and the other NO...
Yes, the reverse number can contain leading zeroes. But the decimal notation of natural numbers cannot contain leading zeroes, so that would mean reverse numbers, can't contain a 0 at the end.
в D2 какой ответ на 0 1 1? решение жюри в тесте 3 ожидает YES, но нетрудно показать, что получается NO
Amazing problems. Waiting for another round