1

На выборах в Государственную думу в избирательные бюллетени внесено N партий. Электронный сканер для считывания информации с бюллетеней передает информацию о каждом бюллетене в следующем формате: если в соответствующей клетке бюллетеня стоит пометка, то сканер передает + (плюс), в противном случае он передает - (минус). Таким образом, он передает последовательность из N символов - плюсов и минусов.

Бюллетень считается действительным, если пометка есть ровно в одной клетке. Недействительные бюллетени в подсчете результатов выборов не участвуют.

Партия проходит в Государственную Думу, только если она набирает не менее 7% от общего числа действительных бюллетеней.

Требуется вывести номера (в порядке их перечисления в бюллетене) всех партий, которые проходят в Государственную Думу.

Входные данные В первой строке входных данных содержатся два числа, разделенные пробелом: N - количество партий и M - количество бюллетеней. Оба числа натуральные, N <= 200, M <= 100 000.

В следующих M строках записана информация, полученная из бюллетеней. Каждая строка - последовательность из N символов + или - (без пробелов).

Гарантируется, что есть хотя бы один действительный бюллетень.

Выходные данные Выведите через пробел номера партий, прошедших в Думу, в порядке возрастания. Если ни одна из партий не проходит в Думу, выводить ничего не нужно.

Мое решение выглядит так:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class main1 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str1 = reader.readLine();
        StringTokenizer stk1 = new StringTokenizer(str1," ");
        String []ar1 = new String[stk1.countTokens()];
        for(int i = 0; i<ar1.length; i++)
        {
            ar1[i] = stk1.nextToken();
        }
        //Выше - разбиение строки на массив
        int N = Integer.parseInt(ar1[0]); //Количество партий
        int M = Integer.parseInt(ar1[1]); //Количество бюллетеней
        int K = 0; //Количество действительных бюллетеней
        int[] result = new int[N]; //Количество голосов к партиям (0-я ячейка - первая партия, 1-я ячейка - вторая и т.д.)
        String[] P = new String[M]; //Бюллетени
        for (int a = 0; a < M; a++){
            P[a] = reader.readLine();
        }

        //Тут очистятся ячейки с недействительными бюллетенями, подсчитается количество действительных и распределятся голоса по партиям(result)
        for (int a = 0; a < P.length; a++){
            int i = 0;
            String parts[] = P[a].split("");
            for (int b = 0; b < parts.length; b++){
                if (parts[b].equals("+")) i++;
            }
            if (i != 1){
                continue;
            }else{
                K++;
                String parts1[] = P[a].split("");
                for (int b = 0; b < result.length; b++){
                    if (parts1[b].equals("+")) result[b] = result[b]+1;
                }
            }
        }

        //Проверяется условие (не меньше 7% от общего числа действительных бюллетеней) и выводится на экран через пробел
        for (int a = 0; a < result.length; a++){
            if (result[a] != 0){
                if ((result[a]*100)/K > 6) System.out.print(a+1+" ");
            }
        }
    }
}

Не прошу решить задачу. Укажите, пожалуйста, в чем моя ошибка. Мой вариант проходит только 1 тест из 23. Какие данные использует тестирующая система при проверке решения - неизвестно.

13
  • вы предлагаете угадать какие трудности возникли?
    – Grundy
    Commented 23 янв. 2016 в 21:10
  • Почему угадать? Условие есть, код тоже. Что же нужно еще? Commented 23 янв. 2016 в 21:13
  • и что же не так с вашим кодом?
    – Grundy
    Commented 23 янв. 2016 в 21:14
  • Именно это я и хочу выяснить - что не так с моим кодом. При проверке кода все вроде бы получается, как и должно получаться. Но при сдаче проходит только 1 тест из 22. Commented 23 янв. 2016 в 21:18
  • получаете ли вы причину провала?
    – Grundy
    Commented 23 янв. 2016 в 21:20

1 ответ 1

5

Тесты для олимпиадных задач учитывают время выполнения и количество используемой памяти, поэтому даже правильное решение может не пройти все тесты если не является оптимальным.

В вашем решении вы храните все исходные данные, хотя задача имеет решение не требующее такого объема памяти. Из всего набора исходных данных достаточно хранить только информацию о количестве бюллетеней и партий, а также текущем введенном бюллетене.

Upd:

Для начала исправим очевидное, не влияющее на ход решения.

Ваш вариант анализа строки описания бюллетеня использует памяти в трое больше чем необходимо (на самом деле еще немного больше, но это уже мелочи). Исправить это можно отказавшись от использования split("") который возвращает массив одно-символьных строк и вспомнить, что строка сама по себе массив и к ее элементам можно обращаться по индексу. Пример исправленного фрагмента (все переменные из исходного фрагмента ТС, оригинальные строки, требующие исправления, закоментированы):

int i = 0;
//String parts[] = P[a].split("");
//for (int b = 0; b < parts.length; b++)
for (int b = 0; b < P[a].length; b++)
{
    //if (parts[b].equals("+")) i++;
    if (P[a][b]=='+') i++;
}
if (i != 1)
{
    continue;//Переходим к обработке следующей строки
}
else
{
    K++;
    //String parts1[] = P[a].split("");
    for (int b = 0; b < result.length; b++)
    {
        //if (parts1[b].equals("+")) result[b] = result[b]+1;
        if (P[a][b]=='+') result[b] = result[b]+1;
    }
}

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

Следующим шагом необходимо избавиться от записи всех бюллетеней в массив строк и обрабатывать их по мере поступления. Заложенная в, предложенном ТС, коде идея алгоритма, позволяет внести соответствующие изменения достаточно безболезненно.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.