module Main where
--------------------------------------------------------------------------------
toCandetat :: Char -> [Char]
toCandetat '0' = "oqz"
toCandetat '1' = "ij"
toCandetat '2' = "abc"
toCandetat '3' = "def"
toCandetat '4' = "gh"
toCandetat '5' = "kl"
toCandetat '6' = "mn"
toCandetat '7' = "prs"
toCandetat '8' = "tuv"
toCandetat '9' = "wxy"
toCandetat n = error "unkown numb"
--------------------------------------------------------------------------------
convertToCandedat :: String -> [String]
convertToCandedat = map toCandetat
--------------------------------------------------------------------------------
testWord :: String -> [String] -> Bool
testWord str can = and $ zipWith elem str  can
--------------------------------------------------------------------------------
loop :: [String] -> String -> String
loop []     acc = tail acc
loop ["-1"] acc = tail acc
loop in_str acc = loop next (acc ++ "\n" ++ fixPart)
  where
   fixPart         = if part == "" then "No soluton." else part
   part            = partSolve test cand []
   (numb:count:xs) = in_str
   cand            = convertToCandedat numb
   int_count       = read count
   (test, next)    = splitAt int_count xs
--------------------------------------------------------------------------------
partSolve :: [String] -> [String] -> String -> String
partSolve []     []  acc                  = tail acc
partSolve (x:xs) can acc | testWord x can = skipX  ++ nextXs
                         | otherwise      = partSolve xs can             acc
  where
    lenX   = length x
    skipX  = partSolve xs can             acc
    nextXs = partSolve xs (drop lenX can) (acc ++ " " ++ x)
partSolve _      _   _                    = ""
--------------------------------------------------------------------------------
main :: IO ()
main = do
  in_str <- getContents
  putStr $ loop (words in_str) []
--------------------------------------------------------------------------------

Anti WA11 Test:
#X#
#OX
XOO
Crosses win

Anti WA12 Test:
#X#
O#O
XOX
Crosses win

I hope these tests will be useful for you.......

Try this

X##
O#X
XOO

Crosses win

My AC recursion for n=8 gives about 8250733 calls. What is the minimum recursive calls value?

There are 3 problems, which can be solved stupidly in two ternary searches: 1755 (this), 1633, 1874

#include<stdio.h>

int main() {
   int  h, l;
   scanf("%d %d", &h, &l);
   int total = h + l;
   printf("%d %d\n", total - l - 1, total - h - 1);
   return 0;
}

Hi. I wonder, how can I solve it with dp? I thinked a whole day and cant find the solution less than O(N*T). Give me please some hint.

Hint:
we start from kk = 1, then kk += kk (2), kk += kk (4) but we cannot advance when kk > k.
get to the maximum kk with this and the remaining n - kk can be easily calculated with
(n - kk) / k + (((n - kk) % k) > 0)

my same logic got tle in c++ but AC in java so beware

Segment Tree/ Fenwick Tree with range update and point query

please give me some tips!

Edited by author 24.04.2022 16:19

k, n = [int(x) for x in input().split()]
a = list(map(int, input().split()))
m = 0

for i in a:
    m += i
    if (m - k >= 0):
        m -= k
    else:
        m = 0
print(m)

6 6
1 2
2 3
3 4
4 5
1 6
6 5
1 5 6
ans : 0

With e=0.0000001 I have WA#14

7 5
1 2 20
2 5 100
2 3 20
6 3 70
4 1 10
3 7 5

Answer: 220

Edited by author 21.04.2022 19:37

#include <iostream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <vector>
#include <bitset>
#include <stack>
#include <sstream>
#include <algorithm>

#define ll long long
using namespace std;

#define maxn 1805
#define maxk 1805

const int MAX_ONE = 1000000000;

struct x86_64 {
    int Length = 0, BigNum[1024] = {};
    x86_64(int Num = 0) {
        int Index = 0;
        while (Num) {
            BigNum[Index++] = Num % MAX_ONE;
            Num /= MAX_ONE;
        }
        Length = Index;
    }
    void operator =(int Num) {
        memset(BigNum, 0, sizeof(BigNum));
        int Index = 0;
        while (Num) {
            BigNum[Index++] = Num % MAX_ONE;
            Num /= MAX_ONE;
        }
        Length = Index;
    }
};

void print(x86_64 Num) {
    for (int i = Num.Length - 1; i >= 0; i--) {
        if (i != Num.Length - 1) {
            printf("%09d", Num.BigNum[i]);
        } else {
            printf("%d", Num.BigNum[i]);
        }
    }
}

x86_64 operator +(x86_64 A, x86_64 B) {
    int Length = max(A.Length, B.Length);
    int Carry = 0;
    x86_64 Answer;
    for (int i = 0; i < Length + 1; i++) {
        Answer.BigNum[i] = (A.BigNum[i] + B.BigNum[i] + Carry) % MAX_ONE;
        Carry = (A.BigNum[i] + B.BigNum[i] + Carry) / MAX_ONE;
    }
    Answer.Length = (Answer.BigNum[Length] == 1) + Length;
    return Answer;
}

x86_64 operator *(x86_64 A, int B) {
    int Length = A.Length;
    int Carry = 0;
    x86_64 Answer;
    for (int i = 0; i < Length + 1; i++) {
        Answer.BigNum[i] = (A.BigNum[i] * (ll)B + Carry) % MAX_ONE;
        Carry = (A.BigNum[i] * (ll)B + Carry) / MAX_ONE;
    }
    int Index = 0;
    while (Answer.BigNum[Index] != 0) {
        Index++;
    }
    Answer.Length = Index;
    return Answer;
}

x86_64 dp[maxn][2];

int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    dp[1][1] = K - 1;
    for (int i = 2; i <= N; i++) {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = dp[i - 1][0] + dp[i - 1][1] * (K - 1);
    }
    print(dp[N][0] + dp[N][1]);
    putchar('\n');
    return 0;
}

#include<iostream.h>
#include<stdio.h>
int main()
{
    int n,i,k;unsigned __int64 a[2000],p;
    cin>>n>>k;a[1]=k-1;a[2]=k*(k-1);
        for(i=3;i<=n;i++)
        {a[i]=(k-1)*(a[i-1]+a[i-2]);p=a[i];}
        if(n==1)
            cout<<k-1;
        else
            if(n==2)
                cout<<k*(k-1);
            else
                if(n>=3)
                    printf("%I64u", p);


    return 0;
}

Edited by author 10.04.2007 21:30

Edited by author 10.04.2007 21:31

Edited by author 10.04.2007 21:32

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    int mul = 1;
    string s;
    cin>>n>>s;
    int k = s.size();
    if(n%k==0){
        int in = n;
        int temp = k;
        while(1){
            mul = mul*in;
            in = in - k;
            if(in==k){
                mul*=in;
                break;
            }
        }
    }
    else{
        int in = n;
        while(1){
            mul = mul*in;
            in = in - k;
            if(in==(n%k)){
                mul*=in;
                break;
            }
        }
    }
    cout<<mul<<endl;
    return 0;
}

What is test case 2?

WA5,and never get Accept without High Eps.It isn't a good Problem.