4
lessonk lessonk lessonk lessonk lessonk
Tuesday 1
tententen lollollol yeah yeah kkk
Thursday 1
sevenll four thr haha
Saturday 1
twostrings yeah
Thursday 3

Hi, I writed this post because I wanted to share with you some of the test cases* that helped me a lot at the time. I hope it helps you :)

--> Test 1:

1
A B C

--> Answer:

A undefined
B undefined
C undefined

------------------------------

--> Test 2:

5
Isenbaev A B
A B C
D Q P
C H N
G N P

--> Answer:

A 1
B 1
C 2
D 5
G 4
H 3
Isenbaev 0
N 3
P 4
Q 5

------------------------------

--> Test 3:

13
Fominykh Isenbaev BBB
BBB CCC AAA
Ayzenshteyn Oparin Samsonov
Ayzenshteyn Chevdar Samsonov
Dublennykh Fominykh Ivankov
Burmistrov Dublennykh Kurpilyanskiy
Cormen Leiserson Rivest
Oparin AA AAA
Isenbaev Oparin Toropov
AA DD PP
PP QQ RR
RR SS TT
TT Toropov Oparin

--> Answer:

AA 2
AAA 2
Ayzenshteyn 2
BBB 1
Burmistrov 3
CCC 2
Chevdar 3
Cormen undefined
DD 3
Dublennykh 2
Fominykh 1
Isenbaev 0
Ivankov 2
Kurpilyanskiy 3
Leiserson undefined
Oparin 1
PP 3
QQ 4
RR 3
Rivest undefined
SS 3
Samsonov 2
TT 2
Toropov 1

------------------------------

--> Test 4:

3
Isenbaev A B
A B C
A Q W

--> Answer:

A 1
B 1
C 2
Isenbaev 0
Q 2
W 2

------------------------------

*(All test cases were made by other users, so you'll probably found them in other Posts/Topics/Discussions).

Acknowledgments to:
-> "Vit Demidenko" & "Nathalie"
-> "Pavel Nikolov"
-> "mccolt89"
-> "Megakrit"


-How I solved it:

I solved this problem in Java, for that, I used:

->1 java.util.Scanner
->1 java.util.HashMap
->1 java.util.TreeMap
->3 java.util.HashSet
->1 java.util.LinkedList
->? java.util.StringTokenizer (or you can just simply use the Scanner method "next()").

(The structures can be declared inside loops or other structures).

Hope all this helped you :)


Edited by author 08.04.2020 00:48

Edited by author 08.04.2020 00:49

New tests were added. 192 authors lost AC.

#include<stdio.h>
#include<math.h>
int main(){
    unsigned long long int a,b,c,d;
    double Sqrt,Sqrt1,Sqrt2,Sqrt3;
scanf("%llu %llu %llu %llu",&a,&b,&c,&d);
Sqrt=sqrt(a);
Sqrt1=sqrt(b);
Sqrt2=sqrt(c);
Sqrt3=sqrt(d);



printf(" %0.4lf %0.4lf %0.4lf %0.4lf",Sqrt,Sqrt1,Sqrt2,Sqrt3);
}


Edited by author 23.06.2022 13:46

Edited by author 23.06.2022 13:46

Edited by author 03.09.2025 07:41

Edited by author 02.09.2025 23:40

Edited by author 01.09.2025 23:44

use iterative segment tree

My Accepted solution got wrong answer on test:

10 3
1 1 6
??????????

My output: X?X?XXXXXX
Correct output: X.X.XXXXXX

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

k = 1

ez

Precalc + don't use set, use bitsets instead

"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

Problem with accuracy, you should print exactly 3 digit after dot

You can use sqrt-decomposition to find nearest point. It much easier than tangent, but slowly

period + preperiod always < 100, so you can use bruteforce:)

WA21;
My tests:
N=9 =>286
N=13 =>12486
N=20 =>12826228
N=25 =>1142161275355632
N=33 =>13654755591665021157

3
0 0 6 8
6 -3 11 6
11 -3 21 0

Answer
21

Please, help!!! Tell me the test 28!