514 - Rails

[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;
}

[brianfry713]

Try running your code on the sample input.

[anup10.duet]

AC

[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();
		}
	}
}

[brianfry713]

I solved it using a stack.

[LanceHAOH]

Yeah. All the other solutions that I saw also used a Stack. But why is my logic wrong?

[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!

[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;
		
	}

}

[brianfry713]

Print a blank line after the last test case.

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

Code: Select all

got AC thks!

[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

Code: Select all

if (counter > 0) puts("");

Change code to

Code: Select all

    counter++;
    puts("");   
  }
  return 0;
}

[alecassis]

Thanks a lot! Got AC

[milesstevenson]

Edit: Please see my post below for my updated code.

[lighted]

Try to check input in this thread before posting.

input:

Code: Select all

10
1 2 5 4 6 3 8 9 10 7
0
0

output:

Code: Select all

Yes

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

Output :

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

[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);
    }
}