151 - Power Crisis

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

Moderator: Board moderators

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Sat Sep 07, 2002 6:22 pm

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

Post by scx » Sun Sep 08, 2002 1:47 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.

Post by zbogi » Tue Sep 10, 2002 1:33 am

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. :wink:
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:

Post by zerocool » Wed Sep 18, 2002 3:02 am

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 ! :wink:
A mediocrityboy

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

I simple can't understand problem 151

Post by crashzero » Tue Oct 29, 2002 7:13 pm

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

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

Post by Adil » Tue Oct 29, 2002 8:35 pm

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

Post by crashzero » Thu Oct 31, 2002 10:53 am

thanks....

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

151 - there is some problem in judge end.

Post by Master » Tue May 06, 2003 3:47 pm



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]

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Wed May 07, 2003 7:59 am

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
Location: St. Johns, Canada
Contact:

Post by Master » Thu Aug 07, 2003 9:32 am

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
New poster
Posts: 6
Joined: Thu Oct 02, 2003 11:48 pm
Location: Dhaka, Bangladesh

How to do 151?

Post by Xander » Fri Oct 03, 2003 1:30 pm

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

Post by Maarten » Fri Oct 03, 2003 2:42 pm

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

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Fri Oct 03, 2003 2:49 pm

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

Post by Subeen » Fri Oct 03, 2003 3:12 pm

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:

Two answers

Post by sacra » Sat Feb 28, 2004 3:05 am

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."

Post Reply

Return to “Volume 1 (100-199)”