TopCoder

Thumb a
中數理論
「因為時間與空間獨立,這些時空的聯合分布可以透過貝氏定理,找出先後的條件機率,並透過微積分找出體用的相對機率,即 PDF/PMF 或 CDF。」

User's AC Ratio

66.7% (8/12)

Submission's AC Ratio

25.2% (28/111)

Description

「上下因心」是現今世上最古老的世家之一,素有東方神秘力量的美名。每代會有三位家主共治著整個世家,而成為家主的人將捨棄過去的名字,從上一代家主手中接下傳承至今的家主名諱:上恩、下恩、以及卡恩。

每年五月十四日的時候,當代家主們會齊聚一堂,舉行名為「番茄大戰爭」的儀式。但數百年前一場離奇的木能寺大火,使所有典籍付之一炬。儀式究竟從何而來,其原理及意義又是什麼如今已無人理解。人們只知道,在儀式中上恩會和下恩決鬥$ T$ 回合的猜猜拳。每回合勝利的一方將吃下一顆番茄,但如果兩者平手的話,將由卡恩吃下一顆番茄。

猜猜拳的決鬥方式為兩人感受東方神秘力量的指示,之後同時出示「剪刀、石頭、布」其中一種手勢,如果手勢相同的話視為平手,不同的話則依石頭砸爛剪刀、剪刀剪破布、布包住石頭的相生相剋規則決定勝利的一方。

在無數次的儀式中人們也漸漸從看似雜亂無章的出拳中歸納出了一些規律。人們發現,上恩跟下恩的出拳其實會不斷循環一個特定的模式。假設上恩的出拳模式為「石頭、剪刀、布」的話,那他在第一回合會出石頭,第二回合出剪刀,第三回合出布,第四回合又開始出石頭,依此類推。

由於要吃下番茄的量可能非常巨大,家主們需要事先開闢好足夠大的異次元胃袋。他們特地聘請你來根據上恩與下恩的出拳模式,預測三位家主分別需要吃下幾顆番茄。

Input Format

測試資料共包含三行,依序為 $T, A, B$。

其中正整數 $T$ 代表決鬥的總回合數,而字串 $A, B$ 則分別代表上恩及下恩的出拳模式,模式字串中的字元S,R,P分別代表剪刀、石頭、布。

  • $1\leq T\leq 10^ 9$
  • $1\leq \lvert A\rvert, \lvert B\rvert \leq 10^ 6$
  • $A, B$ 僅包含 S,R,P 三種字元

Output Format

請輸出三個整數於一行,依序為上恩、下恩及卡恩將在番茄大戰爭中吃下的番茄個數。

Sample Input

Sample Input #1
9
S
PRPR

Sample Input #2
100
PPSP
RSP

Sample Output

Sample Output #1
5 4 0

Sample Output #2
35 33 32

Hints

Problem Source

2016 NPSC高中組決賽

Subtasks

No. Testdata Range Score
1 0~99 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 1
6 1000 262144 262144 1
7 1000 262144 262144 1
8 1000 262144 262144 1
9 1000 262144 262144 1
10 1000 262144 262144 1
11 1000 262144 262144 1
12 1000 262144 262144 1
13 1000 262144 262144 1
14 1000 262144 262144 1
15 1000 262144 262144 1
16 1000 262144 262144 1
17 1000 262144 262144 1
18 1000 262144 262144 1
19 1000 262144 262144 1
20 1000 262144 262144 1
21 1000 262144 262144 1
22 1000 262144 262144 1
23 1000 262144 262144 1
24 1000 262144 262144 1
25 1000 262144 262144 1
26 1000 262144 262144 1
27 1000 262144 262144 1
28 1000 262144 262144 1
29 1000 262144 262144 1
30 1000 262144 262144 1
31 1000 262144 262144 1
32 1000 262144 262144 1
33 1000 262144 262144 1
34 1000 262144 262144 1
35 1000 262144 262144 1
36 1000 262144 262144 1
37 1000 262144 262144 1
38 1000 262144 262144 1
39 1000 262144 262144 1
40 1000 262144 262144 1
41 1000 262144 262144 1
42 1000 262144 262144 1
43 1000 262144 262144 1
44 1000 262144 262144 1
45 1000 262144 262144 1
46 1000 262144 262144 1
47 1000 262144 262144 1
48 1000 262144 262144 1
49 1000 262144 262144 1
50 1000 262144 262144 1
51 1000 262144 262144 1
52 1000 262144 262144 1
53 1000 262144 262144 1
54 1000 262144 262144 1
55 1000 262144 262144 1
56 1000 262144 262144 1
57 1000 262144 262144 1
58 1000 262144 262144 1
59 1000 262144 262144 1
60 1000 262144 262144 1
61 1000 262144 262144 1
62 1000 262144 262144 1
63 1000 262144 262144 1
64 1000 262144 262144 1
65 1000 262144 262144 1
66 1000 262144 262144 1
67 1000 262144 262144 1
68 1000 262144 262144 1
69 1000 262144 262144 1
70 1000 262144 262144 1
71 1000 262144 262144 1
72 1000 262144 262144 1
73 1000 262144 262144 1
74 1000 262144 262144 1
75 1000 262144 262144 1
76 1000 262144 262144 1
77 1000 262144 262144 1
78 1000 262144 262144 1
79 1000 262144 262144 1
80 1000 262144 262144 1
81 1000 262144 262144 1
82 1000 262144 262144 1
83 1000 262144 262144 1
84 1000 262144 262144 1
85 1000 262144 262144 1
86 1000 262144 262144 1
87 1000 262144 262144 1
88 1000 262144 262144 1
89 1000 262144 262144 1
90 1000 262144 262144 1
91 1000 262144 262144 1
92 1000 262144 262144 1
93 1000 262144 262144 1
94 1000 262144 262144 1
95 1000 262144 262144 1
96 1000 262144 262144 1
97 1000 262144 262144 1
98 1000 262144 262144 1
99 1000 262144 262144 1