- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;++i)
#define forn(i, n) for(int i=0;i<n;++i)
#define forv(it, v) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define fst first
#define snd second
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef string st;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
const ld pi = acos(-1.0);
const ll infl = 1000ll * 1000ll * 1000ll * 1000ll * 1000ll * 1000ll;
const ld eps = 1e-7;
#define y1 y1_dhs
В продолжении предыдущего ГК: типичное начало олимпиадной проги на С++.
Follow us!
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
Разумеется, выражения для вывода типов в обратную сторону должны соответствовать некоторым правилам.
Например, можно сделать так, что выражения x
let x = 1 + 2 * 3
станет типа AstNode со значением
(Op Plus (Const 1) (Op Mul (Const 2) (Const 3))
например:
float x = 1.0; // тут выводится, что float
auto y = x*(2.0+3.0); // тут через ветку x распространяется на прочие ветки, что это float;
При наличии хитрых перегрузок не работает.
Грубо говоря, работает только в ветках, внутри которых все функции монотипны (т.е. все аргументы принимают одного типа и возвращают того же типа).
long double operator "" _ld(long double value) {
return value;
}
1.0_ld будет long double.
и функции определять как:
template <typename T>
std::enable_if<std::is_floating_point<T> ::value, T> func(T value) { ... }
Такая функция вернет значение передаваемого в неё аргумента типа с плавающей точкой.
Правда, некоторые люди в оргкомитетах настолько сильно любят питон, что вымеряют ограничения по времени и памяти по решению на нём.
>> либо задача будет решаемой на питоне и в то же время решаемой в лоб на си,
А что, си у нас уже не полны по Тьюрингу?
Полнота по Тьюрингу не имеет никакого отношения к сабжу
(в силу быстродействия)
То есть питон не полон по Тьюрингу?
Типичной гонялке тестов наплевать, что у тебя. Ты сабмитишь только код, он выполняется в заранее оговоренной (версии компиляторов, флажки компилиции и т.п.) изолированной среде.
PyPy поможет тебе разве что в Google Code Jam - там тебе на своей машине тесты надо запускать, а судья принимает только файл с ответами.
> const ll infl = 1000ll * 1000ll * 1000ll * 1000ll * 1000ll * 1000ll;
Тяжелый случай.
"дано 2015 х..."
А я думал, это хак такой, который позволяет решить некоторые задачи без длинной арифметики, с высокой вероятностью.
Заменяем LongInt c долгими арифметическими операциями на ModuleInt с относительно быстрыми:
Деление тоже прекрасно запиливается. Но не так тривиально.
Если P простое :) А так да, расширенный алгоритм Евклида.
Если делитель и P взаимно-простые, емнип. Или я туплю?
Да нет, всё так. Просто модуль P обычно известно в компайл-тайме, а делитель известен только в рантайме.
К счастью, задачки обычно построены так, что деления не нужно, только сложение и умножение.
и сортировкой пузырьком
Да можно ещё проще - средним арифметическим джвух int'ов.
Очевидно, что среднее арифметическое двух int'ов влезает в int. Нужно написать функцию, которая его возвращает :)
Кстати, мы в школе проходим эту ошибку.
В 99.9% случаев в бинпоиске все числа неотрицательные и b > a, поэтому можно смело писать a + (b - a) / 2.
А если в программе есть массив на миллиард элементов, по которому делается бинпоиск, то, наверно, чинить надо не среднее, а крышу.
Но под каждую платформу придётся решать её заново...
В противном случае разобрать два варианта, и либо вернуть a + (b - a) / 2, либо (a + b) / 2
Но я не втупляю в разговор двух господ - мистера Г и мистера Б
Вариант 2: a+b переполняется. Тогда надо вернуть a + (b-a)/2, так как b-a в таком случае не переполняется.
Для проверки на переполняемость можно, например, посмотреть старший бит (a>>1)+(b>>1)+(a&b&1)
P.S. А вообще - на всяких собеседованиях специально вопрос задают в размытой форме, чтобы ты спросил "а как вернуть среднее арифметическое 1 и 2". Если спросил - получишь плюсик в карму. Так что всё ок.
> a/b/c % p != a / (bc) % p
Да ну? Пример в студию или слив засчитан (для b, c, bc взаимнопростых с p само собой).
Если так, то сливаюсь.
У них нет цели писать красивый код. Им надо быстро реализовать алгоритм, часто стандартный но с небольшими отклонениями.
Олимпиадное программирование это как олимпиадная математика - с реальными задачами пересекается редко.
так у нас нет цели собирать красивый код. Это говнокод. От слова говно. Секешь?