1 Тема від zxzpogoncuk

  • zxzpogoncuk
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 20.12.2019
  • Повідомлень: 92
    • Репутація: 15

Тема: Алготестер задача № 0022. Верховна Рада. Java.

https://algotester.com/uk/ArchiveProble … WithFile/7

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++){
            arr[i] = in.nextInt();
        }
        if (n == 1){
            System.out.println(1);
            return;
        }
        int NSD_result = 0, NSD = 0;
        NSD_result = NSD(arr[0], arr[1]);
        for (int i = 1; i < n - 1; i++){
            NSD = NSD(arr[i], arr[i+1]);
            NSD_result = NSD(NSD_result, NSD);
        }
        int result = 0;
        for (int i = 0; i < n; i++){
            result += ( arr[i] / NSD_result);
        }
        System.out.println(result);
    }

    public static int NSD(int a, int b)
    {
        while(a > 0 && b > 0)

            if(a > b)
                a %= b;

            else
                b %= a;

        return a + b;
    }

}

На 11 прикладі пише, що неправильна відповідь. Дякую за допомогу!

2 Відповідь від koala Востаннє редагувалося koala (03.07.2020 12:34:19)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Алготестер задача № 0022. Верховна Рада. Java.

Бачу погане ім'я функції (англійською НСД - це gcd, greatest common divisor) і купу зайвих рухів, достатньо буде робити

int common_gcd = arr[0];
for (int i = 1; i < n; ++i){
    common_gcd= gcd(common_gcd, arr[i]);
}

До речі, і окремий випадок з n==1 тоді не потрібен.
Але до проблеми це не мало б призвести.
Може, десь від'ємне число запхали чи що...

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

koala вебсайт

3 Відповідь від zxzpogoncuk

  • zxzpogoncuk
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 20.12.2019
  • Повідомлень: 92
    • Репутація: 15

Re: Алготестер задача № 0022. Верховна Рада. Java.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++){
            arr[i] = in.nextInt();
        }
        int common_gcd = arr[0];
        for (int i = 1; i < n; ++i){
            common_gcd= GCD(common_gcd, arr[i]);
        }
        int result = 0;
        for (int i = 0; i < n; i++){
            result += arr[i] / common_gcd;
        }
        System.out.println(result);
    }

    public static int GCD(int a, int b)
    {
        while(a > 0 && b > 0)

            if(a > b)
                a %= b;

            else
                b %= a;

        return a + b;
    }

}

Переробив, але результат не змінився.

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Алготестер задача № 0022. Верховна Рада. Java.

Гм. А яка максимальна відповідь у задачі? Якщо там буде 998 чисел по 109 і два близьких до них простих (на кшталт 999983), то відповідь буде близькою до 1012. int в Java вміщає до 2 147 483 647 - тобто недостатньо. Зробіть 

long result = 0;
Подякували: zxzpogoncuk, leofun012

koala вебсайт

5 Відповідь від zxzpogoncuk

  • zxzpogoncuk
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 20.12.2019
  • Повідомлень: 92
    • Репутація: 15

Re: Алготестер задача № 0022. Верховна Рада. Java.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        long arr[] = new long[n];
        for (int i = 0; i < n; i++){
            arr[i] = in.nextLong();
        }
        long common_gcd = arr[0];
        for (int i = 1; i < n; ++i){
            common_gcd= GCD(common_gcd, arr[i]);
        }
        long result = 0;
        for (int i = 0; i < n; i++){
            result += arr[i] / common_gcd;
        }
        System.out.println(result);
    }

    public static long GCD(long a, long b)
    {
        while(a > 0 && b > 0)

            if(a > b)
                a %= b;

            else
                b %= a;

        return a + b;
    }

}

Так, ви маєте рацію. Мені потрібно уважніше читати умову задачі. Щиро дякую за допомогу!

6 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Алготестер задача № 0022. Верховна Рада. Java.

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

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

koala вебсайт