305 - Joseph

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

Moderator: Board moderators

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

Post by hank »

My program already store the answer before input

and...It ran 29s.

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

305 - Joseph

Post by 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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

0.002 seconds with a little trick

Post by 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]

:P :P :P

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

another way

Post by 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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by 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
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

305 AC

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

305

Post by lendlice »

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
Location: Chittagong,Bangladesh
Contact:

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

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

305 Josephone Why Memory Limit Exceeded?

Post by 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]
"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?

Post by CDiMa »

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

Post by Morning »

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

Post by 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
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
Location: Bangladesh
Contact:

Post by emotional blind »

PRE-CALCULATION
PRE-CALCULATION
PRE-CALCULATION

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

Post by 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;
	}
}

Post Reply

Return to “Volume 3 (300-399)”