151 - Power Crisis

[arc16]

RE (runtime error) usually occurs when your array is not big enough or invalid access to array index (out of bound).

[scx]

Thank you very much ... it is working now but I still get wrong answer

[zbogi]

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.

[zerocool]

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 !

[crashzero]

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

[Adil]

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]

thanks....

[Master]

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]

Try n=13, your two programs give different output.

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

[Master]

Thaks for your help

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

anyway thanks again.

[Xander]

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]

as far as I know, this is just simulation. You don't need a formula or anything

[Farid Ahmadov]

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.

[Subeen]

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]

If I'm not mistaken, there are at least to possible answers for N=13, which are 1 and 7.

I think the wording should say something like "If there's more than one solution, print the lowest possible m."