1

Тема: Алготестер задача Коржі

Привіт народ, розв'язував задачі на алготестер, усе було гуд до однієї конкретної задачі(цієї: https://www.algotester.com/uk/ArchivePr … File/40896) при написанні коду на Java він тупо не компілювався їхнім компілятором, хоча у моєму середовищі програмування не було жодних проблем. Код на кавовій чашці:

package com.company;
import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n; n = in.nextInt();
        long sum=0,r, u, rp=0, up=0;


        for (int i = 0; i < n; i++) {
        r= in.nextLong(); u= in.nextLong();
        if (r>rp) sum = sum + u;
        else if(r==rp){
            if (u>up)sum=sum-up+u;
        }
        up = u; rp =r;
        }
    System.out.print(sum);

    }
}


Тоді вирішив перейти на сішку, він хоч скомпілювався, але видає помилку "Неправильна відповідь 1". Може знаєте в чому моя помилка? Код на плюсах:

#include <iostream>
using namespace std;

int main()
{
    int n; cin >>n;
    long sum=0,r, u, rp=0, up=0;

       for (int i = 0; i < n; i++) {
       cin >> r; cin >>u;
        if (r>rp) sum = sum + u;
        else if(r==rp){
            if (u>up)sum=sum-up+u;
        }
        up = u; rp =r;
        }
    cout <<sum;
    return 0;
}

2

Re: Алготестер задача Коржі

А де в умові, що якщо радіуси одинакові, то вона всеодно  кладе. І де сказано, що коржі не можна переставляти в купі.

Подякували: koala1

3

Re: Алготестер задача Коржі

Ок, новий код:

#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
    int n; cin >> n;
    double sum = 0;
    long  r, u;
    
    long **Arr=new long*[2];
    for ( int count = 0; count < 2; count++) {
        Arr[count] = new long[n];
    }
    for (int i = 0; i < n; i++) {
        cin >> r >> u;
        Arr[0][i] = r;
        Arr[1][i] = u;
    }
    for (int startIndex = 0; startIndex < n - 1; ++startIndex)
    {
        int smallestIndex = startIndex;
        for (int currentIndex = startIndex + 1; currentIndex < n; ++currentIndex)
        {
            if (Arr[0][currentIndex] < Arr[0][smallestIndex])
            smallestIndex = currentIndex;
        }
        swap(Arr[0][startIndex], Arr[0][smallestIndex]);
        swap(Arr[1][startIndex], Arr[1][smallestIndex]);
    }
    
    sum = sum + Arr[1][0];

    for (int i = 0; i < n; i++) {
        if (Arr[0][i] < Arr[0][i + 1])sum = sum + Arr[1][i + 1];
        else if (Arr[0][i] == Arr[0][i + 1]) {
            if (Arr[1][i] < Arr[1][i + 1])sum = sum - Arr[1][i] + Arr[1][i + 1];
        }
    }
    cout << sum;
    return 0;
}

Бульбашковий метод сортування все працює, на алготестері помилка "Неправильна відповідь 1".

4

Re: Алготестер задача Коржі

А ви знаєте як об'єм циліндра рахується?

5 Востаннє редагувалося lucas-kane (23.02.2022 04:21:48)

Re: Алготестер задача Коржі

bogdanmasnak написав:

Ваш код

/* ... */
    for (int i = 0; i < n; i++) {
        if (Arr[0][i] < Arr[0][i + 1])sum = sum + Arr[1][i + 1];
        else if (Arr[0][i] == Arr[0][i + 1]) {
           // Тут має бути пошук максимального об'єму коржа із коржів з однаковим радіусом, тобто поки однакові радіуси звіряємо об'єм з попереднім коржем того ж радіусу та беремо останній максимальний об'єм...
        }
    }
/* ... */

та з умови завдання

У другому прикладi з двох коржiв однакового радiуса вибираємо бiльший.

Потрібно здійснити пошук максимального об'єму, а тоді його додати. І що буде коли повторюваних радіусів коржів буде більше двох?! Напевне, що потрібно робити вкладений цикл та шукати цей максимальний об'єм, а тоді вже його додавати до загального об'єму торту.

Та ще хотів додати, який сенс звіряти

Arr[0][i] < Arr[0][i + 1]

, якщо перед цим ти його відсортував... Краще відразу здійснювати перевірку на рівність, пропускати коржі з однаковими радіусами (відповідно знайшовши максимальний) та в кінці сумувати їх.

6

Re: Алготестер задача Коржі

І ще, це ніяк не стосується до алгоритму задачі, але коли виділяєш пам'ять оператором new то в кінці програми має бути оператор delete. Візьми це собі за правило.
Успіхів у навчанні

7

Re: Алготестер задача Коржі

bogdanmasnak написав:

на Java він тупо не компілювався їхнім компілятором

Приберіть package. Це треба для зв'язування коду у файлі з іншими.

bogdanmasnak написав:

видає помилку "Неправильна відповідь 1". Може знаєте в чому моя помилка?

У неправильному алгоритмі.

8

Re: Алготестер задача Коржі

Змінив, за вашими порадами, код, в мене він запускається і виконується, а на їх сайті "Помилка часу виконання 1" хоча час виконання вказаний як 0,003 сек.

#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
    int n; cin >> n;
    double sum = 0;
    long  r, u,max;
    
    long **Arr=new long*[2];
    for ( int count = 0; count < 2; count++) {
        Arr[count] = new long[n];
    }
    for (int i = 0; i < n; i++) {
        do {  cin >> r >> u;} while (r < 0 && u < 0);
        Arr[0][i] = r;
        Arr[1][i] = u;
    }
    for (int startIndex = 0; startIndex < n - 1; ++startIndex)
    {
        int smallestIndex = startIndex;
        for (int currentIndex = startIndex + 1; currentIndex < n; ++currentIndex)
        {
            if (Arr[0][currentIndex] < Arr[0][smallestIndex])
            smallestIndex = currentIndex;
        }
        swap(Arr[0][startIndex], Arr[0][smallestIndex]);
        swap(Arr[1][startIndex], Arr[1][smallestIndex]);
    }
    
    sum = sum + Arr[1][0];

    for (int i = 0; i < n; i++) {
        if (Arr[0][i] < Arr[0][i + 1])sum = sum + Arr[1][i];
        else if (Arr[0][i] == Arr[0][i + 1]) {
            if (Arr[1][i] < Arr[1][i + 1])sum = sum + Arr[1][i + 1]; 
            else sum = sum + Arr[1][i];
            i++;
        }
    }
    cout << sum;
    delete [] Arr[n];
    return 0;
}

9 Востаннє редагувалося koala (23.02.2022 10:52:43)

Re: Алготестер задача Коржі

Ви розумієте, що означає запис

delete [] Arr[n];

Можете словами описати?

10

Re: Алготестер задача Коржі

Ще раз, що вас питають? Знайти об'єм. А що ви шукаєте?

Пс: вибачаюсь, думав, що в другому масиві висота, а не об'єм.

11

Re: Алготестер задача Коржі

Умова написав:

У першому рядку задано цiле число n - кiлькiсть коржiв.
У другому рядку задано n цiлих чисел ri - радiусi-го коржа.
У третьому рядку заданоnцiлих чисел vi - об’ємi-го коржа.

Ви щось не те вводите. Наступного разу, будь ласка, давайте не лише посилання, а й умову переписуйте.

12

Re: Алготестер задача Коржі

Такий код проходить

import java.util.*;

public class Main {

    public static void main(String[] args) {
        List<Cake> cakes = new ArrayList<>();
        getData(cakes);
        System.out.println(resultedVolume(cakes));
    }
    private static void getData(List<Cake> cakes) {
        Scanner in = new Scanner(System.in);
        int amount = in.nextInt();

        for (int i = 0; i < amount; i++) {
            Cake cake = new Cake();
            cake.radius = in.nextInt();
            cakes.add(cake);
        }
        for (Cake cake : cakes) {
            cake.volume = in.nextInt();
        }
        in.close();
    }
    private static long resultedVolume(List<Cake> cakes) {
        Collections.sort(cakes);
        Cake cake_0 = cakes.get(0);
        long previousRadius = cake_0.radius, previousVolume = cake_0.volume, previousVolumeSum = cake_0.volume;
        for (int i = 1; i < cakes.size(); i++) {
            Cake cake_i = cakes.get(i);
            if (previousRadius == cake_i.radius) {
                if (cake_i.volume > previousVolume) {
                    previousVolumeSum -= previousVolume;
                    previousVolumeSum += cake_i.volume;
                    previousRadius = cake_i.radius;
                    previousVolume = cake_i.volume;
                } else {
                    continue;
                }
            } else {
                previousVolumeSum += cake_i.volume;
                previousRadius = cake_i.radius;
                previousVolume = cake_i.volume;
            }
        }
        return previousVolumeSum;
    }
}
class Cake implements Comparable<Cake>{
    long radius, volume;

    @Override
    public int compareTo(Cake o) {
        return Long.compare(o.radius, radius);
    }
}

13 Востаннє редагувалося koala (23.02.2022 22:48:37)

Re: Алготестер задача Коржі

Круто. А ось пайтон:

input()
radius = [int(x) for x in input().split()]
volume = [int(x) for x in input().split()]

cakes = {}

for r, v in zip(radius, volume):
    if r not in cakes or cakes[r] < v:
        cakes[r] = v
        
print(sum(cakes.values()))

можна основний цикл навіть ось так зробити:

from collections import defaultdict
cakes = defaultdict(int)
for r, v in zip(radius, volume):
    cakes[r] = max(cakes[r], v)

14

Re: Алготестер задача Коржі

Дякую за допомогу, на java, але я ще хочу добити сішку.