» Задачи по информатике\программированию

В этой теме пишите интересные задачи по информатике как можно сложнее
Задача должна выглядеть как:
1.Текст задачи
2.Описание входных данных
3.описание выходных данных
4.Пример( входные и выходные данные)

Также можно предложить тестовые наборы данных и свои варианты решений

Прошу не предлагайте классические задачи!

VladislavTim
acm.timus.ru
acm.sgu.ru

raven
и что?

VladislavTim

Цитата:

и что?

Там как раз и собраны "интересные задачи по информатике как можно сложнее " в приведенном тобой формате. Решать не перерешать. По объему базы нам их не переплюнуть, поэтому не вижу смысла постить задачи сюда.
Тут разве что можно обсуждать как решать ту или иную задачу.

вот ещё вспомнил..
если дружишь с англ:
acm.uva.es

Вокруг считающего стоят N человек,один из которых назван первым, а остальные занумированы против часовой стрелки числами от 2 до N. Считающий ведёт счёт до K, начиная с первого. Счёт продолжается со следующего человека (при этом выбывшие из круга не считаются), и так до тех пор, пока останется один человек. Требуется определить начальный номер этого человека.

Если есчё надо могу накидать много задачь =) Так что напрягаем мозги =)

VladislavTim

mmiichae по любому прав, не имеет смысла постить problems сюда, хотя есть предложение изменить данную тему в целях обсуждения алгоритмов решения некоторых мало известных задач.

Лично я сейчас зависаю на acm.uva.es, можно обсуждать задачи оттуда

Предложу еще несколько известных мне contest-ов:

acm.timus.ru
acm.sgu.ru
spoj.sphere.pl
ace.delos.com/ioigate
www.olymp.vinnica.ua

Да кстати киньте пожалуйста ссылку на задачу на динамическое программирование

Цитата:

задачу на динамическое программирование

а что под этим нужно понимать?

xcm
Под этим нужно понимать задачу на динамическое программирование Это метод решения определённого класса задач (оптимального управления например так называемая "задача коммивояжера" или "транспортная задача") см. http://www.pereplet.ru/obrazovanie/stsoros/501.html
http://program.rin.ru/razdel/html/974.html

VladislavTim
Да придумайте сами и не парьтесь возьмите типичную задачу коммивояжера и поменяйте часть слов.

FuzzyLogic
Коммивояжёр это классика программирования,
перебор вершин, рекурсивный алгоритм. круто!
а есть другие?

VladislavTim
На самом деле, твоя рекурсия загнется на приличных ограничениях, как по времени , так и по памяти (хотя такое встречается реже). Другое дело написать тут эвристику, но она не всегда дает правильный ответ.

Кстати на acm.uva.es завтра будет контест, так что приглашаю всех желающих поучавствовать, потом можно будет тут обговорить задачи.

Цитата:

а есть другие?

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

MOFA
Да ну его контест я уже вышел из возраста программирования для искусства

FuzzyLogic
Не для исскуства, а для навыка. Это очень хорошо тренерует мозги. Иногда за ограниченое время такое напишеш, что за месяц написать не мог. Катализатор идей одним словом, точнее двумя .

MOFA
Ты прав

А есть люди тут, которые на ACM ездили ?

Цитата:

А есть люди тут, которые на ACM ездили ?

на финал?
на региональных был, на финале нет

MOFA
пожалуй, но только до определённой степени, да и практическая польза довольно ограничена. Хотя если есть свободное время, то почему бы и нет...

Да действительно, пркатическая полльза я бы сказал заключается в заворачивании мозгов в нужную сторону

Кто там порешать хотел ?


Цитата:

Building blocks (p11)

Introduction

The Babylonians had n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions. A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height. They wanted to construct the tallest tower possible by stacking blocks. The problem was that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the base dimensions of the lower block. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked on top of each other.

Problem

Your job is to write a program that determines the height of the tallest tower the babylonians could build with a given set of blocks.

Input

The input will consist of several test cases. The first line of each case will be n, which is the number of types of each block. It will then be followed by n lines, which will give the dimensions of the blocks of each type. The input will be terminated by a value of 0 for n.

Output

For each case, you have to output the maximum height of the tower that could be built by using the given blocks.

Sample Input

4
2 3 4
7 3 1
4 2 6
1 3 9
2
5 7 3
2 8 5
0


Sample Output

11
8

может есть идеи? Очень надо.

MOFA
Это откуда?

VladislavTim
Это с одного Индийского сервера, они каждый год контест устраивают, но как я понял учавствовать там не стоит. Там все ужасно устроено, ответ на Submit задачи не приходит, Board только на первых 100 команд. Тоесть пока в первую сотню не попадеш, результата своего не увтдиш.

MOFA эту задачу, пусть вам VladislavTim решает, он очень любит задачи на динамическое программирование

FuzzyLogic
Не вопрос

Помогите решить задачу:
Даны два текстовых файла нужно слить их в один с условием:строчки должны идти через одну....нужен алгоритм решение этого

А в чём сложность?
Припустим, что файлы одинакового размера (в смысле кол-ва строк)
Открываем эти два файла на чтение, а третий на запись.
Теперь цикл
Читаем строку с первого файла, пишем в третий.
Читаем строку с второго файла, пишем в третий.
И так до конца

Есть вот такое задание на Pascal:

Код:
Значение переменной С, вычисленное в программе, написанной на языкеPascal,

var K,C:integer;
begin
C:=0;
forK:=l to 1000 do
if (K mod 30 <> 0) and (K mod 70 <> 0) and (K mod 42 = 0) then C:=C+1;
writeln('C=',C)
end.
равно___.

Kostya1991
какая-то лажа написана у тебя. если исправить
Код: var K,C:integer;
begin
C:=0;
for K:=1 to 1000 do
if (K mod 30 = 0) and (K mod 70 = 0) and (K mod 42 = 0) then C:=C+1;
writeln('C=',C)
end.

Там ответ 19.
Вот сфоткал задание:
http://up.li.ru/image/?id=271324
Там знак не =, а <>.
Ой, только сейчас сам заметил, неправильно написал. Сейчас поправлю.

P.S. Только всё равно не считается у меня...

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


Цитата:

Требуется вычислить расход фонда зарплаты по цеху , код которого вводится по запросу. Структуру записей файла дана п.П.13. Записи файла упорядочены по:
П13 реквизитам : 2,1 и 5
П13.1 Потребность в зарплате ОПЛ
П13.2 Имя: ZARPLATA

Структура записей базы данных:
№ п/п Поле записи Имя данного Тип Длина (вид)

Помогите с алгоритмом.

Есть заготовки веревок по метру.
Есть входные данные: кол. и размер необходимых отрезков, тоесть массив чисел 1...N

Необходимо найти варианты оптимальной разрезки веровок на заданные отрезки. т.е. потратив наименьшее колличество веревок.

например, необходимо иметь куски

- 10 штук по 10 см
- 10 штук по 60
- 10 штук по 30

результат должен быть: 10 штук по 60+30+10