Page 3 of 5
wa wa wa... 27... inf
Posted: Tue Jun 26, 2007 11:55 pm
by adelar
Hi friends,,,
Can someone to see my code?
I take 27 WA

Last with 6.133 seconds
what is the error? Can you help me?
thanks in advance...
Posted: Wed Jun 27, 2007 8:04 am
by leocm
I want some case tests.
For all the tests here and in other topics of this problem, my code get the correct answer.
Thank you!
wa, inf wa
Posted: Wed Jun 27, 2007 2:55 pm
by adelar
Hi leocm,
I trying solve this problem too. I did test 4 codes and none take AC... but all algorithms is equals...
1. even?
2. conected?
3. euler and print.
thanks in advance...
wawawa...
Posted: Wed Jun 27, 2007 9:54 pm
by adelar
Hi Jan,
If I send my code you analyse to me?
is some detail that I don't treat... but I don't know what!
thanks in advance.. .......
Posted: Wed Jun 27, 2007 10:18 pm
by Jan
You should explain your algorithm first.
AC, I dont belive...
Posted: Thu Jun 28, 2007 1:29 am
by adelar
Hi Jan,
I take AC finally!!!!!!

after 31 submitions!!!!!!
I was translating the coments to english to post for you and I saw the error... one of variables of control was with same value all time,,,
thank you, thanks a lot for the help...
then the sequence:
1. even?
2. conected?
3. euler and print.
work to this problem
next problem

Posted: Sat Aug 25, 2007 7:53 pm
by duykhang91
Here is my pascal code. I hav WAs. Why? Please anyone can help me? Thanks a lot :X
Program Necklace;
Const
fi='10054.inp';
fo='10054.out';
Type arr=array[1..50,1..50] of integer;
Var
a:arr;
t,n,m:integer;
f:text;
{--------------------------------------------------------------------------}
Procedure euler;
var
b:array[1..51] of integer;
kt:boolean;
{-----------------------}
Procedure print;
var
i:integer;
begin
For i:=1 to n do
writeln(b
,' ',b[i+1]);
end;
{-----------------------}
Procedure dw(i,d:integer);
var
j:integer;
begin
b[d]:=i;
If d=n+1 then
begin
print;
kt:=true;
end
else
begin
For j:=1 to m do
If a[i,j]=1 then
begin
a[i,j]:=0;
a[j,i]:=0;
dw(j,d+1);
If kt then exit;
a[i,j]:=1;
a[j,i]:=1;
end;
end;
end;
begin
kt:=false;
dw(1,1);
end;
{--------------------------------------------------------------------------}
Function even:boolean;
var
i,j,dem:integer;
begin
bac:=true;
For i:=1 to m do
begin
dem:=0;
For j:=1 to m do
If (a[i,j]=1) and (j<>i) then inc(dem);
If dem mod 2 <>0 then
begin
even:=false;
break;
end;
end;
end;
{--------------------------------------------------------------------------}
Function connect:boolean;
var
b:array[1..50] of boolean;
i:integer;
Procedure go(i:integer);
var
j:integer;
begin
b:=false;
For j:=1 to m do
If b[j] and (a[i,j]=1) then
begin
a[i,j]:=0;
go(j);
a[i,j]:=1;
end;
end;
begin
connect:=true;
fillchar(b,m,true);
go(1);
For i:=1 to m do
If b then
begin
connect:=false;
break;
end;
end;
{--------------------------------------------------------------------------}
Procedure nhap;
var
i,j,x,y:integer;
begin
Readln(t);
For i:=1 to t do
begin
writeln('Case #',t);
fillchar(a,sizeof(a),0);
m:=0;
readln(n);
For j:=1 to n do
begin
readln(x,y);
If x>m then m:=x;
If y>m then m:=y;
a[x,y]:=1;
a[y,x]:=1;
end;
If even and connect then
euler
else writeln('some beads may be lost');
If i<>t then writeln;
end;
end;
{--------------------------------------------------------------------------}
Begin
nhap;
End.
Posted: Sat Sep 29, 2007 5:45 am
by sapnil
I get too many WR,more than 15 times.whats wrong help me.........
Thanks
Keep posting
Sapnil
Time Limit Exceeded
Posted: Wed Oct 31, 2007 6:38 am
by puneetm84
Hi,
My code is giving time limit exceeded.I am first checking if euler cycle exists or not and then I find the euler cycle. Here is the code, can anyone help me with this ..Thanks in advance
#include<iostream>
#include<vector>
#include<string>
#include<list>
#include<set>
using namespace std;
void euler_cycle(list<int>euler,int **graph,list<int>::iterator i,int s)
{
for(int j=0;j<51;j++)
{
if(graph[s][j]>0)
{
graph[s][j]--;
graph[j][s]--;
list<int>::iterator it = euler.insert(i,s);
euler_cycle(euler,graph,it,j);
}
}
}
void dfs(int **graph,int color[51],int s)
{
color[s]=1;
for(int i=0;i<51;i++)
{
if(graph[s] && !color)
dfs(graph,color,i);
}
color[s]=2;
}
int main()
{
int N;
cin>>N;
int **graph;
graph = new int*[51];
for(int j=0;j<51;j++)
graph[j]=new int[51];
for(int i=0;i<N;i++)
{
list<int> euler;
int beads;
cin>>beads;
int s;
for(int j=0;j<51;j++)
for(int k=0;k<51;k++)
graph[j][k]=0;
set<int> nodes;
for(int j=0;j<beads;j++)
{
int x,y;
s=x;
cin>>x>>y;
graph[x][y]++;
graph[y][x]++;
nodes.insert(x);
nodes.insert(y);
}
// Check for connectivity
int flag=0;
int color[51];
for(int j=0;j<51;j++)
color[j]=0;
dfs(graph,color,s);
for(set<int>::iterator it=nodes.begin();it!=nodes.end();it++)
{
if(!color[*it])
{
flag=1;
break;
}
}
// Check for degree
for(int j=0;j<51;j++)
{
int degree=0;
for(int k=0;k<51;k++)
{
if(graph[j][k] && j!=k)
degree+=graph[j][k];
}
if(degree%2)
{
flag=1;
break;
}
}
cout<<"Case #"<<i+1<<endl;
if(flag)
cout<<"some beads may be lost";
else
{
euler_cycle(euler,graph,euler.begin(),1);
int ans[euler.size()];
int count=0;
list<int>::iterator it;
for(it = euler.begin(); it != euler.end() ; it++)
ans[count++]=*it;
for(int j=0;j<count;j++)
cout<<ans[j]<<" "<<ans[(j+1)%count]<<endl;
}
if((i+1)!=N)
cout<<endl;
}
}
TLE
Posted: Thu Dec 06, 2007 3:59 pm
by adelar
Thanks Jan,
only to confer...
again was AC in 5.??? seconds, and now show TLE.
this algorithm is correct?
Code: Select all
if(even(graph) || !conected(graph))
"some beads may be lost"
else
print euler path;
thanks in advance...
Re: 10054 - The Necklace
Posted: Wed May 14, 2008 10:38 pm
by Batu
Hi all.
I'm having Runtime Error in this problem.
I think it's very strange because i do not use pointers.
Code: Select all
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int grafo[51][51];
int grado[51];
int grado_aux[51];
bool activo[51];
int visitado[51];
queue<int> colita;
queue<int> cola;
int vtrue;
int primero;
int abalorios;
void borrar() {
for(int i = 0; i <= 50; i++) {
for(int j = 0; j <= 50; j++) {
grafo[i][j] = 0;
}
grado[i] = 0;
grado_aux[i] = 0;
activo[i] = false;
visitado[i] = 0;
}
while(!cola.empty()) cola.pop();
}
void leer() {
int n, m;
scanf("%d", &abalorios);
scanf("%d%d", &n, &m);
grafo[n][m]++;
grafo[m][n]++;
grado[n]++;
grado[m]++;
grado_aux[n]++;
grado_aux[m]++;
primero = n;
activo[n] = true;
activo[m] = true;
for(int i = 1; i < abalorios; i++) {
scanf("%d%d", &n, &m);
activo[n] = true;
activo[m] = true;
grafo[n][m]++;
grafo[m][n]++;
grado[n]++;
grado[m]++;
grado_aux[n]++;
grado_aux[m]++;
}
}
void bfs(int vertice) {
int aux;
while(!colita.empty()) colita.pop();
vtrue++;
colita.push(vertice);
visitado[vertice] = vtrue;
while(!colita.empty()) {
aux = colita.front();
colita.pop();
for(int i = 1; i <= 50; i++) {
if(grafo[aux][i] > 0 && visitado[i] != vtrue) {
colita.push(i);
visitado[i] = vtrue;
}
}
}
}
bool euleriano() {
sort(grado_aux, grado_aux+51);
for(int i = 50; i > 0 && grado_aux[i] > 0; i--)
if(grado_aux[i] % 2) return false;
return true;
}
bool conectado(int vertice) {
bfs(vertice);
for(int i = 1; i <= 50; i++)
if(activo[i] && visitado[i] != vtrue)
return false;
return true;
}
void imprime_sol() {
int aux;
int aux2;
while(!cola.empty()) {
aux = cola.front();
cola.pop();
aux2 = cola.front();
cola.pop();
printf("%d %d\n",aux, aux2);
}
}
int busca_siguiente(int vertice) {
int i;
int candidato;
if(grafo[vertice][vertice] > 0) {
grafo[vertice][vertice] -= 2;
return vertice;
}
for(i = 1; i <= 50; i++){
if(grafo[vertice][i] > 0) {
candidato = i;
grafo[vertice][i]--;
grafo[i][vertice]--;
grado[i]--;
grado[vertice]--;
if(grado[i] <= 0) activo[i] = false;
if(grado[vertice] <= 0) activo[i] = false;
if(conectado(i))
return i;
else {
grafo[vertice][i]++;
grafo[i][vertice]++;
grado[i]++;
grado[vertice]++;
activo[i] = true;
activo[vertice] = true;
}
}
}
return -1;
}
bool calcula_sol() {
int v1 = primero;
int v2;
while(abalorios) {
v2 = busca_siguiente(v1);
if(v1 < 0) return false;
abalorios--;
grado[v1]--;
grado[v2]--;
if(grado[v1] <= 0) activo[v1] = false;
if(grado[v2] <= 0) activo[v2] = false;
cola.push(v1);
cola.push(v2);
v1 = v2;
}
return true;
}
int main() {
int casos;
scanf("%d", &casos);
for(int caso = 1; caso <= casos; caso++){
vtrue = 0;
borrar();
leer();
printf("Case #%d\n", caso);
if(euleriano() && conectado(primero)) {
if(!calcula_sol())
printf("some beads may be lost\n");
else
imprime_sol();
}else{
printf("some beads may be lost\n");
}
if(caso < casos)
printf("\n");
}
return 0;
}
Anyone could help me?
Thanks in advance.
PS. Sorry for my English
Re: 10054 - The Necklace
Posted: Mon Jul 07, 2008 6:33 pm
by Robert Gerbicz
One easy input (contains two tests), but your program may fail these if you don't use multiple edges in your code.
You can form a necklace from both beads tests.
Code: Select all
2
5
50 50
50 50
50 50
50 50
50 50
6
1 50
1 50
1 50
1 50
1 50
1 50
One possible output:
Code: Select all
Case #1
50 50
50 50
50 50
50 50
50 50
Case #2
1 50
50 1
1 50
50 1
1 50
50 1
Re: 10054 - The Necklace
Posted: Sat Oct 04, 2008 2:43 pm
by Piova
I got runtime error in this problem. I can't find the mistake.
Please help me. Thinks.
Code: Select all
#include <iostream>
#include <vector>
using namespace std;
struct node
{
short num;
node *next;
};
struct color
{
short co;
node *now,*head,*last;
}c[51];
short in[50],w;
bool DFS(short a,short &dest,bool v[])
{
v[a]=false;
c[a].now=c[a].head;
do
{
if(c[a].now->num==dest) return true;
if(v[c[a].now->num]&&DFS(c[a].now->num,dest,v)) return true;
c[a].now=c[a].now->next;
}while(c[a].now);
return false;
}
void DFS(short a,bool v[])
{
v[a]=false;
c[a].now=c[a].head;
do
{
if(v[c[a].now->num])
{
DFS(c[a].now->num,v);
}
c[a].now=c[a].now->next;
}while(c[a].now);
}
void run(short &s,bool v[])
{
short i,a=s,b,t=0;
while(t<c[s].co)
{
while(1)
{
node *n,*m;
n=c[a].head;
b=n->num;
c[a].head=n->next;
m=c[b].head;
if(m->num==a) c[b].head=m->next;
else
{
while(m->next->num!=a) m=m->next;
c[b].now=m;
m=c[b].now->next;
if(m==c[b].last) c[b].last=c[b].now;
c[b].now->next=m->next;
}
for(i=0;i<w;i++) v[in[i]]=true;
if(a==b||n->next==NULL||DFS(a,b,v))
{
delete n,m;
break;
}
c[a].last->next=n;
c[a].last=n;
c[a].last->next=NULL;
c[b].last->next=m;
c[b].last=m;
c[b].last->next=NULL;
}
if(a==s) t++;
if(b==s) t++;
cout<<a<<' '<<b<<endl;
a=b;
}
}
void create(short &a,short &b)
{
short i;
for(i=0;i<w;i++)
if(a==in[i]) break;
if(i==w) in[w++]=a;
node *newnode=new node;
c[a].co++;
newnode->num=b;
newnode->next=NULL;
if(c[a].head==NULL)
{
c[a].now=c[a].head=newnode;
}
c[a].now->next=newnode;
c[a].now=newnode;
}
bool even()
{
for(short j=0;j<w;j++)
{
if(c[in[j]].co&1) return false;
c[in[j]].last=c[in[j]].now;
}
return true;
}
bool connect(short &a,bool v[])
{
short j;
for(j=0;j<w;j++) v[in[j]]=true;
DFS(a,v);
for(j=0;j<w;j++)
if(v[in[j]]) return false;
return true;
}
int main()
{
short n,m,a,b,i,j;
bool isStart=false,v[51];
cin>>n;
in[0]=0;
for(i=1;i<=n;i++)
{
w=0;
if(isStart) cout<<endl;
else isStart=true;
cin>>m;
for(j=1;j<51;j++)
{
c[j].co=0;
c[j].head=NULL;
}
cin>>a>>b;
in[w++]=a;
create(a,b);
create(b,a);
for(j=1;j<m;j++)
{
cin>>a>>b;
create(a,b);
create(b,a);
}
cout<<"Case #"<<i<<endl;
if(even()&&connect(a,v))
{
run(a,v);
}
else cout<<"some beads may be lost\n";
}
return 0;
}
Re: 10054 - The Necklace
Posted: Fri Mar 13, 2009 3:52 pm
by MRH
remove after acc......
Re: 10054 - The Necklace
Posted: Fri Mar 13, 2009 7:00 pm
by Chirag Chheda
Your program gives wrong answer for the input