Opencup 2016-2017. GP of Dolgoprudny

→ Обратите внимание

До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя riadwaw

Opencup 2016-2017. GP of Dolgoprudny

Автор riadwaw, история, 8 лет назад, По-английски

Tomorrow is GP of Dolgoprudny which is prepared by my colleagues and me.

Hope, you'll like the problems which we can discuss here after the contest.

Also, we've prepared mini-tutorial which I'll post here after the contest too.

Good luck!

opencup, discussion

+165

riadwaw
8 лет назад
21

Комментарии (19)

Показать архивные | Написать комментарий?

riadwaw

8 лет назад, # |

+136

Кажется, провести опенкап вышло неплохим отвлекающим маневром :)

→ Ответить

riadwaw

8 лет назад, # |

+14

Mini editorial

→ Ответить

riadwaw

8 лет назад, # |

+22

My solutions for problems I had solutions.

#!/usr/bin/env python3
import sys

n, m = [int(x) for x in input().split()]
r = [['0'] * m for i in range(n)]
for i in range(min(m, n)):
	r[i][i] = '1'

for i in range(max(m, n) - 1, min(n, m) - 1, -2):
	if m > n:
		r[0][i] = '1'
	else:
		r[i][0] = '1'

for l in r:
	print(''.join(l))

using Z = Zn<P>;
class CycleExpectation {
public:
	void solve(std::istream& in, std::ostream& out) {
		int n;
		in >> n >> P::value;


		Z ans;
		vector<Z> reverse(n + 1, Z::rawValueOf(1));
		for (int i = 1; i <= n; ++i) {
			reverse[i] /= i;
		}
		vector<Z> addFrom(n + 1);
		for (int least = 1; least <= n; ++least) {
			fill(addFrom.begin(), addFrom.end(), 0);
			Z sum = Z::valueOf(1);
			for (int i = least; i < n; ++i) {
				sum += addFrom[i];
				if (i + least <= n) {
					addFrom[i + least] += sum * reverse[i];
				}
			}
			//cerr << (sum + addFrom[n]) / n << endl;
			ans += (sum + addFrom[n]) * reverse[n];
		}
		out << ans << "\n";
	}
};


class NoPalindromesNoAlpha {
public:
	void solve(std::istream& in, std::ostream& out) {
		int k;
		in >> k;
		string s;
		in >> s;
		auto n = s.size();
		vector<int> v(s.size());
		for (auto i: range(s.size())) {
			if (s[i] >= 'a') {
				v[i] = s[i] - 'a';
			} else {
				v[i] = s[i] - 'A' + 26;
			}
		}
		auto cost = make_vector<int>(k, k, 0);
		for (auto i: range(k)) {
			for (auto j: range(k)) {
				in >> cost[i][j];
			}
		}

		if (n == 1) {
			out << 0;
			return;
		}

		if (k == 1) {
			out << -1;
			return;
		}
		if (n == 2) {
			int ans = 2000000000;
			for (int i: range(k)) {
				for (int j: range(k)) {
					if (i != j)
						ans = min(ans, cost[v[0]][i] + cost[v[1]][j]);
				}
			}
			out << ans << "\n";
			return;
		}
		if (k == 2) {
			out << -1;
			return;
		}

		auto bestIndices = make_vector<int>(k, k, 0);
		for (auto i : range(k)) {
			for (auto j: range(k)) {
				bestIndices[i][j] = j;
			}
			sort(bestIndices[i], [&](int a, int b) {
				return cost[i][a] < cost[i][b];
			});

			if (bestIndices[i].size() > 5) {
				bestIndices[i].resize(5);
			}
		}

		auto cur_ans = default_answer();
		for (auto first_char_id: range(bestIndices[v[0]].size())) {
			int first_char = bestIndices[v[0]][first_char_id];
			cur_ans[first_char_id][0] = {(uint64_t)cost[v[0]][first_char], -1};
		}
		for (auto i: range(1, (int) n)) {
			auto next_ans = default_answer();
			for (auto last_char_id: range(bestIndices[v[i]].size())) {
				int last_char = bestIndices[v[i]][last_char_id];
				auto& two_answers = next_ans[last_char_id];
				for (auto prev_char_id: range(bestIndices[v[i - 1]].size())) {
					int prev_char = bestIndices[v[i - 1]][prev_char_id];
					if (last_char == prev_char) {
						continue;
					}
					int index = 0;
					if (cur_ans[prev_char_id][0].second == last_char) {
						index = 1;
					}
					if (cur_ans[prev_char_id][index].first == std::numeric_limits<uint64_t>::max()) {
						continue;
					}
					int64_t ans = cur_ans[prev_char_id][index].first + cost[v[i]][last_char];
					std::pair<uint64_t, int> curPair = {ans, prev_char};
					for (int z: range(2)) {
						if(curPair < two_answers[z]) {
							swap(curPair, two_answers[z]);
						}
					}
				}
			}
			cur_ans = next_ans;
		}
		uint64_t ans = std::numeric_limits<uint64_t>::max();

		for (auto& c: cur_ans) {
			ans = min(ans, c[0].first);
		}

		out << ans << "\n";
	}

private:
	std::array<std::array<pair<uint64_t, int>, 2>, 5> default_answer() const {
		std::array<std::array<pair<uint64_t, int>, 2>, 5> dp;
		memset(&dp, -1, sizeof(dp));
		return dp;
	}
};

public class JavaSol implements Runnable {

    long leastBit(long x) {
        return x ^ (x & (x - 1));
    }

    void solve() throws IOException {
        int n = nextInt();
        long[] a = new long[n];
        long sum = 0;
        long xor = 0;
        for (int i = 0; i < n; ++i) {
            a[i] = nextLong();
            sum += a[i];
            xor ^= a[i];
        }
        if (xor == 0) {
            out.println(sum);
            int curLeastBit = 0;
            for (int i = 1; i < n; ++i) {
                if (leastBit(a[i]) < leastBit(a[curLeastBit])) {
                    curLeastBit = i;
                }
            }
            out.println((curLeastBit + 1) + " 1");
        }
        else {
            long maxTurn = 0;
            int bestIndex = 0;
            for (int i = 0; i < n; ++i) {
                long need = a[i] ^ xor;
                if (need < a[i]) {
                    if (a[i] - need > maxTurn) {
                        maxTurn = a[i] - need;
                        bestIndex = i;
                    }
                }
            }
            out.println(sum - maxTurn + 1);
            out.println((bestIndex + 1) + " " + maxTurn);
        }
    }
}

class Matrix {
public:
	bool ask(const std::string& s) {
		return ask(vector<string>{s});
	}

	bool ask(const std::vector<string>& s) {
		cout << "Query: " << s.size() << ' ' << s[0].size() << "\n";
		for (const std::string& x: s) {
			cout << x << "\n";
		}
		cout << flush;
		int x;
		cin >> x;
		return (bool) x;
	}

	void solve(std::istream& in, std::ostream& out) {
		int n, m;
		cin >> n >> m;
		string s;
		while (s.size() < m) {
			if (ask(s + "0")) {
				s += '0';
			}
			else if (ask(s + "1")) {
				s += '1';
			}
			else {
				break;
			}
		}
		while (s.size() < m) {
			if (ask("0" + s)) {
				s = "0" + s;
			}
			else {
				s = "1" + s;
			}
		}

		vector<string> v = {s};
		while (v.size() < n) {
			vector<string> x = v;
			x.push_back("1" + string(m - 1, '?'));
			if (ask(x)) {
				v = x;
			} else {
				x.back()[0] = '0';
				if (ask(x)) {
					v = x;
				} else {
					break;
				}
			}
		}

		while (v.size() < n) {
			vector<string> x = v;
			x.insert(x.begin(), "0" + string(m - 1, '?'));
			if (ask(x)) {
				v = x;
			} else {
				x.front()[0] = '1';
				v = x;
			}
		}

		for (int i: range(n)) {
			for (int j: range(m)) {
				if (v[i][j] == '?') {
					v[i][j] = '0';
					if (!ask(v)) {
						v[i][j] = '1';
					}
				}
			}
		}

		cout << "Answer:\n";
		for (auto z: v) {
			cout << z << "\n";
		}
		return;
	}
};

class Restrooms {
public:
	void solve() {
		int n, m, k;
		cin >> n >> m >> k;
		vector<int> b(n + 1, n);
		vector<int> g(n + 1, n);
		for (int i: range(m)) {
			int l, r;
			cin >> l >> r;
			--l, --r;
			b[l] = min(b[l], r);
		}

		for (int i: range(k)) {
			int l, r;
			cin >> l >> r;
			--l, --r;
			g[l] = min(g[l], r);
		}

		vector<int> db(n + 2);
		vector<int> dg(n + 2);

		for (int i: inclusiveRange(0, (int)b.size() - 1)) {
			db[i + 1] = (i <= dg[i]) ? b[i] : min(b[i], db[i]);
			dg[i + 1] = (i <= db[i]) ? g[i] : min(g[i], dg[i]);
		}
		if (db.back() < n && dg.back() < n) {
		    printf("No\n");
			return;
		}

		cout << ("Yes\n");

		string ans(n, ' ');

		int lastB = n;
		int lastG = n;
		for (int i: downrange(n)) {
			if (lastB <= db[i + 1]) {
				ans[i] = '1';
				lastG = i;
			} else {
				assert(lastG <= dg[i + 1]);
				ans[i] = '0';
				lastB = i;
			}
		}
		cout << ans << "\n";
	}
};

class Doors {
public:
	void solve(std::istream& in, std::ostream& out) {
		int n;
		in >> n;
		vector<int> a(n);
		vector<int> b(n);
		for (int i: range(n)) {
			in >> a[i] >> b[i];
		}

		double l = 0, r = 1000000000;
		for (int _: range(100)) {

			auto can_fail = [&](double m) {
				double best_time_up = 0;
				double best_time_down = numeric_limits<double>::infinity();
				for (int i: range(n)) {
					if (b[i] == 0) {
						if (a[i] < m) {
							return true;
						}
					}
					if (b[i] < 0) {
						if (a[i] <= m) {
							return true;
						}
						double time = (a[i] - m) / -b[i];
						best_time_down = min(time, best_time_down);
					}
					if (b[i] > 0) {
						if (a[i] >= m) {
							continue;
						}
						double time = (a[i] - m) / -b[i];
						best_time_up = max(time, best_time_up);
					}
				}
				// can't fail ifx
				// 1 / speed <= best_time_down / n
				// 1 / speed >= best_time_up
				return best_time_down < best_time_up * n;
			};
			double m = (l + r) / 2.0;
			if (can_fail(m)) {
				r = m;
			} else {
				l = m;
			}
		}

		out << (l + r) / 2.0;
	}
};


class Campus {
public:
	void solve(std::istream& in, std::ostream& out) {
		int n;
		in >> n;
		vector<pair<int, int>> a(n);
		for (int i: range(n)) {
			in >> a[i].first >> a[i].second;
			if (a[i].first > a[i].second) {
				swap(a[i].first, a[i].second);
			}
		}

		int64_t answer = 0;
		int m;
		in >> m;
		vector<int> c(m + 1);


		for (int i: range(m)) {
			in >> c[i];
		}
		c.back() = -1000000000;
		sort(a);
		sort(c);
		int cIndex = 0;
		struct Event {
			int64_t x;
			int da;
		};
		vector<Event> events;
		for (int i: range(n)) {
			while (cIndex != c.size() && c[cIndex] < a[i].first) {
				++cIndex;
			}
			answer += a[i].second - a[i].first;
			if (cIndex < c.size() && a[i].second >= c[cIndex]) {
				// ok;
			} else {
				int64_t curExtra = 0;
				if (cIndex == 0) {
					curExtra = c[cIndex] - a[i].second;
				} else if (cIndex == c.size()) {
					curExtra = a[i].first - c[cIndex - 1];
				} else {
					curExtra = min(
							c[cIndex] - a[i].second,
							a[i].first - c[cIndex - 1]
					);
				}
				answer += curExtra * 2;
				events.push_back({a[i].first - curExtra, 2});
				events.push_back({a[i].first, -2});
				events.push_back({a[i].second, -2});
				events.push_back({a[i].second + curExtra, 2});
			}
		}

		sort(events, [](const Event& a, const Event& b) {
			return a.x < b.x;
		});

		int64_t bestDecrease = 0;
		int64_t curx = 0;
		int64_t cura = 0;
		int64_t curda = 0;
		for (auto& event: events) {
			cura += curda * (event.x - curx);
			curda += event.da;
			curx = event.x;
			bestDecrease = max(bestDecrease, cura);
		}

		out << answer - bestDecrease;
	}
};

public class JavaSol implements Runnable {

    void solve() throws IOException {
        int n = nextInt();
        long newS = nextLong();
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; ++i) {
            x[i] = nextInt();
            y[i] = nextInt();
        }
        double P = 0;
        double S = 0;
        for (int i = 0; i < n; ++i) {
            double len = Math.sqrt(sqr(x[(i + 1) % n] - x[i]) + sqr(y[(i + 1) % n] - y[i]));
            P += len;
            S += ((long) x[(i + 1) % n] * y[i] - (long) x[i] * y[(i + 1) % n]) / 2.0;
        }
        S = Math.abs(S);
        if (S >= newS) {
            out.println(0);
            return;
        }
        double A = Math.PI;
        double B = P;
        double C = S - newS;
        double D = B * B - 4 * A * C;
        out.print((-B + Math.sqrt(D)) / 2 / A);
    }

    long sqr(long x) {
        return x * x;
    }
}

class CrossMebius {
public:
	void solve(std::istream& in, std::ostream& out) {
		int n, m;
		in >> n >> m;
		int64_t sumAnswers = n * 1LL * m;
		int mx = 1000000;

		auto lp = linearSieve(mx);
		vector<int> mebius(mx + 1);
		mebius[1] = 1;
		for (int i: inclusiveRange(2, mx)) {
			if (lp[i] == lp[i / lp[i]]) {
				mebius[i] = 0;
			} else {
				mebius[i] = -mebius[i / lp[i]];
			}
		}

		auto a = make_vector<int>(2, 2, mx + 1, 0);
		for (int i: range(n)) {
			int x;
			in >> x;
			if (mebius[x])
				++a[0][(mebius[x] + 1) / 2][x];
		}

		for (int i: range(m)) {
			int x;
			in >> x;
			if (mebius[x])
				++a[1][(mebius[x] + 1) / 2][x];
		}

		auto& s = a;
		for (int k: range(2)) {
			for (int l: range(2)) {
				for (int i: inclusiveRange(1, mx)) {
					for (int j = i * 2; j <= mx; j += i) {

						s[k][l][i] += a[k][l][j];
					}
				}
			}
		}


		int64_t ans[2] = {0, 0};

		for (int i: range(2)) {
			for (int j: range(2)) {
				for (int k: inclusiveRange(1, mx)) {
						ans[i ^ j ^ 1] += 1LL * s[0][i][k] * s[1][j][k] * mebius[k];
				}
			}
		}

		out << ans[0] << ' ' << sumAnswers - ans[0] - ans[1] << ' ' << ans[1] << "\n";
	}
};

→ Ответить

perec1970

8 лет назад, # |

Как решать L и O из див2? (О квадрате из прямоугольников и о сокращении дроби). Спасибо.

→ Ответить

rsFalse

8 лет назад, # ^ |

L. Начиная с последних цифр изменять отдельно числитель и знаменатель дроби. Каждый раз когда они увеличиваються — упрощать (делить оба на 2, 3, 5, 7 <10, т.к. A[i] и B[i] < 10), пока дробь становиться неупрощаемой.

→ Ответить

perec1970

8 лет назад, # ^ |

← Rev. 3 →

Ничего не понял? Я вообще думал , что надо начиная снизу все время получать общие знаменатели и в конце вывести формулу. Но ничего не вышло.

→ Ответить

rsFalse

8 лет назад, # ^ |

Да, верно, так и надо. Только еще надо упрощать, например: 2/4 => 1/2.

→ Ответить

rsFalse

8 лет назад, # ^ |

O. Прямое решение: создать матрицу 301 x 301, заполненую 0. По двум осям (x, y) заполнить единичками. Далее рекурсия: 1) ищим уголки (в начале ровно один — x=1, y=1), 2) от каждого уголка засыпаем единичками прямоугольник двумя вариантами (повернутый и не). Посли засыпки 3 прямоугольников, проверяем от x=1, y=1 — засыпан ли квадрат.

→ Ответить

rsFalse

8 лет назад, # ^ |

← Rev. 2 →

К тому же перед посылкой забыл изменить 15 на 301, но получил AC. Потом взломал себя — код выдает YES на тест "3 3\n3 6\n9 6\n" и NO на "30 30\n30 60\n90 60\n".

→ Ответить

perec1970

8 лет назад, # ^ |

Поясните пожалуйста как Вы делаете заливку на входном тесте 8 2 1 6 6 7 с каких уголков?

→ Ответить

rsFalse

8 лет назад, # ^ |

Заливка с аналогичным тестом (ideone, Perl). Переберая все возможные уголки с поиском по рекурсие.

→ Ответить

g4_e5_f3

8 лет назад, # |

Как решалась задача P. No Triangles ?

→ Ответить

perec1970

8 лет назад, # ^ |

Надо вычеркнуть числа не являющиеся фиббоначи.

→ Ответить

perec1970

8 лет назад, # ^ |

1 2 3 4 5 6 вычеркиваем 4 и 6 ответ 2

→ Ответить

g4_e5_f3

8 лет назад, # ^ |

Спасибо. А почему именно их?

→ Ответить

g4_e5_f3

8 лет назад, # ^ |

Уже понял. Из-за неравенства треугольника. Рассмотрим самое большое число Фибоначчи — fib[i], которое меньше, либо равно n. Оно не может быть стороной треугольника, потому что оно равно сумме двух предыдущих чисел фибоначчи: fib[i-1], fib[i-2]. А все остальные суммы будут меньше. Поэтому мы переходим к числу fib[i-1] и повторяем рассуждения.

→ Ответить