Same program getting WA1 with G++ and AC with MVC++. Idk why. I use linear DP, i print answer with cstdio.

http://pastebin.com/Cr6m0rw7
I think I tried everything that can limit memory but still got MLE :/

i kinda changed the variables
a = the first sum suggested by petr
b = the ---------------------- taxi driver
c = amount added by petr everytime
d = ---------------- taxi driver
we can say that at step n of bargaining:
petr -> a + n*c
taxi -> b - n*d

where looking for a time when petr's suggestion is less than the drivers
which means a + nc <= c - n*d
but there sometime when petr suggest more than what the driver suggest the previous time.
that's why i am comparing between the last petr's suggestion and the previous one of the driver a+c*n > b-d*(n-1). in this case petr says ok to the taxi driver and do not suggest more than that.


void solve() {
    int a, c, b, d;
    cin >> a >> c >> b >> d;
    if (a >= b) {
        cout << a;
        return;
    }
    int n = (b-a)/(c+d);
    if ((b-1)%(c+d)!=0) n++;
    if (a+c*n > b-d*(n-1)) {
        cout << b - d*(n-1) << ln;
    }
    else {
        cout << a + n*c << ln;
    }
}


Edited by author 10.09.2022 21:11

We need version 2 of this problem, where cart can be used in more than one tunnel

string s = "";
int c;
while ((c = getchar()) != EOF)
    s.push_back((char)c);

Correct read input C++

я выбрал корнем вершину 1 и запускал в int main() дфс от этой вершины. Прошло 24 теста и упало на 25, но затем я запустился от всех вершин с условием if(!used[i]) dfs(i) и прошло. я не понял почему..

1
2 6
1 1 1000

answer: 1001.4472135955

my code



using System;
using System.Diagnostics;
using System.Drawing;
using System.Globalization;

namespace Program;

public static class Program
{


public static void Main()
    {
        int number = Convert.ToInt32(Console.ReadLine());
        string number_plus = Convert.ToString(number + 1);
        string number_minus = Convert.ToString(number - 1);
        char[] massiv_plus = number_plus.ToCharArray();
        char[] massiv_minus = number_minus.ToCharArray();
        string str_minus;
        string str_plus;
        while (massiv_minus.Length < 6)
        {
            str_minus = String.Join("", massiv_minus.Reverse());
            str_minus += '0';
            massiv_minus = str_minus.ToCharArray();
            massiv_minus.Reverse();
        }
        while (massiv_plus.Length < 6)
        {
            str_plus = String.Join("", massiv_plus.Reverse());
            str_plus += '0';
            massiv_plus = str_plus.ToCharArray();
            massiv_plus.Reverse();
        }
        int a1_plus = Convert.ToInt32(massiv_plus[0]);
        int a2_plus = Convert.ToInt32(massiv_plus[1]);
        int a3_plus = Convert.ToInt32(massiv_plus[2]);
        int b1_plus = Convert.ToInt32(massiv_plus[3]);
        int b2_plus = Convert.ToInt32(massiv_plus[4]);
        int b3_plus = Convert.ToInt32(massiv_plus[5]);
        int a1_minus = Convert.ToInt32(massiv_minus[0]);
        int a2_minus = Convert.ToInt32(massiv_minus[1]);
        int a3_minus = Convert.ToInt32(massiv_minus[2]);
        int b1_minus = Convert.ToInt32(massiv_minus[3]);
        int b2_minus = Convert.ToInt32(massiv_minus[4]);
        int b3_minus = Convert.ToInt32(massiv_minus[5]);
        if ((Math.Abs(a1_plus + a2_plus + a3_plus) == Math.Abs(b1_plus + b2_plus + b3_plus)) || Math.Abs(a1_minus + a2_minus + a3_minus) == Math.Abs(b1_minus + b2_minus + b3_minus))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}

Lucas theorem, O(p * log(n)).

I don't know if this is my mistake or not. These two submissions differs only in 9th line (double changed to long double) but one submission is AC, while other gives RTE 1:
https://acm.timus.ru/getsubmit.aspx/10678502.cpp - AC
https://acm.timus.ru/getsubmit.aspx/10678503.cpp - RTE 1

It seems to me that this isn't normal.

Admins, please add this to statement: "The coordinates are given with no more than 6 digits after a decimal point

int main()
{
    long int n,res;

    while(1){
        scanf("%ld",&n);
        if(n!=0){
    if(n%2==0){
         res=function(n-1);
         printf("%ld\n",res);
    }
    else{
         res=function(n);
            printf("%ld\n",res);
    }

        }
    else{
        return 0;
    }

    }
//gives right ans in codeblocks but here gives WA....Why??
    return 0;

    }


long int function(long int n){
    if(n==1){
        return 1;
    }
    if(n%2==0){
        return 1;
           }
    else if(n%2==1){
        return function(n/2)+function(n/2+1);
            }

                }

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.