Список форумов Шадринский форум -> Программирование -> Программирование для школьников и студентов. -> Задачка про звериков
Начать новую тему   Ответить на тему   вывод темы на печать

Задачка про звериков

Автор
Сообщение
xdsl
просто хороший человек


Пол: Пол:Муж.
Зарегистрирован: 25.11.2004
Сообщения: 1252
Откуда: shadrinsk

Статус: Offline
СообщениеДобавлено: 2007.03.18 23:05.11
Ответить с цитатой
Увидел тут одну любопытную задачку. В субботу пара наших студентов принимала участие в заочной олимпиаде по программированию, проводимой южноуральским госунивером. При подготовке им дали доступ к условиям задач, которые предлагались на предыдущих олимпиадах. Одна из них меня здорово заинтересовала тем, вроде-бы легко решается "в лоб", но такое решение сквозь тесты не проходит.

Условие примерно такое (точную формулировку не помню, но суть передам):
В зоопарке есть N видов животных. Каждого вида - определенное количество (скажем Xi, где 1<=i<=N). На выставку хотят выбрать три зверика разных видов. Вопрос: сколько всего уникальных комбинаций звериков можно выбрать для выставки?
Пример: при наличии двух львов, одного заяца, одного волка и одного медведя можно получить 7 уникальных комбинаций:
лев1 заяц волк
лев1 заяц медведь
лев1 волк медведь
лев2 заяц волк
лев2 заяц медведь
лев2 волк медведь
заяц волк медведь

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

А теперь самое главное. 1<=N<=100000, общее кол-во зверей также до 100000, время работы программы - не более 2 секунд. Кто первым уложится?

Добавлено спустя 54 минуты 11 секунд:

Совсем забыл. Вот тот-же тест, но для дос и винпррограм. По два символа на перевод строки. А то турбопаскаль или обжектпаскаль, например, хотят символы с кодами 10 и 13 в конце строки. Символ с кодом 10 концом строки не считают.



input.gz
 Описание:

Download File
 Имя файла:  input.gz
 Размер файла:  15.83 KB
 Скачано:  702 раз(а)


input.gz
 Описание:
Это "маленький" тест

Download File
 Имя файла:  input.gz
 Размер файла:  14.02 KB
 Скачано:  676 раз(а)

Посмотреть профиль Отправить личное сообщение
xdsl
просто хороший человек


Пол: Пол:Муж.
Зарегистрирован: 25.11.2004
Сообщения: 1252
Откуда: shadrinsk

Статус: Offline
СообщениеДобавлено: 2007.03.20 02:21.29
Ответить с цитатой
По мотивам международных олимпиад сляпал сегодня тестопрогонщик для произвольных задач:
http://shgpi.ru/scripts/tasks/

Удобно сверять свои результаты с верными.
В IE не проверял, но, имхо, интерфейс должен работать и там.
Посмотреть профиль Отправить личное сообщение
Sas'OK
Писатель


Пол: Пол:Муж.
Зарегистрирован: 06.03.2005
Сообщения: 321


Статус: Offline
СообщениеДобавлено: 2007.03.20 09:10.51
Ответить с цитатой
а какие пары получились можно на выходе сделать?
_________________
Ищи баги в себе!!!
Посмотреть профиль Отправить личное сообщение
xdsl
просто хороший человек


Пол: Пол:Муж.
Зарегистрирован: 25.11.2004
Сообщения: 1252
Откуда: shadrinsk

Статус: Offline
СообщениеДобавлено: 2007.03.20 12:39.22
Ответить с цитатой
Там пары, вернее - тройки, не считаются. Иначе по исходным условиям за 2 секунды вжизь не посчитать.
Посмотреть профиль Отправить личное сообщение
Den - L
troppus


Пол: Пол:Муж.
Зарегистрирован: 21.03.2007
Сообщения: 4


Статус: Offline
СообщениеДобавлено: 2007.03.21 16:07.11
Ответить с цитатой
Если есть решатель, значит задача решена???
Посмотреть профиль Отправить личное сообщение
xdsl
просто хороший человек


Пол: Пол:Муж.
Зарегистрирован: 25.11.2004
Сообщения: 1252
Откуда: shadrinsk

Статус: Offline
СообщениеДобавлено: 2007.03.21 17:27.03
Ответить с цитатой
Ага Podmigivanie
Двадцать минут (с трудом вспоминая комбинаторику) на вывод формулы (листочек+ручка), десять - на программу (клава+freepascal). Плюс пять минут на перевод с freepascal на php, чтобы в решатель вставить. Последнее, понятно, необязательно на своем хостинге, где можно просто исполняемый файл запустить, а результаты выполнения - юзеру отправить. Впрочем 100000 звериков и на php за 0.3 секунды считает, так что можно с исполняемым файлом не заморачиваться.

Кстати, в решатель задачки добавляю очень просто:
class SimpleTask extends OlimpTask 
{
 var $name="Тестовая задача";
 var $description="Возвратить исходные данные без изменений";
 function solve($input="")  {    return $input;  }
}
new SimpleTask;
Посмотреть профиль Отправить личное сообщение
Den - L
troppus


Пол: Пол:Муж.
Зарегистрирован: 21.03.2007
Сообщения: 4


Статус: Offline
СообщениеДобавлено: 2007.03.21 21:55.46
Ответить с цитатой
Двадцать минут!!!
У меня ушло часа три на поиск закономерностей!!!
Но решение получилось красивое, всего строчек в 15.

Добавлено спустя 2 часа 14 минут 57 секунд:

xdsl, а есть ещё подобные задачки?
Посмотреть профиль Отправить личное сообщение
xdsl
просто хороший человек


Пол: Пол:Муж.
Зарегистрирован: 25.11.2004
Сообщения: 1252
Откуда: shadrinsk

Статус: Offline
СообщениеДобавлено: 2007.03.21 22:28.48
Ответить с цитатой
Задачка взята отсюда: http://ipc.susu.ac.ru

Из более сложных попробуйте задачки про лабиринт и особенно волшебный лабиринт отсюда: http://shgpi.ru/f11/info/conf_olimp_2007/objavl_zao_olimp.html

Если заинтересовало и все получается, то вам дорога на http://ttb.by - соревнования по спортивному программированию в индивидуальном зачете
Посмотреть профиль Отправить личное сообщение
zLMP
Начинающий



Зарегистрирован: 27.05.2008
Сообщения: 11
Откуда: X3(икс три)

Статус: Offline
СообщениеДобавлено: 2008.05.28 23:07.01
Ответить с цитатой
xdsl, код решения задачи на freepascal можно увидеть
Посмотреть профиль Отправить личное сообщение ICQ Number
xdsl
просто хороший человек


Пол: Пол:Муж.
Зарегистрирован: 25.11.2004
Сообщения: 1252
Откуда: shadrinsk

Статус: Offline
СообщениеДобавлено: 2008.05.29 10:59.46
Ответить с цитатой
На паскале где-то затерялась, а на php - вот
 function solve($input="")
  {
    $x=preg_split("/\n/", $input, -1, PREG_SPLIT_NO_EMPTY);
    $n=count($x);
    $sl=0;
    $sk=0;
    $si=0;
    for ($l=$n-2-1; $l>=0; $l--)
    {
     $si+=$x[$l+2];
     $sk+=$x[$l+1]*$si;
     $sl+=$x[$l]*$sk;
    }
    return sprintf("% -20.0f",$sl);
  }
Посмотреть профиль Отправить личное сообщение
zLMP
Начинающий



Зарегистрирован: 27.05.2008
Сообщения: 11
Откуда: X3(икс три)

Статус: Offline
СообщениеДобавлено: 2008.05.29 22:16.10
Ответить с цитатой
Если интересно моё решение:
const
  Count = 2;
var
  i, n: Integer;
  a: array [0..Count+1] of Integer = (0, 0, 0, 1);
begin
  while not(Eof) do begin
    Readln(n);
    for i:= 0 to Count do
      a[i]:= a[i]+a[i+1]*n;
  end;
  Writeln(a[0]);
end.

чтение/запись в стандартный поток ввода/вывода
Посмотреть профиль Отправить личное сообщение ICQ Number
xdsl
просто хороший человек


Пол: Пол:Муж.
Зарегистрирован: 25.11.2004
Сообщения: 1252
Откуда: shadrinsk

Статус: Offline
СообщениеДобавлено: 2008.05.30 00:35.08
Ответить с цитатой
Подсобрал наши олимпиадные задачи за пару последних лет и выложил сюда: http://shgpi.edu.ru/scripts/tasks/
Посмотреть профиль Отправить личное сообщение
Страница 1 из 1
Начать новую тему   Ответить на тему   вывод темы на печать
Показать сообщения:   
Список форумов Шадринский форум -> Программирование -> Программирование для школьников и студентов. -> Задачка про звериков

 
Перейти: 
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете вкладывать файлы
Вы можете скачивать файлы