305  Joseph
Moderator: Board moderators
305  Joseph
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.
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.
0.002 seconds with a little trick
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]
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]
another way
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[n1]);
}
[/c]
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[n1]);
}
[/c]

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
305 AC
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=n21;
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[a1]==0)
{
S[a1]=coba(a);
cout<<coba(a)<<endl;
}
else cout<<S[a1]<<endl;
}
}
}[/cpp]
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=n21;
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[a1]==0)
{
S[a1]=coba(a);
cout<<coba(a)<<endl;
}
else cout<<S[a1]<<endl;
}
}
}[/cpp]
305 Josephone Why Memory Limit Exceeded?
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]
[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]
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know this will lead to knowledge."Confucius
"Hold what you really know and tell what you do not know this will lead to knowledge."Confucius
Re: 305 Josephone Why Memory Limit Exceeded?
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.Morning wrote: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]
Ciao!!!
Claudio
305 speed up
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?
Thanks in advance
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;
}
Last edited by jaracz on Sun Aug 07, 2005 12:09 am, edited 2 times in total.
keep it real!

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
Actually there is a way to solve this problem without precalculation!PRECALCULATION
PRECALCULATION
PRECALCULATION
Here's how I've solved it, but I'm too lazy to rederive 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;
}
}