|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
04.06.2013, 16:50 | #1 |
Форумчанин
Регистрация: 26.01.2009
Сообщений: 360
|
Задачи со Всероссийской олимпиады по программированию
Решил выложить задачи, которые были в этом году на Всероссийской олимпиаде по программированию. Может кто-то захочет решить их, по обсуждать и т.д.
Задача №1 Даны два натуральных числа А и B (1 < B < 10). Перевести число A из десятичной системы счисления в систему счисления с основанием B. Определить является ли частное числа A и суммы цифр числа AB целым числом. На вход программе подаются две строки вида: <буква>=<число>. Где: <буква> - A или B. <число> - натуральное число. Программа должна вывести две строки. Первая строка: число A в системе счисления с основанием B. Вторая строка: "is integer", если частное числа A и суммы цифр числа AB - целое число, или "not integer", если не целое (выводить без кавычек). Пример Входные данные A=7 B=2 Вывод программы 111 not integer Входные данные А=21 В=8 Вывод программы 25 is integer Задача №2 Даны N целых чисел. Необходимо расставить знаки арифметических операций (+, -, *) таким образом, чтобы значение выражения было максимальным. 1. Выражение обязательно должно содержать хотя бы один знак плюс, минус и умножить. 2. Числа нельзя менять местами. 3. Если при формировании выражения знак плюс оказался в начале, его символ нужно убрать. Например: + 1 * 2 - 3 должно стать 1*2-3. 4. Если перед отрицательным числом находится знак арифметической операции, это число нужно взять в скобки. Например: 1 + 2 - - 3 * 4 должно стать 1+2-(-3)*4. 5. Должно быть использованно минимально необходимое количество арифметических операций и скобок. Например: в выражении -(-1)+2*3*4 минусы и скобки необходимы, чтобы выполнить первое и четвёртое условие (содержание всех знаков +,-,* и скобки перед отрицательными числами), но недопустимо выражение вида: 1+2*3*(-(-4)), где скобки и отрицания избыточны. На вход программы построчно поступают N целых чисел. Программа должна вывести две строки. Первая строка: вырожение со знаками Вторая строка: число - результат вычисления полученного выражения. Пример Входные данные -4 7 -8 5 -9 Вывод программы -(-4)+7*(-8)*5*(-9) 2524 Входные данные 5 -8 2 8 -9 -4 Вывод программы 5*(-8)*2*8*(-9)-(-4) 5764 Входные данные 1 2 3 4 Вывод программы -(-1)+2*3*4 25 Задача №3 Дана прямоугольная матрица NxM (N<M). Необходимо удалить из неё столбцы таким образом, чтобы получилась квадратная матрица NxN и разность произведений элементов главной и побочной диагоналей полученной матрицы была максимальной. Пример: Матрица, полученная после удаления столбцов: A1 A2 A3 B1 B2 B3 C1 C2 C3 Разность произведений элементов главной и побочной диагоналей вычисляется по формуле: A1*B2*C3 - A3*B2*C1 Столбцы можно менять местами, строки нельзя. Входные данные: матрица NxM (N<M). Вывод программы: матрица NxN. Пример Входные данные 3 6 3 1 6 8 4 5 2 3 7 2 8 1 0 5 5 0 Вывод программы 8 6 3 2 7 4 0 5 8 Входные данные 3 7 3 7 2 5 8 2 6 3 0 5 1 0 7 4 1 0 5 2 Вывод программы 7 7 2 3 6 8 3 5 0 5 7 0 5 1 2 4 Задача №4 Имеется N кг металлического сплава. Из него изготавливают заготовки массой K кг каждая. После этого из каждой заготовки вытачиваются детали массой M кг каждая (из каждой заготовки вытачивают максимально возможное количество деталей). Если от заготовок после этого что-то остается, то этот материал возвращают к началу производственного цикла и сплавляют с тем, что осталось при изготовлении заготовок. Если того сплава, который получился, достаточно для изготовления хотя бы одной заготовки, то из него снова изготавливают заготовки, из них – детали и т.д. Напишите программу, которая вычислит, какое количество деталей может быть получено по этой технологии из имеющихся исходно N кг сплава. Входые данные: Вводятся N, K, M. Все числа натуральные и не превосходят 200. Вывод: Выведите одно число — количество деталей, которое может получиться по такой технологии. Пример Входные данные 10 5 2 Вывод программы 4 Входные данные 13 5 3 Вывод программы 3 Последний раз редактировалось koljsch; 04.06.2013 в 18:07. |
04.06.2013, 17:39 | #2 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Первая неинтересна, чистая техника (прочитать ввод, посчитать цифры, посчитать остаток). Главная засада - большие числа, если их надо учитывать.
Вторая задача. Цитата:
В остальном: либо в списке чисел есть ноль, либо нет нуля. Если ноль есть, то выражение - сумма произведений, разделённых нулями. Далее, в произведении смотрим на самую длинную подпоследовательность единиц и ращепляем её, если это увеличит результат. Далее, если получилось одно произведение, проверяем варианты отщепления множителя, не ограничиваясь крайними. Третья задача неприятная. Нужен строгий максимум - значит, нужно правило отсечения (или полный перебор, O(N * C_M^N)). То, что числа могут быть отрицательными, при этом жутко неудобно. Видимо, нужно выбирать пары столбцов (левый-правый), снижая размерность оставшейся задачи. На этапе выбора пары можно пытаться отслеживать явные мажоранты, но из-за отрицательных значений это в большинстве случаев будет невозможно. Четвёртое задание. Непонятно, что решать. Код:
|
|
04.06.2013, 17:46 | #3 | |
Форумчанин
Регистрация: 26.01.2009
Сообщений: 360
|
Цитата:
|
|
04.06.2013, 18:06 | #4 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
|
|
04.06.2013, 18:11 | #5 |
Форумчанин
Регистрация: 26.01.2009
Сообщений: 360
|
Подправил немного ввод и вывод для второй задачи.
Большое это более одного. К примеру, есть число -1, логично поставить перед ним -, чтобы получилось большее число, а соответственно и результат больший. Теперь есть число 1, нужно обязательно ставить знак минус, ставим, получаем -1, и чтобы получить большее число можно было бы поставить еще один минус, но правилами запрещено. А от расстановки минусов соответственно становится больше скобок, т.к. они ставятся(или не ставятся) перед отрицательными элементами. А скобки обязательно только смотря от условий, т.е. от цифр. |
04.06.2013, 18:34 | #6 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Огроменное спасибо за задания..
№1 Код:
|
04.06.2013, 18:38 | #7 | |
Форумчанин
Регистрация: 26.01.2009
Сообщений: 360
|
Цитата:
|
|
04.06.2013, 18:42 | #8 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
|
|
04.06.2013, 19:05 | #9 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
|
|
04.06.2013, 19:07 | #10 | |
Форумчанин
Регистрация: 26.01.2009
Сообщений: 360
|
Цитата:
Первый день - тестирование. Прошло вполне хорошо, было два конверта с тестами, вскрывали их при всей аудитории, т.е. подвоха никакого не должно было быть. После тестирования узнаю, что пару вопросов, которые у меня были не верными(хоть в их правильности я был уверен) оказались неверно веденными в тестирующую программу, а баллы начислять никто не соглашался за их же ошибку. Ну потеря пары баллов ерунда, забыли. Второй день - само программирование именно этих задач. Задачи придумали за день до самого этого дня, как сказала женщина из жюри, что она придумывала их за ночь дома. Программировать заставили на собственной сборке Linux, в браузере(!!!). Смысл был каков - выбираем язык программирования, я делал на C++, компилятор GCC 4.2, далее нам показывается задание, мы выбираем какое делать и при запуске программы она отправляется на сервер, там выполняется, на стандартный ввод/вывод(STDIN) подаются тесты(входные данные) и проверяется вывод программы, если все хорошо, то засчитывается. Дело в том, что нам говорили, что текст программы сохраняется на сервере каждые три минуты. Был очень интересный баг, при нажатие CTRL+Z код программы мог удалиться, что и произошло после удачного написания программы у меня и еще у одного парня, позвали помощника, чтобы восстановить программу, а нам в ответ "Данная функция сохранения текста программы на сервере сейчас не работает". Зашибись конечно... Обидно после этого было, успел сделать только 3 задачи. Баллы начисляли тоже очень интересно, чем больше людей сделало задачу, тем меньше баллов за нее получали. Вот таким образом за первую и четвертую задачи люди получали всего по 10 баллов из 100 возможных, хоть я при 3 получил всего 35 вроде. В этот же день проходила консультация насчет 3-го дня. Сначала нам женщина из жюри говорит:"Интернета не будет, обязательно будем оценивать дизайн", приходит их парень и сообщает нам при ней же:"Ее не слушайте, она ничего не знает. Интернет будет, можно будет фреймворки скачать и дизайн оцениваться не будет, т.к. Вы не дизайнеры.". Нужно было сделать БД и сайт на PHP, ну и связать их соответственно. Очень большое кол-во людей понадеялись на наличие интернета, т.к. большинство и в глаза не видели PHP и что это вообще такое. Третий день - создание сайта и БД. Мы приходим, нам объявляют о том, что интернета все-таки не будет, а дизайн оцениваться будет. Только вот откуда брать этот самый дизайн? Не было даже простейшего графического редактора, а запросили чтобы изображения были. Поставили нам Apache, MySQL в качестве СУБД и PHPMyAdmin. Я потерял в тот день один час, т.к. нам не дали доступ к подключению к MySQL, соответственно никто это время не прибавил, пока я ждал. Давались нам 5 запросов, следуя из них нужно было сделать несколько таблиц, связать их и провести нормализацию, заполнить своими данными. На сайте выполняли эти самые запросы. Также нужно было сделать заполнение БД с сайта, а также поиск по таблицам и вывод этого на PHP, сделал только поиск. Т.к. дизайн нужен был, то сделал все достаточно просто, изображения взял с PHPMyAdmin, а остальное обычное форматирование текста на HTML(цвет фона, текста, рамка и т.д.). В итоге первое место занял парень из Уфы, с ним к сожалению я не общался. Второе место получил Ростов, кстати они олимпиаду и проводили, до третьего дня этот парень шел на первом месте, и проиграл всего 3 балла, его я увидел только на закрытие, т.е. до этого и в глаза не видел. Третье место уже не помню точно. Я вошел в десятку, хоть это радует. Но был очень разочарован, полнейший бардак был, задания вводили за 5 мин. до начала олимпиады, говорили одно - делали другое. Еще очень интересный момент, женщина из жюри постоянно говорила, что если что-то будет, то спрашивать у нее, а ответы ее на все вопросы были таковы:"Ну ты же не тупой! Делай/думай сам". Также нельзя было использовать файлы, при создание вечного цикла компьютеры переставали отвечать совершенно все, т.е. у кого-то он появился и ты сидишь, ждешь пока сделают. Вообщем надеюсь на следующий год, может будет по другому, хотя бы работать в своей любимой среде и уметь контролировать ввод/вывод. Последний раз редактировалось koljsch; 04.06.2013 в 19:12. |
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Олимпиады по программированию. | vovken1997 | Свободное общение | 11 | 18.10.2012 19:13 |
Финал олимпиады по программированию RussianCodeCup , Победителю $10 000 | kislenko | О форуме и сайтах клуба | 0 | 15.09.2011 14:37 |
Олимпиады по программированию 2011 !? | gefest58 | Свободное общение | 8 | 06.02.2011 08:26 |
шифровка с олимпиады по программированию | vvsh | Помощь студентам | 6 | 09.02.2010 17:44 |
Олимпиады, лекции ЛКШ (видео), задачи с решениями, книги и алгоритмы по программированию | Abzal | Свободное общение | 0 | 30.08.2009 12:35 |