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. KAN have already wrote about this.
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 is loading...
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() — t << endl;
t = gett();
#endif
}
return 0;
}
Tutorial is loading...
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 — 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() — t << endl;
t = gett();
#endif
}
return 0;
}
Tutorial is loading...
code
Tutorial is loading...
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() — t << endl;
t = gett();
#endif
}
return 0;
}
Tutorial is loading...
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() — t << endl;
t = gett();
#endif
return 0;
}
Tutorial is loading...
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 — 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 — 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() — t << endl;
t = gett();
#endif
}
return 0;
}
Tutorial is loading...
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;
}
