TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (17/17)

Submission's AC Ratio

33.0% (35/106)

Tags

Description

近年來由於空氣汙染以及光害,人們在城市裡是越來越難看到滿天的星星了。

然而,曉涵跟她的同學一直很想親眼目睹那傳說中的滿天星斗,體驗看看古人說的「天階夜色涼如水,坐看牽牛織女星」的感覺,

於是,她們決定利用假日的空閒,找幾天沒事的日子一起去曉涵鄉下老家的山上看星星。

經過了漫長的返鄉之路後,他們終於到了距離繁榮的大都市盡百公里遠的地方 ( 沒辦法,台灣的幅員不大... ) ,

在跟鄉下的表弟、表妹以及眾親戚邊吃晚飯邊述說完城市的繁榮情景以及快速的生活步調後,他們終於要到鄰近的山上看星星了~

在表弟妹們以及她大伯的帶路下,曉涵跟她的同學總算是到了山頂,
在地上鋪了個涼蓆後,總算可以好好欣賞這片在城市裡所看不到的美麗星空!

當她們坐在涼蓆上抬頭仰望時,不禁大聲讚嘆,原來這世界上還有這麼美的夜空!

此時,曉涵發現,星星的位置大多雜亂無章,沒有特定的規律可循 (當然XD) ,但是,她卻注意到,有些星星的位置好像呈一直線,
( 此指三個星星以上連成一線的情況 ) 而在她所能看見的範圍內,她發現有不少星星可以用一條線連起來!!

而在她觀察到這個現象的同時,她一個正在念國小的表妹則發現,
這些天上的星星好像可以連成一個個的她在數學課剛學到的形狀── 三角形!!
於是她想要算算看在這片星空中的星星總共可以形成幾個三角形!

無奈天上的星星實在太多,一組組數很難數,
而且也不能確認一樣的組合剛剛是否已經算過了,曉涵知道這件事後,決定請你幫幫她,求出這片星空中總共有幾個三角形。

Input Format

輸入可能包含多筆測試資料,

每筆測試資料的

第一行有一個正整數 N ( N <= 1,000,000 ) 代表這片星空中共有幾顆星星是你可以看見的;

第二行有一個正整數 M ( 0 <= M < N ) 代表曉涵總共看到了幾組星星是共線的,

接下來有 M 行,每行有一個正整數 Ki,
代表這星空中的第 i 組共線的星星是由 Ki 顆星星構成的 ( 3 <= Ki <= N )。

每組測試資料之間會有一行空白行隔開兩組測試資料,當 N = 0 的時候代表輸入結束。( 聰明的你不會對這組資料做處理 )

Output Format

對於每一筆測試資料,請輸出一個正整數代表總共能構成幾個三角形。

如果給的條件不足以構成任何一個三角形,或是根本不可能發生這種情況,則請輸出 "IMPOSSIBLE" ( 不含雙引號 ) 。

Sample Input 1

4
1
3

3
1
3

0

Sample Output 1

3
IMPOSSIBLE

Hints

在本題中所謂的共線的「線」是無限延長的,所以不會有 A B C D 一直線卻分做好幾組三點共線來處理這種情形,
一律直接視為是「四點」共線,你可以假設所有的測試資料全部都符合這個規則。

Problem Source

原TIOJ1438 / Problem setter:SKYLY

Subtasks

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4
4 1500 65536 262144 5
5 1500 65536 262144 6