1

Тема: Алготестер задача № 0777. Шоу.

Шоу
Обмеження: 1 сек., 256 МiБ
У Румунiї пiсля змагань Шеф органiзував грандiозне шоу, на яке зiйшлося чи не пiв Бухаресту.В цьому шоу брали участь Глюк та Маргаритка. Вони по черзi виконували запальний танець живота та отримували вiд суддiв оцiнки. Пiсля цього Шеф визначав переможця.Перевага Маргаритки була в тому, що вона дiвчина. А перевага Глюка це, звичайно ж,пакет IBM на головi. Переможцем Шеф вважав того, чий добуток оцiнок був найбiльшим. Якщо ж добутки Глюка та Маргаритки були рiвними, то вигравав той, у кого краща найбiльша оцiнка.Якщо ж i найбiльшi оцiнки рiвнi то той у кого краща друга найбiльша оцiнка i так далi. Якщо ж набори оцiнок є абсолютно рiвними, то перемагає Маргаритка. Надiюсь вона належним чином оцiнить вибiр Шефа.Ваше завдання  знаючи оцiнки суддiв, визначити переможця.
Вхiднi данi
Перший рядок мiстить цiле число N - кiлькiсть суддiв. Другий рядок мiстить N цiлих чисел через пробiл Gi оцiнки Глюка. Останнiй рядок мiстить оцiнки Маргаритки Mi в такому ж форматi.
Вихiднi данi
Єдиний рядок з iменем переможця Gluk або Margaritka.
Обмеження
1≤N≤100000,
1≤Gi, Mi≤10.
Приклади
Вхiднi данi (stdin)                   Вихiднi данi (stdout)
3                                                      Gluk
3 1 3
2 2 2 
               
5                                                      Gluk
1 3 10 10 3
10 9 2 5 1

5                                                      Margaritka
1 3 5 7 4
4 5 7 3 1
https://algotester.com/uk/ArchiveProble … File/40393

На 53 прикладі неправильна відповідь.

import java.util.Arrays;
import java.util.Scanner;

public class Main {

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

class Show{
    private int  n;
    private int[] Gluk , Margarita;
    private int product_G = 1 , product_M = 1;

    public Show(){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        Gluk = new int[n];
        Margarita = new int[n];

        for (int i = 0; i < n; i++){
            Gluk[i] = in.nextInt();
            product_G *= Gluk[i];
        }

        for (int i = 0; i < n; i++){
            Margarita[i] = in.nextInt();
            product_M *= Margarita[i];
        }
    }

    public String result(){
        if ( product_G > product_M) return "Gluk";
        if ( product_M > product_G) return "Margaritka";
        Arrays.sort(Gluk);
        Arrays.sort(Margarita);
        for (int i = 0; i < n; i++){
            if ( Gluk[i] > Margarita[i] ) return "Gluk";
            if ( Margarita[i] > Gluk[i] ) return "Margaritka";
        }
        return "Margaritka";
    }
}

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

import java.util.Arrays;
import java.util.Scanner;

public class Main {

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

class Show{
    private int  n;
    private int[] Gluk , Margarita;
    private int product_G = 1 , product_M = 1;

    public Show(){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        Gluk = new int[n];
        Margarita = new int[n];

        for (int i = 0; i < n; i++){
            Gluk[i] = in.nextInt();
            product_G *= Gluk[i];
        }

        for (int i = 0; i < n; i++){
            Margarita[i] = in.nextInt();
            product_M *= Margarita[i];
        }

    }

    public String result(){
        if ( product_G > product_M) return "Gluk";
        if ( product_M > product_G) return "Margaritka";
        Arrays.sort(Gluk);
        Arrays.sort(Margarita);
        for (int i = n - 1; i >= 0; i--){
            if ( Gluk[i] > Margarita[i] ) return "Gluk";
            if ( Margarita[i] > Gluk[i] ) return "Margaritka";
        }
        return "Margaritka";
    }
}

2

Re: Алготестер задача № 0777. Шоу.

А і забув подякувати за вирачений час і зусилля!

3 Востаннє редагувалося koala (07.09.2020 12:37:40)

Re: Алготестер задача № 0777. Шоу.

Максимальний добуток буде 10100000, а ви його в int пхаєте.
Скористайтеся формулою log(a*b) = log(a) + log(b), ну і монотонністю логарифму.
Ну і для повної краси можна зберігати не повні масиви оцінок, а масиви на 10 чисел (число оцінок 1, число оцінок 2 і т.д.). І логарифми, і найкращі по таких масивах легко знаходяться.

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

4 Востаннє редагувалося koala (07.09.2020 14:24:37)

Re: Алготестер задача № 0777. Шоу.

Ось код
import java.util.Scanner;
import java.lang.Math;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Dancer gluk = new Dancer(n, in);
        Dancer margaritka = new Dancer(n, in);

        System.out.println(margaritka.less(gluk)?"Gluk":"Margaritka");
    }
}

class Dancer
{
  private static double logs[];
  
  public Dancer(int n, Scanner scanner)
  {
      if(logs==null)
      {
          logs = new double[10];
          for(int i=0;i<10;++i)
              logs[i]=Math.log(i+1);
      }
      
      for(int i=0; i<n; ++i)
      {
          int score = scanner.nextInt();
          scores |= 1<<(score-1);
          product += logs[score-1];
      }
  }
  
  private int scores = 0;
  private double product = 0.0;
  
  public boolean less(Dancer other)
  {
    if(product<other.product)
      return true;
    if(product>other.product)
      return false;
    return scores<other.scores;
  }
}
Подякували: zxzpogoncuk1