1 Тема від zxzpogoncuk

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

Тема: Алготестер задача. Пошук Паліндрома.

Пошук палiндрома
Обмеження: 1 сек., 256 МiБ
Зеник має рядок s довжини n, кожен символ якого - 0 або 1. Зеник може видаляти символи з рядка s, проте екзамени вже скоро i часу лишилося мало, тому вiн може видалити не бiльше половини символiв. Марiчцi подобаються палiндроми - такi рядки, що читаються однаково злiва направо тасправа налiво. Допоможiть Зениковi видалити не бiльше половини символiв, щоб кiнцевий рядок сподобався Марiчцi (тобто був палiндромом).
Вхiднi данi
У першому рядку задано єдине натуральне число n - довжина рядка. В другому рядку задано s - рядок з котрого потрiбно видалити символи.
Вихiднi данi
Виведiть кiнцевий рядок пiсля видалення не бiльше, нiж половини символiв
Обмеження1≤n≤105
Приклади
Вхiднi данi (stdin)
2
01
Вихiднi данi (stdout)
1
Вхiднi данi (stdin)
3
010
Вихiднi данi (stdout)
010

mport java.util.Scanner;
import java.util.Vector;

public class Main {

    static int n;
    static Vector<Integer> vector = new Vector<>();

    public static void main(String[] args) {
        input();
        if (is_it_polindrome()){
            for (int i = 0; i <  n; i++){
                System.out.print(vector.elementAt(i));
            }
        }
    }

    public static boolean is_it_polindrome(){
        for (int i = 0; i <= vector.size() / 2.0; i++){
            if( !vector.elementAt(i).equals(vector.elementAt(vector.size()-i-1 )  )   ) return false;
        }
        return true;
    }

    public static void input(){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        try {
            for (int i = 0; i < n; i++){
                int input = System.in.read() - '0';
                if (input == 0 || input == 1){
                    vector.add(input);
                }
            }
        }catch (Exception e){ }
    }
}

Не зміг прудумати алгоритму. Я просто перевіряв, якщо початкова стрічка паліндром, то виводжу.
Спасибі за допомогу!

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

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

Re: Алготестер задача. Пошук Паліндрома.

Часу до іспиту небагато, тому рахуємо нулі й одиниці і видаляємо ті, кого менше. Результат - гарантовано паліндром.

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

koala вебсайт

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

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

Re: Алготестер задача. Пошук Паліндрома.

import java.util.Scanner;
import java.util.Vector;

public class Main {

    static int n , number_0 = 0 , number_1 = 0;
    static Vector<Integer> vector = new Vector<>();

    public static void main(String[] args) {
        input();
        delete();
        for (int i = 0; i < vector.size(); i++){
            System.out.print(vector.elementAt(i));
        }
    }

    public static void delete(){
        if (number_0 < number_1){
            for (int i = 0; i < vector.size(); i++){
                if (vector.elementAt(i).equals(0)) {
                    vector.remove(i);
                    i--;
                }
            }
        }else {
            for (int i = 0; i < vector.size(); i++){
                if (vector.elementAt(i).equals(1)) {
                    vector.remove(i);
                    i--;
                }
            }
        }
    }
    

    public static void input(){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        try {
            for (int i = 0; i < n; i++){
                int input = System.in.read() - '0';
                if (input == 0 || input == 1){
                    vector.add(input);
                    number_0 += input==0?1:0;
                    number_1 += input==1?1:0;
                }
            }
        }catch (Exception e){ }
    }
}

Не розумію чому 0 балів?

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

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

Re: Алготестер задача. Пошук Паліндрома.

Знайшов кулькість нулів(number_0)  і кількість одиниць(number_1). Потім в методі delete видаляв тих, що менше. Йду по вектору і якщо елемент не той, то видаляю при цьому і зменшую на 1(бо for збільшує на один, а я хоччу залишитися на тому ж місці). Приклади начебто правильно робить.

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

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

Re: Алготестер задача. Пошук Паліндрома.

Підозрюю, що це тому, що в умові чогось не сказано. Наприклад, що видаляти треба найменшу можливу кількість символів. Чи ще щось.

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

koala вебсайт

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

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

Re: Алготестер задача. Пошук Паліндрома.

public class Main {

    static int n , number_0 = 0 , number_1 = 0;

    public static void main(String[] args) {
        input();
        if (number_0 > number_1){
            while (number_0 > 0){
                System.out.print("0");
                number_0--;
            }
        }
        else {
            while (number_1 > 0){
                System.out.print("1");
                number_1--;
            }
        }


    }


    public static void input(){
        try {
            //вводжу n, яке мені не потрібне
            while (true){
                int input = System.in.read() - '0';
                if (input < 0 || input > 9) break;
            }
            while (true){
                int input = System.in.read() - '0';
                if (input!=0 && input!=1) break;
                number_0 += input==0?1:0;
                number_1 += input==1?1:0;
            }

        }catch (Exception e){ }
    }
}

Закинув такий код і пішло на максимальний бал. Чому так?

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

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

Re: Алготестер задача. Пошук Паліндрома.

Я, насправді, лише вчив Java, а не працював із нею, тому мені дещо складно копирсатися в неякісному коді; але, наскільки я бачу, 

        n = in.nextInt();
        try {
            for (int i = 0; i < n; i++){                // всього читаємо n символів
                int input = System.in.read() - '0'; //а тут можна прочитати зайвий символ '\n' - а значить, пропустити один знак із n

Трохи вам якіснішого коду:

import java.util.Scanner;
import java.util.Collections;

class Solver
{
    int number_0 = 0 , number_1 = 0;
    public Solver(String s)
    {
        for(char c : s.toCharArray()) {
            if(c=='0')
                number_0++;
            else if(c=='1')
                number_1++;
        }
    }
    public String solve()
    {
        String symbol = number_0>number_1?"0":"1";
        return String.join("", Collections.nCopies(Math.max(number_0,number_1), symbol));
    }
}

public class Main 
{
    public static void main(String[] args) {

        String s = input();
        Solver solver = new Solver(s);
        System.out.println(solver.solve());
    }
    private static String input()
    {
        Scanner in = new Scanner(System.in);
        in.nextLine(); //skip line with n
        return in.nextLine();
    }
}
Подякували: zxzpogoncuk1

koala вебсайт

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

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

Re: Алготестер задача. Пошук Паліндрома.

Тобто ви кажете якшо ввести       1
                                                   1
то програма прочитає символ '\n', а наступної одиниці не побачить?
Але якщо перевірити функцію input(тобто вивести кількість нулів і кілкість одиниць), то вона покаже правильне значення.

import java.util.Scanner;

public class Main {

    static int n , number_0 = 0 , number_1 = 0;

    public static void main(String[] args) {
        input();
        System.out.println("нулів: " + number_0);
        System.out.println("одиниць: " + number_1);
    }


    public static void input(){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        try {
            for (int i = 0; i < n; i++){
                int input = System.in.read() - '0';
                if (input == 0 || input == 1){
                    number_0 += input==0?1:0;
                    number_1 += input==1?1:0;
                }
            }
        }catch (Exception e){ }
    }
}

Наприклад, вводимо
1
1
Отримуємо
нулів: 0
одиниць: 1
1

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

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

Re: Алготестер задача. Пошук Паліндрома.

Алготестер сказав шо то в нього якість проблеми при перевірці програми

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