Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Клуб программистов > Свободное общение
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 04.06.2013, 16:50   #1
koljsch
Форумчанин
 
Регистрация: 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.
koljsch вне форума Ответить с цитированием
Старый 04.06.2013, 17:39   #2
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Первая неинтересна, чистая техника (прочитать ввод, посчитать цифры, посчитать остаток). Главная засада - большие числа, если их надо учитывать.

Вторая задача.
Цитата:
Например: в выражении -(-1)+2*3*4 минусы и скобки необходимы, чтобы выполнить первое и четвёртое условие (содержание всех знаков +,-,* и скобки перед отрицательными числами), но недопустимо выражение вида: 1+2*3*(-(-4)), где скобки и отрицания избыточны.
Не понял этого условия. Прочитал ещё раз - всё равно не понял.
В остальном: либо в списке чисел есть ноль, либо нет нуля. Если ноль есть, то выражение - сумма произведений, разделённых нулями. Далее, в произведении смотрим на самую длинную подпоследовательность единиц и ращепляем её, если это увеличит результат. Далее, если получилось одно произведение, проверяем варианты отщепления множителя, не ограничиваясь крайними.

Третья задача неприятная. Нужен строгий максимум - значит, нужно правило отсечения (или полный перебор, O(N * C_M^N)). То, что числа могут быть отрицательными, при этом жутко неудобно.
Видимо, нужно выбирать пары столбцов (левый-правый), снижая размерность оставшейся задачи. На этапе выбора пары можно пытаться отслеживать явные мажоранты, но из-за отрицательных значений это в большинстве случаев будет невозможно.

Четвёртое задание.
Непонятно, что решать.
Код:
details N K M = if(N < K) 
  then 0
  else (+ (* (/ N K) (/ K M)) (details (+ (% N K) (* (/ N K) (% K M))) K M))
Abstraction вне форума Ответить с цитированием
Старый 04.06.2013, 17:46   #3
koljsch
Форумчанин
 
Регистрация: 26.01.2009
Сообщений: 360
По умолчанию

Цитата:
Не понял этого условия. Прочитал ещё раз - всё равно не понял.
Имеется в виду, что нельзя ставить большое кол-во минусов или же скобок, но при этом в конечном выражение должны присутствовать хотя бы один знак минус, плюс, умножить, а также скобки.
koljsch вне форума Ответить с цитированием
Старый 04.06.2013, 18:06   #4
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Цитата:
Имеется в виду, что нельзя ставить большое кол-во минусов или же скобок, но при этом в конечном выражение должны присутствовать хотя бы один знак минус, плюс, умножить, а также скобки.
"Большое" - это сколько? Кто сказал про то, что нужны скобки? Количество минусов и скобок одинаково в примере "можно" и в примере "нельзя".
Abstraction вне форума Ответить с цитированием
Старый 04.06.2013, 18:11   #5
koljsch
Форумчанин
 
Регистрация: 26.01.2009
Сообщений: 360
По умолчанию

Подправил немного ввод и вывод для второй задачи.
Большое это более одного. К примеру, есть число -1, логично поставить перед ним -, чтобы получилось большее число, а соответственно и результат больший. Теперь есть число 1, нужно обязательно ставить знак минус, ставим, получаем -1, и чтобы получить большее число можно было бы поставить еще один минус, но правилами запрещено. А от расстановки минусов соответственно становится больше скобок, т.к. они ставятся(или не ставятся) перед отрицательными элементами. А скобки обязательно только смотря от условий, т.е. от цифр.
koljsch вне форума Ответить с цитированием
Старый 04.06.2013, 18:34   #6
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Огроменное спасибо за задания..

№1
Код:
procedure InitStr (var a, b : string);
begin
	ReadLn (a);
	ReadLn (b)
end;


procedure CorrectStr (var a, b : string);

procedure Swap (var a, b : string);
var
	t : string;
begin
	t := a;	a := b;	b := t
end;


begin
	if a[1] <> 'A' then
		Swap (a, b)
end;

procedure GetNumber (const s : string; var n : Integer);
var
	err : Integer;
	
begin
	Val (Copy (s, 3, Length(s)), n, err)
end;


function ConvertRadix (n : LongInt; r : Byte) : string;

var
	s : string;
	c : Integer;
begin
	s := '';
	repeat
		c := n mod r;
		s := Chr (c + 48) + s;
		n := n div r
	until n = 0;

	ConvertRadix := s
end;

procedure SumOfDigits (const s : string; var sum : Integer);
var
	i : Integer;
		
begin
	sum := 0;
	for i := 1 to Length(s) do 
		sum := Ord (s[i]) - 48 + sum
end;
		
		
procedure PrintResult (const n, k : Integer; const s : string);
begin
	WriteLn (s);
	if n mod k = 0 then
		Write ('is ')
	else
		Write ('not ');
	WriteLn ('integer')
end;

var
		a, b, s : string;
		n, base, k : Integer;

begin
	InitStr (a, b);
	CorrectStr (a, b);
	
	GetNumber (a, n);
	GetNumber (b, base);
	s := ConvertRadix (n, base);
	SumOfDigits (s, k);
	
	PrintResult (n, k, s)
end.
Но ИМХО для олимпиад такого уровня нужно четко прописывать ограничения!
Poma][a вне форума Ответить с цитированием
Старый 04.06.2013, 18:38   #7
koljsch
Форумчанин
 
Регистрация: 26.01.2009
Сообщений: 360
По умолчанию

Цитата:
Но ИМХО для олимпиад такого уровня нужно четко прописывать ограничения!
Я с этим согласен, но если бы Вы только знали как эта олимпиада проходила... После того, что я испытал на ней, то веры в образование и учителей не осталось.
koljsch вне форума Ответить с цитированием
Старый 04.06.2013, 18:42   #8
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
После того, что я испытал на ней, то веры в образование и учителей не осталось.
Можно с этого момента по подробнее? Не ужели там были люди, приехавшие на джипах с охраной, всю олимпиаду плюющие в потолок, которые, оказалось, заняли все призовые места?
Poma][a вне форума Ответить с цитированием
Старый 04.06.2013, 19:05   #9
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Цитата:
К примеру, есть число -1, логично поставить перед ним -, чтобы получилось большее число, а соответственно и результат больший. Теперь есть число 1, нужно обязательно ставить знак минус, ставим, получаем -1, и чтобы получить большее число можно было бы поставить еще один минус, но правилами запрещено.
Только в образце именно это и проделано: на входе (1,2,3,4) - на выходе -(-1)+2*3*4.
Abstraction вне форума Ответить с цитированием
Старый 04.06.2013, 19:07   #10
koljsch
Форумчанин
 
Регистрация: 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.
koljsch вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Олимпиады по программированию. 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