Решаем сложные и олимпиадные задачи

[0xDEADBEEF]

Решаем сложные и олимпиадные задачи

Небольшие правила:

• 
  [*:081779a3a9] Задачи выкладываем с полным описаниями, примерами входных/выходных данных, ограничениями на память и на время.
  [*:081779a3a9] Если задача взята с проверяющих серверов, то необходимо дать номер или ссылку на задачу.
  

Peking University Online Judge System
Tianjin University Online Judge
MIPT El Judge
UVa Online Judge
Saratov State University :: Online Contester
Sphere Online Judge
ACM-ICPC Live Archive Around the World
HIT Online Judge System
Timus Online Judge

[*:081779a3a9] Если задача с проверяющих серверов, то желатель перед выкладыванием сдать её на этом сервере и привести время и память.
[*:081779a3a9] Новые задачи выкладываются только после того как решена предидущая.
[*:081779a3a9] Решивший имеет приотритет в выкладывании.
[*:081779a3a9] Решение приводить полное, за исключением, если задача тривиальная либо на моделирования некоторой ситуации. В последнем случае приводить какие-либо хитрости для решения, если таковые имеются.

Абстракционизм в массы

[toll]

Пустая затея... чтоб решать олимпиадную задачу нада уже знать решение этой задачи ...

[0xDEADBEEF]

Пустая затея... чтоб решать олимпиадную задачу нада уже знать решение этой задачи ...

Ээ, чегото я не пойму Смысл процесса решения и заключается в его поиске.

[duk999]

Хорошо вот тебе первая задачя:

Все мы знаем игру судоку надо автоматизировать процесс формирования задания

и

Разработать разгадыватель судоку.

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

[L0K1]

0xDEADBEEF

Задумка хороша =)

duk999

Такую задачку в каком-то LXF - задавали, конкурс на призы..

[Clondike]

duk999 писал:

Все мы знаем игру судоку надо автоматизировать процесс формирования задания

Я не знаю игру судоку. Объясни плз конкретно, что за игра, и что там за "формирование задания".

[0xDEADBEEF]

Задачка класическая. Если я не ошибаюсь, NP-полная. Отсюда и решение. При ограничениях N=3 не должна долго висеть

Генератор судоку - решаем бэктрекингом.

Решатель судоку - это тот-же генератор, только с уже заданными некоторыми позициями.

[fedbur]

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

P.S. Хотя куда я лезу,я не программист вообще то.

[Clondike]

fedbur

ну и что, что ты качал разгадыватель, в чем смысл-то? Тут люди сами решают задачи, а не качают готовые программы.

[fedbur]

Clondike

А разве смысл поста не понятен.

0xDEADBEEF

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

[0xDEADBEEF]

fedbur

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

[X-tender]

0xDEADBEEF +1000, руками и ногами - за давно не разминался но нам бы с загадывающими определиться, а то варианты вроде судоку - просто и скучно. Также не хотелось бы видеть задачи, которые дают ежегодно с небольшими изменениями в порядке слов на всяких региональных школьно-студенческих олимпиадах.

[0xDEADBEEF]

X-tender

С судоку в принципе согласен, задача избитая (зато познавателного чтения английской википедии о совершенном покрытии множества мне до утра хватит)

А задачки планировал именно со студенческих олимпиад, только ACM'овских.

По поводу построения, тут всё просто оказалось. Есть алгоритм со сложностью O(N^4)

Всё предельно просто:

У нас еть массив изначално заполненный числами от 1 до N^2

1. Распечатываем массив,

2. Циклически сдвигаем на N позиций. Повторяем N раз.

3. Сдвигаем массив на 1. Переходим на шаг 2. Повторяем N раз.

int main() {
int k, N, ch;
scanf("%d", &k); N =k*k;
for (int m = 0; m < k; ++m) {
ch=m;
for (int i = 0; i < k; ++i) {
ch += N-k;
for (int j = 0; j < N; ++j, ++ch)
printf (" %d", ch % N + 1);
printf("\n");
}
}
}

#include 

final int[][] field = new int[n*n][n*n];
int x = 0;
for(int i = 0; i < n; i++, x++)
for(int j = 0; j < n; j++, x+=n)
for(int k = 0; k < n*n; k++, x++)
field[n*i+j][k] = (x % (n*n)) + 1;

final int n = 3;

[L0K1]

Я тут прикинул, если и смогу выудить какие-нибудь задачи с компа , то только олимпиадные(вузы).

Да и в сети тоже - они упираются либо в мат. часть - либо просты до ужаса..

[X-tender]

У меня есть нерешенные задачи с олимпиад АСМовских 4-го тура, все мечтал когда-нибудь решить на досуге. Могу их предложить.

То есть нерешенные мной на олмпиаде

[0xDEADBEEF]

X-tender

Какой год, вуз? Четвертьфинальные?

Давайте выкладывать по одной. Можно в принципе давать право загадывания отгодавшему, но это наверно излишне.

[Lakers]

если кто хочет поришать олимпиадные задачи, вот сайт www.acm.timus.ru (внешка)

задачь много от простых до очень сложных.

Игра с камушками

Ограничение времени: 1.0 секунды

Ограничение памяти: 16 МБ

Два Никифора играют в следующую игру. Перед ними лежит кучка из N камней. Никифоры по очереди берут из неё некоторое число камней. За один ход разрешается взять любое число камней, являющееся целой неотрицательной степенью числа 2 (то есть, 1, 2, 4, 8, и т.д.). Выигрывает Никифор, взявший последний камень. Требуется написать программу, которая определяла бы, какой Никифор выигрывает при правильной игре: начинающий или его партнер.

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

В единственной строке находится целое положительное число N, не превосходящее 10250.

РезультатВ первой строке должно находиться число 1, если выигрывает начинающий Никифор, либо 2, если выигрывает Никифор, который ходит вторым. В случае если выигрывает начинающий Никифор, во второй строке должно быть указано минимальное число камней, которое он должен взять первым ходом, чтобы гарантировать себе выигрыш.

Пример

исходные данные:

8

результат:

1

2

номер задачи на сайте: 1180

если че сайт с автоматической проверкой, засылайте решения туда если интересно...

поришаем?

[0xDEADBEEF]

Терминальная антагонистистическая конечная игра с полной информацией. В частности, эта игра типа Ним.

Всё предельно просто, даже функцию Гранди не надо: если N делится нацело на 3, то выигрывает второй, если нет - первый. Соответственно перый раз нужо взять N%3 камней для первого.

К стати, этот

код решение задачи №124 с друго сервера - acm.mipt.ru Московского Физикотехнического Института.

[X-tender]

0xDEADBEEF

при 9 и 12 камнях вроде побеждает первый

[0xDEADBEEF]

X-tender

Нет, если второй следует оптимальной стратегии.

Как это решается (наглядно и без математики):

Выпишем несколко чисел от 0 до (допустим) 12. Числа - это количество камешек, теперь свяжем каждое число с тем, в которое можно попасть по правилам игры Теперь каждому числу дадим 2 разные метки (В и П) по следующему принципу:

1. Метка П дается числу, если мы можем попасть из него только в числа с меткой В.

2. Метка В дается, если среди чисел, в которые можно попасть есть несколько числа с меткой П.

Пометка начинается с 0, и он получает метку П.

Теперь оптимальна стратегия проста. Если мы оказались в числе с меткой В, то должны взять столько камней, чтобы следующий игрок оказался в числе П. И так далее. Нетрудно заметеить, что оказавшись в числе П, мы не можем попасть в другое число П, в том числе и в 0, и вынужденны идти в позицию В. Таким образом позиция П - проигрышная для того, кто должен делать ход.

Для данной игры выйдет так

0 1 2 3 4 5 6 7 8 9 10 ...

П В В П В В П В В П В ...

Вот и всё)

[X-tender]

0xDEADBEEF, ага это я поторопившись сказал. все верно, отталкиваясь от числа 3, находясь в котором человек побеждает, рассчитывается как заставить противника остаться в серии x%3=0

[Lakers]

вот задачка росложнее:

Марсопрыг

Ограничение времени: 0.5 секунды

Ограничение памяти: 16 МБ

Марсопрыг - это новая, усовершенствованная модель лунохода. Умники из конструкторского бюро решили, что в условиях низкой гравитации прыгать выгоднее, чем ходить. Кстати, прыгает он всегда одинаково, ровно на один метр. Для дистанционного управления эти умники приспособили обычную клавиатуру компьютера, точнее, дополнительные цифровые клавиши, те самые, которые справа. Это очень удобно и привычно: цифра 8 значит прыжок на север, 2 - на юг, 6 - на восток, 7 - прыжок на северо-запад, и так далее. Цифра 5 означает команду на взятие пробы грунта. Еще осталась неиспользованной цифра 0, и главный конструктор посоветовал назначить на эту клавишу команду для самоуничтожения марсопрыга, так как это очень полезная функция.

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

Перед отлетом заказчики потребовали провести испытание марсопрыга. Для проведения испытаний умники из конструкторского бюро посадили за компьютер дочку главного конструктора и предложили ей понажимать на разные клавиши. В результате марсопрыг куда-то упрыгал. Теперь его срочно надо найти.

Ваша задача - подсказать поисковой команде, где может находиться этот злополучный прибор. Теоретически он должен находиться в той точке, где впервые была нажата клавиша 0, или (если эту клавишу не нажимали) в той точке, куда он допрыгал к концу испытаний. Вам будет дана последовательность нажатий клавиш. Выведите конечное местоположение марсопрыга. Испытательный полигон считать бесконечной плоскостью.

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

не более чем 1000000 цифр от 0 до 9.

Результат Выведите координаты марсопрыга (в метрах, с точностью 10 знаков после запятой) в формате X Y, где X - смещение относительно начальной точки на восток, Y - смещение на север.

Пример

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

1236987412369870234567890123456789

результат

1.0000000000 0.0000000000

номер задачи:1413

[0xDEADBEEF]

Вообще задачи на моделирование лично я не считаю задачами. Тут алгоритма то нет, получаешь клавишу и прыгаешь туда. Всё. Такое пусть школьники на урока программирования делают.

Даешь настояшюю задачу!

[Lakers]

ща дам

Абстракционизм в массы

Ограничение времени: 1.0 секунды

Ограничение памяти: 64 МБ

Великий художник-абстракционист Герман Брукс придумал новый стиль в живописи — бактографию. И что же это за стиль, спросите вы. А все очень просто: теперь каждая картина — живая, в буквальном смысле этого слова. Герман рисует бактериями.

Такая картина — настоящее произведение искусства. Видели бы вы это завораживающее зрелище, переливающееся двумя, а то и тремя сотнями разных оттенков. Но как же показать это чудо простым людям? Фотография или видео просто неспособны передать всю гамму красок, а музея у Германа пока еще нет (не нравятся новаторские идеи современным хранителям культуры, куда уж с ними спорить). К тому же подробно рисунок можно рассмотреть только под микроскопом. В конце концов было решено скопировать несколько особо удачных картин в тысячах экземпляров и продавать в качестве сувениров. Однако возникла проблема. Сам Герман, как настоящий творец, копировать не желает, а биоинженеры, нанятые Германом, в один голос заявляют, что можно сделать копию, только если знать четкую последовательность, в которой полотно заселяли бактериями. Ваша задача — восстановить эту последовательность.

Для решения этой задачи биоинженеры сообщили следующую информацию:

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

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

В каждой клетке холста может быть не более четырех бактерий.

Процесс рисования заключается в том, что биоинженеры поочередно селят в свободные клетки холста по одной бактерии, при этом в каждой из соседних заселенных клеток (сверху, снизу, справа, слева) количество бактерий увеличивается на одну. Если в некоторой клетке стало 5 бактерий, то из-за перенаселения 4 из них погибают.

Поселить бактерию в уже заселенную клетку невозможно, ибо это приводит к непредсказуемой цепной реакции, портящей все полотно.

Исходные данныеПервая строка содержит числа n и m — размеры картины Германа (1 ≤ n, m ≤ 20). Далее описывается сама картина в виде таблицы из n строк по m чисел, где в каждой ячейке записано количество бактерий в соответствующей клетке картины — целое число от 1 до 4.

Результат

В случае если получить исходную картину процедурой, доступной биоинженерам, невозможно, вывести единственное слово «No». Если же вам удалось найти какую-либо последовательность, позволяющую создать копию шедевра Германа, то выведите в первой строке «Yes», а в следующих строках саму последовательность: по два числа в каждой строке — номер строки и номер стоблца заселяемой клетки картины.

Пример

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

3 3

2 2 1

3 1 3

1 2 2

результат

Yes

2 2

2 1

1 1

1 2

2 3

1 3

3 3

3 2

3 1

номер задачи:1649

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

насчет предыдущей задачи,если просто получать клавишу и прыгать то ты не уложешся во временной лимит=)

[0xDEADBEEF]

Lakers

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

итог - прошла за 0.064