Posted: Sun Mar 12, 2006 4:04 am
"not" is a restricted name.
You are right!!!! Thanks!!!Krzysztof Duleba wrote:"not" is a restricted name.
Page 10 of 14
Posted: Sun Mar 12, 2006 11:49 am
#103 - plz test my input
Posted: Sun Apr 30, 2006 6:48 pm
I'd like you to test my input for the Stacking Boxes problem (#103), give an output and also answer how long does your program take to generate it.
Thx in advance.
Code: Select all
30 10
30 31 32 33 34 35 36 37 38 39
29 30 31 32 33 34 35 36 37 38
28 29 30 31 32 33 34 35 36 37
27 28 29 30 31 32 33 34 35 36
26 27 28 29 30 31 32 33 34 35
25 26 27 28 29 30 31 32 33 34
24 25 26 27 28 29 30 31 32 33
23 24 25 26 27 28 29 30 31 32
22 23 24 25 26 27 28 29 30 31
21 22 23 24 25 26 27 28 29 30
20 21 22 23 24 25 26 27 28 29
19 20 21 22 23 24 25 26 27 28
18 19 20 21 22 23 24 25 26 27
17 18 19 20 21 22 23 24 25 26
16 17 18 19 20 21 22 23 24 25
15 16 17 18 19 20 21 22 23 24
14 15 16 17 18 19 20 21 22 23
13 14 15 16 17 18 19 20 21 22
12 13 14 15 16 17 18 19 20 21
11 12 13 14 15 16 17 18 19 20
10 11 12 13 14 15 16 17 18 19
9 10 11 12 13 14 15 16 17 18
8 9 10 11 12 13 14 15 16 17
7 8 9 10 11 12 13 14 15 16
6 7 8 9 10 11 12 13 14 15
5 6 7 8 9 10 11 12 13 14
4 5 6 7 8 9 10 11 12 13
3 4 5 6 7 8 9 10 11 12
2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10
Posted: Mon May 01, 2006 6:51 am
My AC code produces the following output in around 20ms on a 1.2GHz Unix Server. The slow time is due to the usage of cin/cout.
Code: Select all
30
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
gr8 thx
Posted: Mon May 01, 2006 4:19 pm
Great. Now I'm at home in this problem. Thank you!
103 Funny Judge Problem
Posted: Thu Jun 15, 2006 7:08 pm
Currently, my program got WA.
For this input, my output is correct:
Input:
5 2
41 595
291 836
350 602
483 548
537 624
My Output:
3
1 3 5
However, with an accepted code which I found in this forum, the output is wrong
Output:
2
1 2
Here is the AC code(which produce wrong output for this input)
1. You can try submit this code, just to clarify that it is accepted.
2. Run the program to see the output.
3. Conclude that something is wrong with OJ. Otherwise, please clarify why.
P/S: Dun claim AC code posting to me. I just copy it from here
http://online-judge.uva.es/board/viewto ... =103+input
Tks
// Code compiled with VS 7
#include <iostream>
using namespace std;
#define OJ
const int maxB=30;//max boxes number;
const int maxD=10;//max boxes dimention；
int data[maxB][maxD]={0};//store all boxes information;
//int Ration[maxB][maxB]={0};//each boxes relation:Ration[j]=1,means that i can load j;
int dIndex[maxB]={0}; //sorted information;
int DP[maxB][2]={0};//DP[A][0]:the longest nested chain legnth which end at A;
//DP[A][1]:the nearest boxes which can pack A of the longest length;
int BNum;//boxes bumber;
int DNum;//dimention number;
int maxL;//the longest length;
int maxLP;//the innerest boxes index;
//let all boxes'dimention sorted as descending;
void sortD(void)
{
int i,j,k,temp;
for(i=0; i<BNum ;i++)
{
for(j=0;j<DNum;j++)
{
for(k=j+1;k<DNum ;k++)
{
if(data[k]>data[j])
{
temp=data[k];
data[k]=data[j];
data[j]=temp;
}
}
}
}
}
//let all boxes sorted as descending,information stored in dIndex;
bool IsBig(int a,int b)
{
int i=0;
while(i<DNum)
{
if(data[a]>data)
return true;
if(data[a]<data[i])
return false;
i++;
}
return true;
}
void sortB(void)
{
int i,j,temp;
for(i=0;i<BNum;i++)
dIndex[i]=i;
for( i=1;i<BNum;i++)
{
for(j=0;j<i;j++)
{
if( IsBig(dIndex[i],dIndex[j]) )
{
temp=dIndex[i];
dIndex[i]=dIndex[j];
dIndex[j]=temp;
}
}
}
}
bool IsPackable(int a,int b) //if a can be packed into b,return true;
{
int i=0;
while(i<DNum)
{
if(data[a][i]>=data[i])
return false;
i++;
}
return true;
}
void getMaxL(void)
{
int i,j,tempmax;
//init DP;
for(i=0;i<BNum;i++)
{
DP[i][0]=0;
DP[i][1]=-1;
}
maxL=1;
maxLP=0;
DP[0][0]=1;
DP[0][1]=-1;
for(i=1;i<BNum;i++)
{
for(j=0;j<i;j++)
{
tempmax=DP[j][0]+1;
if(tempmax>DP[i][0] && IsPackable(dIndex[i],dIndex[j]))
{
DP[i][0]=tempmax;
DP[i][1]=j;
if(tempmax>maxL)
{
maxL=tempmax;
maxLP=i;
}
}
}
}
}
bool Input(void)
{
int i,j;
while( cin>>BNum>>DNum )
{
for(i=0;i<BNum;i++)
for(j=0;j<DNum;j++)
cin>>data[i][j];
return true;
}
return false;
}
void print(void)
{
cout<<maxL<<endl;
while(DP[maxLP][1]>-1)
{
cout<<(dIndex[maxLP]+1)<<' ';
maxLP=DP[maxLP][1];
}
cout<<(dIndex[maxLP]+1)<<endl;
}
void main(void)
{
#ifndef OJ
freopen("in.txt", "r", stdin);
freopen("outAC.txt", "w", stdout);
#endif
while(Input())
{
sortD();
sortB();
getMaxL();
print();
}
#ifndef OJ
fclose(stdout);
#endif
}
For this input, my output is correct:
Input:
5 2
41 595
291 836
350 602
483 548
537 624
My Output:
3
1 3 5
However, with an accepted code which I found in this forum, the output is wrong
Output:
2
1 2
Here is the AC code(which produce wrong output for this input)
1. You can try submit this code, just to clarify that it is accepted.
2. Run the program to see the output.
3. Conclude that something is wrong with OJ. Otherwise, please clarify why.
P/S: Dun claim AC code posting to me. I just copy it from here
http://online-judge.uva.es/board/viewto ... =103+input
Tks
// Code compiled with VS 7
#include <iostream>
using namespace std;
#define OJ
const int maxB=30;//max boxes number;
const int maxD=10;//max boxes dimention；
int data[maxB][maxD]={0};//store all boxes information;
//int Ration[maxB][maxB]={0};//each boxes relation:Ration[j]=1,means that i can load j;
int dIndex[maxB]={0}; //sorted information;
int DP[maxB][2]={0};//DP[A][0]:the longest nested chain legnth which end at A;
//DP[A][1]:the nearest boxes which can pack A of the longest length;
int BNum;//boxes bumber;
int DNum;//dimention number;
int maxL;//the longest length;
int maxLP;//the innerest boxes index;
//let all boxes'dimention sorted as descending;
void sortD(void)
{
int i,j,k,temp;
for(i=0; i<BNum ;i++)
{
for(j=0;j<DNum;j++)
{
for(k=j+1;k<DNum ;k++)
{
if(data[k]>data[j])
{
temp=data[k];
data[k]=data[j];
data[j]=temp;
}
}
}
}
}
//let all boxes sorted as descending,information stored in dIndex;
bool IsBig(int a,int b)
{
int i=0;
while(i<DNum)
{
if(data[a]>data)
return true;
if(data[a]<data[i])
return false;
i++;
}
return true;
}
void sortB(void)
{
int i,j,temp;
for(i=0;i<BNum;i++)
dIndex[i]=i;
for( i=1;i<BNum;i++)
{
for(j=0;j<i;j++)
{
if( IsBig(dIndex[i],dIndex[j]) )
{
temp=dIndex[i];
dIndex[i]=dIndex[j];
dIndex[j]=temp;
}
}
}
}
bool IsPackable(int a,int b) //if a can be packed into b,return true;
{
int i=0;
while(i<DNum)
{
if(data[a][i]>=data[i])
return false;
i++;
}
return true;
}
void getMaxL(void)
{
int i,j,tempmax;
//init DP;
for(i=0;i<BNum;i++)
{
DP[i][0]=0;
DP[i][1]=-1;
}
maxL=1;
maxLP=0;
DP[0][0]=1;
DP[0][1]=-1;
for(i=1;i<BNum;i++)
{
for(j=0;j<i;j++)
{
tempmax=DP[j][0]+1;
if(tempmax>DP[i][0] && IsPackable(dIndex[i],dIndex[j]))
{
DP[i][0]=tempmax;
DP[i][1]=j;
if(tempmax>maxL)
{
maxL=tempmax;
maxLP=i;
}
}
}
}
}
bool Input(void)
{
int i,j;
while( cin>>BNum>>DNum )
{
for(i=0;i<BNum;i++)
for(j=0;j<DNum;j++)
cin>>data[i][j];
return true;
}
return false;
}
void print(void)
{
cout<<maxL<<endl;
while(DP[maxLP][1]>-1)
{
cout<<(dIndex[maxLP]+1)<<' ';
maxLP=DP[maxLP][1];
}
cout<<(dIndex[maxLP]+1)<<endl;
}
void main(void)
{
#ifndef OJ
freopen("in.txt", "r", stdin);
freopen("outAC.txt", "w", stdout);
#endif
while(Input())
{
sortD();
sortB();
getMaxL();
print();
}
#ifndef OJ
fclose(stdout);
#endif
}
Posted: Fri Jun 16, 2006 7:54 am
Although I have not verified the input/output, but this problem has a correction program. That is, their could be multiple correct output and both of them will be judged AC.
Please verify whether this is the case with this solution.
Please verify whether this is the case with this solution.
Posted: Fri Jun 16, 2006 10:59 am
Hi,
Tks for reply. Anyway, I can not get what correction program means, and why a program with wrong output got accepted. Just help if you can. Tks a lot.
Tks for reply. Anyway, I can not get what correction program means, and why a program with wrong output got accepted. Just help if you can. Tks a lot.
Posted: Fri Jun 16, 2006 2:44 pm
First thing though, please specify the problem number in your post next time.
I believe you are referring to problem 103, which has a yellow tick next to the problem. This means that for an input, it is possible to have more than one correct output as shamim stated in his post.
I believe you are referring to problem 103, which has a yellow tick next to the problem. This means that for an input, it is possible to have more than one correct output as shamim stated in his post.
Posted: Fri Jun 16, 2006 4:57 pm
Output of that code is wrong, I agree.guitarlover wrote:Here is the AC code(which produce wrong output for this input)
You should post this in Bugs and suggestions forum and notify the admins. They can add more tests cases for this problem.
Posted: Fri Jun 16, 2006 5:10 pm
Dear Ng Chun Yi,chunyi81 wrote:First thing though, please specify the problem number in your post next time.
I believe you are referring to problem 103, which has a yellow tick next to the problem. This means that for an input, it is possible to have more than one correct output as shamim stated in his post.
- I have stated the Problem No in the topic title. Pls check before post.
- It produce a wrong output. It is not a correct one. You can submit and check it carefully before postin. I do so before I post.
P/S: For admin
My first post, so feel free to move to the correct forum. Tks
Posted: Fri Jun 16, 2006 5:41 pm
There should be 2 posibilities:
1 - OJ doesn't cover such a test case.
2 - Test multiple output includes wrong output.
My question is that, how can a program produce a wrong result, can be accepted, because it is a simple case. Keep in mind that for this problem, even multiple output is allowed, they should be all correct.
Welcome discussion.
1 - OJ doesn't cover such a test case.
2 - Test multiple output includes wrong output.
My question is that, how can a program produce a wrong result, can be accepted, because it is a simple case. Keep in mind that for this problem, even multiple output is allowed, they should be all correct.
Welcome discussion.
Posted: Sat Jun 17, 2006 5:49 am
Okok... It looks like I need a visit to the optician.Dear Ng Chun Yi,
- I have stated the Problem No in the topic title. Pls check before post.
- It produce a wrong output. It is not a correct one. You can submit and check it carefully before postin. I do so before I post.
And I agree that the output from that AC program is wrong. My AC program produces the same output as the one you given in your first post.
Posted: Sun Jun 18, 2006 8:14 pm
Hee, Just watching too much soccer...
Anyway, maybe I will notify the admin about this problem. I also notice that many people got WA, I dun know whether it is from this error or not...
Anyway, maybe I will notify the admin about this problem. I also notice that many people got WA, I dun know whether it is from this error or not...
103 - Runtime Error
Posted: Thu Jun 29, 2006 10:47 pm
My code to solve problem 103 is getting Runtime Error. Somebody can help me?
Rodrigo
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#define MAX 31
#define N_MAX 26
struct celula {
int dim[N_MAX];
} box[MAX];
int v[MAX];
int marc[MAX];
int G[MAX][MAX];
int count;
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int cabe (int x, int y, int t)
{
int c;
for(c=0;c<t;c++)
if(box[x].dim[c]>=box[y].dim[c])
return 0;
return 1;
}
int dfs (int p, int n)
{
int l;
for(l=1;l<=n;l++)
if(G[p][l]==1 && marc[l]==0) {
marc[l]=1;
dfs(l, n);
}
v[count]=p;
count--;
return 0;
}
int main ()
{
int n, k, i, j, z, lis[MAX], pred[MAX], resp, resp_inic, final[MAX], count_final;
while(scanf("%d %d", &n, &k)==2) {
for(i=1;i<=n;i++) {
for(j=0;j<k;j++)
scanf("%d", &box[i].dim[j]);
qsort(box[i].dim, k, sizeof(int), compare);
for(z=1;z<i;z++) {
if(cabe(i, z, k)==1) {
G[i][z]=1;
G[z][i]=0;
}
else if(cabe(z, i, k)==1) {
G[z][i]=1;
G[i][z]=0;
}
else {
G[i][z]=0;
G[z][i]=0;
}
}
}
for(i=1;i<=n;i++) {
marc[i]=0;
lis[i]=1;
pred[i]=i;
}
count=n;
for(i=1;i<=n;i++) {
if(marc[i]==0) {
marc[i]=1;
dfs(i, n);
}
}
resp=0;
resp_inic=0;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(G[v[i]][v[j]]==1 && lis[v[j]]<lis[v[i]]+1) {
lis[v[j]]=lis[v[i]]+1;
pred[v[j]]=v[i];
if(lis[v[j]]>resp) {
resp=lis[v[j]];
resp_inic=v[j];
}
}
count_final=0;
printf("%d\n", resp);
while(pred[resp_inic]!=resp_inic) {
final[count_final]=resp_inic;
count_final++;
resp_inic=pred[resp_inic];
}
final[count_final]=resp_inic;
for(i=count_final;i>=0;i--)
printf("%d ", final[i]);
printf("\n");
}
return 0;
}