Яндекс.Алгоритм 2013: тестовый раунд

11 лет назад, # ^ |

+24

Так можно делать с точки зрения технических возможностей, но так нельзя делать по причине того, что нарушителей просто дисквалифицируют при обнаружении факта нарушения.

Да и о чем вообще Вы беспокоитесь? Если у людей, занявших 2000-2100 места на квалификационном раунде, и есть шансы хотя бы на футболку, то они, прямо скажу, призрачные.

→ Ответить

dalex

11 лет назад, # ^ |

+24

В связи с появлением случайных футболок этот шанс возрос в бесконечное количество раз и теперь составляет примерно 4%.

→ Ответить

http://algorithm.contest.yandex.com/

11 лет назад, # ^ |

Все равно нужно решить хотя бы одну задачу на отборочном раунде.

→ Ответить

alpc104

11 лет назад, # |

I am very glad to see that organizers decided to provide more T-shirts as prizes. I think it will greatly enhance the enthusiasm of contestants.

→ Ответить

princerk

11 лет назад, # |

← Rev. 2 →

registration page is in russian .......how .i can register and there is no link..4 english ver

→ Ответить

proVIDec

11 лет назад, # ^ |

Here

→ Ответить

princerk

11 лет назад, # ^ |

thanks...

→ Ответить

DULGUUNBATMUNKH

11 лет назад, # |

Where is the contest link?

→ Ответить

kmamp

11 лет назад, # ^ |

→ Ответить

darkshadows

11 лет назад, # ^ |

You mean contest will be held on this link??

→ Ответить

kmamp

11 лет назад, # ^ |

← Rev. 3 →

-8

I believe it will be held here on Codeforces but I'm not 100% sure because it doesn't mention anything on their website.

→ Ответить

darkshadows

11 лет назад, # ^ |

← Rev. 2 →

-8

It's been updated here's the link. http://algorithm.contest.yandex.com/contest/306/

→ Ответить

kmamp

11 лет назад, # ^ |

-8

thank you!

→ Ответить

Rubanenko

11 лет назад, # |

На хроме очень тупят дропдаун списки. В частности,я не могу заполнить обязательное поле "уровень образования". Только не говорите, что нужно скачать Яндекс.браузер ;)

→ Ответить

11 лет назад, # ^ |

-8

У меня самый обычный хром, ничего не тупит. ЧЯДНТ?^W^W Какая версия хрома? Может, Javascript выключен? Или какие-нибудь странные аддоны установлены?

→ Ответить

Rubanenko

11 лет назад, # ^ |

Я пересел потом на ноут, но хром вел себя там абсолютно так же. Зарегался через ИЕ :)

→ Ответить

yermak0v

11 лет назад, # ^ |

У меня в хроме все нормально.

Версия хрома 27.0.1453.116 m.

→ Ответить

NALP

11 лет назад, # ^ |

+10

У меня тоже были в хроме бесконечные тупняки с дропдаунами, выражалось это в том, что необходимо выбрать 3 значения в них, но при изменении любых двух третий переставал работать :) Я раз 5-6 обновлял страничку и в итоге получилось :) Дерзайте!

→ Ответить

11 лет назад, # |

← Rev. 2 →

Хм... для компиляции Delphi используется fpc. а он Generics.Collections вроде не поддерживает. Опять Дельфийсты в пролёте.

→ Ответить

dalex

11 лет назад, # ^ |

Не оно? http://wiki.freepascal.org/Generics

→ Ответить

11 лет назад, # ^ |

Только что накидал простое приложение с TDictionary и подключением как в Делфе из uses Generics.Collections. Свежеустановленный fpc 2.6.0 ругается на ненайденный Generics.Collections

→ Ответить

dalex

11 лет назад, # ^ |

На страничке говорят, что у них это в модуле fgl...

→ Ответить

11 лет назад, # ^ |

-10

Видимо господа минусующие знаю как научить fpc понимать Generics.Collections, но в силу природной скромности об этом молчат. Либо это организаторы, к-е написали о поддержке Delphi без указания версии.

→ Ответить

11 лет назад, # ^ |

+11

Организаторы всё честно написали:

Delphi fpc <файл> -Sd -o <исполняемый файл>

А вы наверное разучились пользоваться гуглом и читать ответы: вам же сказали, что в FPC есть только модуль fgl, который ограничивается TFPGList, TFPGObjectList, TFPGInterfacedObjectList и TFPGMap. И это совершенно нормально — C++-ники ведь не жалуются, что у них boost'а нет.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

-22

Тогда зачем заявлять в поддерживаемых языках delphi, если он не поддерживается нормально.

→ Ответить

11 лет назад, # ^ |

Что значит "нормально"? Язык — это именно язык, а не всякие библиотеки. Поддерживается именно синтаксис языка Delphi (который существенно отличается от обычного паскаля). Не вижу в этом особой проблемы. Если вам не хватает prewritten generic списка — могли бы и сами его написать ;)

→ Ответить

11 лет назад, # ^ |

-19

Я может быть тупой, но по-моему если язык заявлен (и причём без номера версии), то это означает что я могу писать в любой среде, которая поддерживает этот язык и быть уверенным, что у жюри всё скомпилируется. В данном случае я не могу использовать, например, RAD Studio XE. Тогда надо было написать что поддерживаем Delphi <=7 или, допустим, компилятор совместимый с dcc32 такой-то версии. Или вообще убрать delphi.

→ Ответить

11 лет назад, # ^ |

+16

Вы никогда не можете писать в любой среде, "которая поддерживает этот язык", и быть уверенным, что всё скомпилируется (для любого языка). Например, потому, что в вашей системе могут быть установлены дополнительные библиотеки. Когда пишете код — надо всегда думать головой, прежде чем использовать какую-то библиотеку.

Пример: заявлен язык Java, я хочу писать в IntelliJ Idea, а у меня там подцеплено 100500 сторонних библиотек (например, sat4j). Я же не буду жаловаться, что у меня ничего не скомпилируется, если я их буду использовать.

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

→ Ответить

http://ru.wikipedia.org/wiki/Обобщённое_программирование

11 лет назад, # ^ |

← Rev. 5 →

-7

Обобщённое программирование (англ. generic programming) — парадигма программирования, заключающаяся в таком описании данных и алгоритмов, которое можно применять к различным типам данных, не меняя само это описание. В том или ином виде поддерживается разными языками программирования. Возможности обобщённого программирования впервые появились в 1970-х годах в языках Клу и Ада, а затем во многих объектно-ориентированных языках, таких как C++, Java, Object Pascal[1], D, Eiffel, языках для платформы .NET и других. Смотрим сноску 1: "↑ В Delphi и PascalABC.NET" В Delphi есть обобщённые типы и они по дефолту хранятся в Generics.Collections. Если в fpc их нет по этому адресу — он не поддерживает delphi последней версии. Факт?

В английской википедии в статье про Object Pascal: The Delphi language has continued to evolve over the years to support constructs such as dynamic arrays, generics and anonymous methods.

Представьте что было бы если бы заявили что поддерживают C#, но без указания версии, а при сдаче задач все увидели бы что у жюри .NET 1.0 без System.Collections.Generic — вой стоял бы. А с Delphi так можно поступать. Все делфийсты — не программисты, я знаю.

→ Ответить

11 лет назад, # ^ |

+19

Да блин, вы демагогией занимаетесь. В fpc есть generic'и как возможность языка. Там нет библиотеки с заранее написанными классами, которые по случайному совпадению оказались тоже generic'ами (а точнее потому, что кому-то захотелось скопипастить^W портировать некоторые библиотеки некоторых других языков).

Требования к стандартной библиотеке C# входят в спецификацию языка; спецификации языка Delphi похоже вообще не существует, но если вы её сможете найти и там будет требование "должен присутствовать System.Collections.Generic" — тогда ваши претензии можно будет рассматривать.

→ Ответить

ilona

11 лет назад, # |

+19

Тесты к задачам будут видны?

→ Ответить

11 лет назад, # |

← Rev. 2 →

2337 submission for problem A only 109 got Accepted !!!

most people had precision errors

even I used a user-defined function for comparing that didn't work

long double aabs(long double a){
	if(a>0){
		return a;
	}
	return -a;
}
long double EP=0.0000001;
bool is_equal(long double a,long double b){
	if(aabs(a-b)<EP){
		return true;
	}
	return false;
}

→ Ответить

KrK

11 лет назад, # ^ |

Maybe someone could comment how to solve A? Especially those, who got it right at the first attempt.

→ Ответить

11 лет назад, # ^ |

← Rev. 3 →

$\text{[math]}$ , so you can just compute fractions $\text{[math]}$ with integer numerators and denominators and find the fraction with the most occurrences in the multiset. (I've got it right at the second attempt, but only because I used stdin/stdout instead of files in my first submission).

→ Ответить

11 лет назад, # ^ |

do you mean R=(abc)/(4*S) or R=(4*abc)/(S)

→ Ответить

11 лет назад, # ^ |

Of course $\text{[math]}$ , it was a small typo.

→ Ответить

11 лет назад, # ^ |

you didn't fix the other fraction in your comment :)

→ Ответить

Scalar

11 лет назад, # ^ |

It does not matter for solving :)

→ Ответить

11 лет назад, # ^ |

actually yes it's like you multiplied all fractions with 16

→ Ответить

11 лет назад, # ^ |

← Rev. 3 →

a and b and c themselves may not be integers how can we save the numerator in integer variable ?

Edit: oops got it now , also S may not be integer but 16*S is always an integer

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

a² = (x₂ - x₁)² + (y₂ - y₁)², and so on. (2S)² = ((x₁ - x₀)·(y₂ - y₀) + (x₂ - x₀)·(y₁ - y₀))².

→ Ответить

banarun

11 лет назад, # ^ |

But numerator's maximum value can be (1400)^6 which will cause overflow even for unsigned long long int. How to store the value?

→ Ответить

11 лет назад, # ^ |

2^63 is around 9*10^18

1400^6 is around 7*10^18

→ Ответить

11 лет назад, # |

+22

Пара комментариев:

Хочется отправлять задачу со страницы задачи.
Хочется, чтобы система запоминала, что я отправляю копипастом.
Выбранный язык не влазит в селектбокс. я вижу только GNU c+

Это фича, что на Jav'е в F ML при сортировке массива long/Long ов?

→ Ответить

11 лет назад, # ^ |

Да, у меня тоже был ML. Жюри утверждает что у них есть решение, укладывающееся с тройным запасом..

→ Ответить

11 лет назад, # ^ |

Не, я верю, что можно например входные данные ручками парсить, а не создавать кучу строк а потом Long.parseValue, но вопрос нахера? не покидает меня.

→ Ответить

11 лет назад, # ^ |

-11

Как вы все умудрились там ML получить... У меня 14.97Mb, и я ничего специально для экономии памяти не делал. Неужели ArrayList вместо long[]? Я бы такую штуку на полмиллиона побоялся сортировать не только из-за ML, но и из-за TL :)

→ Ответить

http://pastebin.com/5HZe6i1e

11 лет назад, # ^ |

→ Ответить

11 лет назад, # ^ |

Хм, неужели это из-за парсинга? oO Как я рад, что когда-то написал нормальную парсилку для контестов.

→ Ответить

11 лет назад, # ^ |

Ну тупо же — в String считана вся строка с вводом. 2 байта на символ. По 20 символов (учитывая пробел) на число. Еще вопросы?

→ Ответить

cerealguy

11 лет назад, # ^ |

+16

20*2*500000 = 20M

→ Ответить

11 лет назад, # ^ |

Размер StringBuffer'а, в который читается строка, несколько больше реального размера строки (он расширяется в два раза). Затем еще происходит копирование в строку. У нас уже 4 мегабайта убиты на массив лонгов. Ну и стандартный Java оверхед. А так я сам не понимаю мемори лимитов в 64 Мб, я надеюсь, что здесь это for legacy reasons

→ Ответить

11 лет назад, # ^ |

+16

Вроде бы Олег обещает 256 на остальных раундах

→ Ответить

11 лет назад, # ^ |

Спасибо, с более аккуратным парсером заходит.

→ Ответить

11 лет назад, # ^ |

а в чем разница ArrayList и Long[] ? Вроде ведь оба должны сортиться одинаково?

→ Ответить

11 лет назад, # ^ |

ArrayList и Long[] — зло. long[] — ftw. В первых 2х случаях у вас промах кеша при обращении к любому элементу; это всё равно что int*[] на С++ сортировать.

→ Ответить

11 лет назад, # ^ |

long[] тоже валится по ML (см. мое решение)

→ Ответить

11 лет назад, # ^ |

Моё решение. Выходит, виноват не ArrayList, а парсинг... Впорос в том, почему оно не собрало мусор. Возможно, имеет смысл изменить параметры запуска, чтобы программы на java собирали мусор при приближении к ML.

→ Ответить

11 лет назад, # ^ |

А нету там мусора. Есть факт, что весь массив в одной строке и она читается через readLine

→ Ответить

11 лет назад, # ^ |

Ааа, я сразу и не заметил. Спасибо.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

Эээ.

Во-первых long[] как оказалось не ftw, MLится. Я понял, что вы предлааете использовать ArrayList, но не понял в чем может быть преимущество перед Long[], который тоже МЛится (а на Java6 TLится)

Во-вторых, Причем здесь массив указателей — не понял.

UPD: короче, понял предыдущий коммент не правильно, не актуально

→ Ответить

11 лет назад, # ^ |

Я не предлагаю использовать ArrayList, я предлагаю использовать long[]. "Long[]" и "long[]" — 2 большие разницы; первое — это, грубо говоря, "long long*[]", второе — "long long[]".

→ Ответить

11 лет назад, # ^ |

Спасибо за feedback. Отправка со страницы задачи будет. Запоминание — скорее всего да, с селектами подумаем, как лучше сделать.

→ Ответить

11 лет назад, # |

Вопрос к авторам контеста: зачем нужно было требовать в А использование длинки?

→ Ответить

Korvin79

11 лет назад, # ^ |

+16

я не автор, но длинка там не требовалась

→ Ответить

11 лет назад, # ^ |

Зачем там длинка?

→ Ответить

11 лет назад, # ^ |

+11

Я решал по формуле R = a * b * c / (4 * S), а т.к. длины не целочисленные, находил я R^2. Итого на тесте 0 0 1400 0 700 1400 числитель дроби получается больше 10^19, что в int64 не влазит.

→ Ответить

11 лет назад, # ^ |

1400^6 < 2^63

→ Ответить

11 лет назад, # ^ |

А каждое множитель не надо на 2 умножить? Там же x * x + y * y

→ Ответить

qwerty787788

11 лет назад, # ^ |

если точки (0, 0), (1400, 0), (1400, 1400), то 2 * 1400^6 > 2^63

→ Ответить

11 лет назад, # ^ |

2*1400^6 < 2^64 :)

→ Ответить

11 лет назад, # ^ |

1400^2 * (1400^2 + 700^2)^2 > 2^63

→ Ответить

11 лет назад, # ^ |

1400^2 * (1400^2 + 700^2)^2 < 2^64

→ Ответить

11 лет назад, # ^ |

Я не на сишке пишу :).

→ Ответить

11 лет назад, # ^ |

Ну если на джаве — то BigInteger, если на C++ — то unsigned long long. Не вижу никаких проблем, всё в стандартные типы влезает.

→ Ответить

11 лет назад, # ^ |

Я тоже проблем не вижу, написал в лоб на биг-интах. Переформулирую исходный вопрос: идея задачи была как раз в том, чтобы не получить переполнение? Или она все-таки подразумевалась как тупая халява, но авторы перемудрили?

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

Задача на корректный выбор типа данных, то есть авторское решение — решение в unsigned long long. Приведённый ниже тест против double "случайно" в тупой халяве появиться мог весьма с малой вероятностью...

→ Ответить

ns_serg

11 лет назад, # ^ |

Мое решение с long (на Java) прошло.

→ Ответить

11 лет назад, # ^ |

+18

Скажу по секрету, в signed int64 тоже проходит :)

→ Ответить

forest

11 лет назад, # ^ |

решал точно также с unsigned long long зашло

→ Ответить

rasmus

11 лет назад, # ^ |

Там не нужна длинка, если хранить в виде дроби.

→ Ответить

11 лет назад, # ^ |

У меня другой вопрос. Как в А построили такие дьявольские тесты?:)

Нахожу центр через серперы в даблах — ВА. в лонг даблах — ВА. Играюсь с точностью — ВА. Нахожу через формулу Герона — ВА. Пытаюсь все в целых — не влазит в ансайнд ЛЛ.

В результате внезапно зашло следующее — подсчитываем все в целых числах, кроме собственно числителя и знаменателя радиуса, их в даблах заносим. Сравниваем с точностью 1е-10. Почему это работает, а другое нет?..

→ Ответить

PavelKunyavskiy

11 лет назад, # ^ |

+22

Считал по формуле $\text{[math]}$ . 4 не нужно, возводим в квадрат. Получается $\text{[math]}$ . Площадь считается как векторное произведение. Числитель порядка 8 * 10¹⁸. В чем проблема?

→ Ответить

11 лет назад, # ^ |

В этом решении действительно все хорошо. Проблема в том, что мало какие другие заходили. Даже не проблема, а вопрос, что это за тесты, в которых при координатах до 1400 потеря точности в abc/4S столь велика, что их нельзя нормально сравнивать с точностью и предполагалось, видимо, решение в целых.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

+50

(0,0) (1312,164) (134,1372)

(0,0) (1351,169) (106,1317)

Разность радиусов меньше 2^{-52}

→ Ответить

11 лет назад, # ^ |

+45

Ни...чего себе) Спасибо

→ Ответить

11 лет назад, # ^ |

(abc)^2 ~ (2*1400^2)^3 > 2^64

→ Ответить

KungA

11 лет назад, # ^ |

Там координаты положительные.

→ Ответить

11 лет назад, # ^ |

а сторона 1400sqrt(2) при этом все равно достигается

→ Ответить

PavelKunyavskiy

11 лет назад, # ^ |

а откуда 1400, а не 1000?

→ Ответить

11 лет назад, # ^ |

Можно спросить об этом у авторов

→ Ответить

mmaxio

11 лет назад, # ^ |

← Rev. 2 →

+26

У треугольника (0, 0) — (0, 1400) — (1400, 0) $\text{[math]}$ , (abc)² = 2 × 1400⁶, только в беззнаковый 64-битный тип влезает.

В общем-то, от "белорусских, японских" и особенно "польских профессионалов" этого стоило ожидать.

→ Ответить

DmitriyH

11 лет назад, # ^ |

Считал по формуле: ..и пока не смог понять, на каком сэмпле точности double не хватит, чтобы адекватно сравнить два радиуса. Кто-нибудь поможет придумать контр-тест?

→ Ответить

Ripatti

11 лет назад, # ^ |

Там можно решить в целых числах без длинки.

Используем формулу $\text{[math]}$ .
Посчитаем a², b², c² (очевидно как) и 4S² (через векторное произведение).
Все эти числа влезают в long long.
Теперь надо эту дробь xyz / t нормализовать.
Сначала поделим x и t на их gcd, потом то же самое сделаем с y и t, z и t (это делается последовательно, а не одновременно).
Теперь надо просто сохранить пару xyz и t. c t все нормально, а вот xyz все же может чуток не влезать в long long — это можно сохранить в виде 2-3 чисел по разным взаимно простых модулям (я взял 2⁶⁴ и 10⁹ + 7).

→ Ответить

KungA

11 лет назад, # ^ |

Можно без НОД-а аналогично по модулям сравнивать дроби домножив на знаменатели (R[i] * abc[j] == R[j] * abc[i])(mod p)

→ Ответить

11 лет назад, # |

← Rev. 2 →

+10

Вот смотрю я на ratio accepted/submissions (4.6%, 2.7%, 44.3%, 6.8%, 16.7%, 8.8%) и думаю, а нужны ли такие контесты вообще...

UPD: О, оказывается для прохода дальше, надо было либо решить С в закрытую до 30й минуты, либо решить С в открытую до 9й. Качество зашкаливает.

Может кто рассказать решение F? Мне пока не удаётся обломать своё.

→ Ответить

Korvin79

11 лет назад, # ^ |

вроде традиционное ratio на вид, хоть для топкодера, хоть для codeforces. разве нет? :)

→ Ответить

11 лет назад, # ^ |

Ну, откидываем лёгкую задачу. И остаётся 5 задач с ratio < 10% (16.7% — её только tourist и сдал). Ну и получается лёгкая задача, а все остальные либо геометрия с погрешностями, либо конструкционные задачи, либо имплементационный case-work. Я таких комплектов ещё не видел.

→ Ответить

11 лет назад, # ^ |

А в E какие проблемы? Разве что файл повторно открыть...

→ Ответить

11 лет назад, # ^ |

Ой, да. Я почему-то в эту таблицу запихал ещё и забитые/пропущенные голы. С ними побольше кейсов. Меньше футбол смотреть надо.

В любом случае, имплементационный case-work. Согласен, что если бы народ решал эту задачу, ratio у неё возможно был бы нормальный.

→ Ответить

11 лет назад, # ^ |

Пока мы находимся левее автопарка, всегда выгодно брать самую хорошую машинку — это можно доказать, просто сравнив, куда мы доедем, если будем две машинки использовать в одном и в другом порядке.

Далее, если мы очутились правее автопарка, нам всегда хватит ровно одной машинки, которая может проехать М-Д.

Собственно, все. Либо пытаемся жадно доехать до финиша, либо исключаем самую медленную машинку, которая может проехать М — Д, и пытаемся жадно доехать до автопарка.

→ Ответить

KungA

11 лет назад, # ^ |

А если крутая машина нужна, чтобы доехать после автопарка, но мы ее уже заюзали?

→ Ответить

11 лет назад, # ^ |

Мы сначала выбираем из всех машин, которые могут проехать второй участок, самую плохую и не учитываем ее дальше

→ Ответить

11 лет назад, # ^ |

цитирую:

"Либо исключаем самую медленную машинку, которая может проехать М — Д" (читай — после автопарка) "и пытаемся жадно доехать до автопарка" (то есть — теми, которые остались)

→ Ответить

11 лет назад, # ^ |

А что с кейсом?

105 100 3
198 14 4

Ответ 2, а такой алгоритм получит 3, если не рассмотреть остаток слева у этой выброшенной машины.

→ Ответить

11 лет назад, # ^ |

У меня в решении еще есть бинпоиск, я забыл об этом упомянуть.

А для фиксированного количества машинок:

Скажем так, у нас есть некий универсальный код прогонки для последовательности машин. Мы его запускаем дважды — один раз для отсортированной последовательности, второй раз — для отсортированной последовательности, в которой один lower_bound(m — d) вынут и вставлен в конец. Берем минимум из двух ответов. (Ну, это внутри БП)

→ Ответить

forest

11 лет назад, # ^ |

работает такое что выбрав самую медленную машину как описано выше, нам уже жадно надо доехать не до автопарка, а чуть раньше — позиция автопарка минус избыток расстояния второго участка пополам

→ Ответить

11 лет назад, # ^ |

Это у меня и получало WA 16. Возможно я забажил.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

Я написал именно это и получил WA10.

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

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

WA10 — это вроде то, что можно "припасенного" чувака заюзать чуть раньше, пока не доехали до d, но уже можем доехать до конца

→ Ответить

11 лет назад, # ^ |

ОК, спасибо, вроде тоже самое...

Какие есть пограничные кейсы, если мы исключаем самую медленную машинку, которая может проехать М — Д?

Я рассмотрел остаток у этой машины (последняя может забирать уже с точки чуть левее Д), а также если мы вдруг и без последней доедем до финиша. Я что-то пропустил или просто зафэйлил в реализации?

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

nrg3

11 лет назад, # ^ |

← Rev. 2 →

Рассмотрим 2 случая:

1) m = d, т.е. база такси находиться в конечном пункте. Понятно, что выгоднее сначала ехать на тех такси, которые могут отвезти дальше, поэтому отсортируем x по убыванию и промоделируем поездки.

2) m ≠ d. Весь путь можно разбить на две части — первая от начала до базы такси, вторая — от базы к конечному пункту. Для проезда второй части нужна одна машина с запасом большим равным ее длины (если такой нет, то проехать нельзя). Найдем минимальную такую машину и отложим ее в сторону. Отсортируем х (без отложенной) по убыванию. Снова будем моделировать, но на каждом шаге проверять не хватит ли нам отложенной машины доехать до конца.

При этом нужно учитывать случаи, когда:

текущая машина не может доехать к нам.
мы уже приехали и отложенная машина нам не понадобилась.

Код

→ Ответить

11 лет назад, # ^ |

+12

Это тестовый раунд. Задачи не оригинальные, а когда-то использовались на этапах кубка (или еще где). Задача была проверить систему под нагрузкой

→ Ответить

rumman_sust

11 лет назад, # |

Can i have the test case 9 for problem A?

→ Ответить

11 лет назад, # ^ |

Tests are usually not disclosed in this type of competitions. It decreases motivation to prove your theoretical solution and test/debug your code.

→ Ответить

11 лет назад, # ^ |

+21

We decided to publish the competition archive, you can find it at the competition site

→ Ответить

Romchela

11 лет назад, # |

Расскажите, пожалуйста, решение задачи D

→ Ответить

11 лет назад, # ^ |

У меня зашло перебором)

→ Ответить

cska63

11 лет назад, # ^ |

а Вы можете подробнее рассказать

→ Ответить

11 лет назад, # ^ |

Пусть у нас будет рекуррентная функция F(N, From, Del) — N текущее число, From — минимальный делитель который можно взять, а Del — вектор для чисел из текущего ответа. В ней перебираем следующий делитель и запускаемся соответсвенно F(N/d, d+1, Del + {d})

→ Ответить

cska63

11 лет назад, # ^ |

А вот поясните пример с 4. Вот Вы сначала в ответ положите 2-у, что неправильно. Или я что-то неправильно понял??

→ Ответить

11 лет назад, # ^ |

Суть перебора в том, что он проверяет все варианты. Мы пробуем положить 2, и тогда запустим F(2, 3, {2}). Из-за того, что из двойки разложение на делителей больших 3 нельзя, то этот вариант отбросится. Попробуем положить 4, тогда F(1, 5, {4}), а это уже "крайний" случай.

→ Ответить

ValenKof

11 лет назад, # ^ |

← Rev. 2 →

+11

Найдём все делители числа N. Затем, для каждого делителя найдем его делители, просто перебирая найденные делители до корня. В итоге мы перебираем все тройки i, j, k, что div[i] * div[j] = div[k] (если div[k] делится на div[i], то j можно найти бин. поиском зная div[j]). Добавим в вектор g[j] очередную пару (i, k). Теперь динамика: dp[i][j] — наилучшее разложение делителя j, если использовались делители 1..i. Переход: dp[i][j] = max(dp[i — 1][k]), где i * k = j. Все возможные переходы мы уже сохранили в g, так что просто перебираем i, и переходы из g[i], при этом динамику можно записывать в тот же массив, если j перебирать по убывании.

→ Ответить

yaro

11 лет назад, # |

+64

Неожиданно симпатично все выглядит, единственная просьба авторам системы к следующим раундам — добавьте, пожалуйста, строчку с моим местом в положении участников (или где-то и так можно свое текущее место увидеть без пролистывания?)

→ Ответить

vtenity

11 лет назад, # ^ |

Спасибо! Постараемся добавить такое.

→ Ответить

OSt

11 лет назад, # |

+27

Если на контесте отправил задачу "в тёмную" и она не зашла то даже после контеста её ресабмитить нельзя?

→ Ответить

cska63

11 лет назад, # ^ |

У меня тоже не получается. Странно

→ Ответить

11 лет назад, # ^ |

К сожалению, сейчас нельзя, но мы это исправим.

→ Ответить

sparik

11 лет назад, # |

У меня MLE в E, как решить без сохранения списка имен команд? Длина имены <= 300, количество команд <= 300000

→ Ответить

11 лет назад, # ^ |

Можно переоткрыть файл

→ Ответить

sparik

11 лет назад, # ^ |

Спасибо. Теперь прошло :/

→ Ответить

PavelKunyavskiy

11 лет назад, # |

Авторам хочется высказать много ненависти за 500
000 в задаче F. Вроде правда на firefox не воспроизводится, только в хроме.

→ Ответить

knightL

11 лет назад, # |

+34

Было бы неплохо, если бы где-то можно было посмотреть, на каком месте находишься хотя бы ты, не говоря уже о своих друзьях

→ Ответить

11 лет назад, # ^ |

Про себя будет, про друзей тоже собирались, но пока не успели.

→ Ответить

mmaxio

11 лет назад, # |

+16

В системе не отвечают, спрошу тут: Возможно ли дорешивать задачи, отправленные на раунде вслепую?

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

→ Ответить

vtenity

11 лет назад, # ^ |

Мы постараемся сделать дорешивание слепых задач возможным. Возможность отправлять решение со страницы задачи тоже в планах.

→ Ответить

vtenity

11 лет назад, # ^ |

Теперь дорешивание всех задач стало возможным.

→ Ответить

Igorjan94

11 лет назад, # |

+11

freopen("number.out", "w+", stdout); //PE1
freopen("number.out", "w", stdout); //ОК

в чем причина РЕ1? во всех online judge w+ работает нормально

еще, обычно ошибки на 1ом тесте не считаются в штраф, ибо он совпадает с sample

→ Ответить

11 лет назад, # ^ |

Обычно — это где, кроме Codeforces?

→ Ответить

Igorjan94

11 лет назад, # ^ |

PCMS2Client, informatics.mccme.ru

→ Ответить

11 лет назад, # ^ |

+11

PCMS2? На полуфинале вроде даже compilation error дает штраф

→ Ответить

Igorjan94

11 лет назад, # ^ |

а, я подумал почему-то про первую часть вопроса, так да, только CF кажется

→ Ответить

sergileon

11 лет назад, # ^ |

-21

Может freopen("number.**in**", "w+", stdout); //PE1

→ Ответить

11 лет назад, # ^ |

Мы не давали права на чтение вашего выходного файла, только на запись. Добавим права на чтение.

→ Ответить

aaaaaaaaaaaaaaaaaaaaaaab

11 лет назад, # |

Когда будут известны 50 рандомных, прошедших в отборочный этап?

→ Ответить

dkirienko

11 лет назад, # ^ |

Не проще ли принять участие в квалификации и попасть в число 2000 прошедших квалификацию?

→ Ответить

aaaaaaaaaaaaaaaaaaaaaaab

11 лет назад, # ^ |

← Rev. 2 →

Согласен, просто интересно узнать

→ Ответить

11 лет назад, # ^ |

Будет новость, ждите

→ Ответить

Jarekczek

11 лет назад, # ^ |

Я теперь поучил мaйла. Конечно я случайный, место 350. Хорошо, потому что термин квалификационного раунда мне не подходит.

→ Ответить

Nezzar

11 лет назад, # |

how to solve D?

→ Ответить

11 лет назад, # ^ |

-11

div1 or div2 ? XD

only joking

→ Ответить

11 лет назад, # ^ |

Seems that my code will describe my solution much better than me.

→ Ответить

alexyz

11 лет назад, # |

Будет ли разбор ? Можно ли будет посмотреть тест на котором упало решение ? Как узнать, кто попал в те 50 случайных человек ?

Я решал D вот так:

Нашёл степени всех чисел от 2 до корня из n
Разложил каждую степень на сумму без повторных слагаемых.
Добавил к ответу текущее число в степени слагаемое из суммы.

В чём ошибка ? На слагаемые я вот так раскладывал:

long n = nextInt();
System.out.print(n + " = ");
for(int i = 1; n > i + i; i++) {
	n -= i;
	System.out.print(i + " + ");
}
System.out.println(n);

→ Ответить

eatmore

11 лет назад, # ^ |

На тесте

правильный ответ

4
1 2 3 6

→ Ответить

alexyz

11 лет назад, # ^ |

← Rev. 2 →

Выходит я должен не "склеивать остатки" в разложении на сумму, а искать к ним пару из "остатков" других степеней ?

→ Ответить

11 лет назад, # ^ |

-39

Разбор будет. Тесты на такого рода соревнованиях не выдаются. Новость про прошедших также будет.

→ Ответить

eatmore

11 лет назад, # ^ |

+52

Это на какого рода соревнованиях? На NEERC, например (да и на многих других ACM-контестах), после окончания можно скачать архив, который включает в себя не только тесты, но и решения жюри. На TopCoder и Codeforces можно посмотреть протокол тестирования. На RCC выкладываются архивы с тестами. На GCJ и HC тесты можно скачать даже не после, а во время контеста. Есть, конечно, OpenCup, но мне кажется, что это не тот контест, на который стоит равняться в этом плане. Поэтому не вижу причин, по которым Яндекс не мог бы выкладывать архив с тестами после тура.

→ Ответить

HolyInq

11 лет назад, # ^ |

-14

Финал ICPC, не?

→ Ответить

nk.karpov

11 лет назад, # ^ |

+11

С прошлого и позапрошлого года есть архивы.

→ Ответить

11 лет назад, # ^ |

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

→ Ответить

11 лет назад, # ^ |

+29

Ну раз отношение сообщества к этому вопросу так изменилось и все люто минусуют,- значит выложим тесты. У меня осталось со старых времен мнение, что надо учиться находить ошибку, не зная тест, на котором ошибка.

→ Ответить

yeputons

11 лет назад, # ^ |

← Rev. 2 →

+25

Разумеется, надо уметь, поддерживаю.

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

Есть возможность убедиться, что тест корректен. Например, проверить валидатор или написать его самостоятельно.
Есть возможность использовать задачи для тренировок. Например, если я нашёл 10 задач на какую-то тему, удобнее, чтобы они были собраны в одном контесте, а не раскиданы по 10 online judges.
Можно убедиться, что набор тестов полный. Например, валит какие-то совершенно идиотические решения. А если это не так — можно добавить соответствующие тесты к себе на тренировку.
Никто не гарантирует, что Яндекс.Контест будет доступен еще месяц, год, десять лет. Точно так же никто не гарантирует, что при полном обновлении системы (которое наверняка когда-нибудь произойдёт) старые соревнования случайно не исчезнут. Пример: то, что иногда происходит с тренировками на CF. А задачи не должны теряться.

→ Ответить

Gassa

11 лет назад, # ^ |

С другой стороны, выкладывание полного архива задачи делает её палёной раз и навсегда. Дальнейшее использование её в тренировках, которые влияют хоть на что-то, кроме индивидуального обучения (например, проход на сборы, получение зачёта, локальное соревнование, что-нибудь ещё) — сомнительная затея. С этой точки зрения задача в открытом доступе — это не плюс задача, а минус задача в "банке задач".

→ Ответить

HolyInq

11 лет назад, # ^ |

+14

А то, что её разыгрывали на официальном соревновании, да ещё и с разбором ещё ничего не значит?
Или речь про абстрактную задачу?

→ Ответить

Gassa

11 лет назад, # ^ |

Скорее про абстрактную. Переформулирую: я считаю, что ценность задачи для переиспользования понижается, когда она переходит из состояния "публичны условие и разбор" в состояние "публичен архив с тестами". И в обратную сторону переход невозможен.

Но это с точки зрения человека, у которого есть доступ к некоторым архивам задач, и лежащие там задачи вот таким образом меняют ценность. Понятно, что те, у кого такого доступа нет — а при выкладывании хоть к каким-то появляется, — наоборот, скорее порадуются публичным архивам с тестами. Но вместо этого, например, можно передавать архивы с тестами только между тренерами, как это часто и делается.

Поскольку я одна из заинтересованных сторон, мне сложно судить тут «объективно».

→ Ответить

11 лет назад, # ^ |

+16

Выложено на сайте соревнования

→ Ответить

vsb

11 лет назад, # |

Кто-нибудь может рассказать как решалась "B. Три дроби"?

→ Ответить

Qulinxao

11 лет назад, # ^ |

возможно(и скорей всего так) есть общее решение , но если расмотреть все варианты?

4/(4*k) ==1/k(1/2+1/3+1/6)

4/(2*k)==1/k+1/(k+1)+1/(k(k+1))

остаётся сложный случай когда n — нечётно тут всегда можно разложить на аликвотных что :(

надеюcь можно перебором первой дроби найти случай когда числитель второго слагаемого 1 что всегда можно разложить на сумму

4/n=1/z + остаток

где z начинается с (n+3)/4 и пока не получим удобный остаток 1/t который при ответе развернём на сумму 1/(t+1) +1/((t(t+1))

если же есть(имхо для многих чисел есть ) 2/m =1/p+1/q то поиск z облегчается.

→ Ответить

11 лет назад, # ^ |

+22

Здесь присутствует необходимая теория; то есть большинство случаев решается конструктивно или жадным алгоритмом Фибоначчи для поиска египетских дробей. Получаем, что надо найти решения для простых p<15000, для которых p=24k+1. А это уже делается предпросчётом.

→ Ответить

11 лет назад, # ^ |

+14

...А можно ещё проще — никаких статей не читать и заметить, что если 4/n=1/a+1/b+1/c, то 4/mn=1/ma+1/mb+1/mc.

Соответственно, достаточно предпросчитать локально перебором ответы для всех простых n<15000 и затем уже достроить таблицу значений.

В коде достаточно хранить b и c, a вычисляется по формуле nbc/(4bc-nb-nc).

→ Ответить

Anton_Lunyov

11 лет назад, # ^ |

← Rev. 3 →

+14

Не надо никакого предпросчета и конструктива.

Переберем c от n/4 до 3*n/4. Для данных c и n на a и b имеем уравнение

((4*c-n) * a - c*n) * ((4*c-n) * b - c*n) = (c*n)^2

Факторизуем n^2 * с^2 с помощью заранее посчитанного массива min_prime[] решетом Эратосфена. Формируем эффективно (рекурсией или еще как) все делители n^2 * с^2 и перебираем делитель d. Для данного делителя находим a и b из (4*c-n) * a - c*n = d и (4*c-n) * b - c*n = n^2 * c^2 / d и проверяем подходят они или нет.

Также сохраняем ответы для всех n, чтобы не считать одно и то же два раза.

Если оценивать грубо, то суммарная сложность такого решения зашкаливает, но оно зашло за 0.054.

UPD
Но если это объединить с конструктивом и запускать только для простых чисел вида 24*k+1, то должно получится мега шустро — за секунду можно будет насчитать все ответы до миллиона, я думаю.

→ Ответить

banarun

11 лет назад, # |

Will there be an editorial for this contest?

→ Ответить

11 лет назад, # ^ |

Yes, there will be.

→ Ответить

yeputons

11 лет назад, # |

Были серьёзные проблемы в Firefox 22.0: каждые секунд пять весь браузер подвисал на секунду-другую. Такое ощущение, что либо что-то вычислял, либо ждал ответ от сервера циклом for.

→ Ответить

11 лет назад, # ^ |

Ну а у меня например Firefox 22.0 не подвисал. И как вы предлагаете разработчикам искать, в чём проблема? :) Неужели так тяжело запостить технические детали — OS, аддоны браузера, конфигурацию машины... Тем более, там есть ссылка на багрепорт, которая автоматически технические детали заберёт.

→ Ответить

yeputons

11 лет назад, # ^ |

← Rev. 2 →

Да, тяжело, если не знаешь, что может потребоваться. А где есть ссылка на багрепорт? Я с ходу не заметил ничего, кроме "обратной связи" в футере.

Впрочем, мне уже ответили, что это может быть связано с тем, что я использовал "старый интерфейс" по адресу http://contest.yandex.ru , который при обновлении монитора каждый раз на клиенте просматривает и фильтрует всех участников, вместо того, чтобы предоставить это серверу. Полагаю, что использование "нового интерфейса" должно решить проблему.

→ Ответить

11 лет назад, # ^ |

Ну так да, я про "обратную связь" и говорю; а народе это называется "багрепорт" :) Про "старый интерфейс", наверное, надо было знать — вроде ссылок на него нигде нет. Впрочем, он мне нравится несколько больше — форма самбита находится на странице с задачами и логичнее оформлена, и монитор полный, а не только 50 человек (может, это главная причина тормозов?).

→ Ответить

iscsi

11 лет назад, # |

+16

I'm advanced, but can I participate in the Qualification round?

→ Ответить

11 лет назад, # ^ |

Yes, you can

→ Ответить

ysymyth

11 лет назад, # |

+34

seems awesome but what is Yandex

→ Ответить

11 лет назад, # ^ |

It's the 4th largest search engine in the world, surpassing Bing recently by the number of searches and succesfully competing with Google in Russia for many years. You can read more here and here and here

→ Ответить

patkovskyi

11 лет назад, # |

Друг зарегистрировался после конца тестового раунда и хотел посмотреть задачи, но у него вместо задач пустая страница с надписью "Соревнование началось" или "Контест начался" (не помню точно). Это баг или так задумано?

→ Ответить