forum.boolean.name - Олимпиада по программированию

Страница 3 из 5

Показывать 64 сообщений этой темы на одной странице

forum.boolean.name (http://forum.boolean.name/index.php)

- Загадки (http://forum.boolean.name/forumdisplay.php?f=87)

- - Олимпиада по программированию (http://forum.boolean.name/showthread.php?t=16088)

Igor	20.01.2012 20:17

Ответ: Олимпиада по программированию

Идеи:
1) Круг неспроста. Пусть x,y-координаты середины кольца с радиусом R. Тогда для любой точки S=sqrt((X-Xточки)^2+(Y-Yточки)^2), модуль разности |S-R| должен быть одинаковым для всех точек-тогда мы решили задачу.
2) Если через эти четыре точки можно провести окружность, то ответ - Infinity, координаты центра окружности и радиус=0
В пункте 2 мы исключили варианты, когда все точки либо снаружи либо внутри.
3) Возможный вариант: Три точки лежат снаружи (или 3 внутри), а четвёртая - с другой стороны от дороги.
Берём три точки, ищем центр проходящей через них окружности, (радиус Ra), расстояние от центра до четвёртой точки Rb, возможный вариант решения (R=(Ra+Rb)/2)
смотрим для всех вариантов троек (их 4) и выбираем наименьший R
4) Последний вариант - две точки снаружи и две внутри. Пусть у нас две пары (1 и 2) и (3 и 4). проводим прямую равноудалённую от 1 и 2 (между ними), и прямую, равноудалённую от 3 и 4. Пересечение прямых - центр окружности. R=среднее арифметическое расстояний от центра до т. 1 и до т. 3
Для всех вариантов пар точек ищем наименьший R.
5) Ответ- вариант с наименьшим R из пунктов 3 и 4 если не прокатило со вторым

Igor	23.01.2012 21:05

Ответ: Олимпиада по программированию

Вложений: 8

Московская область, олимпиада. Ограничение по времени - 2 секунды на тест, занимать не более 256 мб оперативки.
1,2,5 задач нет потому что они простые

Задача 3. Имя входного файла xml.in, выходного- xml.out. Есть xml строка типа такой: "<a><ab></ab><c></c></a>" Длина - до 1000 символов. (строчные латинские буквы, <, > и /). Один символ поменялся((( Выходной файл должен содержать корректную xml строку, которая получается путем замены одного символа на другой в исходной строке. Если вариантов ответа несколько, подойдёт любой.

О самой олимпиаде: Проводилось два тура. Задачи (1-4) и (5-8), каждый тур 5 часов. Литературой пользоваться нельзя, программировать можно на паскале, делфи, си++, питоне, джаве. Какой-то парень писал на бейсике, но официально так делать нельзя.
Всё очень хитро. Каждому даётся бумажка с фамилией, паролем и логином. По ним логинишься на сервере олимпиады. всё по-честному, олимпиада у всех начинается одновременно и заканчивается тоже. Пароль заранее неизвестен, условие задач тоже. Тем не менее участники олимпиады сидят в одном здании.(точнее, в двух, но разницы никакой) Доступ в интернет вроде закрыт, хотя я не проверял. Код отправляется на сервер с указанием компилятора, на сервере компилируется и выполняется, проверка заданий автоматизирована. На компе тоже есть компилятор, можно писать и тестировать, но отсылается только код. Есть пара тестовых вариантов проверки (они в примерах к задачам)- если программа на них адекватно реагирует то принимается на проверку, и где-то через день можно узнать свои результаты.

задачи лень переписывать, выкладываю фотки.

h1dd3n

23.01.2012 21:19

Ответ: Олимпиада по программированию

Цитата:

Сообщение от Igor (Сообщение 217585)

Это вам так на разборе задач сказали?

Igor	23.01.2012 21:32

Ответ: Олимпиада по программированию

Цитата:

Это вам так на разборе задач сказали?

да.
Но я решал по-другому, (300 строчек кода набежало), получил 85 баллов из 100. Я искал символ, в котором ошибка, потом исправлял... пару нехороших случаев исправлять не научился, но тем не менее заработал много баллов)

h1dd3n

23.01.2012 21:36

Ответ: Олимпиада по программированию

Цитата:

Сообщение от Igor (Сообщение 217588)

Это и есть "правильный" способ. Неправильный символ либо тот который "неожидался", либо предыдущий, вот и весь перебор.

Igor	23.01.2012 22:02

Ответ: Олимпиада по программированию

далеко не всегда. вот например
<a></a><ab></x><x><sab>

P.S. Увидел результаты. Пичаль. Провалил второй тур - во второй задаче получил бы 100 баллов а не 4 если бы не перепутал m и n в ответе, за третью получил только 18 баллов(( Знал бы решил для частного случая за десять минут и получил бы 40 баллов(((. За четвёртую 30 - знал как решить на 100, но не успел

h1dd3n

23.01.2012 22:54

Ответ: Олимпиада по программированию

Цитата:

Сообщение от Igor (Сообщение 217594)

далеко не всегда. вот например
<a></a><ab></x><x><sab>

А какой правильный вариант то?

Igor	23.01.2012 23:01

Ответ: Олимпиада по программированию

<a></a><ab></x><x><sab>
<a></a><ab></x><x></ab>
ой. я </x> и <x> перепутал
копипастю самые сложные тесты

Nerd	25.01.2012 14:16

Ответ: Олимпиада по программированию

Цитата:

Литературой пользоваться нельзя, программировать можно на паскале, делфи, си++, питоне, джаве.

А по Краснодарскому краю одобрили только cpр и паскаль.

Цитата:

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

А у нас всё просто - нате комп, нате компилятор, нате 5 часов.
---
Да ну блин... Каким образом решение 8 задачи (которая про супрефиксы) могло пройти только 6 тестов из 20,
если входные данные по условию имеют одинкавую структуру - оно либо ни один не пройдёт, либо пройдёт все.
6 тестов мне пририсовали не сразу - на предварительных результатах было по нулям, это показалось мне странным, потому пошёл на апелляцию (и пририсовали уже потом, без моего присутствия).
Там же я узнал, что каким-то волшебным образом в обоих турах все мои решения, кроме первой задачи у проверяющих вылетали на всех тестах, хотя у меня работали с разными инпутами (т.е. хоть часть тестов должны были пройти).
Это... как объяснить? (кроме того, что я криворукий мудак =D)

Igor	25.01.2012 21:23

Ответ: Олимпиада по программированию

хз. В городской олимпиаде можно было прийти и посмотреть, как проверяют работу. Я этой возможностью всегда пользовался - сразу узнавал баллы и вообще на душе спокойней было. У нас на области можно посмотреть результаты работы тестирующей системы - все тесты, ввод, вывод программы, время выполнения и свой код. Сами тесты я условно разбиваю на три типа -
1)простейшие (маленькие числа, к производительности никаких требований), 2)частные и крайние случаи - (в них можно потерять баллы),
3)маньяческие тесты на быстродействие. Иногда совсем непонятно как получить максимум баллов.
В 8 задаче получил 30 баллов - не успел сделать сортировку - для остальных 70 баллов нужна оптимизация

Matt Merkulov

26.01.2012 11:49

Ответ: Олимпиада по программированию

Код:

import java.math.BigInteger;



public class CFactorial {

        public static void main( String[] args ) {

                System.out.println( Factorial( BigInteger.valueOf( 100 ) ).toString() );

        }

        

        private static BigInteger Factorial( BigInteger N ) {

                if( N.equals( BigInteger.ONE ) ) return BigInteger.ONE; else return N.multiply( Factorial( N.subtract( BigInteger.ONE ) ) );

        }

}

Вот, кстати, вам еще задача:
Даны два дробных числа, представленные 8-байтовым значением типа long следующим образом: старшие 4 байта - это целая часть, младшие - дробная. Т. е. это число "поделено" на 0x100000000. Реализовать сложение и вычитание просто, но попробуйте реализовать умножение, деление и вывод на экран не прибегая к другим типам данных.

Matt Merkulov

31.01.2012 15:24

Ответ: Олимпиада по программированию

Оказывается более расширенная задача такого типа довольно часто возникает при программировании микроконтроллеров, бизнес- и математических систем: http://habrahabr.ru/blogs/programming/131171/

shybovycha

08.02.2012 01:19

Ответ: Олимпиада по программированию

Раньше трава была зеленее олимпиады были сложнее и интереснее =)

Gogich

10.08.2012 23:14

Ответ: Олимпиада по программированию

Цитата:

Сообщение от Igor (Сообщение 217585)

Московская область, олимпиада. Ограничение по времени - 2 секунды на тест, занимать не более 256 мб оперативки.
1,2,5 задач нет потому что они простые

Хах, классно. Я тоже их решал, но я с Ростова)

У нас была ситуация другая: c++, c, pascal, python. Вроде был еще один чувак на VB, но я не уверен. Были несколько восьмиклассников, но в основном в первые места прошли 11 классы.

Задачи интересные, но местами туповатые. Тесты отправляются на сервер (к админу локальной сети), проводилась олимпиада в ЮФУ Мехмата.

Кстати уже PDF файлы появились..

Nerd	06.12.2012 16:22

Ответ: Олимпиада по программированию

Вложений: 1

hm? o_O
Решал подбором наугад, а есть ли нормальный алгоритм?

Часовой пояс GMT +4, время: 09:59.

Страница 3 из 5

Показывать 64 сообщений этой темы на одной странице