## 305 - Joseph

Moderator: Board moderators

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

and...It ran 29s.

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

### 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)
{
...etc
}
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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

### 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]

cym
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:

### 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[n-1]);
}
[/c]

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
"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
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

### 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=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
New poster
Posts: 22
Joined: Thu Nov 21, 2002 10:50 am

### 305

i got ac.
Last edited by lendlice on Sun May 25, 2003 9:39 am, edited 1 time in total.

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:

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
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:

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
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

### 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]
"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

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 305 Josephone Why Memory Limit Exceeded?

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]
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
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
Oh,i should remember to delete it.Thanks so much CDiMA:)
"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

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

### 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?

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!

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
PRE-CALCULATION
PRE-CALCULATION
PRE-CALCULATION

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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;
}
}``````