At the elections to the State Duma, N parties were included in the ballot papers. An electronic scanner for reading information from bulletins transmits information about each bulletin in the following format: if there is a mark in the corresponding cell of the bulletin, the scanner sends + (plus), otherwise it sends - (minus). Thus, it transmits a sequence of N characters - pros and cons.

A bulletin is considered valid if the mark is in exactly one cell. Invalid ballots do not participate in the counting of election results.

A party goes to the State Duma only if it gains at least 7% of the total number of valid ballots.

It is required to display the numbers (in the order of their listing in the bulletin) of all parties that pass to the State Duma.

Input The first input line contains two numbers, separated by a space: N - the number of parties and M - the number of ballots. Both numbers are natural, N <= 200, M <= 100 000.

The following M lines contain the information obtained from the bulletins. Each line is a sequence of N characters + or - (without spaces).

It is guaranteed that there is at least one valid newsletter.

Output Output the spaces of the parties that passed to the Duma, in ascending order, separated by spaces. If none of the parties passes to the Duma, it is not necessary to withdraw anything.

My solution looks like this:

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+" "); } } } }

I do not ask to solve the problem. Please indicate what my mistake is. My version passes only 1 test out of 23. What data the testing system uses when checking the solution is unknown.

  • you suggest to guess what difficulties have arisen? - Grundy
  • Why guess? The condition is, the code too. What else is needed? - Vakosta
  • and what is wrong with your code? - Grundy
  • This is what I want to find out - what's wrong with my code. When checking the code, everything seems to be working out, as it should be. But when passing, only 1 test out of 22 passes. - Vakosta
  • Do you get a reason for the failure? - Grundy

1 answer 1

Tests for Olympiad tasks take into account the execution time and the amount of memory used, so even the correct solution may not pass all tests if it is not optimal.

In your solution, you store all the original data, although the task has a solution that does not require such a large amount of memory. From the entire set of source data, it is sufficient to store only information on the number of ballots and parties, as well as the current bulletin entered.

Upd:

To begin, correct the obvious, not affecting the course of the decision.

Your version of the analysis of the description of the bulletin uses three times more memory than necessary (in fact, a little more, but these are trifles). You can fix this by refusing to use split("") which returns an array of single-character strings and recall that the string itself is an array and its elements can be accessed by index. An example of a corrected fragment (all variables from the original fragment of the vehicle, original lines requiring correction are commented out):

 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; } }

In principle, this change alone will be enough to reduce the total memory used by 3 times, which will help pass several more tests, but not all.

The next step is to get rid of the recording of all the ballots in an array of strings and process them as they arrive. The idea of ​​the algorithm, laid down in the code proposed by the CU, allows you to make the appropriate changes fairly painlessly.