Edited by author 02.04.2021 18:58

Hello. My program passes all tests from the forum, but I still get WA6.

I do brute force

First, I go through all the elements that are to the right of the current one, then everything that is to the left

can anyone have any tests?

here is y code is needed:

#include <iostream>

using namespace std;

int n, result = 0, sizeHelpArray = 0, sizeAnswerArray;
int line[100][2], helpArray[100][2], answerArray[100][2];

//initialization and sorting on the left border
void Init()
{
    int i, j;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> line[i][0] >> line[i][1];
        if (line[i][0] > line[i][1])
            swap(line[i][0], line[i][1]);
    }

    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (line[j][0] < line[i][0])
            {
                swap(line[i][0], line[j][0]);
                swap(line[i][1], line[j][1]);
            }
            if(line[j][0] == line[i][0])
                if (line[j][1] < line[i][1])
                {
                    swap(line[i][0], line[j][0]);
                    swap(line[i][1], line[j][1]);
                }
        }
    }
}

//adding a segment to the temporary answer

void AddInHelpArray(int index)
{
    sizeHelpArray++;
    helpArray[sizeHelpArray][0] = line[index][0];
    helpArray[sizeHelpArray][1] = line[index][1];
}

//to record the best current result

void copyInAnswerArray()
{
    int i;
    for (i = 0; i < sizeHelpArray + 1; i++)
    {
        answerArray[i][0] = helpArray[i][0];
        answerArray[i][1] = helpArray[i][1];
    }
}

void sortAnswerArray()
{
    for (int i = 0; i <= sizeAnswerArray; i++)
    {
        for (int j = i + 1; j <= sizeAnswerArray; j++)
        {
            if (answerArray[j][0] < answerArray[i][0])
            {
                swap(answerArray[i][0], answerArray[j][0]);
                swap(answerArray[i][1], answerArray[j][1]);
            }
            if (answerArray[j][0] == answerArray[i][0])
                if (answerArray[j][1] < answerArray[i][1])
                {
                    swap(answerArray[i][0], answerArray[j][0]);
                    swap(answerArray[i][1], answerArray[j][1]);
                }
        }
    }
}

void Solve()
{
    int i, x, tmp = 1, currentPoint;
        //starting from the first element ..
    for (x = 0; x < n; x++)
    {
        sizeHelpArray = 0;
        tmp = 1;
        memset(helpArray, 0, sizeof(helpArray));
                //I write the current element to an auxiliary array
        helpArray[sizeHelpArray][0] = line[x][0];
        helpArray[sizeHelpArray][1] = line[x][1];
        currentPoint = line[x][1];
                //Checking items to the right of the current one
        for (i = x + 1; i < n; i++)
        {
            if (line[i][0] >= currentPoint)
            {
                tmp++;
                currentPoint = line[i][1];
                AddInHelpArray(i);
            }
        }


        currentPoint = line[x][0];
        int border;
        border = line[x][0];
        bool first = true;
                //Checking items to the left of the current one
        for (int j = 0; j < x; j++)
        {
            if (line[j][1] <= currentPoint && first)
            {
                tmp++;
                currentPoint = line[j][1];
                AddInHelpArray(j);
                first = false;
            }
            else if (first == false && line[j][0] >= currentPoint && line[j][1] <= border)
            {
                tmp++;
                currentPoint = line[j][1];
                AddInHelpArray(j);
            }
        }
                //If the result is better than the previous one, then I save it.
        if (tmp > result)
        {
            result = tmp;
            copyInAnswerArray();
            sizeAnswerArray = sizeHelpArray;
        }
    }

    sortAnswerArray();
    cout << result << endl;
    for (int i = 0; i <= sizeAnswerArray; i++)
        cout << answerArray[i][0] << " " << answerArray[i][1] << endl;
}

int main()
{
    Init();
    Solve();
    return 0;
}

Edited by author 02.04.2021 07:26

Edited by author 02.04.2021 07:26

Edited by author 02.04.2021 07:37

Edited by author 02.04.2021 07:37

I've found dp[sum][last][k] as cnt of make sum with k numbers and last number is last, but calculation of this dp is too long, so i've just precalculated it. Can you give me a hint?

(a1 - a2) + (a2 - a3) + .... + (an - a1) == b1 + b2 + .... + bn == 0
-> we have some elements b < 0 and b >= 0

let dp[n][i][j] is cnt of three-primes numbers which 2 last digits is i and j, then dp[n+1][i][j]+=dp[n][k][i], if kij is three-prime number

a = float(input("a:"))
b = float(input("b:"))
print(a+b)

Edited by author 02.11.2019 14:57

Edited by author 02.11.2019 14:59

Check if your solution works correctly with dense graphs

suppose everything is good for the first 'i' columns, but the column is 'i' bad, then let's try to find such 'j' that, by doing the operation, our new column 'i' will become good, what properties should the column 'j' have ?
If you can find 'j' just do operation swap (i, j)

from sys import stdin, stdout, float_info
import re
from math import sin, cos, acos, fabs

CONST_PI = acos(-1.0)
CONST_EPSILON = 2.2204460492503130808472633361816
# CONST_PI = 3.141592653589793
data = []


def solve(a, b, c, d):
    a = a + (c / 3600) + (b / 60)
    # Checking the latitude and longitude position to determine positive pr negative degree
    if d == 'SL' or d == 'WL':
        a = -a
    a = a * CONST_PI / 180
    return a


def distComp(a):
    if fabs(a) < CONST_EPSILON:
        return 0
    elif a > 0:
        return 1
    else:
        return -1


# Input
data = stdin.read().split()

# # Test Input
# data = ['Message', '#513.', 'Received', 'at', '22:30:11.', 'Current', "ship's", 'coordinates', 'are', '41^46\'00"', 'NL',
#         'and', '50^14\'00"', 'WL.', 'An', 'iceberg', 'was', 'noticed', 'at', '41^14\'11"', 'NL', 'and', '51^09\'00"', 'WL.', '===']

# data = ['Message', '#513.', 'Received', 'at', '22:30:11.', 'Current', "ship's", 'coordinates', 'are', '36^46\'00"', 'EL',
#         'and', '50^14\'00"', 'WL.', 'An', 'iceberg', 'was', 'noticed', 'at', '41^14\'11"', 'NL', 'and', '76^09\'00"', 'WL.', '===']


# Message Received
# messageReceived = [int(s) for s in re.findall(r'\b\d+\b', data[4])]
# hh = messageReceived[0]
# mm = messageReceived[1]
# ss = messageReceived[2]
# print('\nMessage Received at: ', hh, mm, ss)

# Ship's Latitude
shipLatitude = [float(s) for s in re.findall(r'\b\d+\b', data[9])]
x1 = shipLatitude[0]
x2 = shipLatitude[1]
x3 = shipLatitude[2]
x4 = data[10]
# print('\nShip Latitude: ', x1, x2, x3, x4)


# Ship's Longitude
shipLongitude = [float(s) for s in re.findall(r'\b\d+\b', data[12])]
y1 = shipLongitude[0]
y2 = shipLongitude[1]
y3 = shipLongitude[2]
y4 = data[13][:2]
# print('\nShip Longitude: ', y1, y2, y3, y4)


# Ice Berg's Latitude
iceBergLatitude = [float(s) for s in re.findall(r'\b\d+\b', data[19])]
a1 = iceBergLatitude[0]
a2 = iceBergLatitude[1]
a3 = iceBergLatitude[2]
a4 = data[20]
# print('\nIce Berg Latitude: ', a1, a2, a3, a4)

# Ice Berg's Longitude
iceBergLongitude = [float(s) for s in re.findall(r'\b\d+\b', data[22])]
b1 = iceBergLongitude[0]
b2 = iceBergLongitude[1]
b3 = iceBergLongitude[2]
b4 = data[23][:2]
# print('\nIce Berg Longitude: ', b1, b2, b3, b4)

shipLatitudeResult = solve(x1, x2, x3, x4)
shipLongitudeResult = solve(y1, y2, y3, y4)
iceBergLatitudeResult = solve(a1, a2, a3, a4)
iceBergLongitudeResult = solve(b1, b2, b3, b4)


dist = 6875.0/2
dist = acos(sin(shipLatitudeResult) * sin(iceBergLatitudeResult) + cos(shipLatitudeResult)
            * cos(iceBergLatitudeResult) * cos(shipLongitudeResult - iceBergLongitudeResult)) * dist

print('\nThe distance to the iceberg:', round(dist, 2), 'miles.')
if dist < 100:
    print('DANGER!')

Edited by author 30.03.2021 16:37

After sorting of array of x and y all you need to do is to compute this two double sums sum(i=1)^n sum(j=1)^(i-1) (x_i-x_j) and sum(i=1)^n sum(j=1)^(i-1) (y_i-y_j). After simplifications one can obtain that they equal
sum(i=1)^n x_i*(2*i-1-n) and sum(i=1)^n y_i*(2*i-1-n).
After computations you divide final sum by C_n^2=n*(n-1)/2 and get required answer.

You can just count letters

Edited by author 25.03.2021 01:13

Please help

Good afternoon! I am a programmer-beginner. I have written the code for this task on c++, but the time limit is exceeded on the second test!
The code is this: (https://ideone.com/Rh98zQ)

#include <iostream>
using namespace std;

float ghj(int a)
{int m;
m=0;
for(int l=1; l<a; l++)
{if(a%l==0)
{m=m+l;}}
float c=(float(int(m)));
float b=c/a;
return b;}

int main() {
int i,j;
cin >> i >> j;
float p=ghj(i);
int n=i;
for(int o=i; o<=j; o++)
{if(ghj(o)<p)
{p=ghj(o);
n=o;}}
cout << n;
return 0;
}

Tell me, please, how can I optimize the code?

Please help

Is it dynamic programming on the profile?
How to apply it?

Wrong answer.
Help pls.

who can tell me what the test6 is? Thanks

Getting WA on test 25, any test case?

По условию, при входных n = 1 и единственном отрицательном значении ответ должен быть 0, но accepted получается и при неправильном решении такого теста...

Либо я чего-то не понимаю...

Input:
1a 1a 1a 1a 1a 1a 1a 1a 1a 1b 3b 5b 1c 1c

Output:
Tenpai