151 - Power Crisis

[Jan]

Use linked lists instead of array. Otherwise precalulate the values.

[andmej]

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

In fact, that's exactly what it says:

Write a program that will read in the number of regions and then determine the smallest number m that will ensure that Wellington (region 13) can function while the rest of the country is blacked out.

[hmelo]

Hello...

I'm getting "runtime error", but i think my inputs and outputs are correct.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

int vet[MAX];
int visited[MAX];
int result[MAX];


void init_vet()
{
	int i;
	
	for(i=0;i<MAX;i++)
	{
		vet[i] = i;
		visited[i] = -1;
		result[i] = -1;
	}

}

int try(int n, int tam)
{
	int i, j, aux;
	init_vet();
	for(i=0, j=0; j< tam; j++)
	{
		
		visited[i]= 1 ;
		result[j] = vet[i] + 1;
		
		
		aux = 0;
		while(aux != n && j<tam -1)
		{
			i = (i+1)%tam;
			if(visited[i] == 1)
				aux--;
				
			aux++;
		}
	}

	if(result[tam-1] == 13)
		return 1;

	else
		return 0;

}

main()
{

	int i,j,n,res=0;
	
	while(scanf("%d",&n)==1)
	{
		res = 0;
		if(!n)
			break;
		
		if(n>=13 && n<MAX)
		{
			while(try(res,n) != 1)
			   res++;
		printf("%d",res);		
		}
	}

	
} 

Please, can anyone help me?
Thanks...

[ovidiu]

"Output will consist of a series of lines, one for each line of the input."
Please remove your code after accepted.

Running your code, I found my mistake. Thank you!

[selvakumaronfire]

My code is here... it gives correct answers for my own cases..

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int func(int N,int m)
{
	int cnt,cur=1;
	vector<bool> temp(N+1,false);
	temp[1]=true;temp[0]=true;
	while(cur-1!=13)
	{
		for(cnt=0;cnt<m;cur++)
		{
			if(cur==temp.size())
				cur=1;	
			if(temp[cur]==false)
				cnt++;
		}
		temp[cur-1]=true;
	}
	if(count(temp.begin(),temp.end(),false)>0)
		return false;
	else
		return true;
}

int main()
{
	int N,m;
	while(true)
	{
		cin>>N;
		if(N==0)
			break;
		m=3;
		while(true)
		{
			if(func(N,m++))
				break;
		}
		cout<<m-1<<endl;	
	}
	return 0;
}

pls give me some test cases....

[mpi]

Try with N=13. Note the difference between what your program should output and what your program actually output.

[jieshuzheng]

The following is my code. I have tested it with every number from 13 to 99 on my machine. But the OJ keeps giving me Runtime Error. The code is checked over and over, but I still cannot find any thing that can raise a RE. Really need your help.

Code: Select all

#include <stdio.h>

int joseph[10001];
int res[10001];

int calc( int n )
{
    int count;
    int i, j;
    int pos;

    for (i = 1;; i++)
    {
        count = n - 1;

        for (j = 1; j < n; j++)
        {
            joseph[j] = j + 1;
        }

        pos = 0;
        while (count > 1)
        {
            pos = (pos + i) % count == 0 ? count : (pos + i) % count;
            for (j = pos; j < count; j++)
            {
                joseph[j] = joseph[j + 1];
            }
            pos -= 1;
            count -= 1;
        }

        if (joseph[1] == 13)
        {
            return i;
        }
    }
}

int main()
{
    int n;

    scanf( "%d", &n );
    while (n != 0)
    {
        if (res[n] == 0)
        {
            res[n] = calc( n );
        }

        printf( "%d\n", res[n] );

        scanf( "%d", &n );
    }
}

[fR0D]

My program seems to work for all cases but donno why it gives wrong answer.Someone Plz Help.

Code: Select all

I was doing the same mistake as above.
The answer for N=13 is 1

[shamsacm]

set m=1 not m=3

[happyson10]

hi
I checked all cases from 13 to 99, all ouput are as same as http://uvatoolkit.com/problemssolve.php, while i got WA. please help !!

Attached my code:

Code: Select all

   the code was removed after getting AC

[brianfry713]

try

Code: Select all

13
17
13
0

[happyson10]

got it, thanks