9
This is my first question, so I hope it goes well.
Background:
It's not the rivers that you might be thinking about. The question revolves around the concept of digital rivers. A digital river is a sequence of numbers where the number following n
is n
plus the sum of its digits.
Explanation:
12345 is followed by 12360 since 1+2+3+4+5=15 and so 12345 + 15 gives
12360. similarly 145 is followed by 155. If the first number of a digital river is M
we will call it river M
.
For e.g: River 480 is the sequence beginning {480,492,507,519....}, and river 483 is the sequence beginning {483,498,519,....}. Normal streams and rivers can meet, and the same is true for digital rivers. This happens when two digital rivers share some of the same values.
Example:
River 480 meets river 483 at 519. River 480 meets river 507 at 507 and never meets river 481. Every digital river will eventually meet river 1, river 3 or river 9.
Write a program that can determine for a given integer n
the value where river n
first meets one of these three rivers.
Input
The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n
(1 <= n <= 16384
). A test case with value of 0
for n
terminates the input and this test case must not be processed.
Output
For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then on a separate line output the line "first meets river x at y". Here y is the lowest value where river n
first meets river x
(x = 1 or 3 or 9). If river n
meets river x
at y
for more than one value of x
, output the lowest value. Print a blank line between two consecutive test cases.
Test case
Input:
86
12345
0
Output:
Case #1
first meets river 1 at 101
Case #2
first meets river 3 at 12423
Scoring:
The fastest algorithm wins. In case of tie. The one with shorter code will win.
Thanks to mbomb007 for pointing out my error.
p.s: I want to have the fastest solution rather than the smallest one. I also have a solution of mine which is slow. For that look here.
Note:
I will be using this for code testing. And performance checking.
3I'm not sure that you can score that way. What if someone's code is O(log(log n))? You can't cover them all, so you need to just say that the fastest algorithm wins, but in case of a tie, shortest code wins, and first posted wins in case both are the same length. – mbomb007 – 2015-09-16T14:43:47.843
Yeah, thanks for that advice. @mbomb007 – Kishan Kumar – 2015-09-16T14:44:35.577
Just wanted it that way.. – Kishan Kumar – 2015-09-16T14:47:59.890
mbomb007 you can edit it for the looks. If you want – Kishan Kumar – 2015-09-16T14:50:32.297
3
I can't find anything on copyright or usability of old ACM-ICPC challenges, but I can find this challenge on the archive site. Is it permissible to use here?
– Geobits – 2015-09-16T15:00:59.110@Geobits. I have solution of the code. But it is not fast enough. I asked it on codereview. No answer there.So thought in golfing people will find dun to find the fastest solution – Kishan Kumar – 2015-09-16T15:02:28.650
1That has nothing to do with copyright. If in doubt, the easiest thing is normally to email the site owner(s) and ask. – Geobits – 2015-09-16T15:03:33.687
And i have found this question in a competition i was participating. I have clearly stated, in the link i have given. – Kishan Kumar – 2015-09-16T15:04:41.807
The convention here for fastest code challenges is usually to post the specs of the machine you will test everything on. That info might be helpful. – DankMemes – 2015-09-16T15:27:59.497
this is fastest algorithm.And then implemented in code – Kishan Kumar – 2015-09-16T15:43:28.297
3"If the last digit of a digital river is
M
we will call it riverM
" doesn't make sense for two reasons: firstly, if a river is an infinite sequence of numbers then it doesn't have a last digit; and secondly, in the next paragraph riverM
means the river starting at numberM
. – Peter Taylor – 2015-09-16T15:48:52.0632From the linked CR.SE question, it seems like a river is whichever number started with in the series, but here's it's the last digit. Which is correct? – Celeo – 2015-09-16T15:54:28.977
@Geobits Ah, that explains why the question was formatted that way. It was mostly pasted, with some parts changed. – mbomb007 – 2015-09-16T16:08:53.253
That question was also asked by me in CR SE. Long ago. So directly copied and pasted the old question – Kishan Kumar – 2015-09-16T16:17:59.580
With the 1 ≤ n ≤ 16384 restriction, what prevents using a large lookup table? – LegionMammal978 – 2016-06-29T13:04:25.573
@LegionMammal978 your own decency – Kishan Kumar – 2016-06-29T13:24:59.977
Would lookup tables for, say, rivers 1, 3, and 9 be allowed? – LegionMammal978 – 2016-06-29T13:29:06.257
Well, Its not stated to not use a lookup table. But i highly don't appreciate the use of lookup table – Kishan Kumar – 2016-06-29T13:34:55.063