Задача с Тимуса

[moonserk]

Здравствуйте! Никак не могу решить задачу. Пожалуйста помогите!

Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ

Новый русский Колян любит две вещи: деньги и порядок. У Коляна много денег, но в них нет порядка. Одним прекрасным утром Колян понял, что он больше не может это переносить, и решил навести порядок в своих деньгах. Он приказал своим верным помощникам извлечь деньги из подземного хранилища, и скоро его большая комната была заполнена красными, зелёными и синими банкнотами. Колян смотрел с отвращением на этот ужасный беспорядок. Сейчас он хочет оставить в своём хранилище банкноты только одного достоинства, а остальные деньги раздать бедным. Он точно знает, что более половины банкнот имеют одинаковое достоинство. Но в беспорядке невозможно понять, какая банкнота встречается чаще всего.

Исходные данные

Первая строка содержит количество банкнот Коляна N (1 ≤ N ≤ 500 000). В следующих N строках даны достоинства K этих банкнот (0 ≤ K ≤ 109). Более половины из этих значений одинаковы.

Результат

Выведите наиболее часто встречающееся достоинство банкнот.
http://acm.timus.ru/problem.aspx?space=1&num=1510

Написал на JAVA и C# работает медленно поэтому не засчитывается. Можно ли как нибудь заставить работать побыстрей мою прогу или может я в корне не так делаю.

import java.util.*;

public class Uno {
	public static void main(String[] args){
		int jb = 0, jc = 0;
		Scanner in = new Scanner(System.in);
		int x = in.nextInt();
		int[] mass = new int[x];
		int[] mass2 = new int[x];
		int[] mass3 = new int[x];
		
		for(int i=0;i<mass.length;i++){
			int y = in.nextInt();
			mass[i] = y;
		}
		
		for(int i=0, j=0, p=0;i<mass.length;i++, j=0, p=0){
			if(mass[i] == 0){
				continue;
			}
			for(;j<mass.length;j++){
				if(mass[j] == 0){
					continue;
				}
				if(mass[i]==mass[j]){
					p++;
					if(i!=j){
					mass[j]=0;
					}
				}
			}
			mass2[i] = p;
			mass3[i] = mass[i];
			if(jb<=mass2[i]){
				jb=mass2[i];
				jc=i;
			}
		}
		System.out.print(mass3[jc]);
	}
}

using System;

public class Uno
{
    public static void Main(String[] args)
    {
        string x; string y;
        int jb = 0, jc = 0;
        x = Console.ReadLine();
        int[] mass = new int[int.Parse(x)];
        int[] mass2 = new int[int.Parse(x)];
        int[] mass3 = new int[int.Parse(x)];

        for (int i = 0; i < int.Parse(x); i++)
        {
            y = Console.ReadLine();
            mass[i] = int.Parse(y);
        }

        for (int i = 0, j = 0, p = 0; i < int.Parse(x); i++, j = 0, p = 0)
        {
            if (mass[i] == 0)
            {
                continue;
            }
            for (; j < int.Parse(x); j++)
            {
                if (mass[j] == 0)
                {
                    continue;
                }
                if (mass[i] == mass[j])
                {
                    p++;
                    if (i != j)
                    {
                        mass[j] = 0;
                    }
                }
            }
            mass2[i] = p;
            mass3[i] = mass[i];
            if (jb <= mass2[i])
            {
                jb = mass2[i];
                jc = i;
            }
        }
        Console.Write(mass3[jc]);
    }
}

Потом я решил попробовать написать на C++ ... Программа вроде работает верно однако при компиляции на Тимусе пишет Wrong Answer не пойму почему.

#include <iostream>
using namespace std;
void main(){
	int x;
	int y;
	int jb = 0, jc = 0;
		cin >> x;
		//int mass[x];
		int *mass = new int[x];
		int *mass2 = new int[x];
		int *mass3 = new int[x];
		
		for(int i=0;i<x;i++){
			cin >> y;
			mass[i] = y;
		}
		
		for(int i=0, j=0, p=0;i<x;i++, j=0, p=0){
			if(mass[i] == 0){
				continue;
			}
			for(;j<x;j++){
				if(mass[j] == 0){
				continue;
			}
				if(mass[i]==mass[j]){
					p++;
					if(i!=j){
					mass[j]=0;
					}
				}
			}
			mass2[i] = p;
			mass3[i] = mass[i];
			if(jb<=mass2[i]){
				jb=mass2[i];
				jc=i;
			}
		}
		cout << mass3[jc];
}

Пожалуйста, помогите!

[koljsch]

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

[moonserk]

Сообщение от koljsch

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

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

[Utkin]

Я бы побаловался с порядком условий. То есть в цикле наверняка какие-то события наступают чаще, чем другие.

if(mass[j] == 0){
					continue;
				}

Во вложенном цикле - не знаю, можно попробовать экспериментально. Возможно и не нужно там это вовсе.

ЗЫ. На месте Коляна я бы завел бухгалтера и оставил его жить в хранилище с деньгами .

[Serge_Bliznykov]

я бы вообще по другому эту задачу решал!
определил бы массив от 1 до 109
читал каждую строчку с номиналом
и увеличивал на 1 соответствующую строчку массива.
одновременно с увеличением обеспечивал поиск максимального. и вся задача.
на абстрактном языке это выглядит так:

начало
  Опеределим массив K размером 110 (от 0 до 109)
  в цикле от 1 до 109 заполним его нулями.
  iMax = 1;
  Читаем число N
  цикл от 1 до N 
      читаем очередное значение - величину купюры в Y
      наращиваем массив купюр на 1: K[Y]++
      если K[Y]>K[iMax] тогда iMax = Y
  конец цикла

  Выдать iMax
конец

ОТБОЙ!! Алгоритм мой не годится!
я сходил по ссылке. достоинства банкнот K от нуля до 10 в 9 степени. массив на миллиард, конечно, создавать не стоит!

[Abstraction]

0) Приводите ключевые моменты условия нормально, пожалуйста.

В следующих N строках даны достоинства K этих банкнот (0 ≤ K ≤ 10^9).

1) Если программа работает медленно - скорее всего, дело не в языке, а в алгоритме.
Зачем во всей этой истории двойной цикл? Решение "в лоб" - отсортировать массив и взять средний элемент (если N чётное - любой из средних), занимает O(N*lnN) по времени, O(N) по памяти.

Можно поискать решения не столь лобовые. Например, использовать самобалансирующееся дерево для хранения пар "номинал - найденное количество купюр". Или попытаться ещё более художественно поиграть с условием "одинаковых элементов больше половины". В любом случае, сомневаюсь, что возможно решение быстрее O(N*lnN), так что

        public static void Main(String[] args) {
            int N = int.Parse(Console.ReadLine());
            
            int[] mass = new int[N];
            for (int i = 0; i < N; ++i) mass[i] = int.Parse(Console.ReadLine());

            Console.Write(mass.OrderBy(i => i).ElementAt(N / 2));
        }

[Serge_Bliznykov]

в обсуждении на Timus
предложено решение с помощью A Linear Time Majority Vote Algorithm
цитирую:

Linear time majority vote algorithm


The O(n) algorithm is Boyer-Moore Majority Vote Algorithm,
which time is linear, and memory constant...
in fact you don't need more than 3 integer variables to run this
algorithm... As some people have mentioned, writing your own int input
procedure may improve your performance a lot. First time with no
optimization i got 1.06s, then i used a getc() based int input procedure
and did some little changes in the code and got 0.046s

ссылочку нашёл - A Linear Time Majority Vote Algorithm
или тут (pdf)

в пользу этого алгоритма говорит то, что в условии задачи

Более половины из этих значений одинаковы.

[Abstraction]

А. Красивый фокус.

        public static void Main(String[] args) {
            int N = int.Parse(Console.ReadLine());
            
            int[] mass = new int[N];
            for (int i = 0; i < N; ++i) mass[i] = int.Parse(Console.ReadLine());

            Tuple<int, int> result = mass.Aggregate<int, Tuple<int, int>>(new Tuple<int, int>(0, 0),
                (acc, next) => 
                    new Tuple<int, int>((acc.Item2 == 0) ? next : acc.Item1, (acc.Item2 == 0) ? 1 : (acc.Item2 + ((acc.Item1 == next) ? +1 : -1)))); 
            Console.Write(result.Item1);
        }

[moonserk]

Сообщение от Abstraction

0) Приводите ключевые моменты условия нормально, пожалуйста.

Извините, не заметил, просто скопировал с источника.

1) Если программа работает медленно - скорее всего, дело не в языке, а в алгоритме.

Это само собой. Просто пробовал на разных.

[kostan3]

#include <iostream>
#include <string>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;
int k[500002];

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        scanf("%d",&k[i]);
    }
    sort(k,k + n);
    k[n] = -1;
    int max = 0;
    int index = k[0];
    int countf = 1;
    for(int i = 1;i <= n;i ++){
        if(k[i] == k[i - 1]){
            countf ++;
        }
        else {
            if(countf > max){
                max = countf;
                index = k[i - 1];
                countf = 1;

            }
        }

    }
    cout << index << endl;



}