I used Java: The following I did.
1. Declare Stack<Integer>.
like this:         Stack<Integer> st = new Stack<Integer>();
                   boolean ok = false; <--// this boolean is tricky.. :))
2. Then, I iterate from 1 to n init i read X and i checked three given if statements in input. They are:
1.if(x>0){st.push(x);}
2.if(x==-1){pw.println(st.pop());}
3.if(x==0){
       int len = st.size();
       if(2*len<=n){
                st.addAll((Collection) st.clone());
    } else{
           if(!ok){
// here If you don't use this if statement you will have Memory Limit #42...
                      st.addAll((Collection<? extends Integer>) st.clone());
             ok=true;
            }
    }
}
Problem is copying all stack elements...
What I am really doing here is using stack clone() method. But When you do so many clones will have MemLimit. That's why I checked that my Stack size and its copies are more than N (2*len>n) then I should copy the whole stack one time not more.
And I am thinking that above code worked because <b<stack size wansn't big enough when I cloned last time....

Sorry If I am mistaken and poor english. But this code AC ...

Edited by author 13.09.2015 07:35

#include <iostream>
#include <math.h>
using namespace std;
int main()
{
double m,n;
 int a[70000],g;
int N;
    cin>>N;
    for  (int i=1; i<=N; i++)
    {
 cin>>m;
  n=(-1+sqrt(8*m+1))/2;
 if((n!=(int)n)){
   g=n;
   g++;
}
else
{
g=n;
}
g--;
int k=((1+g)*g)/2;
if(m-k==1)
a[i]=1;
else
a[i]=0;
}
for(int i=1;i<=N;i++)
 cout<<a[i]<<" ";
    system("pause");
    return 0;
    }

Edited by author 26.11.2013 20:50

222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322222222322
5
a
aa
afa
aaaa
aafaa
-1

this test solved very quickly.


my code:

public class T1002 {

    public static int nnn = 100000;
    public static String sss = "";

    public static int nnn2 = 100000;
    public static String sss2 = "";

    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(System.out);

        HashMap<String,String> hashMap = new HashMap<>();

        while (true) {
            String s = sc.nextLine();

            int length = s.length();

            if (s.charAt(0) == '-' && s.charAt(1) == '1') {
                break;
            } else{
                int n = sc.nextInt();
                for(int i = 0;i<n;i++){
                    String s1 = sc.nextLine();
                    String s2 = change(s1);
                    hashMap.put(s2,s1);
                }
                solve(0,length,s,hashMap,new StringBuilder(""));
                solve2(0,length,s,hashMap,new StringBuilder(""));
                if(nnn == 100000 && nnn2 == 100000){
                    out.println("No solution.");
                } else {
                    if(nnn<nnn2){
                        out.println(sss);
                    } else {
                        out.println(sss2);
                    }
                    nnn = 100000;
                    sss = "";
                    nnn2 = 100000;
                    sss2 = "";
                }
                hashMap.clear();
            }
        }

        out.close();
    }

    public static void solve(int x,int y,String s,HashMap<String,String> hashMap,StringBuilder sb){
        if(x == y){
            nnn = sb.length();
            sss = sb.toString();
        } else if(x != 0){
            sb.append(" ");
        }

        for(int i = y;i>x;i--){
            if(hashMap.containsKey(s.substring(x,i))){
                String s1 = hashMap.get(s.substring(x,i));
                if(nnn == 100000) {
                    solve(x + s1.length(), y, s, hashMap,sb.append(s1));
                }
            }
        }


    }

    public static void solve2(int x,int y,String s,HashMap<String,String> hashMap,StringBuilder sb) {
        if (x == y) {
            nnn2 = sb.length();
            sss2 = sb.toString();
        } else if (y != s.length()) {
            sb.insert(0," ");
        }

        for(int i = x;i<y;i++){
            if(hashMap.containsKey(s.substring(i,y))){
                String s1 = hashMap.get(s.substring(i,y));
                if(nnn2 == 100000) {
                    solve2(x, y - s1.length(), s, hashMap,sb.insert(0,s1));
                }
            }
        }
    }

    public static String change(String s){
        StringBuilder sb = new StringBuilder("");
        for(int i = 0;i<s.length();i++){
            if(s.charAt(i) == 'i' || s.charAt(i) == 'j'){
                sb.append("1");
            } else if(s.charAt(i) == 'g' || s.charAt(i) == 'h'){
                sb.append("4");
            } else if(s.charAt(i) == 'k' || s.charAt(i) == 'l'){
                sb.append("5");
            } else if(s.charAt(i) == 'm' || s.charAt(i) == 'n'){
                sb.append("6");
            } else if(s.charAt(i) == 'p' || s.charAt(i) == 'r' || s.charAt(i) == 's'){
                sb.append("7");
            } else if(s.charAt(i) == 'a' || s.charAt(i) == 'b' || s.charAt(i) == 'c'){
                sb.append("2");
            } else if(s.charAt(i) == 't' || s.charAt(i) == 'u' || s.charAt(i) == 'v'){
                sb.append("8");
            } else if(s.charAt(i) == 'o' || s.charAt(i) == 'q' || s.charAt(i) == 'z'){
                sb.append("0");
            } else if(s.charAt(i) == 'd' || s.charAt(i) == 'e' || s.charAt(i) == 'f'){
                sb.append("3");
            } else if(s.charAt(i) == 'w' || s.charAt(i) == 'x' || s.charAt(i) == 'y'){
                sb.append("9");
            }
        }
        return sb.toString();
    }

    public static class MyScanner {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = System.in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        public long[] nextLongArray(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }

}

Hello,

I just had a WA in test number 6.

After some research found out that my code failed at this test:

1234567ikkjji890

Mind that I used numbers instead of letters for better visibility.

n=1
x=[]
while(n<=10):
    j=int(input())
    if j==0:
        break
    else:
        n+=1
        x.append(j)
def fun(k):
    if k==0:
        return 0
    if k==1:
        return 1
    if (k%2==0):
        return fun(k//2)
    if not(k%2==0):
        return (fun(k//2)+fun(k//2+1))
for l in range(0,len(x)):
    if x[l]%2==0:
        print(fun(x[l]-1))
    if not(x[l]%2)==0:
        print(fun(x[l]))

i used Fleury algorithm to find a Euler cycle

Edited by author 11.09.2015 12:47

p
n
p=0 and n=0    undefined
p=0 and n!=0   error
p!=0 and n=0   error
v (p=0 error, n=0 undefined, vg<=0 error)
t (n=0 error, p=0 undefined, tg<=0 error)

please help！I can't find the bug.

Edited by author 10.09.2015 07:36

My algorithm:

I run BFS to assign levels (DISTANCE TO THE ROOT) to each node.

Then, when read the queries:
If the level of both nodes are the same, no exist any path between them. Answer is 0
If the level of qA is less than level of qB, maybe exist a path between them. Find it.
If found a path, Answer is 1
If no path had been found, and the level of qA is greater than level of qB, Find a path.
If found a path, Answer is 2
If none of the previous worked, the answer to the querie is 0.


I read that it could be solved with LCA, but I think that it's better and elegant algo.
Please help me. Maybe my algo is right, but my problem may be on the code. If need to see code, i'll post it.

Edited by author 11.07.2015 20:44

I couldn't understand why my program got WA in test 22. Can anyone give me some help. Thanks

Есть у кого нибудь идеи?

Can anybody give some hits or information on test 28, thanks!

Is there any linear solution to this problem? I have implemented an O(NlogN) one.

Let me tell you the  way I've solved it. We just pick our last vertex (number) as a root and try to divide another part into 2 subtrees. In order to do this we find a border between those 2 parts, so that all numbers in the first part are less than our root and vice-versa for second part. The latter can be easily implemented using binary search. And then we just do all the same from the very beginning with both parts recursively. It's obvious that the only time-consuming part is binary search, which takes O(logN) time in the worst case. Therefore the complexity of this algorithm is O(NlogN).

Idea is Dijkstra (N times from every node). I can proof that minimal cycle turns when we  add one edge in root tree (tree of distance).

Edited by author 06.09.2015 15:53

Edited by author 06.09.2015 15:54

But AC with C array.

Every solution gives "Restricted function"
Example:
task "1000. A+B Problem"
I'm sending the simplest ever go program (without any import or function call):

package main
func main() {
}

(solution id 6393085)
And get "Restricted function an test 1":
6393085    Evgeny Sibil    1000. A+B Problem    Go 1.3    Restricted function    1

For example
3
12
23
23
67

There are three correct answers:
Error in record #1. Correct number is: 21.
Error in record #2. Correct number is: 32.
Error in record #3. Correct number is: 32.

Wrong answer for this test:
Unrecoverable error.