151 - Power Crisis

[rezwana]

plzzzzzz help.
i am getting WA.why?

here is my code

#include<stdio.h>
#include<string.h>

int a[101];
int i,n,r,count,flag;
int main(){

while(1){
scanf("%d",&n);
if(n==0)
break;
for(r=2;;r++){
i=2;
a[1]=1;
count=0;
flag=0;
while(1){
if(a==0)
count++;
if(count==r){
if(i==13)
break;
a=1;
count=0;
}
if(i==n)
i=1;
else
i++;
}
for(i=1;i<=n;i++){
if((a==0)&&(i!=13))
{
flag=1;
break;
}
}

if(flag==0)
break;
memset(a,0,sizeof(int)*101);
}
printf("%d\n",r);
memset(a,0,sizeof(int)*101);

}
return 0;
}

[midra]

I have a problem with the problem 151 and it's not the input 13
I have read all the topics of this board but I can't figure out what's wrong with my code.
The judge reply Runtime Error (Siggsev) or something like that.
I have make a linked list (my first program of listed link), so maybe there is some function or something wrong...In my computer it compiles it good (I have win98s), and it gives me the correct answers.
I don't know where is the problem
here is my code:

[c]
#include <stdio.h>

struct region{
int num;
struct region *sig;
};

struct region *primero,*ultimo;

void inicializar(int n){
int i; /*counter*/
struct region *nuevo;
nuevo=(struct region *)malloc(sizeof(struct region));
nuevo->num=2;
nuevo->sig=NULL;
primero=nuevo;
ultimo=nuevo;

for (i=3;i<=n;i++){
struct region *nuevo;
nuevo=(struct region *)malloc(sizeof(struct region));
nuevo->num=i;
nuevo->sig=primero;
ultimo->sig=nuevo;
ultimo=nuevo;
}
}


void eliminar(){
struct region *aux;
}

evaluar(int n){
int r=1,m=2;
start:
inicializar(n);
r=1;
while(1){
struct region *anterior,*actual;
anterior=actual=primero;
actual=primero->sig;
r++;
empieza:
if (primero->sig==primero){
if (primero->num==13){
printf("%d\n",m);
return;
}
else{
m++;
goto start;
}
}
while(actual!=primero){
if (r==m){
anterior->sig=actual->sig;
free(actual);
r=0;
}
anterior=actual;
actual=actual->sig;
r++;
}
if (actual==primero){
if (r==m){
primero=actual->sig;
anterior->sig=primero;
free(actual);
r=0;
}
anterior=actual;
actual=actual->sig;
r++;
goto empieza;
}
}
}

int main()
{
int m,n;
while(1){
a:
scanf("%d",&n);
if (n==0)
break;
else if (n==13){
printf("1\n");
goto a;
}

inicializar(n);
evaluar(n);
}
return 0;
}

[/c]

for easy understanding here are the words I use in spanish translated to english:
sig=next
nuevo=new
primero=first
ultimo=last
inicializar=init
actual=present
anterior=earlier

If someone could help me I would appreciate very much!
thanks for reading!
byee!!

[shamim]

There are several issues relating your code:

1) I compiled it using VC 6.0 and it gave me a compile error, malloc() is reported as being undefined, but this may not be the case in UVA.

2) It gave 3 warning messages about certain fucntin not returning any value. So I have redefined the funtion to return void.

3) Your program crashed for the sample input and on doing a step by step debugging, the follwing line caused the crash.

[cpp]
actual=actual->sig;
[/cpp]

[chunyi81]

Also, for uva, it is better to include the headers explicitly, such as #include <stdlib.h> for malloc() function, but uva is using gcc, which implicitly included some headers when your program is compiled, except for headers such as the math.h header (if you use gcc without using -lm).

[midra]

thank you so much for answer me.!!!
but I still don't understand why this line caused a crash:
[c]
actual=actual->sig;
[/c]

I compile with Dev-cpp and it compiles fine.
The others things I think I fixed.
sorry but I am a really begginner in this field, and it's my first code where I use structures...so if anyone could tell me something more about the error I would thanks a lot!!!

good luck!
bye!

[gamesmash]

the output is:
15
29
But beware! The input shuld terminated by 0!

For some reason my program fails on 52. What is your output?

[Maglor]

Hi. I'm a newbie here. I'm having a problem of SIGSEGV (Invalid memory reference) in problem 151.

Here's my code:

-----------------------------------
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
char value;
struct node *next;
struct node *prev;
} NODE;

void initialise(NODE **lista) {

*lista = (NODE *)malloc(sizeof(NODE));
(*lista)->next = NULL;
(*lista)->prev = NULL;

}

void add(NODE **lista, int i) {

NODE *new_node;

if (isempty(*lista)) {
(*lista)->value = i;
(*lista)->next = (*lista);
(*lista)->prev = (*lista);
}
else {
new_node = (NODE *)malloc(sizeof(NODE));

new_node->value = i;
new_node->next = (*lista)->next;
new_node->prev = (*lista);

(*lista)->next->prev = new_node;
(*lista)->next = new_node;
}
}

int isempty(NODE *lista) {
return (lista->next == NULL);
}

int main() {

short reg, i, j;
NODE *lista, *temp;

while (scanf("%d",&reg) == 1) {

if (reg == 0)
break;

for (i = 1; i <= 300; i++) {

initialise(&lista);

for (j = 1; j <= reg; j++) {
add(&lista, j);
lista = lista->next;
}

lista = lista->next;

while (lista->next != lista) {
temp = lista->next;
lista->prev->next = lista->next;
lista->next->prev = lista->prev;
lista->next = NULL;
lista->prev = NULL;
free(lista);
lista = temp;
for (j = 1; j < i; j++)
lista = lista->next;
}

if (lista->value == 13)
break;

}

printf("%d\n",j);

}
}
-----------------------------------

However, in my computer, this code compiles and runs for every number from 13 to 100, returning a result. I've tested making a loop from 13 to 100 and outputing the result.

I've seen the others topics about problem 151, and tested the inputs suggested, and it was OK. For 13, it returns 1, for 20 returns 15 and for 21 returns 29.

I'm using gcc 3.4.2 under Fedora Core 1.

Can anyone help me ???

[Maglor]

Sorry about the identation.

[Karthekeyan]

Code: Select all

#include<iostream>
#include<vector>
using namespace std;
void formqueue(int a[],int &qsize)
{
  a[0]=-1;
  for(int i=1;i<=qsize;i++)
    {
      a[i]=1;
    }
  for(int i=qsize+1;i<101;i++)
    {
      a[i]=-1;
    }
}
int deletequeue(int a[],int &qsize, const int m,const int n,int prev)
{
  if(qsize==n)
    {
      a[1]=0;
      qsize--;
      return 1;
    }
  else
    {
      int j;
      int i=prev;
      int score=m;
      while(score>0)
	{
	  if(a[i]==1)
	    {
	      score--;
	      if(score==0)
		j=i;
	      i++;
	    }
	  else
	    i++;
	  if(i>=100)
	    i=0;
	}
    
      a[j]=0;
      qsize--;
      return j;
    }
}
int main()
{
  int n,m;
  while(cin>>n)
    {
      if(n==0)
	break;

      int flag=0;
      m=1;

      //      for(m=1;m<=500;m++)
      while(flag==0)
	{
	  int a[100],qsize;
	  qsize=n;
	  formqueue(a,qsize);
	  int prev;
	  while(qsize>1)
	    {
	      prev=deletequeue(a,qsize,m,n,prev);
	    }
	  int mans=0;
	  for(int i=1;i<=n;i++)
	    {
	      if(a[i]==1)
		if(i==13)
		  {
		    mans=m;
		    flag=1;
		    break;
		  }
	    }
	  if(mans!=0)
	    {
	      m=mans;
	      break;
	    }
	  m++;
	}

      cout<<m<<'\n';
    }
  return 0;
}

I dont understand why the online judge says my answer is incorrect! I have tried all possible inputs given in this forum and my code works well!!!!!!!!!!!!!!!!!![/code]

[Sedefcho]

The output for 52 is 178.

INPUT

Code: Select all

13
17
20
21
25
52
99
0

OUTPUT

Code: Select all

1
7
15
29
26
178
15

These are outputs from an ACC program.

Peter Petrov
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:19741

[murkho]

Dear, i know my output is all right. But my problem is when first input is zero my programs exit(that is ok). But after some nonzeor input when i give zero in my visual c++ editor it show "send error message to microsoft?" please tell me what is the problem .

Code: Select all

#include<stdio.h>
#define N 105
#define CITY 13


int   main()
{
int in[N],m,sum,present = 0,count= 0,i;
int n;
while(1)

	{	scanf("%d",&n);
		if(n == 0)
			break;         
		
		present = 0;
	 for(m = 1 ;present !=CITY;m++)
		{
		 for(i = 1;i<=N;i++) in[i] = 1;

		 sum = m-1;count = 0;
		 present = 0;
		 
		 for(i = 1;count!=n;i++)
			{
			 sum += in[i];
			 if(sum == m){in[i] = 0;count++;present = i;sum = 0;}
			 if(i == n) i = 1;
			 if(present==CITY && count!=n) {present = 0;break;}
		 
			}
		}
	 printf("%d\n",m-1);
	}
return 0;
}

[sahand]

this part of your code is corrupting the stack:

Code: Select all

for(i = 1;i<=N;i++) 
                in[i] = 1; 

because the array in is defined as:

Code: Select all

int in[N]

Which means the last element that you should write to is in[N-1] not in[N].

So you should either change the definition of in to:

Code: Select all

int in[N+1]

or use this:

Code: Select all

for(i = 1;i<N;i++) 
                in[i] = 1; 

Good luck,
Sahand.

[113020199]

why i get presentation error???
i dont understand,please help. this is my code for problem 151....

#include <stdio.h>

main()
{
int m,n,i,k,l,x;
int Awal[100],Akhir[100],AwalInput[10];
int Temp,Input,Tambah,Cacah,NilaiAkhir,Stop,Bil;

for (m=1; m<=100; m++) Akhir[m]=1;

Bil=1;
do
{
scanf("%i",&AwalInput[Bil]);
Bil=Bil+1;
} while (AwalInput[Bil-1]!=0);
printf ("\n");

for(x=1;x<Bil-1;x++)
{
Input=AwalInput[x];
m=1;
while (Akhir[Input]!=13)
{
i=1;
while (i<=Input)
{
Awal=i;
i++;
}
Temp=1;
n=2;
Akhir[1]=Awal[1];
Awal[1]=0;
Stop=0;
while ((n<=Input)&&(Stop==0))
{
l=0;
k=Temp+1;
while (l<m)
{
if (k==Input+1)
{
k=1;
}
if (Awal[k]==0)
{
k=k+1;
}
else
if(Awal[k]!=0)
{
l=l+1;
k++;
}
}
k=k-1;
Temp=k;
if ((Awal[Temp]==13)&&(n!=Input))
{
Stop=1;
}
else
{
Akhir[n]=Awal[Temp];
Awal[Temp]=0;
n++;
}
}
m=m+1;
}
i=1;
NilaiAkhir=m-1;
printf ("%i\n",NilaiAkhir);
}

return 0;
}

[Solmon K.]

look!

printf ("\n"); <- remove this and got AC

printf ("%i\n",NilaiAkhir);

first one is no use

why two "\n"s??

[albet_januar]

can anybody help me?

Code: Select all

#include <stdio.h>
#include <string.h>

int main()
{
	int n;
   int i;
   char array[1000];
   int counter;
   int count;
   int j;

   while(scanf("%d", &n))
   {
   	if(n==0) break;

      for(i=1;;i++)
      {
      	memset(array, NULL, sizeof(array));

         array[0] = 1;
         j = 1;
         count = i;
         counter = n - 1;

         while(counter!=0)
         {
   			if(array[j]==0)
      		{
      			count--;

         		if(count==0)
         		{
         			array[j] = 1;
					count = i;
					counter--;
				}
			}

			j = (j + 1) % n;
		 }

		 if(j==13)
		 {
			printf("%d\n", i);
			break;
		 }
	  }

   }

	return 0;
}