Can somebody tell me how to implement dp for this probelm?

2
0 0 1 0
1 0 0 0
5 0

Possible answer: -1 0

When N=0, no number is there, or 0 is there. a[0]=1
When N=1, there are k such numbers, or 1..k-1. a[1]=k-1
When N=2, there are k^2-k such numbers.
a[2]=>k^2-k
    =>(k-1)k
    =>(k-1)(k-1+1)
    =>(k-1)(k-1)+(k-1)*1
    =>(k-1)a[1] + (k-1)*a[0]
which can be used for all subsequent digits

#include <iostream>
using namespace std;

int sumDigit(int n) {
  int sum = 0;
  while (n) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

int main()
{
  int n;
  cin >> n;
  if (n % 2 == 1) {
    cout << 0;
  } else {
    // We need to choose at most 4 digits, so the largest digit sum is 9*4
    int count[9*4 + 1] = {0};
    int halfN = n / 2;
    int maxNum = 9;
    for (int i = 1; i < halfN; ++i) {
      maxNum *= 10;
      maxNum += 9;
    }
    // Count the ways to create a particular sum
    for (int i = 0; i <= maxNum; ++i)
      ++count[sumDigit(i)];

    // Now, for each number i whose digit sum are s, there are
    // count[s] numbers (including i itself) have the sum s.
    // So we have count[s] ways to choose the second half.
    int result = 0;
    for (int i = 0; i <= maxNum; ++i)
      result += count[sumDigit(i)];
    cout << result;
  }
  return 0;
}

Reading the entire input char by char can be done quickly this way:

while ((input = (char)getchar())) {
     if (input == EOF) {
          break;
     }

/*
ALGORITHM:
In any substring that is encountered the most, at least one letter of that substring should be encountered the same time as the substring.
So, we just need to find the most encountered symbol in the string.
 */
using System;
using System.Linq;

class Program
{

    static void Main()
    {
        Console.WriteLine((from u in Console.ReadLine().ToArray()
                           group u by u into gg
                           orderby gg.Count() descending
                           select gg.Key).ToList()[0]);
    }
}

The authors should've mentioned these in the question. Like if q is 0 then you should print 10 but if it is any number between 1 to 9 then you should print that number only, i.e. 2 for 2, 4 for 4 not 14 for 4.

13
0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1

ans: 31.513956103964

I used code from well-known library: https://atcoder.github.io/ac-library/production/document_en/maxflow.html. I am getting re1 or re2 when sending it in g++13.2 x64. But i got ac when i sent it in visiual c++ 2022 64. Admins pls fix it.

WA on test 7.
I've used uint64_t in array and sum, and int64_t in result.
Corner case of sum = 0 is taken care of.

Regards,
So Sui Ming

what is wrong with my program? I used Python
code below:

n = input()
list = n.split()
n = int(list[0])
k = len(list[1])

if (n < k):
    p = k
else:
    p = n

i=2
num = n - k
if (n>=1 and n<=10) and (k>=1 and k<=20) and (num > 0):
    if((n%k) == 0):
        while(num>k):
            p = p*num
            num = n-i*k
            i=i+1

        p = p*k
    else:
        while(num>(n%k)):
            p = p*num
            num = n-i*k
            i=i+1
        p = p*(n%k)

print(p)

Edited by author 17.06.2022 20:39

binsearch + dijkstra works but with naive dijkstra

my solution is the following:
start with least common multiple = 1
make char array of 1000 000 to track forbidden divisors

let div be the divisor and ans the answer

if ans == 1 make new lcm of the previous lcm and current divisor. if it is over 10^12 - fail. find all the divisors of div, check that they are not forbidden in the forbidden array
if ans == 0 - check if lcm is divisible by the divisor and fail if it is.

complexitiy O(n * sqrt(1000000)) (sqrt from the "find all divisors)

my solution gets 0.5 sec (using cin,cout with tie(null))
what is the solution that gets less than 0.1 sec? Is there any hint?

ceils cant be negative

Edited by author 26.05.2024 06:13

These are some of the things I had to overcome:
1)Testing on something like:
6
5 5 1 1 2 2
and
6
5 5 1 1 1 2

2)There cant be 2 out of place pairs in the ascending/descending order

3)Swapping elements across all pairs

Hope this helps someone.

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
    int x1, y1, x2, y2, x0, y0, l;

    cin >> x1 >> y1 >> x2 >> y2;
    cin >> x0 >> y0 >> l;
    cout << fixed << setprecision(2); // <|ENG: Set 2 symbols after dot |> <|RUS: stavim 2 simvola dlia tochki |>
    //<|ENG: get all sides |>
    //<|RUS: poluchaem vse storonui |>
    double firstEdge = sqrt(pow(x1 - x0, 2) + pow(y1 - y0, 2));
    double secondEdge = sqrt(pow(x2 - x0, 2) + pow(y2 - y0, 2));
    double field = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
    double ans2 = max(firstEdge, secondEdge) - l; // <|ENG: Second answer - max length |> <|RUS: Vtoroi otvet = prosto maximum do krainih tochek |>

    double ans1;
    //<|ENG: get the squares of the sides|>
    //<|RUS: Vosvodim v kvadrat storonui |>
    double a = firstEdge * firstEdge;
    double b = secondEdge * secondEdge;
    double c = field * field;
    //<|ENG: checking if there are obtuse angles on the side that is the pineapple field |>
    //<|RUS: Proverka est li typie ygli vosle toi storoni kotoraiy iavliaetsia polem c ananasami |>
    if (a+c < b || b+c < a) {
        ans1 = min(firstEdge, secondEdge) - l;
    }
    else {
        //<|ENG: get half the perimeter of triangle|>
        //<|RUS: poluchaem poly perimetr treygolnika |>
        double p = (firstEdge + secondEdge + field) / 2;
        //<|ENG: get square of triangle|>
        //<|RUS: poluchaem ploshad treygolnika |>
        double S = sqrt(p * (p - firstEdge) * (p - secondEdge) * (p - field));

        //<|ENG: If the area is zero and the field with pineapples does not exist (test: 2 2 2 2 3 3 1)|>
        //<|RUS: Esli ploshad ravna 0 i polia c ananasami kak bu net (test: 2 2 2 2 3 3 1)|>
        if (S == 0 && field == 0) {
            ans1 = min(firstEdge, secondEdge) - l;
        }
        //<|ENG: If the area is zero and more than one side is not zero (test: -5 0 5 0 1 0 1)|>
        //<|RUS: Esli ploshad ravna 0 i ni odna storona ne ravna 0 (test:  -5 0 5 0 1 0 1)|>
        else if (S == 0 && firstEdge != 0 && secondEdge != 0 && field != 0) {
            ans1 =  0;
        }
        else {
            //<|ENG: Default. We just look for the height using the formula|>
            //<|RUS: Obichni slychai. Prosto po formule S = a*h/2 (test:  -5 0 5 0 1 0 1)|>
            double d = 2 * S / field;
            ans1 = d - l;
        }
    }
    //<|ENG: If, after subtracting the rope, the length becomes negative, then do 0|>
    //<|RUS: Esli sle vichetania verevki otvet stal menihe nylia to delayem 0|>
    ans1 = ans1 < 0 ? 0 : ans1;
    ans2 = ans2 < 0 ? 0 : ans2;

    //<|ENG: Next just cout "round(ans1 * 100) / 100" and "round(ans2 * 100) / 100"|>
    //<|RUS: Teper prosto vivedi "round(ans1 * 100) / 100" i "round(ans2 * 100) / 100"|>

    //!!!!!!!!!!!!!!!!!!!
    //cout << round(ans1 * 100) / 100 << endl;
    //cout << round(ans2 * 100) / 100;
    return 0;

    //<|ENG: Thanks a lot for your time here!|>
    //<|RUS: Spasibo chto pochitali i uia vam pomog (navernoe)|>
    // :)
}

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    double x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    double px = 0, py = 0;
    double length;

    double A = 0;
    double B = -1;
    double C = 0;
    double slope = 0;

    cin>>x1>>y1>>x2>>y2>>px>>py>>length;

    // get the equation of pineapple line in the form Ax + By + c = 0

    if((x2 - x1) != 0){
        slope = (y2 - y1) / (x2 - x1);
        A = slope;
        C = y2 - slope * x2;
    }

    if((x2 - x1) == 0){
        A = 1;
        B = 0;
        C = -x1;
    }

    // now since we have Ax + By + C = 0
    // we can find the shortest distance between the point and the line

    double short_dist = fabs(A*px + B*py + C) / sqrt(pow(A, 2) + pow(B, 2));
    double dist_x1y1 = fabs(sqrt(pow(px-x1, 2) + pow(py-y1, 2)));
    double dist_x2y2 = fabs(sqrt(pow(px-x2, 2) + pow(py-y2, 2)));

    // once we have calculated the shorted distance, we need to
    // find out the point lying on that pineapple line which is
    // closest to the peg

    double slope_new = 0;
    double B_new = 0;
    double C_new = 0;
    double A_new = 0;
    bool status = true;

    if((x2 - x1) == 0){
        slope_new = 0; // the other line has slope of inifinity, so this is parallel
        B_new = 1;
        A_new = 0;
        C_new = -py;
        status = false;
    }

    if((y2 - y1) == 0){
        B_new = 0;
        A_new = 1;
        C_new = -px;
        status = false;
    }

    if(status){
        slope_new = -1.0/slope;
        C_new = py - slope_new*px;
        A_new = slope_new;
        B_new = -1;
    }

    // calculating the point of intersection

    double inter_X = (-C*B_new - B*(-C_new)) / (A*B_new - B*A_new);
    double inter_Y = (A*(-C_new) - (-C*A_new))/(A*B_new - B*A_new);

    // now check whether this point lies between the given points or not ?
    // to do that we need to check whether both of the above calculated
    // coordinates lie between the range of x1, y1 and x2, y2

    double min_x_coor = min(x1, x2);
    double min_y_coor = min(y1, y2);
    double max_x_coor = max(x1, x2);
    double max_y_coor = max(y1, y2);

    if(inter_X >= min_x_coor && inter_X <= max_x_coor && inter_Y >= min_y_coor && inter_Y <= max_y_coor){
        // this means, the point lies on the line
        double one_pineapple_distance = short_dist - length;
        if(one_pineapple_distance <= 0){
            cout<<"0.00"<<endl;
        }
        else
            printf("%.2f\n", one_pineapple_distance);

        // now to eat all the pineapples
        double larger_distance = max(dist_x1y1, dist_x2y2);
        if(larger_distance - length <= 0){
            cout<<"0.00"<<endl;
        }
        else
            printf("%.2f\n", larger_distance - length);
    }

    // or else the perpendicuar point does not lies on the line
    else{
        // first shorter one
        double shorter_distance = min(dist_x1y1, dist_x2y2);
        double larger_distance = max(dist_x1y1, dist_x2y2);

        double pineapple_1 = shorter_distance - length;
        if(pineapple_1 <= 0){
            cout<<"0.00"<<endl;
        }
        else
            printf("%.2f\n", pineapple_1);

        double pineapple_all = larger_distance - length;
        if(pineapple_all <= 0){
            cout<<"0.00"<<endl;
        }
        else
            printf("%.2f\n", pineapple_all);
    }
    return 0;
}