Number Overload!

Computer Science Level 4

Today, the author is not feeling quite well, so this problem will not have a long intro, with kings, rice fields, little Billies and Johnies, or some Elven related things. A file will be provided that describes one number. In first row of file, a number $N$ is given. The second row contains $N$ digits, which are not separated. Those digits represent a number $L$ .

Let's imagine a function $R(x, y)$ . The function gives the remainder of $x$ when dividing with $y$ , simple as that.

Now, if number $A = R(L, 9)$ , number $B = R(L, 77)$ and number $C = R(L, 41)$ , calculate the following value: $3 \times A - 7 \times B + 10 \times C$ .

The number $L$ is described in file which can be downloaded from here: LINK

The answer is -155.

1 solution

Milan Milanic
Sep 22, 2016

@Siva Bathula

What programming language did You use to solve this problem?

I solved it using C#. It only requires basic operators like % modulo, and an understanding of limits of long, int, BigInteger etc. I will leave a hint, consider the first A = 50 digits, and multiply it with 10 raised to N = (300000 - 50) modulo 9 or 77 or 41. Add the modulo of the next A digits raised to N = (300000 - 2 *50) modulo 9 or 77 or 41 and so on. You can do this repetitively until the last 50 digits. Note that the number 50 is just a limitation of the language/compiler/machine, if you use BigInteger classes provided in C# or Java or other equivalent types in other languages you can take higher number of digits at a time, but beyond a certain value even BigInteger types do not perform well. So find a smaller limit within 100-1000 and iterate.

Siva Bathula - 4 years, 8 months ago

@Milan Milanic What is your source for this question?

Siva Bathula - 4 years, 8 months ago

I only know C and C++ for now. I used the latter. I started programming 2 years ago, so I am still a novice. All my problems from "Computer Science" are solved using C++

However, I heard of Python or something. I am not good in it at all, due to small time spent figuring it out, but I know that it can do "crazy" things, so to say. In C and C++ there is long long int , and working with values that are greater than $2^{64} - 1$ is quite hard and often not efficient. Python practically does not have a limit.

So I thought, maybe this problem is absurdly trivial when Python is used. Still, on the other hand, a number with 3 million digits, I think that should be too much even for Python. Reading Your hint, I see that we had pretty much the same idea.

I also used operator% and I only used regular int , whose maximum value reaches $2^{32} - 1$ . I added one by one digit and after each added digit, I used modulo. Generally speaking, I think idea was the same.

Anyhow, I was curious about all that, especially about idea of Yours, so I hope I did no harm with my curiosity.

Milan Milanic - 4 years, 8 months ago

Could you give the source for this problem?

Siva Bathula - 4 years, 8 months ago

@Siva Bathula – Of course. Here it is

Milan Milanic - 4 years, 8 months ago

@Milan Milanic – I meant, where did you find this problem? Was it part of any programming contest?

Siva Bathula - 4 years, 8 months ago

@Siva Bathula – Ah, sorry. Guess my English did it this time.

I just had an idea, maybe out there some similar problem exist, definitely, but I never faced this one before. Although, generally, all CS problems of mine are inspired by Programming contest in Serbia.

Milan Milanic - 4 years, 8 months ago

@Milan Milanic – Ok, so you generated this problem? Or took it from somewhere? Can you give a link to the contest?

Siva Bathula - 4 years, 8 months ago

@Siva Bathula – If You are thinking about the file, then: I generated the file, more precisely, I made a program to generate a file. I only decided that I want 3 million random digits, and the program ("generator") did the rest.

The link of the contest site, where problems from the original contest from programming in Serbia can be found, is here .

Milan Milanic - 4 years, 8 months ago

Yes your idea seems right, 10 raised to any number x modulo y generally moves in a cycle. For large x you can take advantage of this fact to repeatedly multiply and modulo. So take few digits at a time, multiply it with ten raised to x(modulo 9 or 77 or 41)(you need to keep track of this), multiply repeatedly. Add the final values of all these grouped digits. That should give the values of A B and C.

Siva Bathula - 4 years, 8 months ago

Number Overload!

The answer is -155.

1 solution

0 pending reports