Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Van111
кодер с++
208 / 187 / 4
Регистрация: 03.08.2011
Сообщений: 2,587
Записей в блоге: 12
#1

прошедшая олимпиада 14-16.12.13 - C++

17.11.2013, 19:19. Просмотров 410. Ответов 2
Метки нет (Все метки)

Добрый день, недавно я участвовал на олимпиаде вот на этом сайте http://contest.ncstu.ru.
Первый тур я более менее прошёл, а вот со вторым беда. Кто знает решение этих задач?

5. Непреступная крепость
Кликните здесь для просмотра всего текста

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды
Ограничение по памяти 64 МБ
Однажды Вася прочитал в древней книге легенду о том, как один мудрец руководил обороной города. Для защиты города вокруг него были выкопаны глубокие рвы, сделаны высокие земляные насыпи, а на насыпях из заостренных и обожженных бревен были сделаны стены. Как гласила легенда, стена та сооружалась по определенной схеме, делающей это укрепление непреступным. А секрет заключался в том, что для каждой пары бревен одинаковой длины выполнялось условие, что между ними есть хотя бы одно более длинное бревно. Так же в легенде рассказывалось, что при строительстве использовались бревна длины 1, 2, …, N и было их очень много. Васе стало интересно узнать, какое максимальное количество бревен можно использовать при сооружении неприступной стены по описанной схеме. Напишите программу, которая будет вычислять это количество.
Формат входных данных:
Во входном файле задано целое число N (1 ≤ N ≤ 30) — количество различных видов бревен.
Формат выходных данных:
В выходной файл выведите, какое максиальное количество бревен может быть использовано.
Пример
input.txt output.txt
1 1
2 3
3 7

6. Сканворд
Кликните здесь для просмотра всего текста

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды
Ограничение по памяти 64 МБ
Вася все свое свободное время тратит на решение сканвордов. Сканводр представляет собой прямоугольную таблицу, в пустые клетки которой нужно вписывать слова по горизонтали и по вертикали. В сканводре каждое слово начинается сразу от непустой клеткой или от границы таблицы. Заканчиваются слова соответственно на границе таблицы или перед непустой клеткой. Никакие два слова не следуют друг за другом подряд и не накладываются. Слова могут пересекаться друг с другом только в том случае, если одно слово идет по горизонтали, а второе по вертикали. В сканворде не используются слова длиной меньше двух букв. Для каждого слова в непустые клетки или за границей сканворда записываются вопросы-подсказки, помогающие отгадать слово. Таким образом, любая несвободная клетка может содержать либо вопросы-подсказки, либо рекламу, а во все пустые клетки должны вписываться буквы слов-ответов.
Порешав сотни сканвордов, Вася решил создать свой собственный. Для начала он хочет составить прямоугольную таблицу размером N×M, а затем вписать туда свои слова. При составлении таблицы он случайным образом закрасил часть клеток и решил, что в них будут размещаться вопросы-подсказки. Но тут до него дошло, что при случайном формировании таблицы у него может не получиться правильный сканворд. Так как переделывать всю работу долго, он решил закрасить еще несколько клеток и получить правильный сканворд. Помогите Васе подсчитать, какое минимальное количество клеток придется закрасить.
Формат входных данных:
В первой строке входного файла заданы два целых числа N и M (3 ≤ N, M ≤ 1000). В последующих N строках записано по M символов, причем, символ "." обозначает клетку, в которую будут вписываться буквы, а символ "#" обозначает клетку, в которой будет размещаться вопрос-подсказки или реклама.
Формат выходных данных:
В выходной файл выведите, какое количество клеток нужно закрасить
Пример
input.txt output.txt
3 4
....
....
.... 0
4 3
###
#.#
###
#.# 2

7. Казнь
Кликните здесь для просмотра всего текста

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды
Ограничение по памяти 64 МБ
Не успел Вася отойти от одной легенды, как попалась ему книга о другой. В ней речь шла о великом полководце и его мудром советнике.
Однажды дальняя провинция подняла мятеж, и этот полководец был отправлен туда для подавления восстания. После сокрушительного разгрома он решил наказать мятежников. Для этого он приказал построить их всех в ряд, пронумеровать каждого по порядку и казнить каждого S-го начиная с F-го. Всего должно было быть казнено C человек.
Советник решил, что это наказание слишком суровое, и попытался уговорить полководца отменить свой приказ. На это полководец ответил: "Ладно, так и быть, я пощажу некоторых мятежников, но для этого тебе нужно придумать последовательность равноотстоящих целочисленных номеров, чтобы шли они с шагом больше чем 1 и чтобы шаг не равнялся S. Тогда каждого приговоренного человека, чей номер будет в твоей последовательности, я помилую." Думал советник всю ночь до рассвета, как спасти как можно больше людей, и придумал. Подсчитайте, сколько людей он смог спасти.
Формат входных данных:
В первой строке входного файла заданы три целых числа F, C и S (0 ≤ F ≤ 109, 1 ≤ C ≤ 109, 2 ≤ S ≤ 109) — номер первого человека, количество людей и шаг.
Формат выходных данных:
В выходной файл выведите, какое количество людей он смог спасти.
Пример
input.txt output.txt
1 4 2 2
3 2 4 2

8. Переименование файлов
Кликните здесь для просмотра всего текста
Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды
Ограничение по памяти 64 МБ
Уже не первый год Вася разрабатывает свой собственный файловый менеджер FullCommander. Сегодня он решил добавить новую функциональность — групповое переименование файлов. Пользователь выбирает все файлы в текущей директории и некоторым образом задает новые имена для них. После этого программа самостоятельно переименовывает эти файлы. За один раз эта программа должна выбрать какой-то файл и переименовать его. В любой момент времени в папке не может содержаться два файла с одинаковым именем, даже если буквы в именах файлов разного регистра (это не позволяет делать его операционная система).
Вася долго мучился и все-таки написал эту программу. Причем она была написана наиболее оптимальным образом так, чтобы операций переименования было как можно меньше. В процессе работы программа выводит на экран, сколько переименовано файлов на текущий момент. Но тут Вася понял, что это не информативно, и решил выводить информацию о процессе переименования в процентах. Но для этого ему нужно знать общее количество переименований, которое потребуется программе. Вася уже слишком устал и не в силах написать еще одну программу. Помогите Васе подсчитать наименьшее количество переименований, которое потребуется выполнить программе.
Формат входных данных:
В первой строке входного файла задано натуральное число N, не превосходящее 100 000 — количество файлов в текущей директории. В каждой из последующих N строк через пробел записаны исходное и конечное имя файла.
Имя файла представляет собой строку, состоящую из строчных букв английского алфавита и одной точки, отделяющей имя файла от его расширения. Строка, предшествующая точке, не пуста и имеет длину не более 8 символов, а строка после точки также не пуста и имеет длину не более 3 символов. Гарантируется, что входные данные корректны и решение существует.
Формат выходных данных:
В выходной файл выведите, какое наименьшее количество переименований потребуется выполнить программе.
Пример
input.txt output.txt
2
task1.cpp task3.cpp
task2.pas task4.pas 2
2
solution.pas solution.dpr
solution.dpr solution.pas 3


 Комментарий модератора 
5.16 Запрещено создавать темы с множеством вопросов во всех разделах, кроме разделов платных услуг. Один вопрос - одна тема.
Правила форума


Добавлено через 6 часов 49 минут
для первой задачи ответом является 2^N -1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2013, 19:19     прошедшая олимпиада 14-16.12.13
Посмотрите здесь:

C++ Международная Жаутыковская Олимпиада - 2009
C++ Школьная олимпиада по информатике
C++ Олимпиада 1999г.
C++ Вывести код программы!!!(Олимпиада)
Олимпиада C++
муниципальная олимпиада. Странный output C++
Международная олимпиада по программированию 1994г. Задач "Матрица простых чисел". C++
Олимпиада по программированию C++
C++ Школьная олимпиада
C++ Школьная олимпиада. Задача с кубиками (самая сложная из всех задач)
Олимпиада по информатике C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор FAQ
17.11.2013, 19:42     прошедшая олимпиада 14-16.12.13 #2
Цитата Сообщение от Van111 Посмотреть сообщение
Первый тур я более менее прошёл, а вот со вторым беда. Кто знает решение этих задач?
Van111, мой тебе совет, если хочешь чего-то достичь то при решении олимпиад вообще никого не спрашивай помощи. Для меня выигрыш олимпиады не своими знаниями или с чьей-то помощью был бы хуже провала.

Не по теме:

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

Van111
кодер с++
208 / 187 / 4
Регистрация: 03.08.2011
Сообщений: 2,587
Записей в блоге: 12
18.11.2013, 17:40  [ТС]     прошедшая олимпиада 14-16.12.13 #3
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Для меня выигрыш олимпиады не своими знаниями или с чьей-то помощью был бы хуже провала.
Она уже прошла, я с датой ошибся

Добавлено через 12 минут
решением второй задачи является подсчёт точек ,которых не окружает ни одна точка, ни по горизонтали ,ни вертикали
Yandex
Объявления
18.11.2013, 17:40     прошедшая олимпиада 14-16.12.13
Ответ Создать тему
Опции темы

Текущее время: 00:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru