20 Olimpiada Informatyczna Juniorów OIJ - Omówienia / Kody
DOŁĄCZ do KONKURSU gdzie można ROZWIĄZYWAĆ zadania I etapu OLIMPIADY Informatycznej SZKÓŁ PODSTAWOWYCH: https://szkopul.edu.pl/c/oij-20/join/AUC8Q40QxiybVeDi3-AMHMB6/
1 Etap - Runda szkolna
Chwasty
Kod C++
#include "bits/stdc++.h"
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m; cin>>n>>m;
vector x(n);
for(int i=0; i<n; i++) cin>>x[i];
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
int c=0,k=0;
if(i-1>=0)
{
if(x[i-1][j]=='#') c++;
if(x[i-1][j]=='*') k++;
if(j-1>=0)
{
if(x[i-1][j-1]=='#') c++;
if(x[i-1][j-1]=='*') k++;
}
if(j+1<m)
{
if(x[i-1][j+1]=='#') c++;
if(x[i-1][j+1]=='*') k++;
}
}
if(x[i][j]=='#') c++;
if(x[i][j]=='*') k++;
if(j-1>=0)
{
if(x[i][j-1]=='#') c++;
if(x[i][j-1]=='*') k++;
}
if(j+1<m)
{
if(x[i][j+1]=='#') c++;
if(x[i][j+1]=='*') k++;
}
if(i+1<n)
{
if(x[i+1][j]=='#') c++;
if(x[i+1][j]=='*') k++;
if(j-1>=0)
{
if(x[i+1][j-1]=='#') c++;
if(x[i+1][j-1]=='*') k++;
}
if(j+1<m)
{
if(x[i+1][j+1]=='#') c++;
if(x[i+1][j+1]=='*') k++;
}
}
if(k>c) cout<<'*';
else if(c>k) cout<<'#';
else cout<<'.';
}
cout<<'\n';
}
}
Podzielność Iloczynu
Kod C++
#include "bits/stdc++.h"
using namespace std;
const int MOD=1e9+7;
const int MAXN=1e6+3;
#define ll long long
#define ff first
#define ss second
#define vi vector
#define pii pair<int,int>
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
bool par=false, trzy=false;
for(int i=0; i<n; i++)
{
int a; cin>>a;
if(a%2==0) par=true;
if(a%3==0) trzy=true;
}
if(par==true && trzy==true) cout<<"TAK"<<'\n';
else cout<<"NIE"<<'\n';
}
Kod Python
def main():
n=int(input())
tab=list(map(int,input().split()))
par=False
czy3=False
for i in range(n):
if tab[i]%2==0:
par=True
if tab[i]%3==0:
czy3=True
if czy3 and par:
print("TAK")
else:
print("NIE")
main()
Równanie
Kod C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, x, y;
int lewa_strona;
cin >> a >> b >> c;
cin >> x >> y;
lewa_strona = a*x + b*y;
if (lewa_strona == c)
cout << "TAK\n";
else
cout << "NIE\n";
return 0;
}
Kod Python
def main():
a, b, c = map(int, input().split())
x, y = map(int, input().split())
lewa_strona = a*x + b*y
if lewa_strona == c:
print("TAK")
else:
print("NIE")
main()
Zepsuta Klawiatura
Kod C++
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin>>s;
bool tab[s.size()];
for (int i=0;i<s.size();i++) tab[i]=0;
priority_queue<pair<int,int>> pq;
for (int i=0;i<s.size();i++){
if (s[i]=='d'){
if (pq.empty()==0){
tab[pq.top().second]=0;
pq.pop();
}
} else{
tab[i]=1;
pq.push({(s[i]-'a'),i});
}
}
for (int i=0;i<s.size();i++){
if (tab[i]==1 and s[i]!='d') cout<<s[i];
}
}
1 Etap - Runda zdalna
Kabelki
Kod C++
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
cin>>N;
vector<pair<int,int>> pary;
for (int i=0;i<N*2;i++){
int A,B;
cin>>A>>B;
pary.push_back({A,B});
}
sort(pary.begin(),pary.end());
for (int i=0;i<N*2;i+=2){
cout<<pary[i].first<<" "<<pary[i].second<<" "<<pary[i+1].first<<" "<<pary[i+1].second<<"\n";
}
}
Kod Python
N=int(input())
pary=[]
for _ in range(N*2):
A,B=map(int,input().split())
pary.append((A, B))
pary.sort()
for i in range(0,N*2,2):
p1=pary[i]
p2=pary[i+1]
print(p1[0],p1[1],p2[0],p2[1])
Kwadrat Magiczny
Kod C++
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
string aa[5];
for(int i=0;i<5;++i){ cin>>aa[i];
}
for(int i=0;i<5;++i){
for(int j=0;j<5;++j){
if(aa[i][j] == '?' && aa[j][i] == '?') {
aa[i][j] ='A';
}
else if(aa[i][j] == '?') {
aa[i][j] = aa[j][i]; continue;
}
if(aa[j][i] != '?' && aa[i][j] != aa[j][i]){
cout<<"NIE";
return 0; // lub exit(0);
}
}
}
for(int i=0;i<5;++i){
cout<<aa[i]<<"\n";
}
}Kod Python
def kwadratmagiczny():
aa = []
for i in range(5):
a = input(); aa.append(a)
for i in range (5):
for j in range (5):
if(aa[i][j] == '?' and aa[j][i] == '?'):
aa[i][j] = 'A'
elif(aa[i][j] == '?'):
aa[i][j] = aa[j][i]
if(aa[i][j] != aa[j][i] && aa[j][i] != '?'):
print("NIE"); return
for a in aa:
print(a)
kwadratmagiczny()
Parzysta suma
Kod C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c;
int reszta_a, reszta_b, reszta_c;
cin >> a >> b >> c;
reszta_a = a%2; reszta_b = b%2; reszta_c = c%2;
cout << "TAK" << '\n';
if ( reszta_a == reszta_b ) {
cout << a << ' ' << b << '\n';
return 0;
}
if ( reszta_a == reszta_c ) {
cout << a << ' ' << c << '\n';
return 0;
}
cout << b << ' ' << c << '\n';
return 0;
}
Kod Python
def main():
a, b, c = map(int, input().split())
reszta_a = a%2
reszta_b = b%2
reszta_c = c%2
print("TAK")
if reszta_a == reszta_b:
print(a, b)
return
if reszta_a == reszta_c:
print(a, c)
return
print(b, c)
return
main()
Równoległobok
Kod C++
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int ile_dol, ile_bok;
cin>>ile_dol>>ile_bok;
for(int i = 0; i < ile_dol; ++i){
for(int k = 0; k < i; ++k){
cout<<" ";
}
for(int k = 0; k < ile_bok; ++k){
cout<<"*";
}
cout<<'\n';
}
}Kod Python
def main():
ile_dol = int(input())
ile_bok = int(intput())
for i in range (ile_dol):
print(' ' * i + '*' * ile_bok)
main()
1 Etap - TEST
2 etap
Złośliwiec
Kod C++
#include <bits/stdc++.h>
using namespace std;
int main() {
long long ile_ciastek, minimum, maksimum, i;
cin >> ile_ciastek;
minimum = -1;
for (i=2; i<=ile_ciastek; ++i)
if ( (ile_ciastek%i) != 0) {
minimum = i;
break;
}
maksimum = ile_ciastek-1;
cout << minimum << " " << maksimum << "\n";
return 0;
}
Podzielność Iloczynu 2
Kod C++
#include "bits/stdc++.h"
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
ll n; cin>>n;
vector a(n+1);
ll trzy=0, dwa=0;
for(int i=0; i<n; i++) { cin>>a[i];
if(a[i]%3==0) trzy++;
if(a[i]%2==0) dwa++;
}
ll ans=min(dwa,trzy);
if(ans==dwa)
{
for(int i=0; i<n; i++)
{
if(a[i]%2==0) a[i]++;
}
}
else
{
for(int i=0; i<n; i++)
{
if(a[i]%3==0) a[i]++;
}
}
cout<<ans<<'\n';
for(int i=0; i<n; i++)
{
cout<<a[i]<<' ';
}
}Kod Python
def main():
N=int(input())
tab=list(map(int,input().split()))
ans1=0
ans2=0
for i in range(N):
if (tab[i]%2==0):
ans1+=1
if (tab[i]%3==0):
ans2+=1
if (ans1<=ans2):
print(ans1)
for i in range(N):
if (tab[i]%2==0):
print(tab[i]-1,end=" ")
else:
print(tab[i],end=" ")
else:
print(ans2)
for i in range(N):
if (tab[i]%3==0):
print(tab[i]-1,end=" ")
else:
print(tab[i],end=" ")
main()
Wycieczka Górska
Kod C++
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> polaczenia[1000][1000];
int tab[1000][1000];
vector<pair<int,int>> kierunki={{0,1},{0,-1},{1,0},{-1,0}};
int ile[1000][1000];
int dp[1000][1000];
void DFS(int i,int j){
int wynik=1;
for (pair<int,int> u:polaczenia[i][j]){
if (dp[u.first][u.second]>0){
wynik=max(wynik,dp[u.first][u.second]+1);
} else{
DFS(u.first,u.second);
wynik=max(wynik,dp[u.first][u.second]+1);
}
}
dp[i][j]=wynik;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N,M;
cin>>N>>M;
for (int i=0;i<N;i++){
for (int j=0;j<M;j++){ cin>>tab[i][j];
}
}
for (int i=0;i<N;i++){
for (int j=0;j<M;j++){
for (int k=0;k<4;k++){ int nowe_i=i+kierunki[k].first; int nowe_j=j+kierunki[k].second; if (nowe_i>=0 and nowe_i=0 and nowe_j<M){ if (tab[nowe_i][nowe_j]>tab[i][j]){
polaczenia[i][j].push_back({nowe_i,nowe_j});
ile[nowe_i][nowe_j]++;
}
}
}
}
}
int ans=0;
for (int i=0;i<N;i++){
for (int j=0;j<M;j++){
if (ile[i][j]==0){
DFS(i,j);
ans=max(ans,dp[i][j]);
}
}
}
cout<<ans<<"\n";
}
Spóźnienia
Kod C++
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using lld = long double;
#define FF first
#define SS second
#define v vector
#define pb push_back
#define ALL(a) a.begin(), a.end()
vdrzewo;
void ustaw(ll w, ll m_pocz, ll m_kon, ll p_pocz, ll val){
if(m_kon < p_pocz || p_pocz < m_pocz) return;
if(m_pocz == m_kon && m_pocz == p_pocz) {
drzewo[w] = val;
return;
}
ll mid = (m_pocz + m_kon) /2;
ustaw(w<<1, m_pocz, mid, p_pocz, val);
ustaw((w<<1)+1, mid+1, m_kon, p_pocz, val);
drzewo[w] = max(drzewo[w<<1], drzewo[(w<<1)+1]);
}
ll pyt(ll w, ll m_pocz, ll m_kon, ll p_pocz, ll p_kon){
if(m_kon < p_pocz || p_kon < m_pocz) return 0;
if(p_pocz <= m_pocz && m_kon <= p_kon){
return drzewo[w];
}
ll mid = (m_pocz + m_kon) /2;
return max( pyt(w<<1, m_pocz, mid, p_pocz, p_kon),
pyt((w<<1)+1, mid+1, m_kon, p_pocz, p_kon)); } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); ll ile; cin>>ile;
vaa(ile * 2);
vczasy(ile * 2);
ll wielk = 1;
for(;wielk < ile*2;wielk <<= 1){}
drzewo.resize(wielk * 2, 0);
for(ll i=0;i<ile;i++){ cin>>aa[i];
aa[i+ile] = aa[i];
}
for(ll i=0;i<ile;i++){ cin>>czasy[i];
czasy[i+ile] = czasy[i];
}
ll dodaj = 0;
for(ll i=ile*2 - 1;i>=0;i--){
dodaj += aa[i];
ustaw(1, 1, wielk, i+1, czasy[i] + dodaj);
}
ll odejmij = 0;
stackans;
for(ll i=ile*2-1;i>=ile;i--){
ll a = pyt(1, 1, wielk, i - ile + 2, i+1);
if(i == ile*2-1)
cout<<
3 etap
Podzielność Iloczynu III
Kod C++
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
#define pii pair<int,int>
#define pll pair<long, long>
#define mii map<int,int>
#define mll map
constexpr long long MAXN=1e6+3;
vector p;
vector pierwsze(MAXN+3);
void sito()
{
pierwsze[0]=true; pierwsze[1]=true;
for(ll i=2; i<=MAXN; i++)
{
if(pierwsze[i]) continue;
p.pb(i);
for(ll j=i*i; j<MAXN; j+=i) pierwsze[j]=true; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; ll k; cin>>n>>k;
ll kopia=k;
vector a(n);
for(int i=0; i<n; i++) cin>>a[i];
__int128 il=1;
for(int i=0; i<n; i++) il=(il*(__int128)(a[i]%k))%k;
if(il!=0)
{
cout<<0<<'\n';
for(auto x : a) cout<<x<<' ';
return 0;
}
sito();
vector<pair<ll,int>> dzielniki;
ll kop=k;
for(ll i : p)
{
if(i*i>kop) break;
int ile=0;
while(kop%i==0)
{
kop/=i;
ile++;
}
if(ile>0) dzielniki.pb({i,ile});
}
if(kop>1e12)
{
ll d1=-1,d2=-1,d3=-1;
for(int i=0; i<n; i++)
{
for(int j=-1; j<=1; j++)
{
if(a[i]+j<=0) continue; ll d=gcd(a[i]+j,kop); if(d>1)
{
if(d==d1 || d==d2 || d==d3) continue;
else if(d1==-1) d1=d;
else if(d2==-1) d2=d;
else if(d3==-1) d3=d;
}
}
}
vector ds;
if(d1!=-1) ds.pb(d1);
if(d2!=-1) ds.pb(d2);
if(d3!=-1) ds.pb(d3);
sort(all(ds));
for(ll x : ds)
{
int ile=0;
while(kop%x==0)
{
kop/=x;
ile++;
}
if(ile>0) dzielniki.pb({x,ile});
}
}
else if(kop>1) dzielniki.pb({kop,1});
ll mini=LLONG_MAX;
ll ktory=01;
ll pot=0;
for(auto [x,y] : dzielniki)
{
vector vp; //ile razy dzieli sie przez x, indeks
ll suma=0;
for(int i=0; i<n; i++) { ll aa=a[i]; int ile=0; while(aa%x==0) { aa/=x; ile++; } if(ile>0)
{
vp.pb({ile,i});
suma+=ile;
}
}
sort(all(vp));
int ruchy=0;
ll s=suma;
while(s>=y)
{
s-=vp.back().ff;
vp.pop_back();
ruchy++;
}
if(ruchy<mini)
{
mini=ruchy;
ktory=x;
pot=y;
}
}
cout<<mini<<'\n';
vector zmien(n);
vector vp;
ll suma=0;
for(int i=0; i<n; i++) { ll aa=a[i]; int ile=0; while(aa%ktory==0) { aa/=ktory; ile++; } if(ile>0)
{
vp.pb({ile,i});
suma+=ile;
}
}
sort(all(vp));
while(suma>=pot)
{
suma-=vp.back().ff;
zmien[vp.back().ss]=true;
vp.pop_back();
}
for(int i=0; i<n; i++)
{
if(zmien[i]) cout<<a[i]+1<<' ';
else cout<<a[i]<<' ';
}
}
Kabelki 2
Kod C++
#include <bits/stdc++.h>
using namespace std;
#define int long long
bool pasuje(int x1,int y1,int x2,int y2,int x3,int y3){
return ((x1-x3)*(y2-y3)-(x2-x3)*(y1-y3)==0);
}
pair<bool,pair<int,int>> przeciecie(int x11,int y11,int x12,int y12,int x21,int y21,int x22,int y22){
if (x11>x12){
swap(x11,x12);
swap(y11,y12);
}
if (x21>x22){
swap(x21,x22);
swap(y21,y22);
}
__int128 a1,a2,b1,b2,c1,c2;
a1=y11-y12;
a2=y21-y22;
b1=x12-x11;
b2=x22-x21;
c1=a1*x11+b1*y11;
c2=a2*x21+b2*y21;
if (a1*b2-a2*b1==0) return {0,{-1,-1}};
__int128 x,y;
x=(c1*b2-c2*b1)/(a1*b2-a2*b1);
y=(c1*a2-c2*a1)/(a2*b1-a1*b2);
if (x>=x11 and x<=x12 and x>=x21 and x<=x22) return {1,{x,y}};
return {0,{-1,-1}};
}
vector<pair<int,int>> punkty;
int cwiartka(pair<int,int> p){
int x=p.first;
int y=p.second;
if (x>=0 and y>=0) return 1;
if (x<=0 and y>=0) return 2;
if (x<=0 and y<=0) return 3;
return 4;
}
int komperator(pair<int,int> p1,pair<int,int> p2){
int x1=p1.first;
int x2=p2.first;
int y1=p1.second;
int y2=p2.second;
if (cwiartka(p1)!=cwiartka(p2)){
return cwiartka(p1)<cwiartka(p2); } return (x1*y2)-(x2*y1)>0;
}
vector<pair<int,int>> posortuj(int x,int y){
vector<pair<int,int>> posortowane=punkty;
for (int i=0;i<(int)posortowane.size();i++){
posortowane[i].first-=x;
posortowane[i].second-=y;
}
sort(posortowane.begin(),posortowane.end(),komperator);
for (int i=0;i<(int)posortowane.size();i++){
posortowane[i].first+=x;
posortowane[i].second+=y;
}
return posortowane;
}
pair<int,int> znajdz_odpowiednik(int x,int y){
vector<pair<int,int>> akt=posortuj(x,y);
return akt[(int)akt.size()/2];
}
bool porownaj(pair<int,int> a,pair<int,int> b){
if (a.second!=b.second) return a.second<=b.second;
return a.first<=b.first; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int N; cin>>N;
for (int i=0;i<N*2;i++){
pair<int,int> p;
cin>>p.first>>p.second;
punkty.push_back(p);
}
sort(punkty.begin(),punkty.end(),porownaj); // sortuje punkty PO WSPOLRZEDNYCH
pair<int,int> p1=punkty[(int)punkty.size()-1];
pair<int,int> p2=znajdz_odpowiednik(p1.first,p1.second);
vector<pair<int,int>> nowe;
for (int i=0;i<(int)punkty.size();i++){
if (punkty[i]!=p1 and punkty[i]!=p2) nowe.push_back(punkty[i]);
}
punkty=nowe;
pair<int,int> p3=punkty[(int)punkty.size()-1];
pair<int,int> p4=znajdz_odpowiednik(p3.first,p3.second);
pair<bool,pair<int,int>> gdzie=przeciecie(p1.first,p1.second,p2.first,p2.second,p3.first,p3.second,p4.first,p4.second);
if (gdzie.first==0){
cout<<"NIE\n";
return 0;
}
pair<int,int> punkt_przeciecia=gdzie.second;
punkty.push_back(p1);
punkty.push_back(p2);
punkty=posortuj(punkt_przeciecia.first,punkt_przeciecia.second);
for (int i=0;i<N;i++){
if (pasuje(punkty[i].first,punkty[i].second,punkty[i+N].first,punkty[i+N].second,punkt_przeciecia.first,punkt_przeciecia.second)==0){
cout<<"NIE\n";
return 0;
}
}
for (int i=0;i<N;i++){
cout<<punkty[i].first<<" "<<punkty[i].second<<" "<<punkty[i+N].first<<" "<<punkty[i+N].second<<"\n";
}
}
Prawie Hanoi
Kod C++
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FF first
#define SS second
#define v vector
#define ALL(a) a.begin(), a.end()
#define pb push_back
vdrzewo;
void ustaw(ll w, ll mp, ll mk, ll pp, ll pk){
if(mk < pp || pk < mp) return;
if(pp <= mp && mk <= pk){
drzewo[w] = 1;
return;
}
ll mid = (mp + mk) /2;
ustaw(w<<1, mp, mid, pp, pk);
ustaw((w<<1)+1, mid+1, mk, pp, pk);
drzewo[w] = drzewo[w<<1] + drzewo[(w<<1)+1];
}
ll ask(ll w, ll mp, ll mk, ll pp, ll pk){
if(mk < pp || pk < mp) return 0;
if(pp <= mp && mk <= pk){
return drzewo[w];
}
ll mid = (mp + mk)/2;
return ask(w<<1, mp, mid, pp, pk) + ask((w<<1)+1, mid+1, mk, pp, pk); } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); ll ile, trash; cin>>ile>>trash;
ll wielk = 1;
while(wielk < ile) wielk <<= 1;
drzewo.resize(wielk*2, 0);
vaa(ile);
for(ll i=0;i<ile;i++) cin>>aa[i];
v<tuple<ll, ll, ll>>ans;
reverse(ALL(aa));
for(ll i=0;i<ile;i++){ ll pom = ask(1, 1, wielk, 1, aa[i]); if(pom > 0){
ans.pb({3, 2, pom});
ans.pb({1, 3, 1});
ans.pb({2, 3, pom});
}
else{
ans.pb({1, 3, 1});
}
ustaw(1, 1, wielk, aa[i], aa[i]);
}
cout<<ans.size() + ile<<'\n';
for(auto [a, b, c] : ans) cout<<a<<' '<<b<<' '<<c<<"\n";
for(ll i=0;i<ile;i++) cout<<3<<' '<<2<<' '<<1<<"\n";
}
Tabelka
Kod C++
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N,A,B;
cin>>N>>A>>B;
string s;
cin>>s;
if (s[0]!='1' or s[N-1]!='1'){
cout<<"NIE\n";
return 0;
}
vector<vector<pair<pair<int,int>,int>>> wszystkie;
vector<pair<pair<int,int>,int>> mozliwe_wymiary={{{1,1},-1}};
wszystkie.push_back(mozliwe_wymiary);
vector<vector<pair<int,int>>> rozne(N+1);
for (int i=1;i<=B;i++){
for (int j=1;j<=A;j++){
rozne[i*j].push_back({i,j});
}
}
for (int i=2;i<=N;i++){
if (s[i-1]=='1'){
vector<pair<pair<int,int>,int>> nastepne;
for (int l=0;l<(int)rozne[i].size();l++){
int a=rozne[i][l].first;
int b=rozne[i][l].second;
for (int j=0;j<(int)mozliwe_wymiary.size();j++){
if (mozliwe_wymiary[j].first.first<=a and mozliwe_wymiary[j].first.second<=b){
nastepne.push_back({{a,b},j});
break;
}
}
}
if ((int)nastepne.size()==0){
cout<<"NIE\n";
return 0;
}
mozliwe_wymiary=nastepne;
wszystkie.push_back(mozliwe_wymiary);
}
}
cout<<"TAK\n";
vector<pair<int,int>> prostokaty;
pair<pair<int,int>,int> akt=wszystkie[(int)wszystkie.size()-1][0];
int indeks=(int)wszystkie.size()-1;
while (indeks>0){
prostokaty.push_back({akt.first.first,akt.first.second});
akt=wszystkie[indeks-1][akt.second];
indeks--;
}
int tab[A][B];
for (int i=0;i<A;i++){
for (int j=0;j<B;j++){
tab[i][j]=0;
}
}
tab[0][0]=1;
pair<int,int> last={1,1};
for (int l=(int)prostokaty.size()-1;l>=0;l--){
int a=prostokaty[l].first;
int b=prostokaty[l].second;
int ostatni=last.first*last.second;
ostatni++;
int koncowka=0;
if (last.first==a) koncowka=last.second;
for (int i=b-1;i>=koncowka;i--){
int koniec=0;
if (i<last.second) koniec=last.first; else koniec=0; for (int j=a-1;j>=koniec;j--){
if (tab[i][j]!=0) break;
tab[i][j]=ostatni;
ostatni++;
}
}
last=prostokaty[l];
}
for (int i=0;i<A;i++){
for (int j=0;j<B;j++){
cout<<tab[i][j]<<" ";
}
cout<<"\n";
}
}
Diody
Kod C++
#include <bits/stdc++.h>
using namespace std;
constexpr int BAZA = (1<<19); constexpr int INF = 1e9+7; int dp[BAZA*2]; int lazy[BAZA*2]; void bud() { for(int i = BAZA-1; i > 0; --i)
dp[i] = min(dp[i*2], dp[i*2+1]);
}
void dodaj(int a, int b, int c, int w = 1, int p = 1, int k = BAZA)
{
dp[w] += lazy[w];
if(w*2+1 < BAZA*2)
{
lazy[w*2] += lazy[w];
lazy[w*2+1] += lazy[w];
}
lazy[w] = 0;
if(k < a || p > b)
return;
if(a <= p && k <= b)
{
dp[w] += c;
if(w*2+1 < BAZA*2)
{
lazy[w*2] += c;
lazy[w*2+1] += c;
}
return;
}
dodaj(a, b, c, w*2, p, (p+k)/2);
dodaj(a, b, c, w*2+1, (p+k)/2+1, k);
dp[w] = min(dp[w*2], dp[w*2+1]);
return;
}
int mini(int a, int b, int w = 1, int p = 1, int k = BAZA)
{
dp[w] += lazy[w];
if(w*2+1 < BAZA*2)
{
lazy[w*2] += lazy[w];
lazy[w*2+1] += lazy[w];
}
lazy[w] = 0;
if(k < a || p > b)
return INF;
if(a <= p && k <= b)
return dp[w];
return min(mini(a, b, w*2, p, (p+k)/2), mini(a, b, w*2+1, (p+k)/2+1, k));
}
int znajdz0()
{
int w = 1;
while(w*2+1 < BAZA*2)
{
dp[w] += lazy[w];
if(w*2+1 < BAZA*2)
{
lazy[w*2] += lazy[w];
lazy[w*2+1] += lazy[w];
}
lazy[w] = 0;
if(dp[w*2] < dp[w*2+1])
w = w*2;
else
w = w*2+1;
}
return w-BAZA;
}
int main()
{
for(int i = 0; i < BAZA*2; ++i) dp[i] = INF; ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n;
vector op(n);
for(int &i: op)
cin >> i;
int zap = 0;
vector ilepot(n);
for(int i = 0; i < n; ++i)
{
ilepot[i] = max(0, op[i] - zap);
if(ilepot[i] == 0)
++zap;
dp[BAZA+i] = ilepot[i];
if(dp[BAZA+i] == 0)
dp[BAZA+i] = INF;
}
bud();
vector nnz(n);
int nz = n;
for(int i = n-1; i >= 0; --i)
{
nnz[i] = nz;
if(ilepot[i] != 0)
nz = i;
}
vector odp(n);
int zap0 = zap;
int z;
for(int i = n-1; i >= 0; --i)
{
if(ilepot[i] == 0)
{
odp[i] = zap0;
continue;
}
dodaj(nnz[i]+1, nnz[i]+1, -1);
while(mini(1, BAZA) <= 0)
{
z = znajdz0();
++zap;
dodaj(z+2, BAZA, -1);
dodaj(z+1, z+1, INF);
}
odp[i] = zap + 1;
}
for(auto i: odp)
cout << i << " ";
}
Karty
Kod C++
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
#define pii pair<int,int>
#define pll pair<long, long>
#define mii map<int,int>
#define mll map
vector sp;
vector czer, ziel;
ll d;
bool f(int x)
{
ll val=sp[x];
ll kop=d;
if(val<=kop) return true;
int akt=0;
for(int i=0; i<(int)czer.size(); i++)
{
while(akt=0) kop-=czer[i];
else break;
val-=(x-akt);
if(val<=kop) return true;
}
if(val<=kop) return true;
return false;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin>>n>>d;
for(int i=0; i<n; i++)
{
char c; ll a; cin>>c>>a;
if(c=='Z') ziel.pb(a);
else czer.pb(a);
}
sort(all(czer)); sort(all(ziel));
sp.resize(ziel.size()+1);
sp[0]=0;
for(int i=1; i<=ziel.size(); i++) sp[i]=sp[i-1]+ziel[i-1];
for(ll i=0; i<czer.size(); i++) czer[i]=max((ll)0,czer[i]-i);
int low=0, high=ziel.size();
while(low<high)
{
int mid=(low+high+1)/2;
if(f(mid)) low=mid;
else high=mid-1;
}
cout<<low<<'\n';
}
Kurka Bajtosia
Kod C++
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct line {
int l, r, ind;
bool operator<(const line &o) const { return l == o.l ? r > o.r : l < o.l; } line(int _a, int _b, int _ind = 0) { l = _a; r = _b; ind = _ind; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n;
vector dist(n);
vector turn(n-1);
for (int i = 0; i < n-1; i++) { cin >> dist[i] >> turn[i]; }
cin >> dist[n-1];
if (n == 1) {
cout << "4\n0 R\n1 R\n" << dist[0] << " R\n1\n"; return 0; } reverse(dist.begin(), dist.end()); reverse(turn.begin(), turn.end()); auto opp = [](char c) -> char { return c == 'R' ? 'L' : 'R'; };
vector<pair<int, char>> mov;
mov.pb({0, 'R'}); mov.pb({1, 'R'});
mov.pb({dist[0] + (turn[0] == 'L' ? 1 : -1), opp(turn[0])});
for (int i = 1; i < n-1; i++)
mov.pb({dist[i] + (turn[i]==turn[i-1] ? (turn[i]=='L' ? 2 : -2) : 0), opp(turn[i])});
mov.pb({dist[n-1] + (turn[n-2] == 'L' ? 1 : -1), 'R'});
mov.pb({1, 'R'});
vector<pair<int, int>> pos;
map<int, vector> ver, hor;
int x = 0, y = 0, dir = 0;
for (int i = 0; i < (int)mov.size(); i++) {
int px = x, py = y, len = mov[i].first;
if (dir == 0) y += len;
else if (dir == 1) x += len;
else if (dir == 2) y -= len;
else if (dir == 3) x -= len;
dir = (dir + (mov[i].second == 'R' ? 1 : 3)) % 4;
pos.pb({x, y});
if (dir%2) ver[x].pb({min(y, py), max(y, py), i});
else hor[y].pb({min(x, px), max(x, px), i});
}
for (auto* mp : {&hor, &ver}) for (auto& [k, v] : *mp) {
sort(v.begin(), v.end());
vector nv;
for (int i = 0; i < v.size();) {
auto [a, b, ind] = v[i];
for (; ++i < v.size();) { if (v[i].l > b) break;
b = max(b, v[i].r);
ind = max(ind, v[i].ind);
}
nv.pb({a, b, ind});
}
v.swap(nv);
}
vector<pair<int, int>> out = {};
for (int cur = 0; cur < mov.size()-1;) { int px = pos[cur].first, py = pos[cur].second; int cx = pos[cur+1].first, cy = pos[cur+1].second; out.pb({px, py}); auto &v = cur%2 ? ver[cx] : hor[cy]; int a = (cur%2 ? min(cy, py) : min(cx, px)); int b = (cur%2 ? max(cy, py) : max(cx, px)); cur = (--upper_bound(v.begin(), v.end(), line{a, b}))->ind;
}
out.pb(pos.back());
int pdir = 0;
cout << out.size() << "\n" << "0";
for (int i = 1; i < out.size(); i++) {
int dx = out[i].first - out[i-1].first;
int dy = out[i].second - out[i-1].second;
int ndir = (dx == 0) ? (dy <= 0 ? 1 : 3) : (dx >= 0 ? 0 : 2);
char ch = (i == 1) ? 'R' : ((ndir-pdir+4) % 4 == 1 ? 'R' : 'L');
cout << " " << ch << "\n" << abs(dx + dy);
pdir = ndir;
}
cout << "\n";
}