1 Востаннє редагувалося leofun01 (27.07.2020 00:16:42)

Тема: Алготестер задача № 0023. Депутатські краватки.

https://algotester.com/uk/ArchiveProble … WithFile/8 (pdf)
Задача цікава і на алготестер її розв'язало багато людей, але я навіть не знаю з чого починати. Прошу вас словесно(або кодом) розказати алгоритм розв'язку.

2

Re: Алготестер задача № 0023. Депутатські краватки.

І заздалегідь дякую за витрачений час та зусилля.

3

Re: Алготестер задача № 0023. Депутатські краватки.

Нащо Ви кожного разу приводите посилання на не зрозуміло що??

4

Re: Алготестер задача № 0023. Депутатські краватки.

Перша тупа ідея - бінарний пошук.

5

Re: Алготестер задача № 0023. Депутатські краватки.

Droid 77 написав:

Нащо Ви кожного разу приводите посилання на не зрозуміло що??

Бо сайт там кривий. Натисніть "умова".

Подякували: zxzpogoncuk, leofun012

6

Re: Алготестер задача № 0023. Депутатські краватки.

Та це я і сам зрозумів.
Просто за прямим посиланням на завдання маячня. Вже б писали задача номер такий, та посилання на загальну сторінку з умовами.

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

7

Re: Алготестер задача № 0023. Депутатські краватки.

Спробував придумати рішення в лоба - взяти середнє, якщо не підходить - беремо шматок із найбільшим залишком, що був порізаний на k частин, і беремо його довжину/(k+1) і т.д. Але не думаю, що це буде краще - там буде десь O(n) кроків, тобто у найгіршому разі кілька сотень ітерацій, а бінарний пошук дає O(log(n)).

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

8 Востаннє редагувалося koala (26.07.2020 22:34:53)

Re: Алготестер задача № 0023. Депутатські краватки.

Перепрошую, я мав на увазі бісекцію.

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

9

Re: Алготестер задача № 0023. Депутатські краватки.

Там обмеження в часі 2 секунди, хоча зазвичай 1, тому думаю програма не має бути надто швидка.

10

Re: Алготестер задача № 0023. Депутатські краватки.

Droid 77 написав:

Просто за прямим посиланням на завдання маячня. Вже б писали задача номер такий, та посилання на загальну сторінку з умовами.

На загальній сторінці з умовами потрібно в пошуку вводити або номер задачі, або її назву. Я думав, що вам буде зручніше переходити за прямим посилання на задачу.

11 Востаннє редагувалося koala (27.07.2020 18:50:57)

Re: Алготестер задача № 0023. Депутатські краватки.

Ось розв'язок на Python, якщо цікаво

Прихований текст
def process_input():
    mps = int(input().split()[1])
    ties = [int(x) for x in input().split()]
    return ties, mps

def find_best_length(ties, mps, eps):
    left = max(ties)/mps
    right = sum(ties)/mps
    if sum(tie//right for tie in ties)>=mps:
        return right
    while right-left>eps:
        middle = (right+left)/2
        if sum(tie//middle for tie in ties)>=mps:
            left = middle
        else:
            right = middle
    return (right+left)/2

if __name__== "__main__":
    ties, mps = process_input()
    length = find_best_length(ties, mps, 0.0001)
    print(length)

Тести проходить.

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

12

Re: Алготестер задача № 0023. Депутатські краватки.

koala написав:

Спробував придумати рішення в лоба - взяти середнє, якщо не підходить - беремо шматок із найбільшим залишком,


Зрозумів тільки частину вашого алгоритму. Ось що вийшло:

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Tie tie = new Tie();
        System.out.println(tie.result());
    }
}

class Tie{
    private int number_of_ties, number_of_deputies;
    private int arr_length_tie[];
    private double average = 0;

    public Tie() {
        Scanner in = new Scanner(System.in);
        number_of_ties = in.nextInt();
        number_of_deputies = in.nextInt();
        arr_length_tie = new int[number_of_ties];
        for (int i = 0; i < number_of_ties; i++){
            arr_length_tie[i] = in.nextInt();
            average += arr_length_tie[i];
        }
        average /= number_of_deputies;
    }
    private int index_tie_max_remainder = -1;
    private boolean is_average_result(){
        int new_number_of_ties = 0;
        double max_remainder = -1.0;
        for (int i = 0; i < number_of_ties; i++){
            new_number_of_ties += (int)(arr_length_tie[i]/average);
            if (max_remainder < arr_length_tie[i] % average) {
                max_remainder = arr_length_tie[i] % average;
                index_tie_max_remainder = i;
            }
        }
        if (new_number_of_ties >= number_of_deputies) return true;
        else return false;
    }

    public double result(){
        if (is_average_result()) return average;
        return 0;
    }
}

Будь ласка, допоможіть доробити програму. І був би надзвичайно щасливий, якби ви перевели свою програму на Java і я вже в ній розбирався. Дякую!

13

Re: Алготестер задача № 0023. Депутатські краватки.

Ви не зрозуміли.
Ідея бісекції така: беремо дві точки, одну (умовно ліву) - в якій точно умова не виконується, другу (праву) - в якій точно виконується. Беремо точку на середині і дивимося, чи там виконується? Якщо виконується - зсуваємо праву точку на середину, якщо ні - зсуваємо ліву. Таким чином, після кожного кроку відстань між точками скорочуватиметься удвічі, а відповідь - точка, в якій умова змінюється - лишатиметься між ними. Після кількох десятків кроків відстань скоротиться до однієї десятитисячної, і тоді повертаємо будь-яку точку з проміжку, як відповідь, точність точно достатня.

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

14

Re: Алготестер задача № 0023. Депутатські краватки.

А те була невдала спроба. Цілком можливо, не до кінця продумана.

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

15

Re: Алготестер задача № 0023. Депутатські краватки.

Пане koala, щиро дякую за допомогу! Завдяки вам я навчися методу бісекції. Ось, що вийшло:

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Tie tie = new Tie();
        System.out.println(round( tie.result() , 4));
    }

    private static double round(double value, int places) {
        BigDecimal bd = new BigDecimal(Double.toString(value));
        bd = bd.setScale(places, RoundingMode.HALF_UP);
        return bd.doubleValue();
    }
}

class Tie{
    private int number_of_ties, number_of_deputies;
    private int arr_length_tie[];
    private double left_point = 1_000_000_001.0, right_point = 0.0001;

    public Tie() {
        Scanner in = new Scanner(System.in);
        number_of_ties = in.nextInt();
        number_of_deputies = in.nextInt();
        arr_length_tie = new int[number_of_ties];
        for (int i = 0; i < number_of_ties; i++) {
            arr_length_tie[i] = in.nextInt();
        }
    }

    public double result(){
        double middle = 0.0;
        while ( left_point - right_point > 0.0001){
            middle = (left_point + right_point) / 2.0;
            int new_number_of_tie = 0;
            for (int i = 0; i < number_of_ties; i++){
                new_number_of_tie += (int) (arr_length_tie[i] / middle);
            }
            if (new_number_of_tie >= number_of_deputies) right_point = middle;
            else left_point = middle;
        }
        return middle;
    }

}

Програма пройшла всі тести. Ба більше вона є розв'язком задачі № 0607 Свічки. Достатньо змінити декілька стрічок коду.
https://algotester.com/uk/ArchiveProble … File/40306

16

Re: Алготестер задача № 0023. Депутатські краватки.

Ну, могли б у мене підглянути. Початкове значення правої межі - це середнє; більшою за середнє відповідь точно не може бути (але треба переконатися, що середнє не дає відповіді одразу). Лівої - це максимальна краватка, ділена на кількість депутатів, так гарантовано можна порізати.
І в умові нічого не сказано про округлення, лише про точність.

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