Alkani

Osnovne informacije

Omejitve
  • Čas: 5 s
  • Spomin: 256 MB
Avtor:
  • Jure Slak
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Glavni junak te zgodbe je makaron Mirko. Testenine se v šoli pri pouku biologije učijo o sestavi svojega telesa in trenutno obravnavajo ogljikovodike. Začeli so pri osnovah: Povedali so, da so osnovni ogljikovodiki spojine sestavljene iz dveh elementov – vodika H in ogljika C. Začeli so pri alkanih, pri katerih so vse vezi enojne – vsak ogljik ima natanko štiri vezi in vsak vodik natanko eno. Alkane so tudi risali (sicer rahlo narobe), na primer:

       C     C
       |     |
   C-C-C-C-C-C-C
         |   |
         C   C
         |
         C

Vodikov niso risali, saj bi bile risbe preveč nepregledne. Nato so se jih naučili poimenovati. Enostavne verige iz ogljikov po vrsti od dolžine 1 do 12 so:

metan, etan, propan, butan, pentan, heksan, heptan, oktan, nonan, dekan, undekan, dodekan

Če pa imajo verige tudi dodatne izveske, tako imenovane radikale, pa pravila postanejo bolj zapletena. Najprej je treba poiskati najdaljšo verigo ogljikov, kar da osnovo za ime. V zgornjem primeru je to heptan. Radikale, če so ti enostavne verige, poimenujemo enako kot osnovne verige, le da imajo končnico -il namesto -an. Razvejanih radikalov se niso učili poimenovati. Radikale se nato oštevilči glede na pozicijo v verigi: Gledano z leve imamo zgoraj npr. 3-metil, 4-etil in dvakrat 6-metil. Izmed dveh možnih oštevilčenj (iz ene ali druge strani) izberemo tisto, ki ima leksikografsko manjše številke. (To pomeni, da vzamemo tisto, pri katerem je prva številka najmanjša; če sta enaki pa tisto, kjer je druga najmanjša, itd.) Če sta oštevilčenji leksikografsko enaki, izberemo tisto, pri kateri imajo nižje številke radikali, katerih imena so prej po abecedi (glejte primer spodaj in komentar). V zgornjem primeru se radikali pri številčenju z leve pojavijo na mestih 3, 4, 6 in 6, pri številčenju z desne pa na 2, 2, 4 in 5, zato izberemo slednje. Zagotovljeno je, da bomo dobili enako poimenovanje, ne glede na to, katero najdaljšo verigo izberemo.

Nato je treba ugotoviti, koliko je metilov, koliko je etilov in tako naprej. Če imamo dva metila, se v imenu uporabi dimetil; če imamo 3, se uporabi trimetil itd. Števniki od 2 do 12 so našteti spodaj:

di, tri, tetra, penta, heksa, hepta, okta, nona, deka, undeka, dodeka

Skupno ime alkana je sestavljeno iz zaporedja radikalov, ki so grupirani po dolžini. Pri tem so pred vsako grupo naštete urejene pozicije radikalov iz te grupe. Pozicije so ločene z vejicami. Na koncu sledi še ime glavne verige. Grupe so urejene po abecedi, neupoštevajoč morebitne predpone (zato postavimo etil pred dimetil in pred metil). Vse skupaj je ločeno z vezaji. V imenu ni presledkov. Pravilno poimenovanje zgornje spojine je torej:

4-etil-2,2,5-trimetil-heptan

Mirko je dobil pladenj velikosti n \times m, ki je poln alkanov. Alkani na pladnju so prepleteni kot špageti. Mirko vas zato prosi, da mu jih pomagate poimenovati.

Vhodni podatki

V prvi vrstici sta s presledkom ločeni naravni števili n in m. V naslednjih n vrsticah, ki imajo vsaka po m znakov, je podana risba z vsaj enim alkanom. En alkan je sestavljen iz znaka 'C', ki je lahko z znakoma '-' ali '|' povezan z drugimi 'C'-ji. Alkani se lahko med seboj dotikajo.

Omejitve vhodnih podatkov

  • 1 \leq n \cdot m \leq 10^5
  • Vsi alkani imajo glavne verige (in radikale) krajše od 12.

Izhodni podatki

Za vsak različen alkan, ki se pojavi na pladnju, izpišite vrstico oblike Kx ime-alkana, kjer je K število pojavitev tega alkana. Alkane izpišite padajoče po pogostosti, pri čemer enako pogoste alkane uredite še po abecedi glede na njihovo ime.

Primeri

Vhod

7 17
......C..........
......|..........
C-C-C-C-C-C-C-C..
........|........
........C........
........|........
........C........

Izhod

1x 4-etil-5-metil-oktan

Vhod

21 29
..C-C-C...C.......C-C.....C-C
..........|.........|.....|..
..........C...C.....C...C-C..
..........|...|...........|..
C-C-C-C-C-C-C-C-C-C...C...C-C
......|...|...|.......|......
......C...C...C.......C......
......|...|..................
..C...C...C.....C-C-C.....C-C
..........|.....|...|.......|
....C.....C...C-C...C.......C
....................|.......|
..C.....C...........C-C-C...C
........|...............|....
....C...C...C...C.......C....
....|...|...|...|............
C-C-C-C-C-C-C-C-C-C-C.....C-C
....|...|...|...|...........|
....C...C...C...C.......C...C
........................|...|
C-C...C...C.........C-C-C-C-C

Izhod

5x metan
2x etan
2x propan
1x 3-metil-oktan
1x 3-metil-pentan
1x 5,7-dietil-3,3-dimetil-5-propil-dekan
1x 5-etil-3,3,5,7,7,9,9-heptametil-undekan
1x butan
1x dekan

Vhod

21 29
C.C-C-C...C.C.C-C.C-C.....C-C
|..C...C..|.|...|...|.....|.|
C-C.C...C.C.C.C.C-C.C...C-C.C
........|C|...|...........|..
C-C-C-C-C-C-C-C-C-C...C...C-C
.C....|C..|...|....C..|......
.|....C|..C...C....|..C......
.C-C..|C..|..C-C-C-C-C-C-C-C.
..C|..C...C.....C-C-C|....C-C
..CCC.C..C|.....|...|C......|
.CC.C.....C...C-C...C|......C
..CCC........C-C....|C......|
..C.....C....|......C-C-C...C
........|....C..........|....
....C.C.C.C.C.C.C.......C...C
....|.|.|.|.|.|.|...........|
C-C-C-C-C-C-C-C-C-C-C...C-C-C
....|.|.|.|...|.|...........|
....C.C.C.C.C-C.C.......C...C
........|...............|...|
C-C...C.C-C.........C-C-C-C-C

Izhod

17x metan
4x etan
4x propan
3x butan
1x 3,7-dimetil-nonan
1x 3-metil-heksan
1x 4-etil-5-metil-oktan
1x 5,7-dietil-3,3,6-trimetil-5-propil-dekan
1x 5,8-dietil-3,3,4,4,6,6,7,8,9,9-dekametil-5-propil-undekan
1x dekan

Komentar

Prvi primer prikazuje pravilo oštevilčevanja. Ne glede na to, ali oštevilčimo radikala z leve ali z desne, dobimo mesti (4, 5). Izberemo oštevilčenje z desne, saj je par (etil, metil) po abecedi pred parom (metil, etil).

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task