11256 - Repetitive Multiple

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

Moderator: Board moderators

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

11256 - Repetitive Multiple

Post by hamedv » Sat Aug 04, 2007 1:31 pm

what's wrong with my code i got TLE :(

Code: Select all

#include <stdio.h>
#include <string.h>

int len, m, i, j, cl;
bool b;

bool cut(char s[])
{
	int len = strlen(s);
	if (len % m != 0)
		return 0;
	cl = len / m;
	for (i = 0; i < m-1; i++)
		for (j = 0; j < cl; j++)
			if (s[i * cl + j] != s[(i+1) * cl + j]) return 0;
	return 1;
}

bool isr(int n)
{
	char s[100];
	sprintf(s, "%d", n);
	len = strlen(s);
	m = len;
	while (!cut(s) && m > 1) m--;
	return m-1;
}

int main()
{
	int t, n, i;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		i = 1;
		while (!isr(n*i)) i++;
		printf("%d\n", n*i);
	}
	return 0;
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Aug 04, 2007 2:57 pm

Try this input:

Code: Select all

1
536870912
Correct output:

Code: Select all

536870912536870912

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

Post by sclo » Sat Aug 04, 2007 3:04 pm

Hint: my code is O(d^2 log(d)) where d is the number of digits of n. I think it could've been even faster but I didn't bother, since d<=9 here.

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

Post by jah » Sun Aug 05, 2007 1:16 am

Well in my case I did it with O(d^2 * sqrt(n) ) which can easily be derived to O(d^2 log(n) ).
Last edited by jah on Mon Aug 06, 2007 1:35 am, edited 1 time in total.

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

Post by TimeString » Sun Aug 05, 2007 3:50 pm

My previous program get wrong answer by the following case:

Code: Select all

1
787569631
The correct answer is 100100100100100. Hope it helps.

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » Sun Aug 05, 2007 7:24 pm

Why WA???? i can not find any problem. Please help.....

Code: Select all

Cut after AC. Recode and AC.
Last edited by shakil on Tue Aug 07, 2007 8:38 am, edited 1 time in total.
SHAKIL

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Post by Rocky » Sun Aug 05, 2007 7:37 pm

can any accepted person give me some input/output for this problem....
it really helpful for me

thank's in adcance
Rocky

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Sun Aug 05, 2007 9:00 pm

shakil wrote:Why WA???? i can not find any problem. Please help.....
If you write your code with good indentation, it'll be easier for others to read your code and there is more chance that you can get some help.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sun Aug 05, 2007 9:51 pm

sunny wrote:
shakil wrote:Why WA???? i can not find any problem. Please help.....
If you write your code with good indentation, it'll be easier for others to read your code and there is more chance that you can get some help.
LIKE this

Code: Select all

#include<stdio.h>
typedef long long dt;

dt gcd(dt h1,dt h2)
{
	dt h3;

	while(h2!=0){
		h3=h1%h2;
		h1=h2;
		h2=h3;
	}
	return h1;
}


main()
{

	dt n,n1,sa,max,t,x,y,value,start,i,j,k,p,q,r,a,M,N,count,f;

	scanf("%lld",&n);

	for(n1=1;n1<=n;n1++){
		scanf("%lld",&sa);
		max=sa;
		t=sa;

		while(t!=0){
			t=t/10;
			max=max*10;
		}

		max=max+sa;

		for(i=1;i<=9;i++){
			start=i;
			r=i;
			for(j=2;j<=18;j++){
				r=r*10+i;
				if(r%sa==0){
					if(max>r)
						max=r;
					break;		
				}
			}

			for(j=2;j<=9;j++){
				start=start*10;
				value=start;

				for(k=2;k<=18/j;k++){
					value=value*(start/i)*10;
					value=value+start;
					x=value/start;{
						a=gcd(x,sa);
						M=x;
						N=sa;
						M=M/a;
						N=N/a;
						count=0;
						f=M;	

						while(f!=0){
							f=f/10;
							count++;
						}

						f=N;

						while(f!=0){
							f=f/10;
							count++;
						}

						if(count-1<=18){
							p=N*M;{
								if(p<value){
									if(value%p==0)
										q=value/p;
									else q=value/p+1;
									p=p*q;
								}

								p=p-value;
								if(p%x==0){
									p=p/x;
									count=0;
									f=p;

									while(f!=0){
										f=f/10;
										count++;
									}

									if(count<j){
										y=value+x*p;
										if(y<max)
											max=y;
										else
											break;
									}
								}
							}
						}
					}
				}
			}
		}
		printf("%lld\n",max);
	}
}

I wonder how shakil can manage his large codes without proper indentation.

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » Sun Aug 05, 2007 11:04 pm

hi , every one. i never write indentation in my code and it is my limition. here is my logic...

for i = 1 to 9
{

may iXiX / iXiXiX ........ /iXXiXX/iXXiXXiXX.......up to iXXXXXXXX
///// X = 1 to 8
///// repeted 2 to 18/lenth
so -> like iXXXiXXXiXXX =>
i000i000i000 +100010001 * XXX = N * n //hear XXX = unknown integer
XXX=(N *n -i000i000i000)/100010001; // N = possible small integer
now , i calculate the ans of XXX ,if it is possible and check for minimum.

}

output the minimum.

It is too hard to tell my logic.But i tried.
SHAKIL

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

Post by TimeString » Mon Aug 06, 2007 8:41 am

shakil wrote:Why WA???? i can not find any problem. Please help.....
Try this:

Code: Select all

3
117
121
126
Correct answer is:

Code: Select all

108108
110110
108108

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » Mon Aug 06, 2007 12:57 pm

Thanks TimeString :D .
Last edited by shakil on Wed Aug 08, 2007 4:06 pm, edited 1 time in total.
SHAKIL

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

Post by sclo » Mon Aug 06, 2007 1:18 pm

shakil wrote:My code pass TimeString input and output :( . Can any one give some input and output which my previous post code fail.
Thanks in advance. :lol:
I don't quite understand your code.
why does your X goes from 1 to 8 instead of 1 to 9?
Also, make sure all of the intermediate calculations don't go out of bound for long long. For this problem, it is very easy to go over the bound if not coded carefully.

There is a simpler way to do this problem.
My code is less than 35 lines long.

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » Tue Aug 07, 2007 8:44 am

Thanks sclo. I recode and AC.I optimized my method and it is 37 lines.
In this time i much careful about go over the bound.Thanks again.
SHAKIL

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

again...

Post by miras » Sat Sep 01, 2007 8:28 pm

Hi... I have some problems with that task...

here is my code...

Code: Select all

var ile,iile,i,leng,numb:longint;
    k,w,nn,ret,ans,ww,n,g,tmp:int64;


function nwd(x,y:int64):int64;
 begin
 if (x=0) then nwd:=y else nwd:=nwd(y mod x,x);
 end;


begin
readln(ile);
 for iile:=1 to ile do
 begin
readln(g);
ans:=-1; ret:=-1;
  for leng:=1 to 10 do
    for numb:=2 to 9 do
      if (numb*leng<=18) then
      begin
	ans:=-1;
	n:=g;
        w:=1; k:=1;
	for i:=1 to leng do w:=w*10;
	for i:=1 to numb-1 do k:=w*k+1;

		nn:=nwd(n,k);
		n:=n div nn;
	    if (n<w) then
	          begin
		  if (n>=w div 10) then ans:=k*n else
		          begin
			  if ((w div 10) mod n=0) then ans:=k*(w div 10) else
			                begin
					tmp:=(w div 10) div n;
					if ((tmp+1)*n<w) then ans:=k*(tmp+1)*n;
					end;
			  end;
		  end;


            if (ans<>-1) and (ret=-1) then ret:=ans;
	       if (ret<>-1) and (ans<>-1) and (ans<ret) then ret:=ans;
	end;
               repeat
               until ret<>-1;



writeln(ret);
end;

end.
tell me wether you have any test cases... ;-)
Remember Never Give Up
Regrads
Miras

Post Reply

Return to “Volume 112 (11200-11299)”