This problem is just to troll you. I first thought of doing it using suffix array. Just read the question properly, it says 'any substring'?

I got AC http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=10161&courseid=0, but here I got WA1. Why???

My solution:
Cutting the array into blocks, so I can now update a segment with O(sqrt n) each query;
therefore, I can get the increase in O(1) while scanning each factor (at most 180 in total).
It is obvious that I should prepare all the factors for each number.

The complexity of the algorithm is O((sqrt(n) + 180) * m + 180 * n).

and .. I reduce a lot of modular and divide operations to get this AC. :P

Edited by author 25.10.2015 00:21

Edited by author 26.10.2015 23:24

using System;
class First {
    static void Main() {
        String[] ss = Console.ReadLine().Split();
        Console.WriteLine (int.Parse(ss[0]) + int.Parse((ss[1]));
            }

}

Anyone knows what's the problem with 2nd test? any ideas, please!!

do i misunderstand the meaning of this problem?
64631000033 is a prime,why it not the right answer of the sample?
please help me!thanks!

As far as I understand the tasks the 12 digit number should be prime.
Can it have leading zeros?
Can the number 646310000033 be a corect output for the sample input?
And how to format long long (was it "%I64" ?)?
 Rostislav

Edited by author 19.02.2005 15:48

Stuck at test case #12

Per reply in 2008, someone suggested testing with axayaaxa

I don't know whether this is the real #12. But I tried anyway.

My program answers a x aya axa

And another possible answer is axa y a axa

Both with 4 palindromes. Question says output any is correct.

Suggestion?

Thanks in advance!

import java.util.Scanner;

/**
 * Created by Coder on 05.12.2014.
 */
public class Copy1131_ {
    public static void main(String[] args) {
        Scanner x = new Scanner(System.in);
        int n = x.nextInt();
        int k = x.nextInt();
        int time = 0, i = 1;
        long s = 1;
        while (s < n) {
            if (i >= k) {
                s += k;
            } else {
                s += i++;
            }
            time++;
        }
        System.out.println(time);
    }
}

from math import sqrt
s=input().replace("\n"," ").split()
x=[sqrt(int(i)) for i in s]
x.reverse()
for i in  x:
    print("%.4f"%i)

Pretty much, my program runs as correctly as I can think of...
I am even trying with input such as:

9
Physics education education
Thursday 3
Maths education AND A LOT OF FUN FUN1 FUN LOT OF FUN FUN1 FUN  FUN education education
Tuesday 1
Chemistry education
Thursday 1
Physical education1 education
Saturday 2
Astronomy
Saturday 4
Urban geography AND A LOT OF FUN FUN1 FUN LOT OF FUN FUN1 FUN  FUN education educationA LOT OF FUN FUN1 FUN LOT OF FUN FUN1 FUN  FUN education       educationA A LOT OF FUN FUN1 FUN LOT OF FUN FUN1 FUN  FUN education education
Tuesday 4
A A A A A A A A A A A A A A A  A A A A A A A AA A A  AA  AA A A  AAA  AA  A A  A  A AA  A A A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A  A  A AA  A
Saturday 1
Modeling
Thursday 2
Biology
Thursday 4
1
education
Thursday 2

And it still works. What is test number 3?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Threading.Tasks;

namespace T1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse (Console.ReadLine ());
            int[] data = new int[]{2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161};
            int[] result = new int[n];
            for (int i = 0; i < n; ++i)
                result [i] = data [int.Parse (Console.ReadLine ()) - 1];
            for (int i = 0; i < n; ++i)
                Console.WriteLine (result [i]);
        }
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class _1496 {
    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);
        int amount = s.nextInt();
        if (amount == 0) System.out.println("0");
        else {
            String[] source = new String[amount];
            String[] uniT = new String[amount];
            int j = 0;
            int count = 0;
            for (int i = 0; i < amount; i++) {
                source[i] = s.nextLine();
            }
            Arrays.sort(source);
            uniT[0] = source[0];

            for (int i = 0; i < amount; i++) {
                if (source[i].equals(uniT[j]) != true) {
                    j++;
                    uniT[j] = source[i];
                }
            }
            for (int i = 0; i <= j; i++) {
                count = 0;
                for (int k = 0; k < amount; k++) {
                    if (source[k].equals(uniT[i])) {
                        count++;
                    }
                }
                if (count > 1) {
                    System.out.println(uniT[i]);
                }
            }
        }
    }
}

8
a2 b3 h1
WHITE WINS
8
a2 b3 g2
BLACK WINS

8
d6 e7 e6
BLACK WINS

(if you use DP as me, the following tests are useful)
8
a6 h2 g2
WHITE WINS
8
a2 b3 g3
BLACK WINS

8
a2 b4 h1
BLACK WINS
8
a2 b3 h1
WHITE WINS

The problem is really good. It makes me more considerate and ..trains my patience...

Give me test 9

I had java ML 12. It was solved by replacing BufferedReader/StringTokenizer -> manual integers reading by in.read().

can you give me 5th test, please

I had WA 29, these tests helped me:

abaaa
aab
Answer: aa

baaba
abb
Answer: aa

bcbbc
abcc
Answer: abb

Edited by author 18.10.2015 22:56