Page 5 of 6
514-WE
Posted: Sat Nov 30, 2013 8:26 pm
by anup10.duet
#include<iostream>
#include<stack>
using namespace std;
int main()
{
int N,trainNo,counter1,lastTrainNo,temp,breakFlag;
while(cin>>N)
{
if(N == 0)
break;
breakFlag = 1;
while(breakFlag)
{
lastTrainNo = 0;
stack <int> myStack;
for(counter1 = 1;counter1 <= N;counter1++)
{
cin>>trainNo;
if(trainNo == 0)
{
breakFlag = 0;
break;
}
if(trainNo == lastTrainNo + 1)
{
lastTrainNo = trainNo;
if(myStack.size() != 0)
{
while(myStack.size() != 0)
{
temp = myStack.top();
if(temp == lastTrainNo + 1)
{
lastTrainNo = temp;
myStack.pop();
}
else
break;
}
}
}
else
myStack.push(trainNo);
}
if(breakFlag)
{
if(myStack.size()==0)
cout<< "Yes"<<endl;
else
cout<< "No"<<endl;
}
else
cout<<endl;
}
}
return 0;
}
Re: 514-WE
Posted: Tue Dec 03, 2013 2:28 am
by brianfry713
Try running your code on the sample input.
Re: 514-WE
Posted: Tue Dec 03, 2013 9:43 am
by anup10.duet
AC
514 Rails: WA
Posted: Wed Jun 11, 2014 5:29 pm
by LanceHAOH
I did this problem in a different way from the rest. I saw that others were using stack to simulate the process but I used a general observation that I made to solve this problem (which is, if there is a larger preceding number in front of a later number, then the later number and its consecutive sequence must be displayed in a reversed order. e.g. "5 6 1 2 3 4" is wrong because "1 2 3 4" should be reversed if "5 6" precedes it in the output). I am passing most of the test cases that I found (see below):
Code: Select all
10
1 2 5 4 6 3 8 9 10 7
7 10 9 8 3 6 4 5 2 1
0
3
1 3 2
2 3 1
0
6
4 6 5 3 2 1
5 4 3 1 2 6
6 5 4 2 3 1
0
0
Code: Select all
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0
However, I cannot seem to pass this particular set of tests:
Code: Select all
70
1 2 4 34 5 63 48 30 64 42 23 61 13 68 3 52 24 60 19 36 66 22 53 17 65 69 27 10 29 8 31 32 33 58 51 20 43 38 39 40 41 11 37 44 45 28 47 16 49 50 35 7 14 54 55 56 57 12 59 25 15 62 6 9 18 21 67 46 26 70
23 62 64 34 13 20 24 36 3 42 25 68 9 35 26 7 58 37 38 46 67 44 53 47 12 65 2 63 29 52 31 55 59 27 8 21 57 16 39 4 54 43 17 28 5 51 40 1 49 50 33 19 22 66 14 56 11 61 15 18 45 48 6 69 32 41 10 60 30 70
48 62 36 70 16 20 24 6 23 9 25 32 60 35 4 42 68 13 27 46 50 44 66 57 12 65 2 63 11 52 34 5 14 30 54 67 21 47 38 3 41 43 17 45 55 53 40 49 29 28 33 19 22 51 31 26 56 61 15 7 8 58 64 69 1 37 10 39 18 59
25 47 33 22 16 39 20 6 48 9 57 32 36 40 46 42 30 64 3 38 65 44 66 68 14 10 2 17 37 29 56 60 21 49 54 67 28 61 8 4 41 55 59 45 58 53 50 26 35 27 51 23 70 34 1 24 19 18 15 7 11 13 63 69 5 43 52 31 12 62
69 31 58 28 8 25 49 56 26 11 61 41 44 37 34 12 32 64 15 29 19 14 46 68 45 47 48 43 54 2 42 30 1 20 51 67 23 57 16 13 65 55 60 35 33 53 22 52 27 10 18 38 70 63 4 66 5 7 39 3 59 21 36 50 6 40 17 9 24 62
25 33 58 28 8 69 48 56 44 11 20 41 15 37 36 12 32 21 4 55 19 14 50 68 45 57 3 38 54 46 42 30 31 61 29 18 10 27 16 13 65 5 2 35 17 6 52 22 47 23 1 43 70 26 63 51 24 7 39 49 59 64 34 67 53 40 60 62 66 9
40 33 39 9 61 69 36 56 44 11 20 41 15 37 60 12 32 52 13 55 19 14 50 68 45 57 3 38 54 46 70 30 59 29 8 18 10 48 34 4 65 21 2 35 17 6 42 22 47 23 1 25 5 26 63 51 24 7 58 49 31 64 16 67 53 43 27 62 66 28
29 49 39 9 61 24 36 56 23 11 20 67 5 37 60 12 32 52 13 69 50 14 40 68 45 57 64 1 54 46 70 30 59 19 8 28 10 55 34 4 65 7 2 35 17 6 42 22 16 44 41 25 15 26 63 51 48 21 58 33 47 3 31 38 53 43 27 62 66 18
0
30
22 24 20 1 16 9 13 27 30 25 3 7 4 2 11 23 10 17 19 6 28 26 15 18 12 29 21 8 14 5
5 2 19 1 3 7 20 28 17 4 13 16 29 22 21 24 25 23 11 12 9 8 6 30 15 14 27 18 10 26
7 22 21 9 24 14 26 23 17 5 1 13 10 30 25 28 27 8 29 6 3 15 12 20 19 2 18 11 4 16
1 22 21 13 24 14 26 23 17 5 9 7 10 30 25 28 27 8 29 6 3 15 12 20 19 2 18 11 4 16
13 21 14 6 3 11 26 2 4 5 9 23 10 7 8 17 20 1 22 18 24 15 16 27 29 30 25 28 12 19
1 15 10 6 28 9 18 27 25 14 24 12 30 13 20 26 23 29 22 2 4 11 16 5 7 19 21 3 8 17
0
76
1 2 3 4 5 6 7 8 9 10 11 12 13 34 15 16 17 18 19 20 21 22 23 24 25 26 27 39 29 30 31 32 33 63 35 36 37 38 28 40 41 42 69 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 14 64 65 66 67 68 43 70 71 72 73 74 75 76
0
86
1 3 55 53 44 6 48 39 34 61 28 54 10 84 19 77 57 18 82 16 73 52 32 85 43 83 36 60 62 49 4 46 23 50 75 38 37 58 41 40 33 31 81 45 42 9 47 15 71 35 13 24 27 59 72 51 25 2 67 69 26 70 14 64 80 21 8 68 5 12 11 30 17 74 65 20 29 78 22 56 86 79 76 66 63 7
53 51 1 78 59 23 18 3 81 57 28 54 22 13 85 42 34 32 2 49 45 27 55 50 43 66 4 60 30 62 37 46 75 73 76 10 6 9 58 40 15 31 5 39 20 68 61 56 11 63 36 79 38 64 72 12 71 77 26 25 8 70 48 65 84 52 83 14 69 16 67 86 17 74 47 82 29 80 33 19 44 21 24 7 41 35
24 74 40 76 59 23 86 3 30 52 22 42 9 56 83 77 34 60 2 21 55 8 69 15 19 36 41 27 73 32 31 46 54 64 75 20 47 80 48 39 50 65 44 58 10 1 35 61 85 63 29 26 49 28 70 79 71 18 45 25 82 57 5 38 14 7 43 68 4 51 67 12 17 78 62 81 37 16 33 11 53 66 72 13 6 84
78 74 40 76 55 16 86 84 49 52 5 42 9 56 83 39 34 60 18 21 22 59 69 15 19 10 63 38 73 32 31 46 54 64 75 20 14 80 26 77 62 65 79 58 36 1 35 61 85 41 29 48 30 28 2 44 71 70 45 25 82 57 8 27 3 7 17 37 4 51 67 12 43 24 47 81 68 23 33 11 53 66 72 13 6 50
78 63 40 35 55 16 86 84 62 60 5 42 9 56 83 39 34 52 59 41 22 7 50 15 19 61 74 38 73 32 71 46 54 64 75 48 14 80 45 77 51 3 79 58 36 12 76 10 85 66 21 30 20 28 2 49 31 70 24 25 82 37 8 27 18 47 17 23 4 68 67 1 43 65 29 81 44 26 33 11 53 57 72 13 6 69
13 39 66 35 55 20 40 30 17 58 2 25 85 56 31 45 61 52 59 72 42 7 62 6 70 54 74 68 43 14 78 23 15 10 5 48 38 27 84 77 51 32 21 83 36 46 44 63 12 1 18 64 53 41 69 37 81 8 57 75 82 73 34 80 3 47 60 71 4 29 67 24 76 50 28 86 65 26 33 11 79 19 9 16 22 49
66 39 13 38 55 27 40 15 41 4 2 33 85 82 31 45 61 8 59 72 42 7 62 6 73 54 47 68 43 14 25 32 30 10 5 48 35 20 84 77 51 3 21 83 36 18 44 63 12 1 46 23 53 17 69 37 81 52 57 75 56 70 34 80 64 74 60 24 58 29 67 50 76 71 28 86 65 26 78 11 79 19 9 16 22 49
49 39 13 3 71 70 2 66 41 14 40 35 42 82 30 11 69 37 59 72 67 61 63 84 73 33 85 68 86 4 57 32 27 80 34 48 25 20 46 31 74 45 21 83 62 18 50 26 36 29 6 75 81 17 58 56 60 43 44 54 38 51 47 10 16 53 23 24 52 1 5 77 79 9 28 7 65 76 12 78 8 19 55 64 22 15
23 5 74 50 75 33 2 51 71 14 37 38 61 67 12 36 69 76 60 20 32 62 42 86 63 72 81 7 79 64 28 16 45 44 49 25 9 56 46 31 52 85 83 3 40 18 27 13 55 11 35 30 73 43 77 53 57 68 80 54 19 4 59 58 70 17 29 10 24 1 15 39 26 82 41 22 21 47 84 78 65 48 8 66 6 34
69 27 74 71 5 66 2 63 86 25 37 18 82 62 21 40 6 76 3 20 32 65 26 41 51 15 48 7 79 64 84 39 45 44 49 14 68 56 72 42 8 19 36 38 33 83 12 75 55 11 16 77 30 22 59 53 57 73 80 29 85 4 13 58 70 28 54 10 24 1 46 35 31 61 9 43 17 47 23 78 67 81 52 60 50 34
0
22
10 3 16 5 9 4 1 15 18 2 11 22 13 20 12 6 21 7 17 8 14 19
4 19 11 1 6 15 21 14 8 9 12 20 7 13 2 22 17 3 18 5 16 10
9 10 16 20 1 17 13 22 12 4 5 18 15 8 19 2 3 21 6 14 7 11
16 4 3 13 9 19 7 1 18 20 12 22 6 17 2 15 5 10 14 8 11 21
2 4 16 15 8 10 3 5 22 20 19 6 7 1 11 12 17 13 9 18 21 14
4 6 3 17 10 18 22 19 14 21 16 9 15 12 1 20 13 2 7 8 11 5
21 1 16 8 2 5 6 20 17 10 14 4 11 3 13 9 18 7 19 22 12 15
4 6 16 12 13 18 15 8 9 3 2 7 5 21 22 11 14 19 10 1 17 20
14 17 5 16 12 22 11 21 15 2 18 9 4 3 8 19 7 1 6 10 20 13
9 5 2 14 11 12 19 7 6 18 10 21 4 20 8 22 13 15 3 17 16 1
0
95
1 2 18 4 42 6 5 8 9 10 11 80 55 7 62 16 66 3 19 20 21 22 23 92 25 26 27 28 61 93 14 32 33 34 35 36 37 38 39 53 41 31 57 44 45 94 43 48 49 50 51 52 86 54 56 58 47 46 59 60 15 13 63 64 65 17 89 68 69 91 71 72 73 74 75 76 77 30 79 12 81 29 83 40 85 70 87 88 67 90 84 24 78 82 95
1 84 31 36 10 66 9 21 52 7 8 2 19 34 62 55 5 3 42 88 86 50 23 74 47 43 91 44 70 11 64 71 33 76 17 27 60 38 46 94 81 12 56 28 37 59 20 48 49 85 51 63 61 95 16 78 75 92 90 13 41 24 79 22 40 29 83 26 69 25 57 72 89 15 14 45 77 30 65 6 39 67 58 32 35 82 87 93 68 4 80 73 18 53 54
1 29 28 36 78 66 9 68 25 48 8 2 19 21 52 59 74 3 42 6 86 47 90 5 50 43 91 26 7 80 64 71 40 76 17 39 10 38 46 94 20 12 56 88 37 67 81 61 49 27 69 34 45 95 16 24 85 92 65 13 11 60 79 72 33 84 70 44 51 62 57 93 89 15 14 83 77 30 75 31 35 55 87 18 58 82 23 22 63 4 41 73 32 53 54
39 68 10 86 74 66 50 88 75 3 67 4 19 11 58 59 41 49 54 14 30 6 91 38 9 17 24 37 57 61 64 71 70 76 87 90 73 8 46 25 80 56 78 60 83 31 34 7 40 5 2 52 51 95 16 55 85 92 53 29 36 65 82 23 33 63 89 79 45 13 12 77 1 42 15 47 93 26 27 21 35 84 62 18 43 94 20 22 72 48 69 28 32 81 44
63 92 14 95 38 54 50 5 53 3 28 7 88 11 73 45 62 67 75 44 59 6 2 81 51 19 35 40 90 41 64 4 89 76 87 71 24 61 25 27 56 42 79 31 83 58 1 9 82 68 17 72 91 34 16 65 94 10 30 86 36 66 8 57 33 21 23 48 39 18 85 37 20 77 70 47 29 46 74 32 15 84 22 60 43 49 12 78 26 80 52 55 13 93 69
93 89 30 52 38 32 46 5 53 50 28 7 88 11 9 45 62 67 75 92 26 6 64 81 47 58 35 40 95 41 84 4 44 54 87 71 20 61 18 34 74 42 29 31 86 56 1 73 82 76 17 69 43 27 12 65 94 24 14 83 36 48 8 57 33 21 23 66 39 79 85 37 3 77 70 68 25 63 49 51 10 2 22 60 91 19 16 78 90 80 59 55 13 15 72
50 89 30 69 38 84 20 5 42 93 28 3 67 14 48 4 62 88 11 76 78 94 82 68 47 72 35 40 95 41 21 45 52 26 79 92 18 91 12 49 74 53 73 31 7 80 1 56 39 24 64 70 43 60 46 65 87 17 75 19 23 9 51 57 33 32 36 66 77 6 85 37 86 22 83 81 25 63 34 8 10 2 27 54 44 61 16 71 90 29 58 55 13 15 59
50 8 95 69 60 3 13 40 19 55 39 47 74 16 29 83 26 34 54 51 71 67 82 62 14 77 35 28 70 41 84 32 91 89 52 92 25 43 12 49 56 85 1 86 7 38 94 64 66 53 20 23 36 72 93 30 9 48 73 87 42 21 4 24 11 59 37 76 44 78 75 31 58 15 57 2 22 27 63 45 10 65 79 80 61 17 88 6 90 18 68 5 33 46 81
36 42 95 15 60 24 8 84 19 55 22 47 1 14 29 83 31 75 54 73 71 67 82 94 16 61 51 28 34 56 48 32 27 74 78 76 25 38 43 10 3 85 65 72 7 12 66 23 50 53 68 30 62 49 93 64 26 40 35 91 13 21 4 70 11 59 44 92 37 39 41 89 58 57 9 80 77 87 63 45 86 88 79 2 52 17 69 6 90 18 20 5 33 46 81
36 42 95 15 89 56 55 84 19 8 22 47 21 14 29 83 31 32 54 73 71 67 82 94 50 61 51 28 34 24 48 74 27 69 78 76 25 38 43 10 3 62 65 72 7 12 39 23 16 53 68 30 85 49 93 64 26 40 35 91 13 1 4 70 11 59 44 86 37 66 41 60 58 57 9 80 77 87 63 92 45 88 79 2 52 17 75 6 90 18 20 5 33 46 81
0
62
3 2 1 4 45 6 7 8 9 10 11 12 13 14 15 16 17 18 59 20 22 21 33 24 25 26 43 50 29 30 58 32 31 34 35 36 37 38 39 40 41 42 27 44 5 46 47 48 49 28 51 52 53 54 55 56 57 23 19 60 61 62
12 3 23 4 19 58 56 8 26 1 42 2 13 22 15 55 17 18 59 32 47 21 16 24 25 36 57 50 20 30 52 29 31 45 14 9 37 38 39 11 61 40 27 33 5 46 44 54 49 48 51 43 53 28 35 7 41 10 34 60 6 62
5 2 58 3 47 19 17 8 12 11 48 23 33 49 1 29 32 18 14 36 15 4 16 6 35 62 7 20 31 51 13 60 44 24 61 43 37 42 10 39 22 38 41 54 52 28 59 50 34 53 55 9 57 25 56 21 40 26 46 30 45 27
5 52 58 3 47 7 17 8 21 11 48 43 18 49 1 29 23 27 14 9 51 4 16 10 35 36 19 45 34 54 13 2 44 24 41 55 37 42 60 39 22 38 25 15 6 28 59 50 31 33 57 62 32 61 53 12 40 26 46 30 20 56
5 16 37 15 33 7 17 47 21 11 48 30 18 49 1 29 36 27 38 9 31 39 52 12 35 23 19 2 51 54 13 45 22 60 41 55 32 50 24 43 25 44 20 3 6 28 4 42 34 26 57 62 59 61 53 10 40 14 46 58 8 56
5 41 1 15 43 7 28 37 9 11 27 48 57 29 52 44 38 54 55 32 23 33 30 3 20 8 58 36 61 35 49 45 21 17 16 46 12 25 14 6 50 13 53 31 51 40 47 59 60 26 39 42 18 2 34 4 62 19 24 10 56 22
0
84
31 2 37 19 14 6 7 62 9 35 44 24 13 33 15 16 3 28 26 46 74 53 38 58 22 11 27 49 42 30 40 50 71 34 76 25 43 23 39 29 57 72 17 12 83 65 47 48 4 82 45 51 70 66 52 56 63 18 59 60 84 73 1 64 20 8 67 68 5 36 32 21 54 41 75 69 77 78 79 55 81 10 80 61
53 72 1 75 41 6 20 54 27 77 24 19 25 46 55 76 3 22 13 70 74 33 78 59 71 82 36 5 51 7 66 43 65 15 45 37 84 23 26 21 57 16 58 12 83 17 28 34 63 38 39 9 50 42 49 11 4 18 29 30 64 61 68 67 14 10 79 81 35 52 62 48 60 80 8 69 56 44 32 47 2 31 40 73
48 4 69 79 41 16 20 54 27 77 60 38 45 46 55 76 3 70 13 52 19 33 78 59 71 51 36 5 82 7 72 43 66 14 22 35 84 23 26 75 57 34 58 12 83 17 28 64 31 18 67 9 25 42 49 61 39 74 11 10 6 50 68 65 15 30 37 81 21 47 62 53 24 80 8 1 56 44 32 29 2 40 63 73
23 4 33 20 28 80 35 54 59 77 39 66 55 42 14 48 76 58 13 70 19 27 61 41 84 67 79 5 69 62 63 73 57 78 22 60 82 6 16 75 38 56 11 81 3 17 8 64 1 18 51 9 25 2 49 45 36 74 52 10 43 50 68 65 44 30 31 21 7 47 26 37 24 46 83 15 72 53 32 29 34 40 12 71
45 74 33 54 61 80 35 57 59 47 39 20 55 42 14 48 76 58 65 70 83 27 28 41 84 67 79 78 69 62 25 49 43 5 22 60 82 6 16 75 38 2 64 81 3 17 8 11 1 18 15 9 19 56 73 23 36 4 52 10 66 50 68 13 44 30 31 21 7 77 26 37 24 46 63 51 72 53 32 29 34 40 12 71
45 74 25 54 6 80 35 81 59 47 39 20 55 42 31 3 76 58 65 83 22 9 28 17 84 67 70 78 69 27 73 51 48 5 21 60 82 49 16 75 38 41 64 72 43 53 8 11 1 18 15 32 19 29 57 23 26 4 52 10 66 50 68 13 44 30 14 79 7 77 36 56 24 46 63 62 33 2 61 37 34 40 12 71
45 6 67 54 58 79 11 42 59 33 15 2 44 20 23 3 22 27 29 32 63 37 30 68 70 84 81 17 39 40 83 51 34 72 4 77 66 10 16 18 25 7 1 19 49 36 8 53 76 12 60 35 75 26 57 31 80 78 52 28 64 50 82 13 41 46 47 65 62 74 5 69 24 73 9 48 38 21 61 55 56 43 14 71
45 6 67 21 74 79 7 42 52 33 15 12 36 58 55 3 22 8 1 32 63 46 4 68 51 84 81 72 30 40 83 70 34 17 2 77 66 10 54 38 25 29 11 19 49 44 27 53 76 39 60 35 75 26 57 31 80 78 9 28 64 50 5 14 41 37 47 65 61 20 82 69 24 73 59 48 18 16 62 13 56 43 23 71
45 21 20 6 74 79 7 30 52 33 43 12 57 10 55 51 22 8 1 32 66 46 73 68 3 84 81 72 42 40 83 70 34 9 2 77 63 58 13 65 80 29 11 17 49 44 27 53 76 39 60 35 75 26 36 31 25 78 82 28 64 50 5 14 41 37 47 38 61 67 19 69 24 4 59 48 18 16 62 54 56 15 23 71
0
79
1 6 54 4 60 30 69 64 32 16 22 12 71 50 42 11 31 23 19 20 43 40 63 73 25 9 66 55 14 24 68 13 17 10 36 26 2 38 8 65 45 15 72 56 37 46 53 33 21 41 35 76 44 79 61 47 27 3 59 39 51 62 18 57 58 78 52 48 7 70 77 49 34 74 75 67 28 5 29
0
55
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
1 2 17 4 5 35 7 30 11 39 47 50 37 48 33 16 18 28 41 44 40 36 23 24 27 26 25 12 29 31 55 19 49 34 3 22 6 38 8 13 32 42 43 20 45 21 9 10 53 15 51 52 14 54 46
20 34 52 31 10 48 55 42 11 39 3 2 19 29 18 4 1 7 22 35 28 41 9 8 15 26 46 12 33 24 30 6 25 43 54 32 21 38 49 40 27 13 47 51 44 23 50 5 53 37 16 36 17 14 45
0
36
6 1 28 8 29 12 4 7 11 35 27 36 13 17 5 9 14 20 2 32 30 10 25 21 18 23 3 22 33 16 31 19 26 15 24 34
6 7 24 8 1 15 36 21 11 35 27 22 12 17 4 9 16 20 19 32 30 10 25 3 26 14 2 5 33 13 31 29 18 23 28 34
3 7 31 8 1 15 36 21 11 5 27 22 12 17 4 9 35 20 26 32 30 10 18 6 19 14 2 16 33 13 24 29 25 34 28 23
7 27 13 33 19 14 34 1 2 6 10 25 3 36 24 32 15 30 11 28 35 9 20 12 18 8 31 23 21 22 4 17 26 29 16 5
7 11 10 14 19 30 34 21 22 29 27 15 2 36 1 32 23 25 4 12 20 16 24 33 18 3 26 17 31 9 5 8 13 35 6 28
5 6 29 18 26 30 35 36 10 9 20 15 14 8 4 16 19 34 2 7 12 13 32 11 3 22 33 21 17 24 31 1 27 28 25 23
28 29 20 13 27 21 1 26 10 31 8 14 6 11 9 32 4 34 2 7 17 23 3 36 35 5 18 12 15 25 24 19 30 33 22 16
0
4
3 2 4 1
0
14
4 9 5 3 14 12 2 6 10 11 8 7 1 13
9 14 6 12 3 2 7 4 1 11 8 10 13 5
11 10 6 7 5 3 14 1 8 2 4 9 12 13
4 7 8 13 5 3 14 11 10 6 1 9 12 2
3 1 8 5 13 11 10 12 4 9 7 6 14 2
8 7 9 10 1 6 14 4 12 2 5 13 11 3
2 8 13 14 1 7 12 6 5 11 3 4 10 9
1 6 10 2 5 3 14 8 13 7 9 12 4 11
0
54
46 25 37 23 50 52 30 2 18 26 11 15 13 16 12 41 40 44 31 49 34 35 9 27 38 10 32 28 22 3 45 24 33 19 17 4 43 54 1 8 14 42 21 5 29 53 39 48 20 47 51 6 7 36
46 25 37 23 34 52 30 2 18 26 38 15 13 16 12 22 44 40 31 49 50 35 9 29 11 10 32 28 8 3 45 20 33 19 17 4 43 54 1 41 14 42 21 5 27 53 39 48 24 47 51 6 7 36
8 35 1 12 53 24 30 45 14 33 19 27 22 18 46 21 42 13 17 6 50 44 25 29 9 48 41 15 40 3 38 20 26 51 11 4 23 54 5 31 34 49 2 37 43 52 39 10 32 47 16 36 7 28
14 50 39 32 24 13 48 27 28 1 30 31 52 25 41 49 18 34 17 42 40 2 36 45 12 38 4 10 51 54 29 53 37 22 7 26 23 15 11 8 3 47 21 5 20 6 43 19 16 9 35 44 46 33
27 26 5 32 12 39 48 14 45 13 41 7 15 25 30 49 1 50 17 42 9 2 36 4 16 38 34 10 51 54 29 53 37 22 24 47 23 52 11 8 20 46 21 18 3 6 43 31 19 40 35 44 28 33
43 36 5 18 41 49 48 10 9 32 40 7 15 21 47 44 14 19 26 45 22 33 4 30 52 31 1 23 51 42 28 38 2 17 3 13 39 50 35 37 27 53 16 34 29 20 8 54 12 25 6 24 11 46
43 21 11 6 10 42 36 33 9 32 18 46 15 26 14 44 51 3 7 22 12 41 16 34 52 47 1 35 17 49 54 48 2 40 45 13 27 50 29 37 23 31 30 8 4 20 53 28 25 19 39 24 5 38
0
0
My program's output:
Code: Select all
No
No
No
Yes
No
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
Yes
No
Yes
No
No
No
Yes
No
Yes
No
No
No
No
No
No
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
Yes
No
No
Yes
No
Yes
Yes
Yes
AC Output:
Code: Select all
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
I have pasted my code below. Could someone please explain to me why my logic is wrong?
Code: Select all
import java.util.Scanner;
class Main
{
public static void main(String[] args)
{
int num_trains = 0;
String can_arrange = "";
Scanner in = new Scanner(System.in);
while(true)
{
num_trains = in.nextInt();
if(num_trains == 0) break;
int[] order = new int[num_trains];
/* Process one block */
while(true)
{
can_arrange = "Yes";
int index = 0;
int max_so_far = 0;
while(index < num_trains)
{
/* Get one configuration */
order[index++] = in.nextInt();
if(index > 0 && order[0] == 0) break;
}
if(order[0] == 0) break;
/* process the configuration */
for(index = 0; index < num_trains - 1; index++)
{
max_so_far = (int) Math.max(order[index],max_so_far);
if(max_so_far > order[index] && order[index] == order[index+1] - 1)
{
can_arrange = "No";
break;
}
}
System.out.println(can_arrange);
}
System.out.println();
}
}
}
Re: 514 Rails: WA
Posted: Wed Jun 11, 2014 8:28 pm
by brianfry713
I solved it using a stack.
Re: 514 Rails: WA
Posted: Thu Jun 12, 2014 8:53 am
by LanceHAOH
Yeah. All the other solutions that I saw also used a Stack. But why is my logic wrong?
Re: 514 Rails: WA
Posted: Thu Jun 12, 2014 9:52 am
by LanceHAOH
After thinking it through, there is apparently nothing wrong with my logic. It is just that I used the wrong method to determine whether a number was in a reversed position or not.
The following is the offending block of code:
Code: Select all
/* process the configuration */
for(index = 0; index < num_trains - 1; index++)
{
max_so_far = (int) Math.max(order[index],max_so_far);
if(max_so_far > order[index] && order[index] == order[index+1] - 1)
{
can_arrange = "No";
break;
}
}
I incorrectly thought that a number was reversed in its sequence when its following element is 1 greater than it. But this proposition can easily be countered by the following case:
6
4 5 2 1 3 6
In this case, the incorrect code will output "Yes" because "2 1 3" seems to be reversed as the element after 1 is 3 (this leads to an incorrect answer as 3 - 1 > 1). But actually, the correct form should be "3 2 1".
I finally figured that no matter what the arrangement is, a number is reversed in its sequence if the preceding element is greater than it. This led me to alter the incorrect code to the following:
Code: Select all
/* process the configuration */
for(index = 1; index < num_trains; index++)
{
max_so_far = (int) Math.max(order[index],max_so_far);
if(max_so_far > order[index] && order[index] > order[index-1])
{
can_arrange = "No";
break;
}
}
And finally ... I got the coveted AC result!
514 - Rail : WA
Posted: Fri Jun 27, 2014 9:49 pm
by AmirAz
Hello this is my code, I have tested it with every input on this forum and it generates the expected output. But still I get WA on the Online Judge.
Note : I have tried this code with int, long int and long long int but none worked.
Code: Select all
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <list>
#include <algorithm>
#include <ctype.h>
#include <vector>
#include <stack>
using namespace std;
int main(){
long long int n;
cin >> n;
while (true){
long long int a; cin >> a;
while (a)
{
stack<long long int> A, S, B; long long int *res = new long long int[n]; res[0] = a;
for (long long int i = 1; i < n; i++)
cin>>res[i];
for (long long int i = n; i; i--) A.push(i);
while (A.size() || S.size()){
if ((S.empty() || S.top() != res[B.size()]) && A.size()) {
S.push(A.top());
A.pop();
}else if ((A.empty() || S.top() == res[B.size()])){
B.push(S.top());
S.pop();
}
}
long long int i;
for (i = n-1; i>=0; i--){
if (B.top() == res[i]){
B.pop();
}
else
i = -1;
}
if (B.empty()) cout << "Yes\n";
else cout << "No\n";
cin >> a;
}
cin >> n;
if (n)cout << "\n"; else return 0;
}
}
Re: 514 - Rail : WA
Posted: Tue Jul 08, 2014 12:42 am
by brianfry713
Print a blank line after the last test case.
Re: 514 - Rails
Posted: Thu Oct 23, 2014 6:51 am
by alecassis
Hey guys, I've tried every test case in this thread but can't get AC.
Can anyone help me telling what's wrong or give some more test cases?
Thanks in advance.
Re: 514 - Rails
Posted: Thu Oct 23, 2014 10:36 am
by lighted
In addition, there is one empty line after the lines corresponding to one block of the input file
You must print blank line after each block of input. Remove line
Change code to
Code: Select all
counter++;
puts("");
}
return 0;
}
Re: 514 - Rails
Posted: Thu Oct 23, 2014 4:24 pm
by alecassis
Thanks a lot! Got AC
Re: 514 - Rails
Posted: Sun Oct 26, 2014 2:42 am
by milesstevenson
Edit: Please see my post below for my updated code.
Re: 514 - Rails
Posted: Sun Oct 26, 2014 9:20 am
by lighted
Try to check input in this thread before posting.
shipu_a wrote:input:
output:
tan_Yui wrote:Hi, sunnycare and everyone.
Following input may help you for debugging.
Input :
Code: Select all
5
1 2 3 4 5
5 4 1 2 3
1 4 3 2 5
3 4 2 5 1
3 4 2 1 5
4 3 5 2 1
0
3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
0
4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
0
10
5 7 10 9 8 6 4 3 2 1
5 6 4 8 7 3 2 9 1 10
0
0
Code: Select all
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
No
Yes
No
No
No
No
No
Yes
Yes
Yes
Best regards.
http://www.udebug.com/UVa/514
Re: 514 - Rails
Posted: Sun Oct 26, 2014 8:46 pm
by milesstevenson
It seems I pass on all of the test cases in here, including the test cases from the previous post, but still get WA.
Code: Select all
import java.util.Scanner;
import java.io.OutputStream;
import java.io.IOException;
import java.util.ArrayDeque;
import java.io.PrintWriter;
import java.util.Deque;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
* @author Miles Stevenson
*/
class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
Scanner in = new Scanner(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task514 solver = new Task514();
solver.solve(1, in, out);
out.close();
}
}
class Task514 {
int n;
int[] temp;
Deque<Integer> railwayA;
Deque<Integer> railwayB;
Deque<Integer> trainStation;
public void solve(int testNumber, Scanner in, PrintWriter out) {
while (in.hasNext()) {
n = in.nextInt();
temp = new int[n];
if (n == 0) {
return;
}
else {
parseTrain(in, out);
}
}
}
public void parseTrain(Scanner in, PrintWriter out) {
int i = 0, coach;
String train;
while (in.hasNext()) {
coach = in.nextInt();
if (i == n && coach != 0) {
railwayB = new ArrayDeque<Integer>();
trainStation = new ArrayDeque<Integer>();
initRailA();
stackCoaches(out);
i = 0;
temp = new int[n];
temp[i] = coach;
++i;
}
else if (i == n && coach == 0) {
railwayB = new ArrayDeque<Integer>();
trainStation = new ArrayDeque<Integer>();
initRailA();
stackCoaches(out);
out.println();
return;
}
else if (i != n && coach == 0) {
out.println();
return;
}
else {
temp[i] = coach;
++i;
}
}
}
public void stackCoaches(PrintWriter out) {
for (int i = 0; i < n; ++i)
railwayB.push(temp[n - i - 1]);
marshallCoaches(out);
}
public void marshallCoaches(PrintWriter out) {
while (railwayA.size() > 0) {
if (railwayA.peek() == railwayB.peek()) {
railwayA.pop();
railwayB.pop();
}
else if (trainStation.peek() == railwayB.peek()) {
railwayB.pop();
trainStation.pop();
}
else {
trainStation.push(railwayA.pop());
}
}
while (trainStation.size() > 0) {
if (trainStation.peek() == railwayB.peek()) {
trainStation.pop();
railwayB.pop();
}
else {
out.println("No");
return;
}
}
if (trainStation.size() == 0)
out.println("Yes");
}
public void initRailA() {
railwayA = new ArrayDeque<Integer>();
for (int i = 0; i < n; ++i)
railwayA.push(n-i);
}
}