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

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

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

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

№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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.01.2012, 16:39     Олимпиадные задачи :/
Посмотрите здесь:

Олимпиадные задачи C++
C++ Ошибка в книге Скиены "Олимпиадные задачи по програмированию"?!
C++ задачи
C++ Олимпиадные задачи
Задачи в VS C++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,692
25.01.2012, 20:44     Олимпиадные задачи :/ #21
на то олимпиадная задача и является олимпиадной, что ее не решить в лоб из-за ограничений, которые наложены на память и время. вы же прекрасно все это понимаете, зачем это на форуме разводить.
не дождетесь вы ответа от своей программы при большом n, ну что, разве не так?
я знаю, что ваш код будет работать при любом n, я и не говорил что будет ошибка, я говорил, что он не пойдет для этой задачи.

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

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

Не по теме:

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

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2012, 21:29     Олимпиадные задачи :/
Еще ссылки по теме:

3 задачи по С++ C++
C++ Олимпиадные задачи по программированию
C++ Олимпиадные задачки

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

Или воспользуйтесь поиском по форуму:
go
Эксперт C++
3582 / 1362 / 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;
}
и понял, что простым перебором здесь не обойтись.
Yandex
Объявления
25.01.2012, 21:29     Олимпиадные задачи :/
Ответ Создать тему
Опции темы

Текущее время: 00:05. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru