## 151 - Power Crisis

Moderator: Board moderators

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
RE (runtime error) usually occurs when your array is not big enough or invalid access to array index (out of bound).

scx
New poster
Posts: 4
Joined: Sat Sep 07, 2002 5:13 pm
Thank you very much ... it is working now but I still get wrong answer

zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

### may be you should paste you code.

Don`t worry this site is full of broken code. If you paste it someone may find the error.
By the way WA could also be a result of "array" problems. For example on my computer I write on MS Visual C and as a result it treats these two codes identical:
[cpp]int a[5];
...
a[0]=...; <=> a[5]=..;[/cpp]
Good luck.
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com

zerocool
New poster
Posts: 7
Joined: Wed May 15, 2002 10:30 am
Location: Kaohsiung,Taiwan
Contact:
When you start to test your code, it's better to think the bound condition.
For example, In this problem . Do you ever think "13" ? In this problem
The input is 13 <= n < 100. After 13, it's better to think 99.

sample input
13
sample output
1
Best Regards !
A mediocrityboy

crashzero
New poster
Posts: 4
Joined: Thu Oct 10, 2002 8:11 pm

### I simple can't understand problem 151

Someone could explain me why it isn't 1 always the right answer in problem 151?

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
i can try.

if m = 1, consider when N is 14. you cut the power off like 1,2,.. thus you cut off the power of 13 before 14. but you are supposed to cut off the power of 13 only after all the other areas have been cut-off.

hope this helps.

crashzero
New poster
Posts: 4
Joined: Thu Oct 10, 2002 8:11 pm
thanks....

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Contact:

### 151 - there is some problem in judge end.

Can any one tell me what is the difference between the following codes :
Code A

Code: Select all

``````#include<stdio.h>

#define MAX 150

/** Implementatiom of circular queue  **/
int queue[MAX];
int e,f,r;
/** _f is front; _r is rear & _e is element number **/
void push(int i)
{
r++;
e++;
if(r>=MAX)
r=1;
queue[r] = i;
}
int pop(void)
{
e--;
int i=queue[f];
f++;
if(f>=MAX)
f = 1;
return i;
}

/** End of circular queue **/
/** A general joshusf function **/
/** This function start removing element from first element */
/** and return the sirviver **/
int joshups(int n,int v)
{	register int i;
e=n;
for(i=1;i<=n;i++)
queue[i] = i;
f = 1; // 0 for serviving first element.
r = n; // n+1 for serviving first element.
i = 0;
if(n > 1)
pop();
while(e!=1)
{
if(i!=v)
{
i++;
push(pop());
}
else
{
if((pop())==13) /** this if statement and its body (not the pop) is out ofgeneral code **/
return -1;
i = 0;
}
}
return queue[f];
}

/** end of jouishof functionb **/
main(void)
{
int i,m;
scanf("%d",&i);
while(i)
{   m=1;
while((joshups(i,m++)) != 13 );
printf("%d",m);
putchar('\n');
scanf("%d",&i);
}
return 0;
}
``````
Code B

Code: Select all

``````#include<stdio.h>
int count(int *region,int N)
{
int i,t=0;
for(i=0;i<N;i++)
if(!region[i])
{
t++;
if(t>1)
return t;
}
return 1;
}
void main()
{
int N,i,m,j,inc,tag;
int region[100];
while(scanf("%d",&N)==1)
{
if(!N)break;
tag=0;
m=1;
while(!tag)
{
j=0;
for(i=0;i<100;i++)region[i]=0;
region[j]=1;
j++;
while(count(region,N)!=1)
{
inc=m;
for(i=0;i<inc;)
{
if(j==N){j=0;continue;}
if(!region[j])i++;
if(j<N)j++;

}
j--;
region[j]=1;
}
for(i=0;i<N;i++)
if(!region[i])
break;
if(i==12)
{
printf("%d\n",m);
tag=1;
break;
}
m++;
}
}
}
``````
When I submit the first code I got the wrong answer but when I submit the second one I got accepted. But both of the code gives same answer for all possible input (13 <= n < 100) so why the first one got wrong answer. I think the judge has some problem. Am I right????????????????

[/b]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Try n=13, your two programs give different output.

There is also another case where the result is not consistent.

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Contact:

i have repair my code
but i do not find any deffrent output with the two code other then 13.

anyway thanks again.

Xander
New poster
Posts: 6
Joined: Thu Oct 02, 2003 11:48 pm

### How to do 151?

Is there any overall formula for Josephus problem according to the problem 151. Please let me know it in detail.

In my Concrete Math (Knuth) there Josephus problem written for cuting Head one man after another and cutting start from the 1st person. So everything become so complex for me. Plsease help me.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
as far as I know, this is just simulation. You don't need a formula or anything

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
There are other problems about Josephus. This is simulation as Maarten said. Just find a rule. According to this rule you will visit towns and find the answer. You will simulate the statement of this problem.
_____________
NO sigNature

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
I knew the formula but I have forgotten...
what i can remember is u can find it in chapter 3 (floor/ceiling) of concrete math (knuth)

sacra
New poster
Posts: 8
Joined: Sun Oct 27, 2002 9:36 pm
Location: Coimbra, Portugal
Contact: