A – Казка про поросят icon

A – Казка про поросят




Скачати 78.74 Kb.
НазваA – Казка про поросят
Дата29.09.2012
Розмір78.74 Kb.
ТипДокументи

A – Казка про поросят


Имя входного файла:

fence.in

Имя выходного файла:

fence.out

Ограничение времени:

1 с

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

64 M

Ім’я вхідного файлу: fence.in

Ім’я вихідного файлу: fence.out

Обмеження по часу: 1 секунда

Обмеження по пам’яті: 64 мегабайт

Усім відома з дитинства казка про трьох поросят. Актуальною є вона і нині. От тільки поросят вже більше, та і вовки зліші.Зібрались якось поросята і стали думати що їм робити. День думали, другий, і вирішили будувати паркан навколо своїх будинків. Звісно поросята відчувають себе спокійніше, якщо навколо їх будинків побудовано якомога більше парканів. Напишіть програму, яка допоможе визначити, яке максимальне число парканів можна побудувати, якщо:
- кожен паркан має бути побудованим навколо щонайменше одного будинку;
- паркани не можуть перетинатись;
- ніякі два паркани не оточують один і той же набір будинків;
- розмірами будинків і товщиною паркана можна знехтувати.



Сірим кольором позначені будинки поросят

Формат вхідних даних

вхідний файл містить одне ціле число N (0 ≤ N ≤ 1012).

Формат вихідних даних

єдиний рядок вихідного файлу має містити одне число – максимальна кількість парканів, що можна збудувати.

Примеры


Входные данные в файле fence.in

Результат работы в файле fence.out

2



3


^

B – Степан у казино


Имя входного файла:

casino.in

Имя выходного файла:

casino.out

^ Ограничение времени:

1 с

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

64 M

Ім’я вхідного файлу: casino.in

Ім’я вихідного файлу: casino.out

Обмеження по часу: 1 секунда

Обмеження по пам’яті: 64 мегабайт

Одного разу Степан вирішив відвідати казино. Не будучи заядлим любителем азартних ігор, він зрозумів, що зовсім не знає правил ні однієї із ігор, доступних у казино. Недовго думаючи, Степан вирішив все-таки пограти. Його зацікавила гра з досить нехитрими правилами. На ігровому столі лежать N карток. На кожній картці написано ціле додатне число. Гра відбувається між гравцем і круп’є. Картки лежать на столі числами вниз. Гра полягає в тому, що гравець відкриває рівно N/2 карток. Сума всіх чисел, написаних на картках відкритих гравцем, називається “сумою гравця”. Наступним ходом круп’є відкриває N/2 карток, що залишились. Сума всіх чисел, написаних на картках відкритих круп’є, називається “сумою круп’є”. Виграш гравця визначається різницею чисел між “сумою гравця” і “сумою круп’є”. Очевидно, що отримана різниця може бути від’ємним числом. Це свідчить проте, що гравець програв і винен казино відповідну суму. Все б нічого, але Степан володіє даром бачити надписи крізь папір будь-якої щільності. Ваше завдання визначити максимальну суму виграшу, яку може отримати Степан з урахуванням того, що він бачить всі числа, написані на картках.

Формат вхідних даних

перший рядок вхідного файлу містить одне парне натуральне число N (2 ≤ N ≤ 100). Другий рядок вхідного файлу містить рівно N чисел Ai(1 ≤ Ai ≤ 106) – числа, написані на гральних картках. Всі числа у рядку розділяються одиночними пробілами, Ai – число, написане на i-й картці. Картки нумеруються послідовно, починаючи з одиниці.

Формат вихідних даних

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

Примеры


^ Входные данные в файле casino.in

Результат работы в файле casino.out

2

1 3



2



4

3 1 8 100



104





^

C – Степан брокер


Имя входного файла:

broker.in

Имя выходного файла:

broker.out

^ Ограничение времени:

1 с

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

64 M

Ім’я вхідного файлу: broker.in

Ім’я вихідного файлу: broker.out

Обмеження по часу: 1 секунда

Обмеження по пам’яті: 64 мегабайт

Степану з першого дня студентського життя легко давались, як не дивно, економічні дисципліни. Але реалізувати свої знання на практиці йому не вдавалось. Розпочати свій шлях до мільйона Степан вирішив з торгів на фондовому ринку. Основним і єдиним об’єктом торгівлі Степан невипадково обрав Державні Короткострокові Облігації (ДКО). Правила торгівлі цінними паперами регулює Фондова біржа. Торги проходять кожного дня. Правила торгівлі забороняють брокеру здійснювати більше однієї операції купівлі або продажу в день. Окрім цього, об'єктом операції може бути лише одна одиниця коштовних паперів – одна облігація. Правила торгівлі також визначають наступне: якщо брокер заявив про свою участь в торгах в якийсь певний день, то він зобов'язаний цього дня зробити операцію купівлі або продажу, тобто або купити одну облігацію, або продати облігацію. Ціна покупки і продажу облігації в кожен окремо взятий день однакова. Степан склав план, реалізацію якого вирішив почати з сьогоднішнього дня. Він взнав, що облігації із завтрашнього дня почнуть дорожчати на одну гривню в день. Наприклад, якщо сьогодні вартість однієї облігації складає одну гривню, то завтра вона коштуватиме дві гривні, післязавтра – три гривні, і так далі, на X-й день – вартість однієї облігації складе X гривен. Сьогодні ціна облігації рівна одній гривні. Степан заявив про свою участь в торгах протягом K днів, тобто в кожен з подальших K днів, починаючи з сьогоднішнього, Степан зобов'язаний або купувати одну облігацію або продавати одну облігацію. Вважатимемо, що дні нумеруються послідовно з одиниці, починаючи з сьогоднішнього дня. Вироблена Степаном стратегія торгів надзвичайно проста: якщо на момент торгів у нього досить грошей для покупки облігації, то він неодмінно купує її, інакше продає одну облігацію. Відомо, що на початку торгів наш брокер має N гривен і чимала (не менше K) кількість облігацій. Ваше завдання визначити суму грошей, яка буде у Степана в кінці K-го дня участі в торгах, якщо все розвиватиметься згідно з його планом і стратегією.

Формат вхідних даних

перший рядок вхідного файлу два цілих числа N і K (1 ≤ N, K ≤ 1015) відповідно. Де N – кількість гривен, K – кількість днів. Числа розділені одним пробілом.

Формат вихідних даних

єдиний рядок вихідного файлу має містити рівно одне ціле число – кількість грошей у Степана в кінці K-го дня у часті у торгах.

Примеры


^ Входные данные в файле broker.in

Результат работы в файле broker.out

7 4



5



1000 2010



1647





^

D – Степан і кубики


Имя входного файла:

cubes.in

Имя выходного файла:

cubes.out

^ Ограничение времени:

1 с

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

64 M

Ім’я вхідного файлу: cubes.in

Ім’я вихідного файлу: cubes.out

Обмеження по часу: 1 секунда

Обмеження по пам’яті: 64 мегабайт

Одного разу батьки на день народження подарили Степану набір кубиків. Батьки, прекрасно знаючи винахідливість свого сина, були упевнені, що подарунок прийдеться по душі їх чаду. Так і виявилось – Степану давно вже надоїли звичайні іграшки, оскільки вони, на його думку, не давали належного простору для винаходу своїх ігор і головоломок, чого не можна було сказати про набір кубиків. Не довго думаючи, Степан став вибудовувати в своїй кімнаті послідовність із стовпчиків, де стовпчик – це деяка додатна кількість кубиків, поставлених один на одного. Іншими словами, стовпчик – це послідовність кубиків не нульової довжини, де перший кубик є основою, а кожен наступний, починаючи з другого, ставиться поверх попереднього. На малюнку нижче намальована послідовність з п'яти стовпчиків.



На основі отриманої моделі Степан швидко придумав цікаву гру для одного гравця. За один хід гравцеві дозволяється або збільшити висоту будь-якого з існуючих стовпчиків послідовності на одиницю, додавши в стовпчик новий кубик, або зменшити висоту стовпчика, що містить більш, ніж один кубик, прибравши з нього один кубик. Гра продовжується до тих пір, поки в послідовності стовпчиків не виявиться M однакових по висоті стовпчиків, що стоять підряд. Вважатимемо, що кількість кубиків в дарованому наборі Степану велика і не може статися так, що для здійснення ходу не виявиться необхідного кубика. Ваше завдання полягає в тому, щоб по заданій послідовності кубиків і заданого числа M визначити мінімальну кількість ходів, яку доведеться зробити гравцеві для успішного завершення гри. Для наведеного вище прикладу при M = 3 вистачає двох ходів – збільшити висоту другого стовпчика на одиницю і зменшити висоту третього на одиницю, тоді отримаємо, що стовпчики з номерами 2, 3 і 4 мають однакову висоту 4.

Формат вхідних даних

перший рядок вхідного файлу містить два цілих числа – N і M (1 ≤ M ≤ N ≤ 200000), де N – кількість стовпчиків у послідовності. Наступний рядок вхідного файлу містить N натуральних чисел Hi (1 ≤ Hi ≤ 109), розділених одиночними пробілами – висота відповідного стовпчика у послідовності.

Формат вихідних даних

у першому рядку вихідного файлу має знаходитись одне ціле число – мінімальна кількість ходів, які необхідно зробити гравцю, щоб отримати із заданої послідовності стовпчиків другу послідовність із M стовпчиків однакової висоти, що стоять поруч.

Примеры


Входные данные в файле cubes.in

Результат работы в файле cubes.out

5 3

2 3 5 4 1



2



7 4

3 19 3 15 8 14 5



16



b

Схожі:

A – Казка про поросят iconВасиль симоненко казка про дурила

A – Казка про поросят iconКінофільми 5клас О. С. Пушкін «Казка про рибака І рибку»
А. Конан Дойль «Собака Баскервілів» О. Грін «Пурпурові вітрила» О. Шолохов «Доля людини»
A – Казка про поросят iconКазка про день, якого не було
Хлопчик не знав, що маленьким дітям не слід прокидатися так рано. Бо чим раніше прокинешся, тим більше встигнеш побачити, тим більше...
A – Казка про поросят iconПоложення про Міжнародний конкурс учнівських та студентських ілюстрацій до казки “Усі ми будемо королевами, або Казка про Маринку І Мишенятко”
Конкурс спрямовано на підтримку розвитку творчої уяви та художньої майстерності дітей-школярів І студентської молоді, а також популяризацію...
A – Казка про поросят iconВартість путівок в оздоровчий табір «лісова казка»

A – Казка про поросят iconКазка як засіб формування морального здоров’я орлова Олександра
move to 0-17796277
A – Казка про поросят iconРезюме власних досягнень, Анастасія Темборська. Театральна студія крокодил: Новорічна казка «Буратіно»
Студент польського університету wsb national Luis University, Nowy Sącz, представник кроку – 2011
A – Казка про поросят iconКазка як засіб формування морального здоров’я орлова Олександра
Казкові переживання залишають глибокий слід у свідомості дитини, сприяють розвитку добрих почуттів. У казці розкривається духовний...
A – Казка про поросят iconУкраїнська народна казка як засіб морального виховання дітей старшого дошкільного віку
Головна мета виховання, визначена в концепції національного виховання, полягає у передачі молодому поколінню багатств духовної культури...
A – Казка про поросят iconКазка як засіб розвитку творчості дітей у спадщині в. О. Сухомлинського магістрантка Інституту розвитку дитини Камонгар Марія
Тобто її головний герой схожий на дитину, він переживає ті ж проблеми І емоції. Він бореться, наприклад, з темрявою, й за його вчинками...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи