Условия задачи - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
«Простые задачи на движение» 1 67.5kb.
Практическая часть. Банк задач 1 71.22kb.
Модуль «Личность в истории педагогики» Задачи 1 19.54kb.
Экспериментальное решение задач по теме Металлы 1 33.48kb.
Комплексные задачи 1 80.38kb.
Цель: создать условия для воспитания художественного, эстетического... 1 54kb.
Решение логических задач при помощи таблиц 1 183.04kb.
Викторина по сказкам А. С. Пушкина Задачи 1 83.61kb.
Классный час №3 (для средних классов) «все мы разные» цели и задачи... 1 51.08kb.
Условия задачи: Англичанин живет в красном доме 1 21.86kb.
Задача синтеза и условия разрешимости 1 Формулировка исследуемой... 3 258.04kb.
Рабочая программа музыке «Палитра детских голосов» 1 236.36kb.
Цвет погон, околышей фуражек и кантов на предметах военной формы... 1 71.79kb.
Направления изучения представлений о справедливости 1 202.17kb.

Условия задачи - страница №1/1

Погоны для революционной армии (автор М.Баландин)

Условия задачи

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

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

Всем африканцам свойственна любовь к самоукрашению, причём издавна количество украшений одновременно служило мерой влиятельности носящего их человека. Согласно этой традиции, чем выше армейское звание, тем больше звёздочек должно быть на погонах. Однако тут возникает проблема: попробуйте-ка при встрече с офицером быстро, одним взглядом определить, сколько звездочек у него на погонах, если их там больше десятка! (Надо сказать, что от проклятого старого режима новому революционному порядку достались ещё и большие проблемы с грамотностью населения; тут и до пяти-то не каждый сосчитает…)

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

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

во-первых, звёздочки должны располагаться не как попало, а в узлах прямоугольной сетки. (Это всё же армия, тут легкомысленные художества недопустимы!);

во-вторых, схема размещения звёздочек должна быть симметричной относительно продольной оси погона. (Чтобы не приходилось производить в уме лишних преобразований, увидев обладателя погон со спины);

Красивость погон майор понимал очень просто: чем разнообразнее рисунок, тем и красивее погоны. Разнообразие в его понимании тоже выглядело просто. Возьмём, к примеру, первый из погонов на рисунке. Выпишем число звёздочек в каждом ряду, начиная от плеча к шее (1,2,1) и расставим знаки сравнения (1<2>1). Для второго погона по той же схеме получится 2>1=1. В первом случае между числами стоит больше знаков, отличных от равенства, чем во втором (два против одного). Если же рисунок звёздочек симметричен не только относительно продольной, но и относительно поперечной оси погона, то красивость возрастает аж вдвое. А потому и первый погон красивее второго в четыре раза.



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

Анализ и решение задачи

Входными данными являются четыре целых положительных числа: количество продольных рядов звёздочек на погонах (обозначим его p), количество поперечных рядов (пусть будет r), количество звёздочек на майорских погонах (пусть будет m) и на генеральских (соответственно, g). Выходные данные — это строка символов, образующая слово: «YES», если ответ положительный: «NO», если ответ отрицательный; «IMPOSSIBLE», если в указанную сетку нельзя вписать m или g звёздочек по описанным правилам.

Формально задача относится к типу «размещения с ограничениями»: нужно рассмотреть всевозможные (удовлетворяющие армейским требованиям) генеральские погоны и определить минимальную красивость gm. Затем аналогично рассмотреть всевозможные майорские погоны и определить их максимальную красивость mm. Если , то ответ будет положительным, иначе отрицательным. А перед тем, как начинать рассматривать, необходимо определить, существуют ли вообще такие погоны.

Написать такую переборную программу, конечно, возможно, но эта идея по некотором размышлении оказывается совершенно бредовой. Сложность подобного алгоритма в самом лучшем случае будет . Несколько минут размышлений приводят к набору довольно-таки несложных условий, позволяющих определить ответ без впадения в алгоритмический маразм.
Определимся прежде всего с вопросом о том, когда создание погонов невозможно. Совершенно очевидно, что невозможность имеет место при или (эта ситуация настолько тривиальна, что её можно оговорить в условии задачи как заведомо недопустимую). Будем в дальнейшем предполагать, что «вместимость» погонов достаточна как для майорских, так и для генеральских звёздочек.

Теперь рассмотрим ситуацию, когда число p нечётно, т.е. . Легко увидеть, что в этом случае других ограничений нет. Действительно, представим число m (или g, неважно) в виде , где . Первые звёздочек можно разместить целым числом () поперечных рядов, а последние — в один ряд: если этот остаток чётный, то разделить его пополам и оставить центральные позиций пустыми; если он нечётный, то занять звёздочками центральные позиций.

Если же число чётно, т.е. , то возникает дополнительное ограничение: требование симметричности относительно продольной оси означает, что в левой и правой половинах погона должно быть звёздочек поровну — иными словами, числа и обязаны быть чётными. Коль скоро это так, звёздочки можно будет разместить так же, как описано в предыдущем абзаце.

Резюмируем условия невозможности, они выглядят так:



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


Теперь перейдём к вопросу о генеральских погонах. Если чуть подумать, то становится ясно, что минимальная их красивость будет равна нулю или единице. Действительно, коль скоро удастся расположить генеральских звёздочек прямоугольником (в каждом поперечном ряду поровну), то красивость будет равна нулю; сюда входит и кратный случай . В противном же случае снова пользуемся факторизацией , и красивость таких погон единична. Меньше уже просто некуда.

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



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



или, что то же самое,



Написать функцию, проверяющую возможность такой факторизации, не составляет никакого труда; пусть эта функция называется pr2k.


И, наконец, майорские погоны. Как видно, искать их максимальную красивость вовсе не обязательно; если можно обеспечить красивость не меньше двух, то этого уже вполне достаточно для положительного ответа на вопрос задачи. А её можно обеспечить, если допустимо разложение числа на сумму трёх слагаемых , каждое из которых способно дать различный вклад в рисунок:

При этом сумма поперечных рядов, необходимых для размещения трёх отдельных групп из , и звёздочек, не должна превосходить . Функцию, проверяющую такое представление, написать также нетрудно; пусть она называется sum3k. Заметим еще, что при чётном числа также должны быть чётными, это эквивалентно произвольному разложению числа .

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

(У меня анализ задачи занял около 25 минут и примерно 10 минут ушло на написание и отладку программы.)
P.S. Страна Гванерония действительно существует. Только не на карте, а в юмористическом рассказе А.Бушкова «Страна, о которой знали все».

Алгоритм


если m>pr или g>pr то ответ «IMPOSSIBLE»; стоп.

если p=2k

то если m!=2k или g!=2k то ответ «IMPOSSIBLE»; стоп.

иначе p=p/2, m=m/2, g=g/2

если pr2k(g) то gm=0 иначе gm=1

если sum3k(m)

то mm=2

иначе если (m<3 или m=pr) то mm=0 иначе mm=1

если mm>gm то ответ «YES» иначе ответ «NO»
Программа

#include
int pr2k(int g,int p,int r) {

for(int i=1;i<=g;i++)

if(!(g%i)) { int j=g/i; if((i<=p)&&(j<=r)) return 0; }

return 1;

}
inline int rw(int a,int b) { int i=a/b; return (a%b)?i+1:i; }
int sum3k(int m,int p,int r) {

for(int i=1;i<=m;i++)

for(int j=1;j<=m;j++) {

int k=m-i-j, q=rw(i,p)+rw(j,p)+rw(k,p);

if((q<=r)&&(k>0)&&(i%p!=j%p)&&(j%p!=k%p)) return 1; }

return 0;

}
void main() {

int p,r,m,g,gmin,mmax;

scanf("%u%u%u%u",&p,&r,&m,&g);

if((m>p*r)||(g>p*r)) { printf("IMPOSSIBLE\n"); return; }

if(!(p%2)) {

if((m%2)||(g%2)) { printf("IMPOSSIBLE\n"); return; }

p/=2; m/=2; g/=2; }

gmin=pr2k(g,p,r);

if(sum3k(m,p,r)) mmax=2; else mmax=((m>=3)&&(m


if(mmax>gmin) printf("YES\n"); else printf("NO\n");

return;

}

Столкновение с реальностью



Задача предлагалась на межвузовской олимпиаде 29 апреля 2006 года. Как и ожидалось, она попала в статус «довольно сложных»: решать её взялись лишь два участника (оба, кстати, представляли НГУ). Из этих двух участников одному решить задачу удалось (на что у него, правда, ушло 13 неудачных попыток); другой, предприняв 11 неудачных попыток, найти решение так и не сумел.





Если учесть, до какой степени люди дурны, нельзя не удивляться, как хорошо они себя ведут. Сальвадор де Мадарьяга
ещё >>