Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
No subject | Electron31 | 1011. Кондукторы | 3 сен 2025 07:38 | 1 |
Edited by author 03.09.2025 07:41 |
solved | Andre Marin C# | 1100. Таблица результатов | 2 сен 2025 22:44 | 1 |
solved Andre Marin C# 2 сен 2025 22:44 Edited by author 02.09.2025 23:40 |
solved | Andre Marin C# | 1139. Городские кварталы | 1 сен 2025 23:26 | 1 |
solved Andre Marin C# 1 сен 2025 23:26 Edited by author 01.09.2025 23:44 |
TLE? | Nisikto | 1846. НОД 2010 | 29 авг 2025 14:31 | 1 |
TLE? Nisikto 29 авг 2025 14:31 use iterative segment tree |
ADMINS, PLEASE ADD NEW TESTS (tests are weak) | Oleg Vasilenko (Chelyabinsk) | 1508. Японский кроссворд | 24 авг 2025 14:10 | 1 |
My Accepted solution got wrong answer on test: 10 3 1 1 6 ?????????? My output: X?X?XXXXXX Correct output: X.X.XXXXXX |
Idea | __Andrewy__ | 1615. Трамвайный пасьянс | 12 авг 2025 22:26 | 1 |
Idea __Andrewy__ 12 авг 2025 22:26 1) Посмотрим, как выглядят плохие расстановки. Тогда ответ = количество хороших расстановок / количество всех расстановок. Обозначим расстановки карт как x = x_1 x_2 ... x_2n. 2) Количество всех расстановок (2n)! 3) Как выглядят плохие расстановки, те когда пасьянс в конце будет содержать >=3 карт? Чтобы нельзя было сделать ход, нужно чтобы суффикс имел вид (1) ai * bj либо (2) bi * aj, где i != j, а * - любая карта. Заметим, что если какой-то суффикс x после всех просеиваний переходит в один из таких видов, то пасьянс не сойдётся. Можно доказать обратное: если никакой суффикс x при просеиваниях не перейдёт в (1) или (2), то пасьянс сойдется. 4) Из 3) можно построить все плохие расстановки. Они будут иметь вид: x_1 ... x_[2n-3] bj x_[2n-1] ai x_1 ... x_[2n-4] bj a_l1 a_l2 ai x_1 ... x_[2n-5] bj a_l1 a_l2 a_l3 ai x_1 ... x_[2n-5] bj a_l1 a_l2 a_l3 a_l4 ai ... Здесь bj, ai, a_l1, a_l2, ... - выбранные карты (j != i), x_k - оставшиеся карты. Аналогично к плохим расстановкам будут относится все с заменой местами bj и ai (вместо a_l1, a_l2, ... будут b_l1, b_l2, ...). Первых расстановок ровно 2n*(n-1)*(2n-2)! Вторых расстановок 2n*(n-1)*(n-1)*(n-2)*(2n-4)! = 2n*(n-1)*(n-1)! * (2n-4)! Третьих расстановок 2n*(n-1)*(n-1)*(n-2)*(n-3)*(2n-5)! = 2n*(n-1)*(n-1)! / 2! * (2n-5)! Четвертых расстановок 2n*(n-1)*(n-1)*(n-2)*(n-3)*(n-4)*(2n-6)! = 2n*(n-1)*(n-1)! / 3! * (2n-6)! И т.д. до n+1. Итого плохих расстановок bad_cnt = 2n*(n-1)*(2n-2)! + 2n*(n-1)*(n-1)! * sum((2n-k)!/(n-k+1)!), k=4,...,n+1 good_cnt = (2n)! - bad_cnt d = gcd(good_cnt, (2n)!) Ответ = (good_cnt / d, (2n)! / d) PS: надеюсь не опечатался Тесты: (2, '2/3') (3, '8/15') (4, '13/28') (5, '19/45') (6, '13/33') (7, '34/91') (8, '43/120') (9, '53/153') (10, '32/95') (11, '76/231') (12, '89/276') (13, '103/325') (14, '59/189') (15, '134/435') (16, '151/496') (17, '169/561') (18, '94/315') (19, '208/703') (69, '2483/9453') (100, '5149/19900') (666, '111388/443223') (1234, '381614/1522139') (10000, '50014999/199990000') (100000, '5000149999/19999900000') Edited by author 12.08.2025 22:29 |
Wa 25-27 | Hououin`~`Kyouma | 1863. Мирный атом | 12 авг 2025 17:06 | 1 |
Wa 25-27 Hououin`~`Kyouma 12 авг 2025 17:06 |
suffix automaton | datym | 1713. Ключевые подстроки | 11 авг 2025 16:07 | 1 |
|
Hint for Tl | Hououin`~`Kyouma | 1844. Лидер армии магов | 11 авг 2025 12:45 | 1 |
Precalc + don't use set, use bitsets instead |
Hint for WA 2 and 5, that helped me | Hououin`~`Kyouma | 1844. Лидер армии магов | 11 авг 2025 12:41 | 1 |
"You have to determine whether such a stupid DEFEAT is possible." NOT a victory, but a DEFEAT. Edited by author 11.08.2025 12:41 |
WA 6 | ~'Yamca`~ | 1655. Сомалийские пираты | 10 авг 2025 14:12 | 1 |
WA 6 ~'Yamca`~ 10 авг 2025 14:12 Problem with accuracy, you should print exactly 3 digit after dot |
hint/spoiler | ~'Yamca`~ | 2196. Апокалипсис | 9 авг 2025 05:21 | 1 |
You can use sqrt-decomposition to find nearest point. It much easier than tangent, but slowly |
a little hint | ~'Yamca`~ | 1558. Periodical Numbers | 8 авг 2025 11:53 | 1 |
period + preperiod always < 100, so you can use bruteforce:) |
Help.Need in tests | Felix_Mate | 1387. Папа у Васи | 8 авг 2025 11:26 | 2 |
WA21; My tests: N=9 =>286 N=13 =>12486 N=20 =>12826228 N=25 =>1142161275355632 N=33 =>13654755591665021157 N=25 => 2067174645 N=33 => 7929819784355 |
This test helped me | 0bla4ko`~ | 1202. Путешествие по прямоугольникам | 7 авг 2025 20:22 | 1 |
3 0 0 6 8 6 -3 11 6 11 -3 21 0 Answer 21 |
WA Test 28 | Maxim Popkov | 1884. Путь к универу | 7 авг 2025 04:30 | 1 |
Please, help!!! Tell me the test 28! |
WA 2 | ~'Yamca`~ | 1323. Одноклассники | 5 авг 2025 08:50 | 1 |
WA 2 ~'Yamca`~ 5 авг 2025 08:50 if you use dp + bimatching your matching algo is wrong |
Beautiful accepted | Axmed | 1385. Интересное число | 4 авг 2025 16:26 | 1 |
We have number n = a * (10 ^ n) + b. n mod a = 0 and n mod b = 0 If n mod a = 0 that b mod a = 0. If n mod b = 0 that a * (10 ^ n) mod b = 0 We have now b mod a = 0 a * (10 ^ n) mod b = 0 Ok, now let's imagine b = k * a. First condition is fulfilled. a * (10 ^ n) / (k * a) = 10 ^ n / k K is divider of 10 ^ n. Let's note that k is less then 10. Why? Because a * 10 have n + 1 digit but b must have n digit. Now for all 1 <= k <= 9 and 10^n mod k = 0 we calculate how many good numbers a we can use, a * k must have n digit that 10 ^ (n - 1) <= a <= (10 ^ n - 1) // k. Sum of all good ways to choose a and k is answer! |
If you don't understand how the figures produces | andreyDagger`~ | 1442. Дымолётный порошок | 4 авг 2025 15:33 | 1 |
Let l="line which connects top corner of cone and one of the points on the corner of base" Also a="angle between 'l' and surface" A line is drawn on the surface with distance d to the center of cone. Then two 2d planes are drawn through this line. The angle between plane and surface is equal to 'a'. These planes are directed in the opposite angles. Set of points that are in the cone and between these 2d planes will fall in the slit |
Easy Accepted | Axmed | 1204. Идемпотенты | 4 авг 2025 13:11 | 1 |
At first N = p * q, let's find this prime numbers p and q. Now we have x * x = x mod N. x * x - x = 0 mod N x * (x - 1) = 0 mod N Let's note that x != pq, because x < n. That means x mod p = 0, x - 1 mod q = 0 or x mod q = 0, x - 1 mod p = 0. Consider { x mod p = 0 x mod q = 1 } another case is symmetrical. x = k * p, because x mod p = 0. Now we have k * p mod q = 1 k = 1 / p mod q k = p ^ (-1) mod q Use Fermat's little theorem k = p ^ (q - 2) mod q. We find x = k * p, problem is solved. |