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

No. Testdata Range Score
1 0~4 15
2 5~9 25
3 0~14 30
4 0~19 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 3 4
1 1000 65536 262144 1 3 4
2 1000 65536 262144 1 3 4
3 1000 65536 262144 1 3 4
4 1000 65536 262144 1 3 4
5 1000 65536 262144 2 3 4
6 1000 65536 262144 2 3 4
7 1000 65536 262144 2 3 4
8 1000 65536 262144 2 3 4
9 1000 65536 262144 2 3 4
10 1000 65536 262144 3 4
11 1000 65536 262144 3 4
12 1000 65536 262144 3 4
13 1000 65536 262144 3 4
14 1000 65536 262144 3 4
15 50 65536 262144 4
16 50 65536 262144 4
17 50 65536 262144 4
18 50 65536 262144 4
19 50 65536 262144 4