## 11392 - Binary*3 Type Multiple

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

### 11392 - Binary*3 Type Multiple

I don't understand why my O(n) algorithm get TLE. Is there any faster way to solve it?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I got AC with 2.65~ sec using O(n) algorithm.

-----
Rio

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:
I have got AC in 1.960 sec.
My algorithm is order of no. of 3 (most obvious one)

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...
O(n)? I don't see any relationship between the numbers and their answers, other than the fact that at some point when you reach an odd prime number that hasn't been used in the factors of the previous answers its answer will be p-1 p-1 0. What am I missing that makes this problem easy to calculate?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Heres my approach:
For k=14, the answer is 3333330.

Code: Select all

``````3333330 = 3*(10^6+...+10^1)
``````
14 does not have factor 3, so it means 10^6+...+10^1 is divisible by 14.

If k doesn't have factor 3, the problem is to find (a,b) such that 0<=a<=b and 10^b+10^(b-1)+...+10^a is divisible k.
This could be done by O(n) algorithm.
If k is divisible by 3, divide it by 3 and do the same thing.
-----
Rio

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
I did similar approach, except it doesn't matter if k is divisible by 3 or not. I basically compute 333...3 mod k for each length

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
problem 10127 is another version of this problem. you can code it in less than 15 lines. in this problem numbers can be multiple of 2 or 5 because you can add zeros to the end of your number.

crackerwang
New poster
Posts: 10
Joined: Sun Jan 20, 2008 8:19 am
but i want to know is any num which can'ti div by 2 or 5 have a mutiple like 111..1111

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
if a number is a multiple of 2 it's first digit must be 0 or 2 or 4 or 6 or 8.
and if a number is a multiple of 5 it's first digit must be 0 or 5.
due this a number which is like this "11..11" is not a multiple of 2 or 5.

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

### What's the output for this

Can somebody check whether my output is correct?
Or is there any tricky input?

Code: Select all

``````Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
236773
42610
207363
428950
718729
958356
227092
63702
922718
84511
298077
803248
249764
882133
249776
858939
723076
244080
954760
335073
``````

Code: Select all

``````Output:

1 1 0
2 1 1
1 1 0
3 1 2
2 1 1
2 1 1
6 6 0
4 1 3
3 3 0
2 1 1
2 2 0
3 1 2
6 6 0
39462 39462 0
4261 4260 1
2652 2652 0
2048 2046 2
16206 16206 0
11408 11406 2
14195 14193 2
10615 10614 1
230680 230679 1
12072 12072 0
22926 22926 0
8224 8220 4
7346 7344 2
126018 126018 0
7660 7656 4
11792 11792 0
2757 2755 2
1012 1008 4
23871 23868 3
3660 3660 0
``````
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
My AC code got same output as yours.

-----
Rio

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

### I'm using GCD in

The problem is to find (a,b) such that 0<=a<=b and 10^b+10^(b-1)+...+10^a is divisible k.
This could be done by O(n) algorithm.
My algo is O(L + K) where L is the length of the multiple in the output. K iteration is needed to initalize the array. I use GCD in each iteration of L. I got TLE. How to better than this?
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:
First of all it suffices to look at the numbers 3,33,333, 3333 etc., since any number ending in some number of 0s can be expressed as the difference of two of these numbers with no 0s, ie. 333 - 33 = 300.

Hint: If you start marking the remainders you get mod K from this sequence, what happens when you get a remainder that you have seen before (and why does this prove that a solution always exists)?
For help with problems, visit http://www.uvatoolkit.com/

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
First of all it suffices to look at the numbers 3,33,333, 3333 etc., since any number ending in some number of 0s can be expressed as the difference of two of these numbers with no 0s, ie. 333 - 33 = 300.

Hint: If you start marking the remainders you get mod K from this sequence, what happens when you get a remainder that you have seen before (and why does this prove that a solution always exists)?
Awesome.. I never thought of this elegant solution. Thanks greve
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### Re: 11392 - Binary*3 Type Multiple

Hi! I got AC within 2.XX sec by O(n), but i see that there are someone who got AC within only 1 sec
is there a O(1) algorithm ??
electron