## 759 - The Return of the Roman Empire

Moderator: Board moderators

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

### 759 - The Return of the Roman Empire

this has to be nominated for one of the most frustrating problems

It states:
The program should reject improperly formed numerals.
and it does not define what a 'properly' formed numeral is. Now I have my own ideas on this:
1. it contains any of I=1, V=5, X=10, L=50, C=100, D=500, and M=1000 in descending order, like MDCLXVI.
2. any of IXCM can be repeated up to three times.
3. it can contain any of IV=4, IX=9, XL=40, XC=90, CD=400, CM=900 however it cannot contain both IV and IX, or XL and XC or CD and CM.

So given this the highest number you can form is MMMCMXCIX or 3999. Are these assumptions right ? or is there something else/more ?

scottaugust
New poster
Posts: 18
Joined: Thu Jun 20, 2002 4:54 pm
Since this has been a little while since Caesum posted this, I am assuming that he has solved it, so this is for everyone else that has as many problems as I have - since there was no answer to Caesum, I had to ask for help from others who have solved it.

So here goes.

1) 0 < n < 4000. This falls out because there is no zero in roman numerals, and MMM maxes the number out to something less than 4000.
2) Addition/subtraction rules apply, as Caesum pointed out in 3, only one "roman digit" can act as a subtraction, and 3 "roman digits" act as an addition.
3) There can only be 1 "roman numeral" per decimal digit. This gives Caesum's rule number 3, IV and IX can not exists together in the same number.
4) No special cases, such as blank lines, extra characters, split numbers, etc. The input is fairly straight forward.

Hope this helps those that follow.

Scott

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
I guess the easiest way to solve it is to loop through all numbers 1-3999 and generate what that number is in Roman numerals (a much easier task), and then do a table lookup. A linear search even worked, but that was slooow

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Actually it can be several valid Roman numbers for one Arabic number, for example, from P185: "Note that 299 could be written as CCXCIX or CCIC".

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
I believe that the writing CCIC is not really valid - or not a "correct" writing. Either such cases are omitted in this problem, because my program (which was AC) didn't consider them valid, or they are really incorrect. But I guess there are different opinions in this matter.

luizflip
New poster
Posts: 2
Joined: Tue Oct 29, 2002 8:17 pm

### Output for this

What is the correct answer fot these:

XD
XCIM
XCID
ID
CMXDIV
XDI
MMMM
MMMMM
MMMMDCCCLXIV
IC
IVXCDDLCLVIVID

Does it allow whitespace in a number, such as CC C?
What about lowercase: are i,v,x,l,d,c,m valid?

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
I finally passed this one today......
luizflip, they are all invalid.
The only way that I finally passed it was to create a table of all numbers from 1 to 3999 in roman numerals, and use gets() and strcmp() on the whole list - it passed but slowly. I couldnt get my original program to pass it at all. In fact my hard drive going down and losing my original sources has meant a few passes when I have rewritten programs now
So I can say that: lowercase is not allowed and nor is whitespace - if you find this then its an invalid number.

ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm
my algo for this problem quite simple.
1.convert the input to decimal
2.try to find the roman for decimal from the given input.
3.compare the roman with the original input and bounded the decimal
below 4000.

the result runs quite fast within 0.1 second.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
I know this Thread about problem 759 is very old ( year 2003 ) but
as I have troubles with problem 759 now, I am going to make a post

I use the standard algorithm which is described above ( by Yarin ).
Firstly, generate the roman representation of all numbers N which
are in the range [1,3999] and put them in a hashtable let's say. This
hashtable maps

Code: Select all

``roman string --> arabic number``
.

Secondly, read the input line by line and using the line read as
a key check if there is an element in the hashtable under
that key. If there is such element then print it, otherwise print that
the roman number given in the input is not valid.

So ...

I have this quesiton - are we sure that on each line
of the Judge Input there is either an invalid Roman Number
or a valid Roman Number representing an Arabic Integer
in the range [1,...,3999].

If the answer to this question is YES then I have more
serious troubles. I probably have a BUG and generate wrong
Roman Representation for some integers 1<=N<=3999.
So my precalculated hashtable contains invalid values which
results in a WA of course.

If the answer is NO then ... What is the range ? Can we have
as input some Roman Number whose Arabic Integer
represantation N is such that N < 1 or N >= 4000 ?!

Yes, I forgot to mention that currently I have WA on this problem.
Last edited by Sedefcho on Tue May 10, 2005 6:39 pm, edited 1 time in total.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Oh, that's unbelievable !

There are EMPTY LINES in the Judge Input. In such cases we
must print the number ZERO ( 0 ) as answer.

Just by adding this behaviour to my program I got ACC.

Is that some joke or what ?!
Last edited by Sedefcho on Tue May 10, 2005 6:37 pm, edited 2 times in total.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Here is some sample I/O for anyone who
might be still fighting with this problem.

INPUT

Code: Select all

``````MCMXCVIII

CCM
CCXCIX
XD
XCIM
XCID
ID
CMXDIV
CXXXVIII
XDI
MMMM
CCLVII
MMMMM

MMMMDCCCLXIV
IC
IVXCDDLCLVIVID
MMMM
MMMCCC
MMMCC
MMMCCCC
MMMCD
MMMC
MMMCMXCIX
MMMCMXCII
I
VIII
CCIC

XLIX
MMIX
MMCDIII
XLIIIII
MMCDXLIV``````

OUTPUT

Code: Select all

``````1998
0
This is not a valid number
299
This is not a valid number
This is not a valid number
This is not a valid number
This is not a valid number
This is not a valid number
138
This is not a valid number
This is not a valid number
257
This is not a valid number
0
This is not a valid number
This is not a valid number
This is not a valid number
This is not a valid number
3300
3200
This is not a valid number
3400
3100
3999
3992
1
8
This is not a valid number
0
49
2009
2403
This is not a valid number
2444``````

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
I'm using the same algorithm as ezra (see above).

The program passes all sample data, including sedefcho's.

There is quite a lot of published functions for roman-decimal conversion and vice versa. I tried several of them and they all give the same answers as my original function. Nevertheless it's still "Wrong Answer".

Maybe someone could verify the following data:

Code: Select all

``````I
II
III
IV
V
VI
VII
VIII
IX
X
XI
XII
XIII
XIV
XV
XVI
XVII
XVIII
XIX
XX
XXI
XXII
XXIII
XXIV
XXV
XXVI
XXVII
XXVIII
XXIX
XXX

IIII
MIM
MCMXCIX

L
C
D
M

CVIII
CCVIII
DCCVIII
MDCCVIII

MMMCCCIII
XLMLILVIVCLIVCLV
DCCCXLVI
XIXXLDMXMXCXLLLLXL
MDXIX
IXC
MMDCXCVI
IVIXXIVXLIVIVMXCVCLLL
DCLXXVI
VCMV
CCIV
XCLDIVDXLCMCM
MMMDCCXXXVIII
CLMXLIVMCMIVMCMXC
MMMDCCXI
ILXCLCLIXCL
MMMMLXXXIII
XIXIXXICL
MDLXXVI
XLXLXC
DCCCLXVIII
XCIX
CXCVI
IVXLIVIXD
MMCLXXIII
VCLX
MMMMCLXCIX
IVCLCLXMMIX
MDCXLI
IVIXCLXXIVLCMCXCX
MDLXXXV
VD
MCXCVIII
XCCLLIVCMIXCMIVIVCMIX
CMLIV
XCLLCMICLCMXCCXIIIV
MMCCLXXXV
DIXIXXCMCXCDICLCMD
MMIX
CIXVIIIX
MCMVI
CXL
MCCLXXI
IXIXLX
MCCXXXI
LXXLIL
MMMMCCLXXXIV
XLC
CXXI
XCIXMCXLMCLXCCLL
MMMXII
CCXDIXCCLLMMMIL
MMDLV
MCL
MMMMDCCCXCV
IXCIMIVCMXCXCLILXXC
MMLIV
XIVIVIVCM
MDCCCXXXI
MXLCCLIXV
MMMCCXXX
XCMVVCMMDXLIX
LXII
CIXI
MMDCCXI
VIXCCV
MMDCXXII
VIVDDVCMVXLIXCM
MMMDCXXIX
DXLIVIXXCCMIV
MMDXXXII
IXLCLICXLCLCMICMM
MMCCLXXXVI
DIXXLCMCXC
MMMDXXXIV
CMXCLICLIVMCIXIVXC
MCMXXV
CX
MMMMCMXIII
IVVIMIXXLCLCLXL
MMMMXC
IIVIXCXLXIXXCIV
CXCI
IVXX
MMMCXI
XCIIVXCIXVXCLLIVCMIXXC
MMDLIX
CMCLVXLCM
MMMMCCCXVI
IIVL
MMMMVI
CMIVLLIVLIV
MMDCCCXXXVI
XCCICLXCX
MDLIII
DDILCMXXLVVX
MMMCLLXXVII
XCDLXCVCM
MCMXLII
CMDIXL
CMXIV
IVCMXCIVVXMIXCM
MDCCCLIII
VCMCXCIV
CL
XCC
MMMCCCLVIII
VCXIMCXCV
MCLLXXX
CLDCIVCDCM
MMDCLXVII
IVIVCMCLVIVDM
MMMCCXVIII
CMVCLLXCX
MMCMXI
LXLXCIVIIVIVXCCMID
MCCXLVIII
MIVCIIVXMDCMCMCMXLXL
MDCCVIII
XCCMVIVIXCLIVVCLIXDC
MMMMCLXXX
CIVXCCDXL
XII
IXXLMVVIXXLIXXII
MXCVI
VIIXLCLVVIXXLCMXLIV
MMCCCXCIV
XCVVCMLVCMCLXLVCMC
MCCLXXIV
IVV
IX
IVXCLXXLICIVDIVIXIX
MMMLXXI
XLXCCMXC
MDCVIII
CMXCVXLCLML
DCXCI
L
MCMXXVI
IVXCVICIICLVV
MMMDCCXXXIII
XCCMXIVVC
MCMXXVII
CMIXX
MMMMLVIII
VCLIIVCM
MMMMLXVI
XLXLXCMIXIXCLXL
MMCLXXXI
ICM
MMXXIV
IVDCLCLCLIIVLCLXIDX
MMDCCCXCVIII
CIXXCMICVXCIVLXCIX
MMMCCLXI
XLXLMVIXCIVVICMX
MMDCIX
CLMLIXIVD
MCXII
L
DCCLXXVI
LXCIVXCMXL
MDCCCXVI
CLXCIXCLVXDIVIVVIV
MDLXXV
MICMI
MMMMDXXXVIII
CMX
MMMMCCCXXV
CMXLLIXVDCM
MMMDCLVII
XXCIVXLDMX
MCLXXXVIII
L
MMMXIII
XLXLXVIX
MDV
IVCVXIVXXCM
MCMXCVII
XL
MMMCCCLXXXIV
CLMIXIVCLIXL
MCLLVIII
MIXIVV
CLLXXI
XCXMCXCIVIIMIV
MMMMDCCCXI
LIVDIXIVMXLCLIVCM
CVI
CLD
MCCLVIII
MIIVL
MMMMCXXVII
VDIXVCMVXCXCMDV
MMMDCCCXVIII
MIXXL
MMCLXCIX
MMCLCDXLCMLMVXCI
MMMMCCXLVII
IXCLDL
MLIV
VIVVIDVXIVVXIV
MMMMCMXXXVI
C
DCCLXXXIX
IVCCMMCXIXCCM
MMCLXVIII
XCCCCLCLCDDX
CLXXVII
LIVLLIVXMCMCLIVLL
MMDCCC
CVDXCXMVDLDXC
MMDCCXXXV
VXIXXCVCL
MMMMCMLXX
IVIIXCLICIVVCM
MCCLVI
LXLXLXXLIXCLIVDCLXC
MDCCXXXIX
CLIX
MDCCXIV
CM
MMMXXXVI
CMXXLCIXMCIXDXLL
MDCCXXXVI
MXLIV
MMMMCCLXII
CMCMXCDCXMIVIXCMXL
MMMCCCXCIX
DXDCLIIV
MMDCXCIII
CLILMIVXCVIX
MMMDCCXXVI
CL
DCCVIII
IILVDDXC
MMMMCMLX
VCMIVMCLIXIXIV
MMMCXXI
IIXCIVCL
DLXX
ILDIVICMIVLMM
MMMMXXIX
XXLD
MDCXXXV
VXVDLDVCMM
DCCCXI
MXDIVX
MMMMDXXIV
IVLVCML
MMMXXXV
VCCCMIVDIXICLD
MMMCMXVI
CLCXC
``````
output:

Code: Select all

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
0
This is not a valid number.
This is not a valid number.
1999
0
50
100
500
1000
0
108
208
708
1708
0
3303
This is not a valid number.
846
This is not a valid number.
1519
This is not a valid number.
2696
This is not a valid number.
676
This is not a valid number.
204
This is not a valid number.
3738
This is not a valid number.
3711
This is not a valid number.
This is not a valid number.
This is not a valid number.
1576
This is not a valid number.
868
99
196
This is not a valid number.
2173
This is not a valid number.
This is not a valid number.
This is not a valid number.
1641
This is not a valid number.
1585
This is not a valid number.
1198
This is not a valid number.
954
This is not a valid number.
2285
This is not a valid number.
2009
This is not a valid number.
1906
140
1271
This is not a valid number.
1231
This is not a valid number.
This is not a valid number.
This is not a valid number.
121
This is not a valid number.
3012
This is not a valid number.
2555
1150
This is not a valid number.
This is not a valid number.
2054
This is not a valid number.
1831
This is not a valid number.
3230
This is not a valid number.
62
This is not a valid number.
2711
This is not a valid number.
2622
This is not a valid number.
3629
This is not a valid number.
2532
This is not a valid number.
2286
This is not a valid number.
3534
This is not a valid number.
1925
110
This is not a valid number.
This is not a valid number.
This is not a valid number.
This is not a valid number.
191
This is not a valid number.
3111
This is not a valid number.
2559
This is not a valid number.
This is not a valid number.
This is not a valid number.
This is not a valid number.
This is not a valid number.
2836
This is not a valid number.
1553
This is not a valid number.
This is not a valid number.
This is not a valid number.
1942
This is not a valid number.
914
This is not a valid number.
1853
This is not a valid number.
150
This is not a valid number.
3358
This is not a valid number.
This is not a valid number.
This is not a valid number.
2667
This is not a valid number.
3218
This is not a valid number.
2911
This is not a valid number.
1248
This is not a valid number.
1708
This is not a valid number.
This is not a valid number.
This is not a valid number.
12
This is not a valid number.
1096
This is not a valid number.
2394
This is not a valid number.
1274
This is not a valid number.
9
This is not a valid number.
3071
This is not a valid number.
1608
This is not a valid number.
691
50
1926
This is not a valid number.
3733
This is not a valid number.
1927
This is not a valid number.
This is not a valid number.
This is not a valid number.
This is not a valid number.
This is not a valid number.
2181
This is not a valid number.
2024
This is not a valid number.
2898
This is not a valid number.
3261
This is not a valid number.
2609
This is not a valid number.
1112
50
776
This is not a valid number.
1816
This is not a valid number.
1575
This is not a valid number.
This is not a valid number.
910
This is not a valid number.
This is not a valid number.
3657
This is not a valid number.
1188
50
3013
This is not a valid number.
1505
This is not a valid number.
1997
40
3384
This is not a valid number.
This is not a valid number.
This is not a valid number.
This is not a valid number.
This is not a valid number.
This is not a valid number.
This is not a valid number.
106
This is not a valid number.
1258
This is not a valid number.
This is not a valid number.
This is not a valid number.
3818
This is not a valid number.
This is not a valid number.
This is not a valid number.
This is not a valid number.
This is not a valid number.
1054
This is not a valid number.
This is not a valid number.
100
789
This is not a valid number.
2168
This is not a valid number.
177
This is not a valid number.
2800
This is not a valid number.
2735
This is not a valid number.
This is not a valid number.
This is not a valid number.
1256
This is not a valid number.
1739
159
1714
900
3036
This is not a valid number.
1736
1044
This is not a valid number.
This is not a valid number.
3399
This is not a valid number.
2693
This is not a valid number.
3726
150
708
This is not a valid number.
This is not a valid number.
This is not a valid number.
3121
This is not a valid number.
570
This is not a valid number.
This is not a valid number.
This is not a valid number.
1635
This is not a valid number.
811
This is not a valid number.
This is not a valid number.
This is not a valid number.
3035
This is not a valid number.
3916
This is not a valid number.
``````

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### many dots -> many WAs

WR,

as many WAs as many dots ( . ) you print at the end of each
sentence "This is not a valid number."

It's quite sure that you have no other problems
in your output, my ACC program gives
same output, the only differences are the dots.

Good luck !

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
This is simply ridiculous!!!!

I don't even know where I got that point from!

Thanks a lot, sedefcho!

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

### 759 How to know this input is valid

I know how to convert roman to int and vice versa this is easy.
But there is a problem , i can not know is this valid numeral or not
Can any one who get Ac Help me..........I try to convert roman to int then i convert this int to roman and compare strings but this give WA.
As i know there are many represantaion for the same int.
Sleep enough after death, it is the time to work.