Решение задач
Товарищи! Давайте делится своими идеями решения задач на последних срмах. Я думаю, что немногие могут решить все три задачи 1-го дивизиона. А зачем ждать, пока на топкодере напишут problem set & analyses к последнему контесту? К тому же, всегда в чужих решениях можно открыть для себя что-то новое :)
Лучше расскажи, как 1000 решать. Или, хотя бы, как сэмплы получаются.
500-я упала, потому что люди в большинстве своем не умеют писать динамику. Один фраг я увидел два параметра (а я умею за 4), другой - вообще жадность была написана.
1000-я
две-три минуты медитируем и выводим формулу
ans = n * sum(i=0;i<k;i++)(1/(n - i))
или
ans=n * (harm(n) - harm(n - k))
где
harm(n)=sum(i=1;i<=n;i++)(1/i)
теперь считаем harm(n) с помощью Тэйлора (видимо, для больших n), говорят - достаточно 2-х слагаемых, у Пети в решении было то ли 6, то ли 8. Еще отдельно обработать случай, когда harm(n)~=harm(n-k), Потому что два близких числа вычитать днем нельзя. (У меня есть подозрение, что это случается только при маленьких k, т.е. можно считать по самой верхней формуле)
Ну, если они решали так как я, то могли возникнуть следующие проблемы:
1). При извлечении корня i-ной степени из N функця pow возвращает вещественное число. При приведении его к типу int могли случится проблемы округления, но можно было прибавить 0.5 к числу и оно бы округлилось правильно. Если же извлекать корень посредством бин. поиска, то может случится переполнение (если например корень из большого числа возводить в степень > 2).
Вариант 1. Нам нужно подсчитать a = min(a * b, 2e18), так?
if ((ll)2e18 / a < b)
a = (ll2e18;
else
a = min((ll)2e18, a*b);
Вариант 2. Подсчитать степень по модулю и в long double. Если второе почему-то больше 2e18, значит мы взяли чуть больше, чем надо.
Олег, спасибо большое!
пересекаем окружность единичного радиуса с прямой на плоскости xOy, находим t1, t2 - время пересечения
потом смотрим, где окажутся спираль и прямая в 3-ем измерении в точках со временем t1 и t2
ну еще частный случай, когда прямая проходит перпендикулярно окружности :)
Точка (x,y) покрываемая многоугольником будет хорошей если существует точка (x+a(n-1), y+b(n-1)), которая тоже покрывается многоугольником.
То есть - если существует точка со сравнимыми координатами по модулю n-1.
Можно посчитать все хорошие точки за O(500000):
Разобьем все x от 0 до 10000 на классы эквивалентности по модулю n-1
Для каждого такого класса эквивалентности делаем следущее:
для каждого x в нем проходимся от минимального до максимального допустимого y и запоминаем в массив y%(n-1).
Потом смотрим какие y mod (n-1) встретились >1 раза эти точки и надо учитывать
еще надо отдельно учесть случаи когда в столбце >=n точек (чтобы не посчитать дважды одну и тужу точку)
Только сейчас закодил и сдал. Идея с классами эквивалентности оч красивая.
А вообще такая идея, наверное, рождается у каждого. У каждого, кто не прочитал сразу ограничения =D
Task
John and Brus often visit a forest not far from their home. There are N beautiful glades and N-1 two-way footpaths in the forest. Each footpath connects two glades. Also it’s possible to get from any glade to any other using footpaths. Thus there is exactly one simple path (i.e. path that consists of distinct glades) from one glade to another. Guys will visit the forest for M successive days. Before the first day there are Fi very beautiful flowers growing on i-th glade. At the beginning of each day one additional flower will appear on each glade. After that John and Brus will either pick all the flowers on a glade or calculate the number of flowers on the simple path between two glades inclusive.
Input
The first line contains single integer T – the number of test cases. Each test case starts with a line containing integers N and M. The following line contains N integers Fi. Each of next N-1 lines contains integers Ai and Bi - the glades connected by i-th footpath. Each of next M lines starts with a single character (‘P’ or ‘C’). If it is ‘P’ then it will be followed by integer Gi and it means that on i-th day guys will pick all the flowers on glade Gi. Otherwise ‘C’ character will be followed by integers Ui and Vi. In this case John and Brus will calculate the number of flowers on a simple path between glades Ui and Vi inclusive. All the integers in a single line are separated by single spaces.
Output
For each test case and for each calculation print a single line containing desired number of flowers.
Constrains
Time Limit: 12 sec, memory limit: 65 mb
1 ≤ T ≤ 47
1 ≤ N, M ≤ 100000 (10^5)
0 ≤ Fi ≤ 1000000000 (10^9)
1 ≤ Ai, Bi, Gi, Ui, Vi ≤ N
Sample input
2
2 3
4 7
1 2
C 1 2
P 2
C 1 2
1 1
100
C 1 1
Sample output
13
8
101
Task
John and Brus are practicing multiplying integer numbers. There are N distinct integers written down and each time they choose some subset and try to calculate the product of all the numbers in this subset. Sometimes the result they got is the square of some integer number. You have to calculate the number of nonempty subsets where the product of the numbers is the square of some integer number.
Input
The first line contains single integer T – the number of test cases. Each test case starts with a line containing the integer N - the number of integers written down. The next line contains N integers Ai separated by single spaces.
Output
For each test case print a single line containing the number of desired subsets.
Constrains
time limit: 12 sec, memory limit: 65 mb
1 ≤ T ≤ 47
1 ≤ N ≤ 1000
1 ≤ Ai ≤ 1000
All Ai will be distinct.
Sample input
2
4
3 6 2 1
3
4 9 16
Sample output
3
7
ANY HELP WILL BE APPRECIATED
1000 - действительно диаграмма Вороного, но ограничения такие что хоть за пятую степень решать можно