Всем привет! Сегодня хочу сделать разбор на прошедший контест. Если какая-то часть из разбора покажется непонятной, можете смотреть код для полной ясности)
Полное решение:
Давайте заметим, что в конце нам придется выбрать одного кандидата из списка лузеров и произвести матч между этим кандидатом, и уже готовым кандидатом, который до этого момента выиграл все свои матчи.
А до этого выбора, матчей было как минимум 2*(n-2), дальше мы произведем всего 2 матчей, а именно, как я уже сказал выберем одного кандидата из койки лузеров, и проведем финальный матч.
Поэтому ответ 2*(n-2)+2 => 2n-2.
Сложность: O(1)
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
void bruh() {
ll n; cin >> n;
ll bs = 0;
cout << 2*n-2 << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
//4+3z>9+2z
ll t; cin >> t;
// cin >> t;
while (t--) {
bruh();
}
}
Давайте заметим, что пока у нас есть хотя бы две клетки свободные, то мы всегда можем сделать так, чтобы ответ существовал. Но если у нас только, одна свободная клетка, то ответа не может быть.
Поэтому если n*n-1==k, то ответ “No”. Иначе можно всегда поставить самые первые k клеток знаком ‘U’, а другие уже с помощью цикла перенастроить, чтобы ответ существовал.
Выводим нашу матрицу как ответ.
Сложность: O(n*k).
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
void bruh() {
ll n,k; cin >> n >> k;
vector<vector<char>> a(n, vector<char>(n, '.'));
ll cnt = 0;
for (ll i = 0;i<n;i++){
for (ll j = 0;j<n;j++){
if(a[i][j]=='.' && cnt<k){
a[i][j] = 'U';
cnt++;
}
}
}
if(k==n*n-1){
cout << "NO" << endl;
}else{
cout << "YES" << endl;
for (ll i = 0;i<n;i++){
for (ll j = 0;j<n;j++){
if(a[i][j]!='U'){
if(j-1>=0 && a[i][j-1]!='U'){
a[i][j] = 'L';
}else if(j+1<n && a[i][j+1]!='U'){
a[i][j] = 'R';
} else if(i-1>=0 && a[i-1][j]!='U'){
a[i][j] = 'U';
}else if(i+1<n && a[i+1][j]!='U'){
a[i][j] = 'D';
}
}
}
}
for (ll i = 0;i<n;i++){
for (ll j = 0;j<n;j++){
cout << a[i][j] << "";
}cout << endl;
}
}}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
//4+3z>9+2z
ll t; cin >> t;
// cin >> t;
while (t--) {
bruh();
}
}
Какое самое наивное решение? Это перебор всех пар, однако ясно, что он вряд ли сработает. Тогда давайте оптимизируем этот перебор.
Давайте попробуем просимулировать перебор, пусть n = 6.
1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6
В итоге мы сделаем O(n*n-(n*(n+1)/2)) запросов.
Давайте попробуем вместо того, чтобы делать полный перебор, рассматривать числа диапазонно. Заметим, что 1 5 может покрыть 5 1, однако для этого диапазон должен быть не менее 2, потому для самой 5 нужно еще покрыть пару 5 6. Или пара 2 4 может быть покрыта парой 4 2, однако длина должна быть не менее 4, потому что самой 4 нужно покрыть 5 и 6 и 1.
Главный смысл в том, что разбивая числа на диапазоны, мы гарантируем, что когда то все пары покроются, но для этого нужно определить минимальную длину диапазона.
Тут можно заметить, что эта длина равна половине отрезка, т.е n/2.
Пусть x*n>=(n*(n-1)/2). x>=(n*(n-1)/2) / n x>=(n-1)/2.
Возьмем n/2 для полной уверенности.
Теперь давайте докажем, что пары покроют друг друга.
Пусть ln = n/2. Тогда давайте определим для каждого числа диапазоны длины ln(6/2=3)
[1 2 1 3 1 4] [2 3 2 4 2 5] [3 4 3 5 3 6] [4 5 4 6 4 1(7%6=1)] [ 5 6 5 1 5 2] [6 1 6 2 6 3].
Как можем видеть всего пар = 18(может входить и не различные пары). Это более чем покроет все 15 пар.
Однако потратим мы N/2*N => N*N/2 операции/запросов в худшем случае, если адаптируем под нашу задачу это N*N/a приблизительно, как раз то, что ждала от нас задача.
Сложность O(n/2*n).
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
ll ask(ll a, ll b){
cout << a << " " << b << endl;
ll x; cin >> x;
return x;
}
void bruh(){
ll n; cin >> n;
vector<ll> a;
for (ll i = 1;i<=n;i++){
a.pb(i);
}
ll ans1 = -1; ll ans2 = -1;
bool opt = 0;
for (ll f = 1;f<=n/2;f++){
if(opt){
break;
}
for (ll i = 1;i<=n;i++){
ll bs = (i+f>n? (i+f)-n: i+f);
ll x = ask(i,bs);
if(x==1){
ans1 = i; ans2 = bs;
opt = 1;
break;
}
if(x==-1){
opt = 1;
break;
}
}
}
cout.flush();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
// cin >> t;
while (t--) {
bruh();
}
}
