I use recursion method for solve this problem.But it verdict as TLE. How can i improve my code? Here is my code>

#include<iostream>
#include<stdio.h>
#include<algorithm>

using namespace std;


int fac(int a,int b)
{
    if(a==1)
        return 1;
     else if(a<0 || a==0)
            return 2;

    else
        return a*fac(a-b,b);
}

int main()
{
    int n,k,a;
    long long int sum;

    while(scanf("%d %d",&n,&k)!=EOF)
    {
         sum=1;

        if((n>=1 && n<=10)&& (k>=1 && k<=20)){

        sum=sum*fac(n,k);
        cout<<sum<<endl;
        }

    }
    return 0;
}

Could anyone helps me with test 7?

I wrote simple (dummy) solution - just store all input values in array - then sort it (qsort) - and write array[n/2].

I use free pascal.

On my PC program works correct. at least there no any runtime errors. I tested it with input N=1, 2, 3, 5, 1000, 500000. I enabled all checks like I/O, range check, stack check, overflow check, even init variables with garbage...

Could s/w get me any clue what can be wrong?

my last try - id 6409005

Edited by author 16.09.2015 13:22

Edited by author 13.09.2015 07:34

wrong ans #26.Is there any test.

String s = scanner.next();
        TreeSet<String> c = new TreeSet<String>();
        for (int i=0; i<s.length(); i++) {
            c.add(s.substring(i));
        }
        int L = c.size() + 1;
        long total = L - c.first().length();
        while(c.size()>1) {
            String first = c.pollFirst();
            String second = c.first();
            int lcp = LCP(first, second);
            total+= L - second.length() - LCP(first, second);;
        }
        System.out.println(total);

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