11256 - Repetitive Multiple

[hamedv]

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]

Try this input:

Code: Select all

1
536870912

Correct output:

Code: Select all

536870912536870912

[sclo]

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]

Well in my case I did it with O(d^2 * sqrt(n) ) which can easily be derived to O(d^2 log(n) ).

[TimeString]

My previous program get wrong answer by the following case:

Code: Select all

1
787569631

The correct answer is 100100100100100. Hope it helps.

[shakil]

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

Code: Select all

Cut after AC. Recode and AC.

[Rocky]

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

thank's in adcance
Rocky

[sunny]

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.

[emotional blind]

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]

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.

[TimeString]

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]

Thanks TimeString .

[sclo]

My code pass TimeString input and output . Can any one give some input and output which my previous post code fail.
Thanks in advance.

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]

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.

[miras]

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...