deleted

Edited by moderator 23.07.2022 20:36

Почему в случае 1 10 ответ 9 если 0 тоже число в котором не идут два подряд ноля?

Просто 2 раза получил ВА, поменял на 9 и АС.

Calculate matrix with modulo 10^9 + 7

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

int const N = 123456;
#define pi acos(-1.0)
typedef long long ll;

int ar[N],xar[N],uses[N];

struct points {
     double x, y;
     int id;
     points() {}
     points(double x, double y) : x(x), y(y) {}
 } ;

double ang(const points &p){
    double res = atan2(p.y, p.x);
    if(res < 0) res += 2.0 * pi;
    return res;
}

struct cmp{
    inline bool operator () (const points &p1, const points &p2){
        double ang1 = ang(p1)*(180/pi), ang2 = ang(p2)*(180/pi);
        if(fabs(ang1 - ang2) < 1e-9){
            ll d1 = (ll)p1.x * (ll)p1.x + (ll)p1.y * (ll)p1.y;
            ll d2 = (ll)p2.x * (ll)p2.x + (ll)p2.y * (ll)p2.y;

            return d1 < d2;
        }
        return ang1 < ang2;
    }
};

points pt[N];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> pt[i].x >> pt[i].y;
        pt[i].id = i+1;
    }
    sort(pt, pt+n, cmp());
    cout<<pt[0].id<<" "<<pt[(n/2)].id<<endl;

    return 0;
}

Sort the intervals by length. and from i=0 to no_of_intervals, mark the query numbers.
Make sure that each query number is marked by only one interval.

Edited by author 17.05.2022 11:32

What's the test for WA#9?

Windows, linux, maxOS?
Why I can't include <windows.h>? (Compilation error: No such file or directory)

3 4
1   100 1000 0
1   1   1000 0
100 0   1000 100
//answer 1 1 2 2

1 1
1000000000
//answer 1

5 6
525   0 171   0 872 673
  0 843   0   0   0   0
  0 277   0 202   0   0
  0   0 733 957  65  96
637 566   0   0   0 441
//answer: 4 4 5 5 5 5

10 1  10 10 10
1  1  10 10 10
1  10 1  1  1
1  1  1  10 1
10 10 10 10 1
//answer: 2 2 1 1 1 1

1 10
100 90 80 70 60 50 40 30 20 10
//answer: 10

5 6
1 0 1 1 1 1
1 0 0 1 1 1
1 1 0 1 1 1
1 0 0 1 1 1
1 0 1 1 1 1
//answer: 2 2 3 3 3 2 2

3 2
3 1
1 1
1 3
//answer: 2 2 1 1

3 1
1
1
1
//answer: 1 1 1

тест 1: n=9 k=2
тест 2: n=1 k=1
тест 3: n=10 k=1
тест 4: n=8 k=1
тест 5: n=10 k=2
тест 6: n=7 k=2
тест 7: n=1 k=2
тест 8: n=2
тест 9: n=10 k=5
тест 10: n=9 k=5
n=3,4,5,6 не встречается...

clarification if you are stuck.
RedBlue Mana can be made from red or blue i.e C can use (remA + remB) after using A and B through X and Y respectively. Do count what you use from C when required.

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)