Задача А
Ідея зрозуміла із формули: K=((k-5)/(m-1))*(n-1)+5;
(Якщо ми перебуваємо на к –ому поверсі, то під нами к-1 поверх.)
#include<iostream>
using namespace std;
int main()
{
unsigned long long m,n,k,K;
cin>>m>>n>>k;
if((m==1)&&(k!=1)) cout<<"-1";
else
{
K=((k-5)/(m-1))*(n-1)+5;
cout<<K;
}
}
Задача B
Ідея: зміна рахунку на табло – це послідовні числа від 0 до n . Сума цих чисел – сума арифметичної прогресії S=n*(n-1)/2. Звідси отримуємо: n=((int)sqrt(8*S+1)-1)/2;
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
long long n, S;
cin>>S;
n=((int)sqrt(8*S+1)-1)/2;
cout<<n;
}
Задача С
Задача на алгоритм Евкліда.
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
long long a,b;
cin>>a>>b;
while(b)
{
a%=b;
swap(a,b);
}
cout<<a;
}
Задача D
У даному алгоритмі використаний метод включення –викключення.
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
freopen("prosto.in","r",stdin);
long long sum = 0,a,b;
int n, p[10];
cin>>a>>b>>n;
for(int i=0;i<n;i++) cin>>p[i];
for (int i = 0; i < (1 << n); i++) {
int f = 1;
long q = 1;
for (int j = 0; j < n; j++)
if ((i & (1 << j)) > 0) {
f *= -1;
q *= p[j];
};
sum += f * (b / q - (a - 1) / q);
};
cout<<sum;
}
3адача E
Ідея: скануюча пряма:
Проходимо сканпрямою і маємо події двох видів --- прямокутник починається або закінчився.
Ці запити = +-1 на відрізку прямої. А відповідь на задачу це максимум на всій прямій.
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#include <vector>
#define MAXN 524288
#define MAXC 200000
#define INFINITy 1000000000
struct tseg{
int miny, maxy, d,x;
tseg(){}
tseg(int p, int q, int b, int a){
miny = p;
maxy = q;
d = b;
x = a;
}
friend bool operator <(const tseg &a, const tseg &b){
if (a.x!=b.x) return a.x<b.x;
if (a.d!=b.d) return a.d>b.d;
return false;
}
};
int max(int a, int b){
return (a>b?a:b);
}
struct window{
int x1,y1,x2,y2;
};
struct tree{
int a[MAXN*2+2];
int d[MAXN*2+2];
tree(){
for (int i = 0; i < MAXN*2+2; i++){a[i]=0;d[i]=0;}
}
void add(int l, int r, int D, int v, int nL, int nR){
if ((nR<l)||(nL>r)) return;
if ((nL>=l)&&(nR<=r)){
d[v] += D;
return;
}
d[v*2+1] += d[v];
d[v*2+2] += d[v];
d[v] = 0;
add(l,r,D,v*2+1,nL,((nL+nR)>>1));
add(l,r,D,v*2+2,((nL+nR)>>1)+1,nR);
a[v] = max(a[v*2+1]+d[v*2+1],a[v*2+2]+d[v*2+2]);
}
pair<int,int> getmax(){
int v = 0;
int l = 0;
int r = MAXC*2+1;
while (l!=r){
d[v*2+1] += d[v];
d[v*2+2] += d[v];
d[v] = 0;
a[v] = max(a[v*2+1]+d[v*2+1],a[v*2+2]+d[v*2+2]);
if (a[v*2+1]+d[v*2+1]>a[v*2+2]+d[v*2+2]){
v = v*2+1;
r = (l+r)>>1;
}else{
v = v*2+2;
l = ((l+r)>>1)+1;
}
}
a[v] += d[v];
d[v] = 0;
return make_pair(a[v],l);
}
};
vector<tseg> v;
tree t;
window w[50000];
int n;
int main(){
freopen("windows.in", "rt", stdin);
scanf("%d", &n);
for (int i = 0; i < n; i++){
int x1,y1,x2,y2;
scanf("%d%d%d%d", &x1,&y1,&x2,&y2);
w[i].x1=x1;w[i].x2=x2;w[i].y1=y1;w[i].y2=y2;
x1 += MAXC; y1 += MAXC; x2 += MAXC; y2 += MAXC;
v.push_back(tseg(y1,y2,1,x1));
v.push_back(tseg(y1,y2,-1,x2));
}
sort(v.begin(),v.end());
int omax = 0;
int _x = 0;
int _y = 0;
for (int i = 0; i < n*2; i++){
t.add(v[i].miny, v[i].maxy, v[i].d, 0, 0, MAXC*2+1);
pair<int, int> tmp = t.getmax();
if (tmp.first>omax){
omax = tmp.first;
_x = v[i].x;
_y = tmp.second;
}
}
printf("%d\n", omax);
fclose(stdin);
fclose(stdout);
return 0;
}
3адача F
Ідея: вставляємо зірочку між кожними символами і для кожної позиції рахуємо найбільший паліндром з центром в даній позиції.
Хеш-функція з використанням бінарного пошуку.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define mlen 200010
int n, len, num[mlen], sum[mlen];
char s[mlen], s1[mlen], t[mlen];
int p[mlen], code[mlen], q[mlen], ncode[mlen];
int tr[mlen * 2];
int TGet( int l, int r )
{
if (l > r) swap(l, r);
r--;
l += n, r += n;
int mi = (int)1e9;
while (l <= r)
{
if (l & 1) mi = min(mi, tr[l++]);
if (!(r & 1)) mi = min(tr[r--], mi);
if (l > r) break;
l >>= 1, r >>= 1;
}
return mi;
}
int main( void )
{
int i, k;
freopen("palind.in", "rt", stdin);
gets(s);
len = strlen(s);
for (i = 0; i < len; i++)
s1[i] = s[len - i - 1];
s1[len] = 0;
sprintf(t, "$%s#%s!", s, s1);
n = strlen(t);
memset(num, 0, sizeof(num));
for (i = 0; i < n; i++)
num[(int)t[i]]++;
sum[0] = 0;
for (i = 0; i < mlen; i++)
sum[i + 1] = sum[i] + num[i];
for (i = 0; i < n; i++)
p[sum[(int)t[i]]++] = i, code[i] =(int)t[i];
for (k = 1; k < n; k *= 2)
{
memset(num, 0, sizeof(num));
for (i = 0; i < n; i++)
num[code[i]]++;
sum[0] = 0;
for (i = 0; i < max(n, 256); i++)
sum[i + 1] = sum[i] + num[i];
for (i = 0; i < n; i++)
q[sum[code[(p[i] - k + n) % n]]++] = p[i];
int cc = 0;
for (i = 0; i < n; i++)
{
if (i && (code[q[i]] != code[q[i - 1]] || code[(q[i] - k + n) % n] != code[(q[i - 1] - k + n) % n])) cc++;
ncode[i] = cc;
}
for (i = 0; i < n; i++)
p[i] = q[i], code[p[i]] = ncode[i];
}
for (i = 0; i < n; i++)
p[i] = (p[i] - k + 1 + n * 2) % n;
for (i = 0; i < n; i++)
q[p[i]] = i;
for (i = 1; i < n; i <<= 1);
for (k = i = 0; i < n; i++)
{
if (k) k--;
if (q[i] < n)
while (k < n && t[i + k] == t[p[q[i] + 1] + k])
k++;
tr[n + q[i]] = k;
}
for (i = n - 1; i > 0; i--)
tr[i] = min(tr[i + i], tr[i + i + 1]);
long long ans = 0;
for (i = 0; i < len; i++)
ans += max(0, TGet(q[i + 1], q[len * 2 - i + 1]) - 1);
for (i = 0; i < len - 1; i++)
ans += TGet(q[i + 2], q[len * 2 - i + 1]);
cout << ans;
return 0;
}