Start

2017-03-18 02:00 AKDT

Beta 2017

End

2017-03-18 08:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1313 days 5:36:30

Time elapsed

6:00:00

Time remaining

0:00:00

Problem D
Önnur tilgáta Goldbachs

Heiltalan $P$ er kölluð frumtala ef einu heiltölurnar sem ganga upp í hana eru $1$ og $p$ sjálf. Til dæmis er $20$ ekki frumtala, því heiltalan $5$ gengur upp í hana. Aftur á móti er $11$ frumtala, því aðeins $1$ og $11$ ganga upp í $11$.

Fræg tilgáta um frumtölur er Tilgáta Goldbachs, en hún segir:

Allar sléttar heiltölur stærri en $2$ er hægt að tákna sem summu tveggja frumtalna.

Þessi tilgáta er frá árinu 1742. Enn þann dag í dag hefur engum tekist að sanna tilgátuna, né koma með mótdæmi gegn henni. Okkur datt í hug að láta ykkur sanna hana hér í dag, en það væri of auðvelt.

Við kynnum heldur erfiðari tilgátu þekkt sem Önnur tilgáta Goldbachs:

Allar oddatölur stærri en $5$ er hægt að tákna sem summu þriggja frumtalna.

Í þessu verkefni gefum við oddatöluna $N$ sem er stærri en $5$. Við biðjum þig að finna þrjár frumtölur $P_1$, $P_2$, $P_3$ þannig að $P_1 + P_2 + P_3 = N$, eða tilkynna okkur að $N$ brjóti Aðra kenningu Goldbachs.

Inntak

Inntakið inniheldur eina oddatölu $N > 5$.

Úttak

Skrifið út þrjár frumtölur aðskildar með einu bili þar sem summa þeirra er $N$. Ef það eru margir möguleikar megið þið skrifa hvern þeirra sem er. Ef engar slíkar tölur eru til, skrifið þá út Neibb.

Útskýring á sýnidæmum

Í fyrsta sýnidæminu er $N = 65$. Ef þú skoðar úttakið sérðu að allar tölurnar eru frumtölur og summa þeirra $65$. Þessar tölur geta komið út í hvaða röð sem er. Aðrar mögulegar lausnir eru 11 37 17 og 11 11 43.

Stigagjöf

Lausnin mun verða prófuð á miserfiðum inntaksgögnum, og er gögnunum skipt í hópa eins og sýnt er í töflunni að neðan. Lausnin mun svo fá stig eftir því hvaða hópar eru leystir.

Hópur

Stig

Inntaksstærð

1

15

$N \le 31$

2

20

$N \le 500$

3

20

$N \le 10^4$

4

25

$N \le 10^8$

5

20

$N \le 10^{18}$

Sample Input 1 Sample Output 1
65
41 7 17
Sample Input 2 Sample Output 2
14846458157
13287470381 1378762933 180224843