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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.71
petrole
2 / 2 / 0
Регистрация: 22.01.2012
Сообщений: 6
#1

Олимпиадные задачи :/ - C++

22.01.2012, 16:39. Просмотров 2812. Ответов 23
Метки нет (Все метки)

Здравствуйте!

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

№1

Среди всех комбинация из N цифр найти те, сумма которых равно числу K.

Формат входных данных:
Вводятся два целых числа через пробел – количество цифр N (1 ≤ N ≤ 100) в номере и сумма его цифр K (0 ≤ S ≤ 9•N).

Формат выходных данных:
Вывести количество номеров, состоящих ровно из N цифр, сумма цифр в которых равна заданному K.

Пример входных - выходных данных:
input:

2 7
output:
8

№2

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

Формат входных данных (input.txt)
В первой строке входного файла содержится одно целое число S (3 ≤ S ≤ 1000) – сумма делителей.

Формат результата (output.txt)
В выходной файл вывести в порядке возрастания по одному числу на строке все числа, у которых сумма двух наибольших делителей, исключая само число, равна заданному S.

Пример входных данных
12

Пример результата
16
27
35
121

№3
В центре городского парка, имеющего форму круга радиусом R2, находится круглый фонтан радиусом R1. Деревья в парке растут в узлах координатной сетки, начало которой находится в центре фонтана. Шаг координатной сетки равен 1. На границах парка и фонтана деревья не растут. Подсчитайте количество деревьев в парке.

Формат входных данных (input.txt)
Вводятся два целых числа R1 и R2 через пробел (1 ≤ R1 < R2 ≤ 10000).
Формат результата (output.txt)
Вывести количество деревьев.
Пример входных данных
1 3
Пример результата
20
1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.01.2012, 16:39
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Олимпиадные задачи :/ (C++):

Олимпиадные задачи - C++
Посоветуйте хороший сайт, на котором есть много олимпиадных задач?

Олимпиадные задачи - C++
Дорогие друзья! Обращаюсь к вам с необычной просьбой. В прошлом году здесь кто-то выложил ответы на олимпиадные задачи, которые проводились...

Олимпиадные задачи по программированию - C++
Пробуйте :) Окружной этап всероссийской олимпиады школьников по информатике Москва, 2 декабря 2012 Во всех задачах входные...

Ошибка в книге Скиены "Олимпиадные задачи по програмированию"?! - C++
Итак, всем привет:) Начал я на днях читать книгу Скиены, сейчас на главе про структуры даных. В книге приведен премер задачи &quot;Сборы на...

Олимпиадные задачки - C++
Всем привет. Скажите, олимпиадные задачки вообще полезны? Для опыта там, или вообще. :)

Олимпиадные задачи - Turbo Pascal
Вася очень любил играть в карты. Однажды он решил написать программу, которая за него будет выбирать правильный ход. Программу он составил,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
25.01.2012, 20:13 #16
neske, а длинная арифметика??? Про нее то забыли, алгоритм решения я предложил.
0
neske
1495 / 862 / 82
Регистрация: 26.03.2010
Сообщений: 2,951
25.01.2012, 20:19 #17
да не пойдет этот алгоритм, на n > 15 уже вечность работать будет.

Добавлено через 1 минуту
это ж кстати 1 гугол, 10^100
0
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
25.01.2012, 20:30 #18
Цитата Сообщение от neske Посмотреть сообщение
это ж кстати 1 гугол, 10^100
Что?
Специально для вас набросал http://liveworkspace.org/code/1a9b70...c255fb9742b3fb
0
neske
1495 / 862 / 82
Регистрация: 26.03.2010
Сообщений: 2,951
25.01.2012, 20:35 #19
спасибо, но писать длинную арифметику я вроде и сам умею.
лучше проверьте свою программу, хотя бы для n > 10, и убедитесь, что такой алгоритм при данных ограничениях не подойдет.
0
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
25.01.2012, 20:38 #20
Цитата Сообщение от neske Посмотреть сообщение
лучше проверьте свою программу, хотя бы для n > 10, и убедитесь, что такой алгоритм при данных ограничениях не подойдет.
Алгоритм работает для любого кол-во цифр. Данный код работает для n < 20. Но использую длинную арифметику, можно увеличить и до 100 (как в задании). Писать это за Вас я не собираюсь.

Цитата Сообщение от neske Посмотреть сообщение
я вроде и сам умею.
Странно, что спрашиваете.
0
neske
1495 / 862 / 82
Регистрация: 26.03.2010
Сообщений: 2,951
25.01.2012, 20:44 #21
на то олимпиадная задача и является олимпиадной, что ее не решить в лоб из-за ограничений, которые наложены на память и время. вы же прекрасно все это понимаете, зачем это на форуме разводить.
не дождетесь вы ответа от своей программы при большом n, ну что, разве не так?
я знаю, что ваш код будет работать при любом n, я и не говорил что будет ошибка, я говорил, что он не пойдет для этой задачи.

Цитата Сообщение от go Посмотреть сообщение
Странно, что спрашиваете.
что я спрашивал ?)
0
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
25.01.2012, 21:06 #22
Цитата Сообщение от neske Посмотреть сообщение
я знаю, что ваш код
мы говорим про алгоритм. Если отпираться от кода, то он будет работать при n < 20. Для увеличения n нужно использовать длинную арифметика, писать с ней у меня нет интереса.
P.S. Алгоритм пишется без привязки к языку (в jawa, например, длинная арифметика есть по умолчанию). А чтобы решить задачу №1 особых знания языка не требуется.

Добавлено через 2 минуты
Цитата Сообщение от neske Посмотреть сообщение
не дождетесь вы ответа от своей программы при большом n, ну что, разве не так?
В моем понимании работать, это выдавать правильный результат.
Цитата Сообщение от neske Посмотреть сообщение
что он не пойдет для этой задачи.
Код или алгоритм?
0
neske
1495 / 862 / 82
Регистрация: 26.03.2010
Сообщений: 2,951
25.01.2012, 21:13 #23
ваш алгоритм не подойдет для этой задачи (даже на jaWa, например, где длинная арифметика есть по умолчанию) из-за ограничений, он просто по времени не уложится - time limit будет.

Не по теме:

при n = 100, ваш алгоритм будет перебирать чисел больше, чем частиц в нашей вселенной, говорит нам википедия)

0
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
25.01.2012, 21:29 #24
Цитата Сообщение от neske Посмотреть сообщение
go, вы знаете, при n = 100, ваш алгоритм будет перебирать чисел больше, чем частиц частиц в нашей вселенной, говорит в википедия, ну это так, просто интересный факт.
Мда. Набросал вот такой код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream> 
#include <limits> 
 
typedef unsigned long long T_my;
 
int main() 
{ 
   T_my max = std::numeric_limits<T_my>::max();
   int i;
   T_my j;
   for ( i = 0, j = 0 ; i < 3 ; ++j ) 
      if ( j == max ) 
      {
         ++i;
         j = 0;
      }  
   std::cout << "OK" << std::endl;    
   return 0;
}
и понял, что простым перебором здесь не обойтись.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2012, 21:29
Привет! Вот еще темы с ответами:

Олимпиадные задачи - C#
Вопрос: имеет ли практический(коммерческий, денежный в будущем) смысл решения олимпиадных задач по программированию? С одной стороны мне...

Олимпиадные задачи - Turbo Pascal
Найти количество целых решений, удовлетворяющих неравенству: A &lt; B*x + C ≤ D. Формат входных данных: В единственной строке заданы...

олимпиадные задачи - Turbo Pascal
решить в паскаль. В молочных магазинах города Х продается сметана с жирностью 15, 20 и 25 процентов. В городе X был проведен мониторинг...

Олимпиадные задачи - Pascal ABC
Даны задачи: Заранее спасибо.


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
25.01.2012, 21:29
Ответ Создать тему
Опции темы

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