TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (8/8)

Submission's AC Ratio

78.8% (26/33)

Tags

IMO

Description

建康中學(簡稱建中)是傳說中的「千湖中學」。既然處處都是湖,自然就會有青蛙囉!

在建中裡,有$n$隻青蛙,每隻青蛙都想要在一條直線上跳躍,從直線的一端跳到另一端。除此之外,這$n$條直線中沒有平行的線,也沒有共點的三條線。然而中間是個汪洋大湖,所以他們在湖中只能停在石頭上(在任兩條直線的交點處都會有一顆石頭)。

有一天,這$n$隻青蛙突發奇想,想來跳一支舞。為了完成這支舞,這$n$隻青蛙必須從他們所在的直線的某一端,整齊劃一地跳到另一端。具體地說,每過一拍,每隻青蛙都要跳到下一顆石頭,直到跳到另一端為止。

當然,如果有兩隻青蛙同時停在同一個石頭上,其中一隻青蛙就會被擠到水裡,舞就跳不成了。因此這$n$隻青蛙想找出所有的跳法,使得任兩隻青蛙都不會同時停在同一個石頭上。

Input Format

第一行有一個正整數$2\leq n\leq 10^ 4$,代表青蛙的個數。
接下來的$n$行中每行都有兩個絕對值不超過$10^ 4$的整數$a,b$以及一個絕對值不超過$10^ 8$的整數$c$, 其中$b\neq 0$,代表有一隻青蛙要在直線$ax+by=c$上跳躍。

子任務(測資) 額外限制 分數
1 (0~4) $n\leq 15$ 15
2 (5~9) $n$是偶數 25
3 (0~14) 30
4 (0~19) 時限縮短 30

Output Format

第一行請輸出一個非負整數,代表所有滿足題目條件的跳法有幾種。
若第一行的數字非零,請在第二行輸出長度為$n$的01字串,代表其中一種可行的方法。其中第$i$個位置是0代表第$i$隻青蛙要從直線的左端開始往右跳,是1代表要從右端開始往左跳。

Sample Input

Sample Input 1
2
1 1 1
1 2 3

Sample Input 2
5
1 1 1
2 -1 5
1 2 7
2 -5 6
29 -1 87

Sample Output

Sample Output 1
0

Sample Output 2
2
01100

Hints

範例測資2的一個可行方案如下:

Problem Source

Problem/Description by Paupière
改編自2016 IMO P6

Subtasks

For Testdata: 0 ~ 4, Score: 15
For Testdata: 5 ~ 9, Score: 25
For Testdata: 0 ~ 14, Score: 30
For Testdata: 0 ~ 19, Score: 30
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144
13 1000 65536 262144
14 1000 65536 262144
15 50 65536 262144
16 50 65536 262144
17 50 65536 262144
18 50 65536 262144
19 50 65536 262144