Форум программистов, компьютерный форум 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ilyawow
24 / 24 / 5
Регистрация: 18.11.2011
Сообщений: 266
22.01.2012, 16:43     Олимпиадные задачи :/ #2
это облостная 2 тур?
petrole
2 / 2 / 0
Регистрация: 22.01.2012
Сообщений: 6
22.01.2012, 16:44  [ТС]     Олимпиадные задачи :/ #3
Областная 1 (заочный) тур.
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
22.01.2012, 17:01     Олимпиадные задачи :/ #4
3я решается перебором х/у для Р2 и Р1, результат: Р2 - Р1.
Рассмотрим все х, которые лежат в диапазоне [ 0; R ]. Для каждого х найде соответсвующий у, который является максимальным, при этом находящимся в круге, этот игрик есть число точек в круге для выбранного х ( точнее не в круге, а в 1/4 круга - если нарисовать на листочке, то станет ясно почему ).
Найдём количество у для Р2 ( все точки для заданого х от центра парка до его границы ), а также количесвто у для Р1 ( все точки для х от центра фонтана до границы фонтана ), прибавим разницу к результату.
+ еще проверяем, есть ли точка на границе, если так, то просто инкрементируем у.
В конце умножим результат на 4, потому что мы нашли число деревьев (точек) только в 1,4 круга.
Примерно так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
cin >> R1 >> R2;
for ( x = 0; x < R2; ++x )
{
    y2 = ( int )( sqrt( R2 * R2 - x * x ) + eps );
    y1 = ( int )( sqrt( R1 * R1 - x * x ) + eps );
 
    y2 -= ( R2 * R2 == x * x + y2 * y2 );
    y1 -= ( R1 * R1 == x * x + y1 * y1 );
 
    Result += y2 - y1;
}
Result *= 4;
petrole
2 / 2 / 0
Регистрация: 22.01.2012
Сообщений: 6
22.01.2012, 17:07  [ТС]     Олимпиадные задачи :/ #5
Цитата Сообщение от x1Mike7x Посмотреть сообщение
eps
Что есть эта переменная?
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
22.01.2012, 17:22     Олимпиадные задачи :/ #6
Цитата Сообщение от petrole Посмотреть сообщение
Что есть эта переменная?
Допустимая погрешность при выичслении чисел с плавающей запятой.
C++
1
const double eps = 1e-9;
Teravisor
30 / 30 / 3
Регистрация: 07.08.2011
Сообщений: 89
22.01.2012, 18:01     Олимпиадные задачи :/ #7
Первая задача:
переформулируем. Дан массив A из N элементов, изначально 0, не могут превышать 9
Дано число K
Надо найти число комбинаций распределения K вещей по N местам.
Решение:
пусть есть функция, которая распределяет T элементов по всем массивам начиная с номера U.
запускаем цикл. Начало рекурсии: U=0,T=K
функция F(T,U):
Для каждого A[U] 0<=i<=min(9,T) делаем F(T-i,U+1); Считаем сумму всех F(T-i,U+1) которые мы запускали и возвращаем.
Каждый запуск функции при Т=0 - это один из вариантов. Значит возвращаем 1 ничего не запуская. Конец рекурсии.

Если после последнего цикла T(T,N) - возвращаем 0 при T>9. Иначе 1. Второй конец рекурсии.

Написать на С++ не проблема по этому алгоритму. Кому не лень.

Edit: опечатки.

Добавлено через 21 минуту
По сути в прошлом A[U] нужен только для виду. в программе его не будет.

Вторая задача:
Дан К - сумма двух наибольших делителей.
Переформулируем:
перебрать все варианты разложения К вещей по двум полкам A[0] и A[1], так чтобы
A[0]*A[1]%B >0 для любого B больше A[0] или A[1] и меньшего K
A[0]+A[1]==K

Т.е. банально три вложенных цикла, которые ищут два числа, удовлетворяющие этим условиям. Плюс третий вложенный в них цикл по поиску B, которое бы удовлетворяло A[0]*A[1]%B==0. Ответом будет их сумма. Это если писать на скорость.
Даже распишу:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Function(int K)
{
   int A0=0;
   int A1=0;
   for(A0=K;A0>0;A0--)
       for(A1=K;A1>0;A1--)
       {
//Тут мы не будем использовать math::min или другие библиотеки. Поэтому так.
          if(A0==A1)continue;
          for(int B=K;a>0;a--)
          {
              if((A0*A1%B)==0)break;
              if((B<A0)&&(B<A1))return A[0]+A[1];
          }
       }
//Такого числа нет.
   return -1
}
Вроде так.

З.Ы. можно сделать циклы A0 и A1 >1 т.к. если одно из них равно 1, то строка 12 всегда сработает. Можно еще 14й строкой вставить else break;
Увеличит производительность, но для олимпиадных оно не требуется вроде?
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
22.01.2012, 19:59     Олимпиадные задачи :/ #8
Цитата Сообщение от Teravisor Посмотреть сообщение
Увеличит производительность, но для олимпиадных оно не требуется вроде?
наоборот, один из самый важный факторов 8) там же везде ограничения на время и память.

Добавлено через 2 минуты
Teravisor, во второй задачи вы намудрили, как минимум из за того, что ответов может быть несколько.
Vergil111
31 / 31 / 6
Регистрация: 30.11.2010
Сообщений: 81
23.01.2012, 00:33     Олимпиадные задачи :/ #9
Имхо, все намного проще насчет первой задачи. Первое условие вам дает количество возможных перестановок цифр в числе, то есть в указанном вами примере это будет 2! Второе условие дает количество уникальных вариантов, равное [k/2]+1, где скобки обозначают нацело.То есть опять-таки согласно вашему примеру получается так. Выписываем "уникальные" числа
0 7
1 6
2 5
3 4
Далее они начинают просто меняться местами. Получилось 4 варианта, то есть как раз [7/2]+1=4
Далее просто умножаем одно на другое и получаем наш ответ.
Правда вот если количество цифр равно 1, то метод не работает=)
А для трехразрядных чисел мне было лень проверять
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
23.01.2012, 00:42     Олимпиадные задачи :/ #10
Цитата Сообщение от Vergil111 Посмотреть сообщение
Второе условие дает количество уникальных вариантов, равное [k/2]+1
будет работать только для n = 2
Vergil111
31 / 31 / 6
Регистрация: 30.11.2010
Сообщений: 81
23.01.2012, 00:46     Олимпиадные задачи :/ #11
neske, ты прав, да и вообще количество уникальных вариантов неверное, если подставить сумму, равную 10 в условие. Хм, буду дальше думать над нахождением количества уникальных элементов=/
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
23.01.2012, 01:33     Олимпиадные задачи :/ #12
Vergil111, верно начал и неверно кончил. Правильный ответ http://www.cyberforum.ru/cgi-bin/latex.cgi?\(K + 1\)^{N - 1}. Какие-то номера в условии, кто его составлял, это условие... сложность в том что N (1 ≤ N ≤ 100) ,а это длинная арифметика.
Vergil111
31 / 31 / 6
Регистрация: 30.11.2010
Сообщений: 81
23.01.2012, 10:07     Олимпиадные задачи :/ #13
alkagolik, я знал, что должно быть короткое решение) Чуть-чуть не хватило, спать хотелось) спасибо)
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
25.01.2012, 19:50     Олимпиадные задачи :/ #14
Цитата Сообщение от petrole Посмотреть сообщение
№1
На самом деле очень легкая задача для олимпиадной. Делается очень просто. Вот
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cmath>
 
typedef unsigned long long T_my;
 
size_t dig_sum(T_my val)
{
   size_t sum = 0;
   
   do
   {
      sum += val % 10;
   }
   while ( val /= 10 );
   return sum;
}
 
int main()
{
   int k = 7, n = 2;
   T_my max = static_cast<T_my> (pow( 10., n));
   T_my i;
   T_my cnt = 0;
   
   for ( i = 0; i < max ; ++i )
      if ( dig_sum(i) == k )
         ++cnt;
   std::cout << cnt << std::endl;
   return 0;
}
http://liveworkspace.org/code/d77a7a...0a8363727ff9f0

Добавлено через 1 минуту
Цитата Сообщение от Teravisor Посмотреть сообщение
Дан массив A из N элементов,
Все намного проще...
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
25.01.2012, 20:05     Олимпиадные задачи :/ #15
go, вы на ограничения смотрели? 10^100 чисел перебирать будете?
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
25.01.2012, 20:13     Олимпиадные задачи :/ #16
neske, а длинная арифметика??? Про нее то забыли, алгоритм решения я предложил.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
25.01.2012, 20:19     Олимпиадные задачи :/ #17
да не пойдет этот алгоритм, на n > 15 уже вечность работать будет.

Добавлено через 1 минуту
это ж кстати 1 гугол, 10^100
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
25.01.2012, 20:30     Олимпиадные задачи :/ #18
Цитата Сообщение от neske Посмотреть сообщение
это ж кстати 1 гугол, 10^100
Что?
Специально для вас набросал http://liveworkspace.org/code/1a9b70...c255fb9742b3fb
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
25.01.2012, 20:35     Олимпиадные задачи :/ #19
спасибо, но писать длинную арифметику я вроде и сам умею.
лучше проверьте свою программу, хотя бы для n > 10, и убедитесь, что такой алгоритм при данных ограничениях не подойдет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2012, 20:38     Олимпиадные задачи :/
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
25.01.2012, 20:38     Олимпиадные задачи :/ #20
Цитата Сообщение от neske Посмотреть сообщение
лучше проверьте свою программу, хотя бы для n > 10, и убедитесь, что такой алгоритм при данных ограничениях не подойдет.
Алгоритм работает для любого кол-во цифр. Данный код работает для n < 20. Но использую длинную арифметику, можно увеличить и до 100 (как в задании). Писать это за Вас я не собираюсь.

Цитата Сообщение от neske Посмотреть сообщение
я вроде и сам умею.
Странно, что спрашиваете.
Yandex
Объявления
25.01.2012, 20:38     Олимпиадные задачи :/
Ответ Создать тему
Опции темы

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