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

Найти представление числа S в виде суммы слагаемых из множества - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ количество маршрутов, ведущих узника к выходу http://www.cyberforum.ru/cpp-beginners/thread50576.html
Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в...
C++ Оцените информационный объем предложения введенного текста человеком Считая, что каждый символ кодируется одним байтом, оцените информационный объем предложения введенного текста человеком http://www.cyberforum.ru/cpp-beginners/thread50574.html
C++ Как сделать заставку-картинку из файла
на языке С. Для создания игры нужно чтобы при запуске программы сначала появлялась заставка(картинка формата .bmp) Пробовала функцию fopen - что-то не получилось...(( учусь работать в Borlande
Не компилируется проект C++
Добрый день Странная проблема, которая появилась недавно : в студии проект создается, но не компилируется, ни при нажатии Ф7 и тд в папке проекта не создается папка debug c файлом .exe В чем причина, помогите разобраться
C++ Возвращение функциями указателей http://www.cyberforum.ru/cpp-beginners/thread50536.html
Читаю про указатели, тут для примера,предоставляется код. Программа ищет какую-то подстроку в строке. Кто нибудь может объяснить,каким образом ищется подстрока из этого кода,если не сложно. Заранее благодарю. #include <iostream> using namespace std; char *get_substr(char *sub, char * str); //char *get_substr возвращает указатель на char,что Это даёт? int main() {
C++ Проблема с фукнцией. Доброго времени. Проблема в след: Хочу чтобы в программе при неправильном ответе, через оператор if выводилась функция о неправильном ответе, но не получается ;(. Подскажите пожалуйста. #include <iostream> #include <conio.h> #include <windows.h> char bufRus; char* RusText(const char* text) // Русский текст в окне. { CharToOem(text, bufRus); подробнее

Показать сообщение отдельно
Rustam
 Аватар для Rustam
12 / 12 / 3
Регистрация: 05.09.2009
Сообщений: 438

Найти представление числа S в виде суммы слагаемых из множества - C++

12.09.2009, 14:51. Просмотров 2638. Ответов 5
Метки (Все метки)

1 Банкомат
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. Помогите Национальному банку решить эту задачу.
Формат входных данных

Первая строка входных данных содержит натуральное число n, 0<n<=100. Вторая строка входных данных содержит n различных натуральных чисел x1, x2, ..., xn, не превосходящих 1.000.000. Третья строчка содержит натуральное число S, не превосходящее 5.000.000.
Формат выходных данных

Программа должна найти представление числа S в виде суммы слагаемых из множества {xi}, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести слово impossible.
Пример

Входные данные
5
1 3 7 12 32
40

Выходные данные
1 7 32

Входные данные
5
10 50 100 500 1000
99

Выходные данные
шmpossible

2. Расписание
На конференции работников народного образования с докладами об очередном улучшении финансирования желает выступить несколько министров правительства. Но поскольку министры, как правило, очень заняты, то каждый из министров назначил время, когда он хочет выступить с докладом. Естественно, министры не смогли распределить время между собой, поэтому заявленные ими времена пересекаются. Перед вами стоит задача выбрать из всех поданных заявок несколько непересекающихся, при этом максимизировать число выбранных заявок.
Формат входных данных

Первая строка входных данных содержит целое число n, 0<n<=10000. Далее идет n строк, каждая из которых содержит два целых числа si и ti, 0<=si<ti<=30000. Каждая строка соответствует одной заявке с номером i (1<=i<=n), si является временем начала заявки, ti – временем ее окончания.

Программа должна найти подмножество множества {1, 2, ..., n}, содержащее наибольшее число элементов, такое, что для любых двух элементов i и j из найденного подмножества верно одно из двух неравенств: ti<=sj

или tj<=si. Указанные неравенства означают, что заявки с номерами i и j не пересекаются, то есть одна из них заканчивается не позднее, чем начинается другая. При этом время окончания одной удовлетворенной заявки может совпадать со временем начала другой заявки (один министр на трибуне меняется на другого министра).
Формат выходных данных

Программа должна вывести номера удовлетворенных заявок в произвольном порядке, разделяя их пробелами. Заявки нумеруются, начиная с 1.
Пример

Входные данные
3
1 3
2 4
3 5

Выходные данные
1 3

Входные данные
5
2 6
1 3
1 4
4 5
5 6

Выходные данные
2 4 5

3 Игра в 8
Всем хорошо известна "Игра в 15", представляющая собой 15 квадратных фишек, пронумерованных числами от 1 до 15. Фишки уложены в квадрат со стороной в 4 стороны фишки, одна позиция для фишки свободна. Если обозначить свободную позицию за *, то головоломка состоит в том, чтобы получить из произвольной начальной позиции позицию следующего вида:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 *

Единственной разрешенной операцией является обмен * с одной из соседних по ребру фишек. Операции будем кодировать буквами:
r
поменять * с фишкой, которая стоит справа от *
l
поменять * с фишкой, которая стоит слева от *
u
поменять * с фишкой, которая стоит сверху от *
d
поменять * с фишкой, которая стоит снизу от *

Например, решением головоломки
1 2 3 4
5 6 7 8
9 10 12 *
13 14 11 15

является последовательность ldr.

Не все возможные произвольные расположения фишек можно привести к требуемому виду, например, если в требуемой позиции поменять местами две фишки, то получить из такой позиции требуемую используя только описанные операции становится невозможно.

От вас требуется решить более простую головоломку "Игра в 8", в которой требуется расположить 8 фишек в виде:
1 2 3
4 5 6
7 8 *
Формат входных данных

На вход программе подается описание исходной позиции в виде строки, в которой перечислены номера фишек, разделенные пробелами в квадрате слева направо сверху вниз. Вместо свободной фишки напечатана *.

Например, позиция
1 2 3
* 4 6
7 5 8

задается строкой
1 2 3 * 4 6 7 5 8
Формат выходных данных

На выход программа должна вывести одну строку, состоящцю из букв l, r, u, d, содержащую последовательность операций, разрешающую данную головоломку, в которой одна буква соответствует перемещению одной фишки (см. выше правило кодирования операций). Если же головоломка неразрешима, то требуется вывести одно слово unsolvable.
Пример

Входные данные
2 3 4 1 5 * 7 6 8

Выходные данные
Ullddrurdllurdruldr

4 .Ферзя в угол
В левом нижнем углу доски M×N стоит ферзь. Двое игроков по очереди ходят ферзем, перемещая его на любое число клеток по вертикали вверх, по горизонтали вправо, или по диагонали вправо-вверх. Выигрывает тот, кто поставит ферзя в правый верхний угол доски. Определите, какой из игроков имеет выигрышную стратегию.
Входные данные

На вход программе подается два положительных числа M и N, не превосходящих 1000.
Выходные данные

Программа должна вывести номер игрока (1 или 2), который имеет выигрышную стратегию.
Пример входных данных
3 4
Пример выходных данных
1

5.Морской бой
На прямоугольном поле для игры в морской бой размером M×N

расположено несколько прямоугольных кораблей. Корабли не соприкасаются друг с другом. Ваша задача — определить всевозможные типы кораблей на поле и число кораблей каждого типа. Два корабля относятся к одному типу, если их размеры совпадают (корабли, которые могут быть получены друг из друга поворотом, также относятся к одному типу).
Входные данные

Первая строка входных данных содержит два положительных числа M и N, не превосходящих 1000, задающие размеры поля. Далее идет M строк, каждая из которых состоит из N символов. Символ `1' означает, что соответствующая клетка поля занята кораблем, символ `0' — что свободна. Пробелов в строке нет.
Выходные данные

Программа должна для каждого обнаруженного типа корабля вывести одну строку, содержащую три числа. Первые два числа задают размеры корабля (первое число должно быть не меньше второго), третье число задает количество кораблей данного типа на поле. Строки в выводе должны быть отсортированы по первому числу, затем по второму числу.
Пример входных данных
6 10
0111000011
0000011011
0100011000
0101011011
0100000000
0001111011
Пример выходных данных
1 1 1
2 1 2
2 2 2
3 1 2
3 2 1
4 1 1

6."Ну, погоди!" на катке
Заяц стоит в центре большого катка и поет свою любимую песенку в игрушечный микрофон. От микрофона тянется достаточно длинный шнур, конец которого находится в руках у Волка. Волк хочет незаметно замотать Зайца этим шнуром. Для этого он катается вокруг Зайца на коньках и постепенно его заматывает. Траектория Волка — ломаная линия. При перемещении Волка микрофонный шнур всегда натянут (как будто он эластичный).

Напишите программу, которая по заданной траектории Волка определяет на сколько полных оборотов Волк замотал Зайца. Учтите, что Волк во время движения может не только заматывать Зайца, но и разматывать, а также что заматывать Зайца можно в двух различных направлениях.

Заяц первоначально находится в точке (0,0), Волк — в точке (1,0). Координаты представляются вещественными числами. Гарантируется, что траектория Волка не проходит через начало координат (местоположение Зайца).
Формат входных данных

Первая строка входных данных содержит число N≤1000, задающее число звеньев в ломаной траектории Волка. Далее идет N строк, i-я строка содержит 2 действительных числа x_i и y_i, задающие координаты i+1-й вершины траектории.
Формат выходных данных

Программа должна вывести единственное число — количество полных оборотов.
Пример входных данных
3
-3 3
-1 -1
2 1
Пример выходных данных
1

7.Разминирование
Решил как-то Иванушка-дурачок навестить Змея Горыныча. Пришел он к замку, а перед воротами минное поле раскинулось. Причем поле не простое, а волшебное – мины расположены в узлах регулярной решетки. Однако, была у Иванушки лягушка-сапер, работающая по следующему алгоритму. Лягушка прыгает с мины на мину, разряжая ту, на которой сидит. Если она видит, что перед ней нет мины, или мина перед ней разряжена, она поворачивается на 90 градусов вправо. Если вокруг лягушки не остается заряженных мин, то она останавливается. Перед тем как запускать свою лягушку, решил Иванушка определить где она остановится. Для этого он ввел систему координат, причем ось x оказалась направлена вправо, а ось y – вверх. Потом он обнаружил, что мины оказались расположены в точках с координатами (i, j), причем 1<i<N;1<=i<=N, 1<j<M;1<=j<=M, а лягушка изначально находится в точке (1,1) и смотрит по оси y. Требуется определить координаты точки, в которой остановится лягушка.
Входные данные

Программа получает на вход два натуральных числа N и M, не превосходящие 106.
Выходные данные

Программа должна вывести два натуральных числа – координаты точки, где остановится лягушка.
Пример входных данных
3 4
Пример выходных данных
2 3

8.Странная математика
В связи с реформой образования в тридесятом царстве был введен новый предмет, на котором изучаются различные альтернативные науки. Одной из таких наук является странная математика. Ее основное отличие от обычной математики в том, что числа в ней упорядочены не по возрастанию, а лексикографически, то есть как в словаре (сначала по первой цифре, затем, при равной первой цифре – по второй, и так далее). Кроме того, рассматривается не бесконечное множество натуральных чисел, а лишь первые n чисел. Так, например, если n=11, то числа в странной математике оказываются упорядочены следующим образом: 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9.

Помогите ученикам в изучении этой науки – напишите программу, которая по заданному n находит место заданного числа k в порядке, определенном в странной математике. Например, если n=11 и k=2, программа должна выдать в качестве ответа 4.
Формат входных данных

Первая строка входный данных содержит натуральное число n, 1<=n<=10^9. Вторая строка входных данных содержит натуральное число k, 1<=k<=n.
Формат выходных данных

Программа должна вывести единственное натуральное число – номер числа k среди первых n натуральных чисел в лексикографическом порядке.
Пример
Входные данные:
11
2
Выходные данные:
4

9. Игра в спички
На столе лежит N спичек. Двое играющих по очереди берут со стола 1, 2 или 5 спичек. Выигрывает тот, кто возьмет последнюю спичку. Определите, какой игрок выигрывает при правильной игре.
Формат входных данных

Программа получает на вход единственное число N, 0<N≤1000.
Формат выходных данных

Программа должна вывести единственное число 1 или 2 – номер игрока, у которого есть выигрышная стратегия.
Пример
Вход Выход
6 2

10. Перевод
Как известно, с целью экономии электроэнергии многие страны используют переход на так называемое летнее время. Перевод времени осуществляется два раза в год – весной и осенью. Весной осуществляется переход на летнее время: часы переводятся на один час вперед. Осенью летнее время отменяется и часы переводятся на один час назад.

Перевод времени осуществляется ночью. При переходе на летнее время через минуту после 01:59 сразу наступает 03:00. При отмене летнего времени час с 02:00 по 02:59 повторяется два раза. А именно, в день перевода, когда первый раз после 02:59 должно стать 03:00, вместо этого снова становится 02:00.

Как одному из разработчиков новой операционной системы Mocrosoft Widows 2006, вам поручено написать фрагмент ядра операционной системы, который будет осуществлять автоматический перевод системных часов на летнее время и обратно.

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

Первая строка входного файла содержит целое число m – количество минут, которое прошло от начала текущих суток, до первого момента времени, который следует вывести. Гарантируется, что оно неотрицательно и строго меньше числа минут в текущих сутках.

На второй строке находятся два целых числа d1 и d2, которые указывают, какой перевод времени осуществляется в текущие и в следующие сутки. Значение 1 означает, что осуществляется переход на летнее время, -1 означает, что осуществляется отмена летнего времени, а 0 означает, что перевода времени не осуществляется.

На третьей строке записано число k – количество отсчетов времени, которое ваша программа должна вывести (1≤k≤600).
Формат выходных данных

Выходной файл должен состоять из k строк, i-я из которых должна содержать показания часов через i-1 минут после начального момента времени. Выводите время в формате hh:mm.
Примеры
Вход Выход
118 01:58
1 0 01:59
4 03:00
03:01


190 02:10
-1 1
1


0 00:00
-1 0 00:01
3 00:02


1438 23:58
0 1 23:59
4 00:00
00:01


Пожалуйста очень прошу, помогите мне!!!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 22:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru