1

Тема: Алготестер, задача 1505.Голум та піца.Цікава задача

Не розумію в чому причина, але алготестер каже, що відповідь на третьому тесті неправильна. https://www.algotester.com/uk/ArchivePr … play/40681 . Буду вдячний допомозі.

#include <iostream>

using namespace std;

void QuickSort(int arr[],int Left,int Right)
{
    int i=Left;
    int j=Right;
    int etalon = arr[(Left+Right)/2];
    while(i<j){
        while(arr[i]<etalon) i++;
        while(arr[j]>etalon) j--;
        if(i<=j){
            swap(arr[i],arr[j]);
            i++;j--;
        }
    }
    if(Left<j) QuickSort(arr,Left,j);
    if(i<Right) QuickSort(arr,i,Right);


}

int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
    QuickSort(arr,0,n-1);
    int maxx = -1; //якщо я присвою максимум -1 то в будь якому випадку перший кусок стане максимумом
    for(int i=1;i<n;i++){
        if( (arr[i]-arr[i-1])>maxx ) maxx = arr[i]-arr[i-1]; // знаходжу найбільший кусок
    }
    if( (360-arr[n-1]+arr[0] )>maxx  ) maxx = 360-arr[n-1]+arr[0];
    // порівнюю найбільший кусок з тим куском, що лежить між першим та останнім розрізом
    cout<<maxx/2.0;

    return 0;
}

2

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

молодий чоловіче, вам не соромно жебракувати на форумі? не свербить під пахвою?
Такі задачі люди розробляють для здатних дітей, у яких інтелектуальній рівень вищий за середній, щоб розвивати їх здібності.
Як оно вскакнути в чужу маршрутку?

3

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Пане ur_naz, мені це набридло. Вам попередження за порушення п.2.4 Правил. Додайте конструктиву до своїх дописів, бо підете за Віталієм.

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

4

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

По питанню: яка буде відповідь при вхідних даних

0 180

? А що пише ваш код? Як гадаєте, чому? А якби було 0 150, якою була б відповідь?
Загальна порада: починайте писати тести.

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

5

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Вибачте, не так зрозумів умову задачі. Завтра спробую зробити задачу правильно

6

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Я таки перепитаю чи так я зрозумів задачу. В задачі ми маємо розрізати найбільший шматок піци, щоб після розрізу найбільшиий шматок був як найменший, тобто коли ми введемо 0 і 150, то відповідь малла б бути 150?(При розрізі в 0 і 150 ми отрумуємо два шматки градусною мірою 150 і 210. Після цього ріжемо найбільший шматок, так щоб утворився як найменший максимальний)
https://replace.org.ua/uploads/images/9774/37906bd338304621a83d92c4a6140204.png

7

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Давайте трохи абстрагуємося. Половину ви зрозуміли правильно: треба відсортувати кути і знайти розміри шматків, включно з останнім, який (360-останній кут+перший кут)

Прихований текст

Хоча алгоритм сортування у вас трохи кривий, але на цих даних це ніби не важливо. А взагалі треба користуватися стандартною функцією сортування, це швидше і надійніше.

Тепер у нас немає єдиної піци, у нас купа шматків. І треба один з них порізати так, щоб мінімізувати максимальний шматок піци. Кути вже не мають значення - у нас є шматки P1, P2, ..., Pmax. Якщо розрізати будь-що, крім максимального, то максимум не зміниться. Якщо розрізати максимальний не навпіл, то одна з половинок може опинитися новим максимумом, який би міг бути меншим, тобто треба таки розрізати максимальний навпіл. Але після цього ці половинки можуть виявитися не максимальними. Ясно, чому?

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

8

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Пробував переробити ось що вийшло: 

#include <iostream>

using namespace std;

void QuickSort(int arr[],int Left,int Right)
{
    int i=Left;
    int j=Right;
    int etalon = arr[(Left+Right)/2];
    while(i<j){
        while(arr[i]<etalon) i++;
        while(arr[j]>etalon) j--;
        if(i<=j){
            swap(arr[i],arr[j]);
            i++;j--;
        }
    }
    if(Left<j) QuickSort(arr,Left,j);
    if(i<Right) QuickSort(arr,i,Right);
}
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
    QuickSort(arr,0,n-1);
    int arr_kyskiv[n];
    for(int i=1;i<n;i++){
        arr_kyskiv[i-1] = arr[i] - arr[i-1];
    }
    arr_kyskiv[n-1] = (360 - arr[n-1]) + arr[0];
    QuickSort(arr_kyskiv,0,n-1);
    if(arr_kyskiv[n-1]/2.0 >  arr_kyskiv[n-2]){
        cout<<arr_kyskiv[n-1]/2.0;
    }
    else{
        cout<<arr_kyskiv[n-2];
    }
    return 0;
}

#include <iostream>

using namespace std;

void QuickSort(int arr[],int Left,int Right)
{
    int i=Left;
    int j=Right;
    int etalon = arr[(Left+Right)/2];
    while(i<j){
        while(arr[i]<etalon) i++;
        while(arr[j]>etalon) j--;
        if(i<=j){
            swap(arr[i],arr[j]);
            i++;j--;
        }
    }
    if(Left<j) QuickSort(arr,Left,j);
    if(i<Right) QuickSort(arr,i,Right);
}
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
    QuickSort(arr,0,n-1);
    int maxx = 1, maxx_poperednyk=1;
    for(int i=1;i<n;i++){
        if((arr[i]-arr[i-1])> maxx   ){
            maxx_poperednyk = maxx;
            maxx = arr[i]-arr[i-1];
        }
    }

    if( (360-arr[n-1]+arr[0] )>maxx  ){
            maxx_poperednyk = maxx;
         maxx = 360-arr[n-1]+arr[0];
    }
    if(maxx_poperednyk >= maxx/2.0){
        cout<<maxx_poperednyk;
    }
    else{
        cout<<maxx/2.0;
    }


    return 0;
}

9

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Ви не написали, чи влаштовує вас цей результат.

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

10

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Ні, алготестер каже помилка

11

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Уважно перечитайте розділ "вихiднi данi".
І скористайтеся стандартним сортуванням.

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

12

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Перечитав розділ "вихідна інфрмація", але так і не зрозумів в чому помилка. І функція QuickSort сортує досить швидко.

13

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

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

Виведiть одне число з рiвно одним знаком пiсля коми

число з рiвно одним знаком пiсля коми

одним знаком пiсля коми

одним знаком пiсля коми

одним знаком пiсля коми
Подякували: zxzpogoncuk1

14

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Я перепрошую, а скільки знаків після коми повинно мати те число?

15

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Умову про один знак після коми я знав і пробував реалізувати так:

#include <iostream>

using namespace std;

void QuickSort(int arr[],int Left,int Right)
{
    int i=Left;
    int j=Right;
    int etalon = arr[(Left+Right)/2];
    while(i<j){
        while(arr[i]<etalon) i++;
        while(arr[j]>etalon) j--;
        if(i<=j){
            swap(arr[i],arr[j]);
            i++;j--;
        }
    }
    if(Left<j) QuickSort(arr,Left,j);
    if(i<Right) QuickSort(arr,i,Right);
}
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
    QuickSort(arr,0,n-1);
    int arr_kyskiv[n];
    for(int i=1;i<n;i++){
        arr_kyskiv[i-1] = arr[i] - arr[i-1];
    }
    arr_kyskiv[n-1] = (360 - arr[n-1]) + arr[0];
    QuickSort(arr_kyskiv,0,n-1);
    if(arr_kyskiv[n-1]/2.0 >  arr_kyskiv[n-2]){
        cout<<float(arr_kyskiv[n-1])/2.0;
    }
    else{
        cout<<float(arr_kyskiv[n-2]);
    }
    return 0;
}

Не перевіривши код, я закинув на алготестер. Аж потім я зрозумів, що він не працює.
Тому ось до що вийшло:

#include <iostream>

using namespace std;

void QuickSort(int arr[],int Left,int Right)
{
    int i=Left;
    int j=Right;
    int etalon = arr[(Left+Right)/2];
    while(i<j){
        while(arr[i]<etalon) i++;
        while(arr[j]>etalon) j--;
        if(i<=j){
            swap(arr[i],arr[j]);
            i++;j--;
        }
    }
    if(Left<j) QuickSort(arr,Left,j);
    if(i<Right) QuickSort(arr,i,Right);
}
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
    QuickSort(arr,0,n-1);
    int arr_kyskiv[n];
    for(int i=1;i<n;i++){
        arr_kyskiv[i-1] = arr[i] - arr[i-1];
    }
    arr_kyskiv[n-1] = (360 - arr[n-1]) + arr[0];
    QuickSort(arr_kyskiv,0,n-1);
    if(arr_kyskiv[n-1]/2.0 >  arr_kyskiv[n-2]){
        if(arr_kyskiv[n-1]%2==0){
            cout<<arr_kyskiv[n-1]/2<<".0";
        }else{
            cout<<arr_kyskiv[n-1]/2.0;
        }
    }
    else{
        cout<<arr_kyskiv[n-2]<<".0";
    }
    return 0;
}

Можливо допис нуля можна зробити якось грамотніше?
Дуже дякую всім хто відкликається на моє прохання, а особливо koala. koala ви за декілька днів допомогли більше ніж вчитель з інформатики за рік.

16

Re: Алготестер, задача 1505.Голум та піца.Цікава задача

Треба налаштувати виведення:

cout<<fixed; //фіксована кількість знаків після коми
cout.precision(1);//1 знак
cout<<x; //буде рівно 1 знак після крапки

Можна скористатися маніпулятором:

#include <iomanip>
...
cout<<fixed<<setprecision(1)<<x;
Подякували: zxzpogoncuk1