1.Use a DP with the O(30N) time
2.Use ternary (long long in C++ is needed) to indicate each solution
3.Use a rolling array in case it MLEs

Good luck! ~_~

Edited by author 05.07.2011 19:05

I have WA 7 and I don't understand what the problem is.
My tests:
// check(<input string #1>, <input string #2> as integer, <output string>)

      // tests from acm.timus
      check("10.23", 0, "10")
      check(".04", 1, "0.0")
      check("-0.051e0", 1, "0.0")
      check("1.1e30", 10, "1100000000000000000000000000000.0000000000")
      check("-1.1e-30", 1, "0.0")
      check("2468097632.1358642324268913e-2", 20, "24680976.32135864232426891300")
      check("e23", 3, "Not a floating point number")
      check("1 e3", 1, "Not a floating point number")

      // my tests
      check(" 1 e3", 1, "Not a floating point number")
      check("1e3", 1, "1000.0")
      // http://acm.timus.ru/forum/thread.aspx?id=26503&upd=634425663233423296
      // Posted by Igor Dex 1 Jun 2011 18:28
      // It is clear that we can't have leading spaces in case correct real number. But is it possible to have spaces after correct number till the end of the string?
      // Posted by AterLux 1 Jun 2011 23:05
      // No. Trailing as leading spaces not satisfy the syntactical description.
      check("   ", 1, "Not a floating point number")
      check(" ", 1, "Not a floating point number")
      check("-", 1, "Not a floating point number")
      check(" 1e3", 1, "Not a floating point number")
      check(" .1e3", 1, "Not a floating point number")
      check(".1e-3", 1, "0.0")
      check(" .1e-3 ", 1, "Not a floating point number")
      check(".1e-3 ", 1, "Not a floating point number")
      check(".0e-10000000000000000000", 1, "0.0")
      check(".0e+10000000000000000000", 1, "0.0")

      // int and uint tests
      check("10", 0, "10")
      check("10", 1, "10.0")
      check("-10", 1, "-10.0")
      check("+10", 1, "10.0")
      // simplefloat and usimplefloat tests
      check(".10", 1, "0.1")
      check("10.10", 1, "10.1")
      check("10.01", 1, "10.0")
      check("+.10", 1, "0.1")
      check("+10.10", 1, "10.1")
      check("+10.01", 1, "10.0")
      check("-.10", 1, "-0.1")
      check("-10.10", 1, "-10.1")
      check("-10.01", 1, "-10.0")
      // float tests
      check("10e0", 0, "10")
      check("10e-1", 1, "1.0")
      check("-10e+1", 1, "-100.0")
      check("+10e+3", 1, "10000.0")
      check(".10e-3", 1, "0.0")
      check("10.10e-1", 1, "1.0")
      check("10.01e-2", 1, "0.1")
      check("+.10e-10000", 1, "0.0")
      check("+10.10e-100", 1, "0.0")
      check("+10.01e1", 1, "100.1")
      check("-.10e1", 1, "-1.0")
      check("-10.10e-1", 1, "-1.0")
      check("-10.01e-2", 1, "-0.1")
      // "Not a floating point number" tests

      // But see http://acm.timus.ru/forum/thread.aspx?id=10235&upd=632909844439020000
      // Posted by Kopeliovitch Sergey (1) 30 Jul 2004 21:29
      // Segey say his progamm have AC with other answers, but right answers are
//Update: Now Segey have WA #1 and WA #12 and didn't have AC.
      check("10.", 1, "Not a floating point number")
      check("10.0e", 1, "Not a floating point number")
      check("10.e", 1, "Not a floating point number")

      //
      check("1E1 1", 1, "Not a floating point number")
      check("-+3", 1, "Not a floating point number")
      check("+", 1, "Not a floating point number")
      check("-", 1, "Not a floating point number")
      check(" ", 1, "Not a floating point number")
      check("-10.01ee", 1, "Not a floating point number")
      check("12.e10", 1, "Not a floating point number")
      check("-.e10", 1, "Not a floating point number")
      check("1e", 1, "Not a floating point number")
      check("e1", 1, "Not a floating point number")
      check("e", 1, "Not a floating point number")
      check("se-1", 1, "Not a floating point number")
      check("+e", 1, "Not a floating point number")
      check("-e1", 1, "Not a floating point number")
      check(".e4", 1, "Not a floating point number")
      check("0.", 1, "Not a floating point number")
      check("1e", 1, "Not a floating point number")
      check("0x123", 1, "Not a floating point number")
      check("1E2.1", 1, "Not a floating point number")
      check("-1E2.1", 1, "Not a floating point number")
      check("1E2.1e2", 1, "Not a floating point number")
      check("1e00-1", 0, "Not a floating point number")
      // # tests
      check("1#", 1, "Not a floating point number")
      check("#1", 1, "Not a floating point number")
      check("# 1", 1, "Not a floating point number")
      check("1 #", 1, "Not a floating point number")
      // big power test
      check("1e10", 1, "10000000000.0")
      check("1e10", 0, "10000000000")
      check("-1e10", 0, "-10000000000")
      check("1e-10", 0, "0")
      check("0e+10", 0, "0")
      check("0e+100", 0, "0")
      check("0e+10000000000000000000", 0, "0")
      check("0e-10000000000000000000", 0, "0")
      check("0e10000000000000000000", 0, "0")
      check("1e000000000000000000000000000000000000000000000000000000000000000000000000000000", 0, "1")
      check("1e000000000000000000000000000000000000000000000000000000000000000000000000000001", 0, "10")
      check("1e-000000000000000000000000000000000000000000000000000000000000000000000000000001", 0, "0")
      check("234565432452433e-10000000000000000000", 0, "0")
      check("-234565432452433e-10000000000000000000", 0, "0")

      // An integral part of a number should be non-empty.
      check(".1e+0", 1, "0.1")
      check("-.1e+0", 1, "-0.1")
      // There shouldn't be leading zeroes in a non-zero integral part of a number.
      // A zero integral part of a number should consist of an only zero.
      check("00000.1e+0", 1, "0.1")
      check("-00000.1e+0", 1, "-0.1")
      check("00001.1e+0", 1, "1.1")
      check("-00001.1e+0", 1, "-1.1")
      check("00001.1", 1, "1.1")
      check("-00001.1", 1, "-1.1")
      check("00001.1", 0, "1")
      check("-00001.1", 0, "-1")
      // A fractional part of a number should contain exactly N symbols.
      check("00001.1", 0, "1")
      check("00001.1", 3, "1.100")
      check("-00001.1", 1, "-1.1")
      // There shouldn't be a sign "+" before a positive number.
      check("+00001.1", 0, "1")
      check("+1.1", 0, "1")
      check("+1.1", 3, "1.100")
      check("+1.1e+1", 1, "11.0")
      // You shouldn't round off a number.
      check("+1.5e+1", 1, "15.0")
      check("+1.06", 1, "1.0")
      check("+1.6e-1", 1, "0.1")

Edited by author 29.03.2017 22:42

Edited by author 29.03.2017 22:47

Edited by author 30.03.2017 00:56

New anti-hash test was added. 141 author lost AC.

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

My AC answer:
18
3
4
8
1
2
5
7
9
10
-------------------------
5 7
1 1 1 1 1
2 0
3 0
4 0
5 0
1 0
1
0
1 2 0

My AC answer: No Solution

Good luck!

please give me some hints how to solve the problem fast

use unordered_map instead of map

int main(int argc,char *argv[]){
    //freopen("data.txt","r",stdin);
    int n,i,key = 0,count = 0;
    char p[105],input[105];
    scanf("%d",&n);
    getchar();
    for(i = 0; i < n; i++){
        scanf("%c",&input[i]);
        getchar();
    }
    input[i] = '\0';
    strcpy(p,input);
    while(next_permutation(p,p+n)){
        if(strcmp(p,input) == 0){
            break;
        }
        else {
            count++;
            if(count >= 5){
                printf("Yes\n");
                return 0;
            }
        }
    }
    if(count >= 5){
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
}

/*
ye mera template hai
apna khud likho bc :P
*/

/*
Author : Sarvagya Agarwal
*/

#include<bits/stdc++.h>
using namespace std;

//defines
#define openin freopen("input.txt","r",stdin)
#define openout freopen("output.txt","w",stdout)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define int long long
#define mod 1000000007
#define repr(i,x,y) for (__typeof(x) i=x;i>=y;i--)
#define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++)
#define all(c) (c).begin(),(c).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair

/* Print pair */
template <typename T,typename S>
ostream & operator << (ostream &os , const pair<T,S> &v) {
    os << "(" ;
    os << v.first << "," << v.second << ")" ;
    return os ;
}
/* Print vector */
template <typename T>
ostream & operator << (ostream &os , const vector<T> &v) {
    os << "[" ;
    int sz = v.size() ;
    for(int i = 0 ; i < sz ; ++i) {
        os << v[i] ;
        if(i!=sz-1)os << "," ;
    }
    os << "]\n" ;
    return os ;
}
/* Print set */
template <typename T>
ostream & operator << (ostream &os , const set<T> &v) {
    T last = *v.rbegin() ;
    os << "[" ;
    for(auto it : v) {
        os << it  ;
        if(it != last) os << "," ;
    }
    os << "]\n" ;
    return os ;
}
/* Print Map */
template <typename T,typename S>
ostream & operator << (ostream &os , const map<T,S> &v) {
    for(auto it : v) {
        os << it.first << " : " << it.second << "\n" ;
    }
    return os ;
}
int power(int a , int b)
{
    int res = 1 ;
    while(b)
    {
        if(b%2) {
            res = (res * a) % mod ;
        }
        b/=2 ;
        a = (a*a) % mod ;
    }
    return res ;
}

//debug
#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
        cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
int sum , n , arr[105] ;
int dp[105][1005] ;
int ans[105] ;
int solve(int index,int weight)
{
    if(weight == 0) {
        // found a configuration
        return 1 ;
    }
    if(index > n) {
        return 0 ;
    }
    int &res = dp[index][weight] ;
    if(res != -1) return res ;
    res = 0 ;
    res += solve(index + 1 , weight) ;
    if(arr[index] <= weight)res += solve(index + 1 , weight - arr[index] ) ;
    return res ;
}
void go(int index, int weight)
{
    if(index > n || weight == 0) return ;
    // can you take this ?
    if(arr[index] <= weight && solve(index + 1 , weight - arr[index]) == 1) {
         ans[index] = 1 ;
         go(index + 1 , weight - arr[index] ) ;
         return ;
    }
    go(index + 1 , weight) ;
    return  ;
}
int32_t main()
{
    fast;
    cin >> sum >> n ;
    rep(i,1,n) {
        cin >> arr[i] ;
    }
    memset(dp,-1,sizeof(dp)) ;
    int res = solve(1,sum) ;
    if(res == 0) {
        cout << res ;
        return 0 ;
    }
    if(res > 1) {
        cout << -1 ;
        return 0 ;
    }
    go(1,sum) ;
    for(int i = 1 ; i <= n ; ++i) {
        if(ans[i] == 0) {
            cout << i << " " ;
        }
    }
    return 0;
}

Simply use DP with Recurse and You'll get AC!

here is my code im getting test# 1 WA
btw im using python 2.7


import sys
print sys.argv
pages = raw_input()
pages = int(pages)

nums = [0]*10

def countingNums(pages):
    global nums
    if pages == 0:
        return ""
    else:
        sPages = str(pages)
        for i in range(len(sPages)):
            nums[int(sPages[i])] += 1
        return countingNums(pages-1)

countingNums(pages)
for i in range(len(nums)):
    print nums[i]

Edited by author 10.05.2017 17:30

[code deleted]
My first submit got WA#8, my second WA#9, my third got WA#10 of course. I  am going so straight,  so incrementally.  Maybe author made tests in such an amazing increasing-difficulty way.

Edited by moderator 03.12.2019 21:46

I compiled my code on ideone and there I have 0.4 sec for test 1800 10
So I have tle 9. Maybe there are stronger tests?
By the way my program use vectors in long arithmetics. Should I use strings in it?

Edited by author 08.05.2017 22:14

WTF?! I have RE4(Access Violation). I don't understand why?

Use ternary search.

So,  I just wrote solution with C long double and got WA #5 (Laplacian).
Then I just rewrote it in Python with decimal.py and got WA...#3! Then I started to add more precision to decimal and got TLE #3.
Yeah, I use some epsilon constant and add it to determinant  before convert determinant to integer and get its modulo  10**9.

import sys

def reverse(i):
    if len(i) == 1:
        return i
    else:
        return i[len(i)-1]+reverse(i[:len(i)-1])

def getReverseLine(s):
    start = 0
    for i in range(len(s)):
        if (ord(s[i]) < 123 and ord(s[i]) > 64) and (ord(s[i]) < 91 or ord(s[i]) > 96):
            if i == len(s)-1:
                if start < i:
                    s = s.replace(s[start:i+1], reverse(s[start:i+1]))
        else:
            if start < i:
                s = s.replace(s[start:i], reverse(s[start:i]))
                start = i+1
            else:
                start += 1
    return s

lines = []
while True:
    line = sys.stdin.read()
    if line == '':
        break
    lines.append(getReverseLine(line))

text = '\n'.join(lines)

print text

3
6 1 2 5 7 5 2 1
4 1 4 7 4 1
5 2 3 6 5 4 2
my solution:
15 2 5 7 5 2 1 2 3 6 5 4 7 4 1 4 2

2
4 1 2 3 4 1
4 1 2 3 4 1
my solution:
4 1 2 3 4 1

4
1 1 1
1 1 1
1 1 1
1 1 1
my solution:
1 1 1

Are there any test cases for debugging?

Here is my program,I have taken WA on the test of 2, I think it is correct,please tell me what is wrong,please if you can..

program fillword;
var a:array[1..10] of string;
    b,k:array[1..100] of string;
    i,j,n,m,p,t:integer;
    ch:char;
    l,r:string;
begin
 read(n,m,p);
 readln;
 for i:=1 to n do
  readln(a[i]);
 for j:=1 to p do
  readln(b[j]);
 for i:=1 to p do
  for j:=1 to n do
   if b[i]=a[j] then begin t:=t+1; k[t]:=b[i];  break; end;
 for i:=1 to t do
  begin
   r:='';
   l:=k[i];
   for ch:='A' to 'Z' do
    for j:=1 to m do
     if ch=l[j] then r:=r+ch;
   writeln(r);
  end;
end.

BTW: I have used self-implemented high-precision longint to solve this problem.

1000 0 0 -1000 0 0 1000 1000
VISIBLE

1000 -0.000001 0 -1000 0 0 1000 1000
INVISIBLE

1000 0 -0.000001 -1000 0 0 1000 1000
INVISIBLE

1000 0 0.000001 -1000 0 0 1000 1000
VISIBLE

1000 -0.000001 0.000001 -1000 0 0 1000 1000
VISIBLE

1000 -1000 999.999999 -1000 0 0 1000 1000
INVISIBLE

1000 -1000 999.999999 -999.999999 0 0 1000 1000
VISIBLE

-999.999999 -1000 1000 999.999999 0 0 1000 1000
VISIBLE

1 2 1 0 0 0 0 1
VISIBLE

1.000001 2 1 0 0 0 0 1
VISIBLE

0.999999 2 1 0 0 0 0 1
INVISIBLE

1000 0 1000 -0.000001 0 0 0.000001 1000
VISIBLE

1000 0 1000 -0.000002 0 0 0.000001 1000
VISIBLE

1000 0 1000 -0.000003 0 0 0.000001 1000
INVISIBLE

var
  s: array[1..50] of string;
  si, i1, i, c: integer;
  input, output: text;

begin
  {$IFNDEF ONLINE_JUDGE}
  assign(input, 'input.txt');
  reset(input);
  assign(output, 'output.txt');
  rewrite(output);
  {$ENDIF}
  while not seekeof(input) do
  begin
    inc(si);
    read(input, s[si]);
  end;
  c := 1;
  for i := 1 to si do
    for i1 := 1 to length(s[i]) do
    begin
      if c = 0 then s[i][i1] := lowercase(s[i][i1]);
      if (c = 1) and (s[i][i1] <> ' ') and (s[i][i1] <> '-') and (s[i][i1] <> ':') then c := 0;
      if (s[i][i1] = '?') or (s[i][i1] = '.') or (s[i][i1] = '!') then c := 1;
    end;

  for i := 1 to si do
    writeln(output, s[i]);
  {$IFNDEF ONLINE_JUDGE}
  close(input);
  close(output);
  {$ENDIF}
end.