305 - Joseph

[hank]

My program already store the answer before input

and...It ran 29s.

[epsilon0]

i looked at Joseph (315) and saw on this board someone that oculd not solve it faster than 29s.

this kind of problem can be solved fast very easily, because there are only 13 possible values. they say each line is a 0<k<13
so you compute f(k) for each k on your home PC, then write something like:

while(1)
{
k = get_next_input();
switch(k)
{
case 1: answer = 1;
case 2: answer = 13;
...etc
case 13: answer = 131313;
}
output(k);
}

there you go, you should blow the scores with a brilliant 0.00 seconds

of course the answers in the example are wrong, i did not solve this problem, but i figured this trick, although it's obvious, i wanted to let you know about it.

[epsilon0]

Your C program has solved Ok the problem 305 (Joseph)
in 0.002 seconds with low memory spent.
Congratulations!

here is the code (answers for k>4 hidden):


[c]#include <stdio.h>

int solution[14] = {0,2,7,5,30,*,*,*,*,*,*,*,*,*};

int main()
{
int k;
while(scanf("%d",&k) && k != 0)
printf("%d\n",solution[k]);
return 0;
}[/c]

[cym]

another way to avoid TLE

you can save the results in an array after calculating
then get the input and output the corresponding answer
like the following:

[c]
#include<stdio.h>
void main(void)
{
int n,i,ans[13];

for(i=0;i<13;i++)
{......}

while(scanf("%d",&n)!=-1 && n>0)
printf("%d\n",ans[n-1]);
}
[/c]

[junjieliang]

"Table-method", as I call it, is not exactly what I like. But I do have an open mind, let's just call it "efficient program".

To hank: Can you post your code here or through personal mail so I can get a clearer picture of your program?

[Zhao Le]

i tried several times got your programme solved.
first, it must be 1 input 1 ouput meathod
second, it should use a table to store the result
i think acmer tried 100 more times the final results.

Nasty!

[cpp]#include <iostream.h>

long S[13]={0};

long coba(long n)
{
long a=n,b,n2=2*n,nn;
while(1)
{
a++;
b=a;
b=b%n2;
nn=n2-1;
if (b==0) b=n2;
while (nn>n && b>=n+1 )
{
b--;
b+=a;
b%=nn;
if (b==0) b=nn;
nn--;
}/*while*/
if (nn<=n && (b>n || b==0))
return a;
}
// return 0;
}

void main()
{
long a;
while(1)
{
cin>>a;
if(a==0) break;
else
{
if(S[a-1]==0)
{
S[a-1]=coba(a);
cout<<coba(a)<<endl;
}
else cout<<S[a-1]<<endl;
}
}
}[/cpp]

[lendlice]

i got ac.

[erfan]

while(ans%k2>k||ans%k2==0)
{
ak=ans%k2;
ans=i;
if(ak!=0)
ans=ans-(k2-ak);
count++;
k2--;
}

I think u miss somthing here.Pls check it again.

[erfan]

while(ans%k2>k||ans%k2==0)
{
ak=ans%k2;
ans=i;
if(ak!=0)
ans=ans-(k2-ak);
count++;
k2--;
}

I think u miss somthing here.Pls check it again.

[Morning]

can anyone tell me which part of my code will cause it?
[cpp]
#include <iostream>
using namespace std;
class Joseph
{
public:
Joseph(int t,int e);
int judge();
private:
int *array;
int totalNum;
int execute;
int point;
int judgeCondition;
};
Joseph::Joseph(int t,int e)
{
array = new int[t+1];
for(int loop = 1;loop <= t;loop++)
{
array[loop] = loop;
}
totalNum = t;
execute = e;
point = 1;
judgeCondition = t / 2;
}
int Joseph::judge()
{
while(totalNum > judgeCondition)
{
point += execute - 1;
while(point > totalNum)
{
point -= totalNum;
}
if (array[point]<= judgeCondition) return 0;
for(int temp = point;temp < totalNum;temp++)
{
array[temp] = array[temp + 1];
}
totalNum--;
}
return 1;
}
int main(int argc, char *argv[])
{
int k;
Joseph *j;
while(cin>>k)
{
switch(k)
{
case 0:break;

if (k == 10)
{
cout<<"93313"<<endl;
continue;
}
if (k == 11)
{
cout<<"459901"<<endl;
continue;
}
if (k == 12)
{
cout<<"1358657"<<endl;
continue;
}
if (k == 13)
{
cout<<"2504881"<<endl;
continue;
}
for(int loop = k+1;;loop++)
{
j = new Joseph(2*k,loop);
if (j->judge())
{
cout<<loop<<endl;
break;
}
}
}
return 0;
}
[/cpp]

[CDiMa]

can anyone tell me which part of my code will cause it?
[cpp]
for(int loop = k+1;;loop++)
{
j = new Joseph(2*k,loop);
if (j->judge())
{
cout<<loop<<endl;
break;
}
}
[/cpp]

I think you are creating new objects at each loop without destroying them. Since you should expect a lot of cases you'll end up using too much memory.

Ciao!!!

Claudio

[Morning]

Oh,i should remember to delete it.Thanks so much CDiMA:)

[jaracz]

Hi
I'm really confused abt how to speed up my algo, I did it several times, but still gettin' TLE
my algo actually stacks with number->12 (about 8sec) and 13 more...
It makes me angry!! Will I be forced to write down on paper result from my TLE solution and make big "switch"??

here's my code if someone wants to help me
any suggesions?

Code: Select all

#include <stdio.h> 
#include <vector> 

int main() 
{ 
    int k; 
    while(scanf("%d",&k)==1 && k) 
    { 
        std::vector<int> v,w;int k2 = 2*k; 
        std::vector<int>::iterator iter; 
        for(int i = 0; i < k2;)w.push_back(++i); 
        int step = k,count; 
        start:; 
        step++; 
        v = w; 
        count = 0; 
        iter = v.begin(); 
        while(count < k) 
        { 
            int len = step % v.size(); 
            for(int i = 0; i < len;++iter,i++) 
            { 
                if(iter == v.end())iter = v.begin(); 
            } 
            if(iter == v.begin())iter = v.end()-1; 
            else iter--;
            if(*iter <= k)goto start; 
            v.erase(iter);count++; 
        } 
        printf("%d\n",step); 
    }    
    return 0; 
}   

Thanks in advance

[emotional blind]

PRE-CALCULATION
PRE-CALCULATION
PRE-CALCULATION

[mf]

PRE-CALCULATION
PRE-CALCULATION
PRE-CALCULATION

Actually there is a way to solve this problem without precalculation!

Here's how I've solved it, but I'm too lazy to re-derive my solution now.
The code solves the case k=13 in less than a second.

Code: Select all

int f(int k)
{
	int m, n, p, r;

	for (n = 2 * k, m = 2;; m++) {
		for (p = 0, r = n; r > k; r--)
			if ((p = (p + m - 1) % r) < k) break;
		if (r == k) return m;
	}
}