Jadvalda sonlarni ketma-ket joylashtirilsa, bir elementning ikki qo'shisi aniq bir biridan farqli bo'ladi (o'zi juft bo'lsa qo'shi toq, o'zi toq bo'lsa qo'shnisi juft bo'ladi). Misol tariqasida quyidagi joylashtirish usulini ko'rishingiz mumkin: 1,2,3,4,5,6… . Bu misoldan ko'rinib turibdiki ikki yon qo'shnini farqli qilib joylashtirish muammo emas.
Ammo jadvaldagi elementning yuqoridagi va pastdagi qo'shnilarini joylashtirishda biroz muammoga duch kelishimiz mumkin. Bu holda N soni juft son bo'lsa boshqacha usulda, toq son bo'lsa boshqacha usulda joylashtirish kerak.
N=juft holati uchun:
-----→
←-----
-----→
←-----
…
N=toq holati uchun:
-----→
-----→
-----→
-----→
….
Shunda sonlarda aniq hamma qo'shnilari bir biridan farqli usulda joylashadi.
Masala yakunida shuni anglab yetish mumkin, N ning har qanday qiymatida masala shartini qanoatlantirish mumkin. Demak masala doim YES qiymay qaytaradi.
B. Play Off
Futbol bo'yicha o'tkaziladigan chempionatlarning aksariyatida jamoalar keyingi bosqichga chiqishi uchun 2 ta o'yin o'ynashadi. O'yinlar dastlab bir jamoning uyida, so'ng esa ikkinchi jamoaning uyida bo'lib o'tadi. Hammasi oddiy agar qaysidir jamoa 2 o'yin hisobida yaqqol ustunlikka erishgan bo'lsa albatta g'alaba qozonadi. Ammo agar durrang qayt etilsa qaysi jamoa raqib uyida ko'proq gol urgan bo'lsa o'sha jamoa g'alaba qozonadi. Agar urgan gollari bir hil bo'lsa u holda o'yin qo'shimcha daqiqalarda davom etadi.
Bu holatda siz jamoalarning urgan gollari yig'indisini hisoblashingiz va g'alaba durrang uchun qancha gol yetmayotganini hisoblashingiz kerak bo'ladi. Durrang uchun yetmagan gollarni qo'shib qaysi jamoa mehmonda kop gol urganini aniqlashingiz kerak. Shunga qarab jamoaga yana bitta go'l qo'shiladi, yoki qo'shilmaydi.
s=input().split();
t=input()
a,b=map(int,s[1].split('-'))
x,y=map(int,s[3][1:-1].split('-'))
if t==s[0]:
if a+x<=b+y:
if x>b:
print(b+y-a-x)
else:
print(b+y-a-x+1)
else:
print(0)
else:
if a+x>=b+y:
k=a+x-b-y
if x>=k+b:
k+=1
print(k)
else:
print(0)C. Shaxboz va 8-mart
Masala bir qarashda oddiy matematik amallar yoki konteynerlarning qandaydir holarlarini eslatishi mumkin. Ammo masala “Binar qidiruv” algoritmi yordamida ishlanadi.
def solve():
n = int(input())
a = []
b = []
t = []
for _ in range(n):
ai, bi, ti = map(int, input().split())
a.append(ai)
b.append(bi)
t.append(ti)
all_val, sovga= map(int, input().split())
l = -1
r = 10**12
while r > l + 1:
m = (l + r) // 2
res = 0
v = []
for i in range(n):
x = (m - t[i] - b[i]) // a[i]
if x > 0:
v.append(x)
v.sort(reverse=True)
for i in range(min(len(v), all_val)):
res += v[i]
if res >= sovga:
r = m
else:
l = m
print(r)
solve()Shashka o'yini masalasi “brute forse” usulida yechiladi. Bunda siz oq donalarning barcha holatlarini ko'rib chiqishingiz kerak bo'ladi. Shaxmat donasi bir joyda aylanib qolmasligi uchun har bir urilgan donani eslab qolishingiz kerak. Masalaning qiyinchiligi esa shaxmat donasi bir marta bosib o'tgan katakchasidan yana o'tishi mumkin va bu holatda yangi yo'nalishda harakatlanadi.
#include <bits/stdc++.h>
#define int long long
const int mod=1e9+7;
const int N=2e5+5;
const int inf=1e18;
using namespace std;
int n, res=0, c=0;
vector<vector<char>> g;
void dfs( int x, int y, vector<vector<bool>> vis, int cnt ){
c++;
if ( min(x,y)<1 || max(x,y)>n ){
res=max(res,cnt);
return;
}
if ( g[x+1][y+1]=='&' && !vis[x+1][y+1] && max(x+2,y+2)<=n && g[x+2][y+2]=='#' ){
vis[x+1][y+1]=1;
res=max(res,cnt+1);
dfs(x+2,y+2,vis,cnt+1);
vis[x+1][y+1]=0;
}
if ( g[x+1][y-1]=='&' && !vis[x+1][y-1] && x+2<=n && y-2>=1 && g[x+2][y-2]=='#' ){
vis[x+1][y-1]=1;
res=max(res,cnt+1);
dfs(x+2,y-2,vis,cnt+1);
vis[x+1][y-1]=0;
}
if ( g[x-1][y-1]=='&' && !vis[x-1][y-1] && max(x-2,y-2)>=1 && g[x-2][y-2]=='#' ){
vis[x-1][y-1]=1;
res=max(res,cnt+1);
dfs(x-2,y-2,vis,cnt+1);
vis[x-1][y-1]=0;
}
if ( g[x-1][y+1]=='&' && !vis[x-1][y+1] && x-2>=1 && y+2<=n && g[x-2][y+2]=='#' ){
vis[x-1][y+1]=1;
res=max(res,cnt+1);
dfs(x-2,y+2,vis,cnt+1);
vis[x-1][y+1]=0;
}
}
void solve(){
n=8;
g=vector<vector<char>>(n+5,vector<char>(n+5,'.'));
vector<pair<int,int>> vc;
for ( int i=1; i<=n; i++ ){
for ( int j=1; j<=n; j++ ){
cin >> g[i][j];
if ( g[i][j]=='@' ){
vc.push_back({i,j});
}
}
}
res=0;
for ( auto [x,y]:vc ){
vector<vector<bool>> vis(n+5, vector<bool>(n+5));
g[x][y]='#';
dfs(x,y,vis,0);
g[x][y]='@';
}
cout << res;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int t=1;
for ( int test=1; test<=t; test++ ){
solve();
if ( test!=t ) cout << '\n';
}
}D masala kabi bu masalani ham rekursiya, dinamik dasturlash va grafning ayrim funksiyalarini ishlatgan holda, har bir holatni korib chiqish yo'li bilan ishlashimiz mumkin bo'ladi. Har bir tekshiradigan katakchadagi harfni berilgan so'zning mos harflari bilan to'g'ri kelishini tekshirib boramiz. Agar qaysidir harf mos kelmasa, u holda shu joyda harakatni to'xtatib boshqa yo'nalishda harakatni davom ettiramiz. Holatlar sonini keskin kamaytirish uchun har bir katakchadan so'ng hosib bo'lgan qism satrni dinamik usulda saqlab ketishimiz kerak bo'ladi.
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define int long long
#define fs first
#define ss second
using namespace std;
string s;
vector <vector <char>> g;
vector <vector <int>> used;
int res = 0, n;
void rec(int x, int y, int cnt){
if (res) return;
if (cnt == n){
res = 1;
return;
}
if (x > 5 || y > 5 || x < 1 || y < 1 || used[x][y]) return;
if (s[cnt] != g[x][y]) return;
used[x][y] = 1;
rec(x + 1, y, cnt + 1);
rec(x - 1, y, cnt + 1);
rec(x, y + 1, cnt + 1);
rec(x, y - 1, cnt + 1);
used[x][y] = 0;
}
void solve(){
g.assign(6, vector <char>(6, '#'));
used.assign(6, vector <int>(6, 0));
for (int i = 1; i < 6; ++ i)
for (int j = 1; j < 6; ++ j)
cin >> g[i][j];
cin >> s;
n = s.size();
for (int i = 1; i < 6; ++ i)
for (int j = 1; j < 6; ++ j){
rec(i, j, 0);
}
cout << (res == 1 ? "Yes" : "No");
}
signed main(){
cin.tie(nullptr)->ios::sync_with_stdio(false);
solve();
}F. Ajoyib shakllar
Masalalar har doim ham to'liq yechimga ega bo'lmaydi, ba'zi contest va musobaqalarda yechimi qidirilayotgan masalalar ham qo'yiladi. Bunday turdagi masalar odatda aniq testlangan holatda bo'lishi kerak.
Ajoyib shakllar masalasini piksellar yordamida yechish g'oyasi ilgari surilishi mumkin. Ammo piksellar to'rtburchak shaklda bo'lib, ular yordamida aylanalarni aniq chizish imkonsiz. Ikkinchi yoli esa aylanalarni urinma tenglamasi yordamida bir biriga optimal urintish mumkin. Ammo bu holatda ham eng optimal holatni topish qiyin, chunki aylana va kvadratlardan hosil bo'lgan sohalar ichiga ham aylana va kvadratlar joylashtirilishi mumkin va bu masalani yana ham murakkablashtiradi.
Telegram kanalimizga obuna bo'ling