| ENG RUS | Timus Online Judge |
Общий форум__Andrewy__ Idea // Задача 1615. Трамвайный пасьянс 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 Hououin`~`Kyouma Wa 25-27 // Задача 1863. Мирный атом 12 авг 2025 17:06 k = 1 datym suffix automaton // Задача 1713. Ключевые подстроки 11 авг 2025 16:07 ez Hououin`~`Kyouma Hint for Tl // Задача 1844. Лидер армии магов 11 авг 2025 12:45 Precalc + don't use set, use bitsets instead Hououin`~`Kyouma Hint for WA 2 and 5, that helped me // Задача 1844. Лидер армии магов 11 авг 2025 12:41 "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 ~'Yamca`~ WA 6 // Задача 1655. Сомалийские пираты 10 авг 2025 14:12 Problem with accuracy, you should print exactly 3 digit after dot ~'Yamca`~ hint/spoiler // Задача 2196. Апокалипсис 9 авг 2025 05:21 You can use sqrt-decomposition to find nearest point. It much easier than tangent, but slowly ~'Yamca`~ a little hint // Задача 1558. Periodical Numbers 8 авг 2025 11:53 period + preperiod always < 100, so you can use bruteforce:) Felix_Mate Help.Need in tests [1] // Задача 1387. Папа у Васи 30 апр 2016 13:48 WA21; My tests: N=9 =>286 N=13 =>12486 N=20 =>12826228 N=25 =>1142161275355632 N=33 =>13654755591665021157 ~'Yamca`~ Re: Help.Need in tests // Задача 1387. Папа у Васи 8 авг 2025 11:26 N=25 => 2067174645 N=33 => 7929819784355 0bla4ko`~ This test helped me // Задача 1202. Путешествие по прямоугольникам 7 авг 2025 20:22 3 0 0 6 8 6 -3 11 6 11 -3 21 0 Answer 21 Maxim Popkov WA Test 28 // Задача 1884. Путь к универу 7 авг 2025 04:30 Please, help!!! Tell me the test 28! ~'Yamca`~ WA 2 // Задача 1323. Одноклассники 5 авг 2025 08:50 if you use dp + bimatching your matching algo is wrong Axmed Beautiful accepted // Задача 1385. Интересное число 4 авг 2025 16:26 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! andreyDagger`~ If you don't understand how the figures produces // Задача 1442. Дымолётный порошок 4 авг 2025 15:33 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 Axmed Easy Accepted // Задача 1204. Идемпотенты 4 авг 2025 13:11 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. andreyDagger`~ WA 4 // Задача 1661. Додекаэдр 4 авг 2025 12:08 Rotations with cycles of length 2 actually have two fixed points grmmmely Whats 28 WA // Задача 1014. Произведение цифр 3 авг 2025 20:52 👑TIMOFEY👑`~ wa12 // Задача 1074. Очень короткая задача 1 авг 2025 16:32 maybe -0 0 -0 1 answer should be without -, i changed that and got ac Sergey How come there are solutions that are 0.015 sec and less than 0.1 sec [3] // Задача 2130. Алиса + Боб 18 янв 2020 20:35 my solution is the following: start with least common multiple = 1 make char array of 1000 000 to track forbidden divisors let div be the divisor and ans the answer if ans == 1 make new lcm of the previous lcm and current divisor. if it is over 10^12 - fail. find all the divisors of div, check that they are not forbidden in the forbidden array if ans == 0 - check if lcm is divisible by the divisor and fail if it is. complexitiy O(n * sqrt(1000000)) (sqrt from the "find all divisors) my solution gets 0.5 sec (using cin,cout with tie(null)) what is the solution that gets less than 0.1 sec? Is there any hint? soldSoulToTheGame Re: How come there are solutions that are 0.015 sec and less than 0.1 sec // Задача 2130. Алиса + Боб 27 май 2024 15:51 no need to find all divisors. u can just use lcm and mod operations. i can send you easy solution if u r still interested 👑TIMOFEY👑`~ Re: How come there are solutions that are 0.015 sec and less than 0.1 sec [1] // Задача 2130. Алиса + Боб 12 июл 2024 13:38 need to pray to god for quick solutions #pragma GCC optimize("Ofast") #pragma GCC optimize(O3) #pragma comment(linker, "/stack:200000000") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("profile-values,profile-reorder-functions,tracer") #pragma GCC optimize("vpt") #pragma GCC optimize("rename-registers") #pragma GCC optimize("move-loop-invariants") #pragma GCC optimize("unswitch-loops") #pragma GCC optimize("function-sections") #pragma GCC optimize("data-sections") #pragma GCC optimize("branch-target-load-optimize") #pragma GCC optimize("branch-target-load-optimize2") #pragma GCC optimize("btr-bb-exclusive") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") ~'Yamca`~ Re: How come there are solutions that are 0.015 sec and less than 0.1 sec // Задача 2130. Алиса + Боб 31 июл 2025 19:45 amin datym suffix automaton // Задача 1769. Старая уральская легенда 30 июл 2025 20:33 ez
|