Задача А.
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,n,k,h,x,y,L,R,m,len,i,l,r,c[100],LL[100],ans,pos,ANSWER,st[100],val,kol;
inline int f(long long x)
{
len = 0;
while(x>0)
{
x/=10;
++len;
}
return len;
}
inline void solve()
{
cin>>a>>b>>n>>k;
x=y=0;
h = a;
while(h>0)
{
++x;
h/=10;
}
h = a + b * n;
while(h>0)
{
++y;
h/=10;
}
L = 0;
R = n;
for(i=x;i<=y;++i)
{
l = L;
r = R;
while(l+1<r)
{
m = (l+r)>>1;
if(f(a + m * b)>i) r=m; else l=m;
}
for(m=min(r+10,R);m>=max(L,r-10);--m)
if(f(a + m * b)==i)
{
c[i] = (m-L+1);
LL[i] = L;
L=m+1;
break;
}
if(L>R)break;
}
ans = 0;
for(i=x;i<=y;++i)
{
ans+=c[i] * i;
if(ans>=k)
{
ans-=c[i] * i;
k-=ans;
pos = k / i;
if(k % i == 0)
{
val = a + b * (LL[i] + pos - 1);
ANSWER=val % 10;
} else
{
val = a + b * (LL[i] + pos);
k%=i;
kol = 0;
while(val>0)
{
st[++kol] = val % 10;
val/=10;
}
reverse(st+1,st+kol+1);
ANSWER=st[k];
}
cout<<ANSWER<<'\n';
return;
}
}
cout<<-1<<'\n';
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}
Задача В.
#include<bits/stdc++.h>
using namespace std;
int m[] = {31,28,31,30,31,30,31,31,30,31,30,31};
pair<int,int> add[100],val[100][100],ans;
int t,i,j,pos,x,y,n;
string s;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>t;
m[1]+=t;
cin>>n;
add[0] = {1000,0};
add[1] = {5000,0};
add[2] = add[3] = {3000,0};
add[4] = {0,3};
for(i=1;i<=12;++i)
for(j=1;j<=m[i-1];++j)
{
val[j][i] = add[pos];
++pos;
if(pos==5) pos = 0;
}
for(i=1;i<=n;++i)
{
cin>>s;
x = (s[0] - '0') * 10 + (s[1] - '0');
y = (s[3] - '0') * 10 + (s[4] - '0');
ans.first+=val[x][y].first;
ans.second+=val[x][y].second;
}
cout<<ans.first<<' '<<ans.second<<'\n';
}
Задача С.
#include<bits/stdc++.h>
using namespace std;
int x,y,n,k,tt,i;
set<pair<int,int> > st;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
for(i=1;i<=n;++i)
{
cin>>x>>y;
if(x<0)tt=1,x=-x; else tt = 0;
k = __gcd(x,y);
x/=k;
y/=k;
if(tt)x=-x;
st.insert({x,y});
}
cout<<(int)st.size()<<'\n';
}
Задача D.
#include<bits/stdc++.h>
#define N 1111
#define left jdjdjs
#define right sjssjsjj
using namespace std;
int up[N][N],left[N][N],down[N][N],right[N][N],l[N],r[N],n,m,ptr,mink,ans,kol;
char c[N][N];
int s[N];
pair<int,int> times[N];
inline int prev(int x){
return x&(x-1);
}
inline int next(int x){
return (x<<1)-(x&(x-1));
}
inline void modify(int pos,int value){
for (;pos<N;pos=next(pos)) s[pos]+=value;
}
inline int get_sum(int l,int r){
if (l>r) return 0;
int k=0,p;
for (p=r;p>0;p=prev(p)) k+=s[p];
for (p=l-1;p>0;p=prev(p)) k-=s[p];
return k;
}
inline void input(){
scanf("%d%d%d\n",&n,&m,&mink);
mink=mink%4?mink/4+2:mink/4+1;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) scanf("%c",&c[i][j]);
scanf("\n");
}
}
inline void init(){
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
up[i][j]=c[i][j]=='#'?0:up[i-1][j]+1;
left[i][j]=c[i][j]=='#'?0:left[i][j-1]+1;
}
for (int i=n;i>=1;i--)
for (int j=m;j>=1;j--){
down[i][j]=c[i][j]=='#'?0:down[i+1][j]+1;
right[i][j]=c[i][j]=='#'?0:right[i][j+1]+1;
}
}
inline void upd_ans(){
memset(s,0,sizeof(s));
kol=0;
for (int i=1;i<=ptr;i++){
if (l[i]>=mink){
modify(i,1);
times[++kol]=make_pair(l[i]+i-1,i);
}
}
sort(times+1,times+kol+1);
int f=1;
for (int i=1;i<=ptr;i++){
ans+=get_sum(i-r[i]+1,i-mink+1);
while (times[f].first==i && f<=kol){
modify(times[f].second,-1);
++f;
}
}
}
int main(){
input();
init();
for (int I=1;I<=n;I++){
ptr=0;
for (int i=I,j=1;i<=n && j<=m;i++,j++){
l[++ptr]=min(right[i][j],down[i][j]);
r[ptr]=min(left[i][j],up[i][j]);
}
upd_ans();
}
for (int I=2;I<=m;I++){
ptr=0;
for (int i=1,j=I;i<=n && j<=m;i++,j++){
l[++ptr]=min(right[i][j],down[i][j]);
r[ptr]=min(left[i][j],up[i][j]);
}
upd_ans();
}
printf("%d",ans);
}
Задача Е.
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <ctime>
using namespace std;
struct query {
int parent;
int color;
int index;
query(int p, int c, int i):
parent(p), color(c), index(i) {}
bool operator < (const query& other) const {
if (parent != other.parent)
return parent < other.parent;
return color < other.color;
}
};
void solve() {
int N, M, K;
scanf("%d%d%d", &N, &M, &K);
vector<int> A(N + 1);
for (int i = 1; i <= N; ++i)
scanf("%d", &A[i]);
vector<int> P(N + 1);
P[2] = 1;
for (int i = 3; i <= N; ++i)
scanf("%d", &P[i]);
vector<int> X(M), Y(M);
for (int mi = 0; mi < M; ++mi) {
scanf("%d%d", &X[mi], &Y[mi]);
}
vector<query> colors;
vector<int> p_index(N + 1);
vector<int> v_index(N + 1);
vector<int> value(N + N + M + M);
vector<int> p_new_index(M);
vector<int> v_new_index(M);
colors.reserve(N + N + M + M);
for (int i = 2; i <= N; ++i) {
colors.push_back(query(P[i], A[i], i));
}
for (int i = 1; i <= N; ++i) {
colors.push_back(query(i, A[i], i + N));
}
for (int mi = 0; mi < M; ++mi) {
colors.push_back(query(P[X[mi]], Y[mi], 2 * N + mi + 1));
colors.push_back(query(X[mi], Y[mi], 2 * N + M + mi + 1));
}
sort(colors.begin(), colors.end());
int ind = 0;
for (int i = 0; i < colors.size();) {
int j;
for (j = i; j < colors.size() && colors[i].parent == colors[j].parent && colors[i].color == colors[j].color; ++j) {
if (colors[j].index <= N) {
p_index[colors[j].index] = ind;
++value[ind];
continue;
}
if (colors[j].index <= 2 * N) {
v_index[colors[j].index - N] = ind;
continue;
}
if (colors[j].index <= 2 * N + M) {
p_new_index[colors[j].index - 1 - N - N] = ind;
continue;
}
v_new_index[colors[j].index - 1 - N - N - M] = ind;
}
i = j;
++ind;
}
int ans = 0;
for (int i = 1; i <= N; ++i)
ans += value[v_index[i]];
for (int mi = 0; mi < M; ++mi) {
if (A[P[X[mi]]] == A[X[mi]]) --ans;
ans -= value[v_index[X[mi]]];
--value[p_index[X[mi]]];
A[X[mi]] = Y[mi];
if (A[P[X[mi]]] == A[X[mi]]) ++ans;
p_index[X[mi]] = p_new_index[mi];
v_index[X[mi]] = v_new_index[mi];
ans += value[v_index[X[mi]]];
++value[p_index[X[mi]]];
printf("%d\n", ans);
}
}
int main() {
solve();
cerr << clock() << endl;
return 0;
}