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.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class T1226_esreveR_redrO {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in, "ISO-8859-1"));
        PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out, "ISO-8859-1"));
        String line = "";
        while ((line = reader.readLine()) != null) {
            String[] lineSplit = line.split(" ");
            reverse(lineSplit);
            String lineReversed = "";
            for (int i = 0; i < lineSplit.length - 1; i++) {
                lineReversed = lineReversed + lineSplit[i] + " ";
            }
            lineReversed = lineReversed + lineSplit[lineSplit.length - 1];
            writer.println(lineReversed);
        }
        writer.flush();

    }

    private static void reverse(String[] lineSplit) {
        for (int i = 0; i < lineSplit.length; i++) {
            String head = "";
            String tail = "";
            String word = lineSplit[i];
            if (!Character.isLetter(word.charAt(0))) {
                head = word.charAt(0) + "";
                word = word.substring(1, word.length());
            }
            if (!Character.isLetter(word.charAt(word.length() - 1))) {
                tail = word.charAt(word.length() - 1) + "";
                word = word.substring(0, word.length() - 1);
            }
            StringBuffer sb = new StringBuffer(word);
            sb = sb.reverse();
            word = head + sb.toString() + tail;
            lineSplit[i] = word;
        }
    }

}

We have to perform some service works with Timus Online Judge. So for a couple of days solutions could be checked with delays up to several hours. Just keep patience.

If you're doing a greedy solution and you're sorting by the rightmost endpoints (B_i), you need to sort with the leftmost endpoints as second key. That is, if B_i == B_j, the shortest segment of i and j goes first in the list.

This basically means that longer segments are kept, so for inputs:

3
3 5
1 5
5 6

You would get result
2
1 5
5 6

instead of
2
3 5
5 6

which means you get a bigger covering of the set but the problem statement didn't mention this requirement.

Edited by author 24.12.2014 21:07

program Bourne;
  var
    n,i,j,x:longint;
    a:array[0..150000] of smallint;
    b:array[0..150000] of longint;
  begin

    readln(n);
    for i:=1 to n do
      begin
        readln(b[i],a[i]);
      end;

    for x:=100 downto 0 do
      begin
        for i:=1 to n do
          if a[i]=x then writeln(b[i],' ',a[i]);
      end;

  end.