Codeforces Round #421 Editorial
Разница между en9 и en10, 0 символ(ов) изменены
First, I apologize for problems with round and serious problem with Div1A/Div2C. It was very important round for me and, as always, something goes wrong. [user:KAN,2017-06-28] have already [wrote about this](http://codeforces.net/blog/entry/52944).↵

Anyway, there are problems, so editorial must exists. Due some circumstances, Editorial will be upload in parts.↵
Also, most of tutorials will contain main ideas how to solve task, not ready algorithm.↵

[tutorial:820A]↵

<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)↵
#define forn(i, n) fore(i, 0, n)↵

#define all(a) (a).begin(), (a).end()↵
#define sqr(a) ((a) * (a))↵
#define sz(a) int(a.size())↵
#define mp make_pair↵
#define pb push_back↵

#define x first↵
#define y second↵

using namespace std;↵

template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵

template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵

typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵

inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵

const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵

int c, l, v0, v1, a;↵

inline bool read() {↵
if(!(cin >> c >> v0 >> v1 >> a >> l))↵
return false;↵

return true;↵
}↵

inline void solve() {↵
int pos = v0;↵
int t = 1;↵

int add = v0;↵

while(pos < c) {↵
add = min(v1, add + a);↵

pos += add - l;↵
t++;↵
}↵

cout << t << endl;↵
}↵

int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵

int t = gett();↵
#endif↵

srand(time(NULL));↵
cout << fixed << setprecision(10);↵

while(read()) {↵
solve(); ↵

#ifdef _DEBUG↵
cerr << "TIME = " << gett() &mdash; t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:820B]↵

<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)↵
#define forn(i, n) fore(i, 0, n)↵

#define all(a) (a).begin(), (a).end()↵
#define sqr(a) ((a) * (a))↵
#define sz(a) int(a.size())↵
#define mp make_pair↵
#define pb push_back↵

#define x first↵
#define y second↵

using namespace std;↵

template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵

template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵

typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵

inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵

const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵

int n, a;↵

inline bool read() {↵
if(!(cin >> n >> a))↵
return false;↵

return true;↵
}↵

inline void solve() {↵
int base = n * a / 180;↵
base = max(1, min(n &mdash; 2, base));↵

int bk = base;↵
for(int ck = max(1, base - 2); ck <= min(n - 2, base + 2); ck++) {↵
if(abs(180 * ck - n * a) < abs(180 * bk - n * a))↵
bk = ck;↵
}↵

cout << 2 << " " << 1 << " " << bk + 2 << endl;↵
}↵

int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵

int t = gett();↵
#endif↵

srand(time(NULL));↵
cout << fixed << setprecision(10);↵

while(read()) {↵
solve(); ↵

#ifdef _DEBUG↵
cerr << "TIME = " << gett() &mdash; t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:819A]↵

<spoiler summary="code">↵
</spoiler>↵

[tutorial:819B]↵

<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)↵
#define forn(i, n) fore(i, 0, n)↵

#define all(a) (a).begin(), (a).end()↵
#define sqr(a) ((a) * (a))↵
#define sz(a) int(a.size())↵
#define mp make_pair↵
#define pb push_back↵

#define x first↵
#define y second↵

using namespace std;↵

template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵

template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵

typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵

inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵

const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵

const int N = 1000 * 1000 + 555;↵

int n, p[N];↵

inline bool read() {↵
if(!(cin >> n))↵
return false;↵
forn(i, n)↵
assert(scanf("%d", &p[i]) == 1);↵
return true;↵
}↵

li sum[N], df[N], res[N];↵

inline void add(int lf, int rg, int k, int b) {↵
if(lf > rg)↵
return;↵

sum[lf] += b;↵
df[lf] += k;↵

sum[rg + 1] -= b + k * 1ll * (rg - lf);↵
df[rg] -= k;↵
}↵

inline void calc() {↵
li curdf = 0;↵
forn(i, n) {↵
sum[i] += curdf;↵
curdf += df[i];↵
}↵

li cursm = 0;↵
forn(i, n) { ↵
cursm += sum[i];↵
res[i] += cursm;↵
}↵
}↵

inline void solve() {↵
memset(sum, 0, sizeof sum);↵
memset(df, 0, sizeof df);↵
memset(res, 0, sizeof res);↵

forn(i, n) {↵
int c1 = i + 1, p1 = 0;↵
int c2 = n,     p2 = p1 + c2 - c1;↵
int c3 = i,     p3 = p2 + c3;↵

if(p[i] <= c3) {↵
add(p1, p2, 1, c1 - p[i]);↵
add(p2 + 1, p2 + p[i], -1, p[i] - 1);↵
add(p2 + p[i] + 1, p3, 1, 1);↵
} else {↵
add(p1, p1 + p[i] - c1, -1, p[i] - c1);↵
add(p1 + p[i] - c1 + 1, p2, 1, 1);↵
add(p2 + 1, p3, -1, p[i] - 1);↵
}↵
}↵

calc();↵

int ans = 0;↵
forn(i, n)↵
if(res[ans] > res[i])↵
ans = i;↵

cout << res[ans] << " " << ans << endl;↵
}↵

int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵

int t = gett();↵
#endif↵

srand(time(NULL));↵
cout << fixed << setprecision(10);↵

while(read()) {↵
solve(); ↵

#ifdef _DEBUG↵
cerr << "TIME = " << gett() &mdash; t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:819C]↵

<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)↵
#define forn(i, n) fore(i, 0, n)↵

#define all(a) (a).begin(), (a).end()↵
#define sqr(a) ((a) * (a))↵
#define sz(a) int(a.size())↵
#define mp make_pair↵
#define pb push_back↵

#define x first↵
#define y second↵

using namespace std;↵

template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵

template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵

typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
typedef pair<li, li> ptl;↵

inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵

const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵

int n[3], m[3], s[3];↵

inline bool read() {↵
if(scanf("%d %d %d", &n[0], &n[1], &n[2]) != 3)↵
return false;↵
forn(i, 3)↵
assert(scanf("%d", &m[i]) == 1);↵
forn(i, 3)↵
assert(scanf("%d", &s[i]) == 1);↵
return true;↵
}↵

const int N = 2 * 1000 * 1000 + 55;↵
int ls[N];↵

inline void precalc() {↵
memset(ls, -1, sizeof ls);↵

ls[0] = ls[1] = 1;↵
fore(i, 2, N) {↵
if(ls[i] != -1)↵
continue;↵

ls[i] = i;↵
for(li j = i * 1ll * i; j < N; j += i)↵
if(ls[j] == -1)↵
ls[j] = i;↵
}↵
}↵

inline vector<pt> fact(int n[3]) {↵
vector<int> divs;↵

forn(i, 3) {↵
int cur = n[i];↵
while(ls[cur] != cur) {↵
divs.pb(ls[cur]);↵
cur /= ls[cur];↵
}↵
if(cur > 1)↵
divs.pb(cur);↵
}↵

sort(all(divs));↵
vector<pt> ans;↵

int u = 0;↵
while(u < sz(divs)) {↵
int v = u;↵
while(v < sz(divs) && divs[v] == divs[u])↵
v++;↵

ans.pb(mp(divs[u], v - u));↵
u = v;↵
}↵

return ans;↵
}↵

li ans;↵

li nn, mm, ss;↵
vector<pt> fs;↵
vector<li> bad;↵

void calcDivs(int pos, li val) {↵
if(pos >= sz(fs)) {↵
ans += (val <= nn);↵
return;↵
}↵

li cv = 1;↵
forn(i, fs[pos].y + 1) {↵
calcDivs(pos + 1, val * cv);↵

cv *= fs[pos].x;↵
}↵
}↵

void calcInEx(int pos, li val, int cnt) {↵
if(pos >= sz(bad)) {↵
li k = cnt ? -1 : 1;↵

ans += k * (mm / val);↵
return;↵
}↵

calcInEx(pos + 1, val, cnt);↵
calcInEx(pos + 1, val * bad[pos], cnt ^ 1);↵
}↵

inline void solve() {↵
ans = 0;↵
s[0] *= 2;↵

nn = n[0] * 1ll * n[1] * 1ll * n[2];↵
mm = m[0] * 1ll * m[1] * 1ll * m[2];↵
ss = s[0] * 1ll * s[1] * 1ll * s[2];↵

fs = fact(s);↵
calcDivs(0, 1);↵

bad.clear();↵
vector<pt> fn = fact(n);↵

forn(i, sz(fn)) {↵
li cv = fn[i].x;↵
forn(k, fn[i].y) {↵
if(ss % cv != 0) {↵
bad.pb(cv);↵
break;↵
}↵
cv *= fn[i].x;↵
}↵
}↵

calcInEx(0, 1, 0);↵

printf("%I64d\n", ans);↵
}↵

int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵

int t = gett();↵
#endif↵

srand(time(NULL));↵
cout << fixed << setprecision(10);↵

int tc; assert(cin >> tc);↵
precalc();↵

while(tc--) {↵
assert(read());↵

solve(); ↵
}↵

#ifdef _DEBUG↵
cerr << "TIME = " << gett() &mdash; t << endl;↵
t = gett();↵
#endif↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:819D]↵

<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)↵
#define forn(i, n) fore(i, 0, n)↵

#define all(a) (a).begin(), (a).end()↵
#define sqr(a) ((a) * (a))↵
#define sz(a) int(a.size())↵
#define mp make_pair↵
#define pb push_back↵

#define x first↵
#define y second↵

using namespace std;↵

template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵

template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << ", ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵

typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵

inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵

const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵

int gcd(int a, int b) {↵
if(a == 0)↵
return b;↵
return gcd(b % a, a);↵
}↵

int exgcd(int a, li &x, int b, li &y) {↵
if(a == 0) {↵
x = 0, y = 1;↵
return b;↵
}↵

li xx, yy;↵
int g = exgcd(b % a, xx, a, yy);↵

x = yy - b / a * xx;↵
y = xx;↵

return g;↵
}↵

const int N = 200 * 1000 + 555;↵
int t, n, a[N];↵

inline bool read() {↵
if(!(cin >> t >> n))↵
    return false;↵
forn(i, n)↵
assert(scanf("%d", &a[i]) == 1);↵
return true;↵
}↵

int pf[N], s;↵

inline li up(li a, li b) {↵
return (a + b &mdash; 1) / b;↵
}↵

inline int findPos(int a, int b, int c) {↵
li x, y;↵
int g = exgcd(a, x, b, y);↵
assert(c % g == 0);↵

x *= +c / g;↵
y *= -c / g;↵
assert(a * 1ll * x - b * 1ll * y == c);↵

int ag = a / g;↵
int bg = b / g;↵

li k = 0;↵
if(x < 0)↵
k = up(-x, bg);↵
if(x >= bg)↵
k = -up(x - bg, bg); ↵
x += bg * k;↵
y += ag * k;↵

assert(0 <= x && x < bg);↵

k = 0;↵
if(y < 0)↵
k = up(-y, ag);↵
x += bg * k;↵
y += ag * k;↵

return x;↵
}↵

map< int, set<pt> > cycle;↵

int ans[N];↵

inline void solve() {↵
cycle.clear();↵
pf[0] = 0;↵
fore(i, 1, n)↵
pf[i] = (pf[i &mdash; 1] + a[i]) % t;↵

s = (a[0] + pf[n - 1]) % t;↵
int g = gcd(s, t);↵

forn(i, n) {↵
int st = pf[i] % g;↵
auto& cc = cycle[st];↵

int pos = findPos(s, t, pf[i] - st);↵

if(cc.empty()) {↵
ans[i] += t / g;↵
cc.insert(pt(pos, -i));↵
} else {↵
auto rg = cc.lower_bound(pt(pos, -i));↵
if(rg == cc.end()) {↵
ans[i] += t / g - pos;↵
rg = cc.begin();↵
ans[i] += rg->x;↵
} else↵
ans[i] += rg->x - pos;↵

auto lf = cc.lower_bound(pt(pos, -i));↵
if(lf == cc.begin())↵
lf = --cc.end();↵
else↵
lf--;↵
ans[ -(lf->y) ] -= ans[i];↵

cc.insert(pt(pos, -i));↵
} ↵
}↵

forn(i, n)↵
printf("%d ", ans[i]);↵
puts("");↵
}↵

int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵

int t = gett();↵
#endif↵

srand(time(NULL));↵
cout << fixed << setprecision(10);↵

while(read()) {↵
solve(); ↵

#ifdef _DEBUG↵
cerr << "TIME = " << gett() &mdash; t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:819E]↵

<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

using ll = long long;↵
using ld = long double;↵
using D = double;↵
using uint = unsigned int;↵
template<typename T>↵
using pair2 = pair<T, T>;↵

#ifdef WIN32↵
    #define LLD "%I64d"↵
#else↵
    #define LLD "%lld"↵
#endif↵

#define pb push_back↵
#define mp make_pair↵
#define all(x) (x).begin(),(x).end()↵
#define fi first↵
#define se second↵

const int maxn = 305;↵

int pair3[maxn];↵
int n;↵
vector<vector<int>> answer;↵

void add3(int a, int b, int c)↵
{↵
    answer.pb({a, b, c});↵
}↵

void add4(int a, int b, int c, int d)↵
{↵
    answer.pb({a, b, c, d});↵
}↵

int main()↵
{↵
    cin >> n;↵
    if (n % 2 == 0)↵
    {↵
        pair3[0] = 3; // 0 1 3↵
        pair3[2] = 1; // 2 3 1↵
        add3(0, 1, 2);↵
        add3(2, 3, 0);↵
        for (int i = 4; i < n; i += 2)↵
        {↵
            add4(0, pair3[0], 1, i);↵
            add3(i, i + 1, 0);↵
            pair3[i] = 1;↵
            pair3[0] = i + 1;↵
            for (int j = 2; j < i; j += 2)↵
            {↵
                add4(j, pair3[j], j + 1, i);↵
                add4(j, i, j + 1, i + 1);↵
                pair3[j] = i + 1;↵
            }↵
        }↵
        for (int i = 0; i < n; i += 2)↵
        {↵
            add3(i, i + 1, pair3[i]);↵
        }↵
    } else↵
    {↵
        pair3[1] = 0; // 1 2 0↵
        add3(0, 1, 2);↵
        for (int i = 3; i < n; i += 2)↵
        {↵
            add3(i, i + 1, 0);↵
            pair3[i] = 0;↵
            for (int j = 1; j < i; j += 2)↵
            {↵
                add4(j, pair3[j], j + 1, i);↵
                add4(j, i, j + 1, i + 1);↵
                pair3[j] = i + 1;↵
            }↵
        }↵
        for (int i = 1; i < n; i += 2)↵
        {↵
            add3(i, i + 1, pair3[i]);↵
        }↵
    }↵
    printf("%d\n", (int)answer.size());↵
    for (auto &t : answer)↵
    {↵
        printf("%d", (int)t.size());↵
        for (auto t2 : t) printf(" %d", t2 + 1);↵
        printf("\n");↵
    }↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский adedalic 2017-06-28 17:40:28 9572 Первая редакция перевода на Русский
en11 Английский adedalic 2017-06-28 17:35:28 5513 Tiny change: 'rn (a + b &mdash; 1) / b;\n' -> 'rn (a + b - 1) / b;\n'
en10 Английский adedalic 2017-06-28 01:50:03 0 (published)
en9 Английский adedalic 2017-06-28 01:46:24 2012
en8 Английский adedalic 2017-06-28 01:43:41 56
en7 Английский adedalic 2017-06-28 01:42:04 24
en6 Английский adedalic 2017-06-28 01:40:14 10
en5 Английский adedalic 2017-06-28 01:39:13 9077
en4 Английский adedalic 2017-06-28 01:36:10 331
en3 Английский adedalic 2017-06-28 01:34:44 1758
en2 Английский adedalic 2017-06-28 01:16:21 9
en1 Английский adedalic 2017-06-28 01:15:57 2156 Initial revision (saved to drafts)