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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
#1

Задачи с олимпиады - C++

12.04.2013, 13:29. Просмотров 1534. Ответов 38
Метки нет (Все метки)

Помогите разобраться с данными задачами с олимпиады:

1. Вводиться 3 остатка от деления числа на 971, 997 и 1033. Вывести это число.
Например:
I: 5 10 15
O: 835049324
Ограничения: 64 мб памяти, время 1 с

Мое решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
 
using namespace std;
 
int main(void)
{
    int n1, n2, n3;
    long i;
    cin>>n1>>n2>>n3;
    for (i = 0; i < 2147483647; i++)
        if ((i % 971 == n1) && (i % 997 == n2) && (i % 1033 == n3)) break;
    cout<<i;
    return 0;
}
Превышен лимит времени на 9 тесте.

2. Найти количество чисел не больше N, которые не делятся на 2, 3 и 5.
I: 10
O: 2
Ограничения: 64 мб памяти, время 1 с

Мое решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
 
using namespace std;
 
int main(void)
{
    long n, i, k = 0;
    cin>>n;
    for (i = 0; i <= n; i++)
        if ((i % 2 != 0) && (i % 3 != 0) && (i % 5 != 0)) k++;
    cout<<k;
    return 0;
}
Превышен лимит времени на 10 тесте.

3. Саша сел делать домашнее задание и просидел за столом N часов. Из них Х минут он чесал затылок и смотрел в окно, Y минут искал в письменном столе резинку, чтобы стереть в учебнике по английскому языку карикатуру на своего товарища, на рисование которой он потратил перед этим Z минут. Все последнее время Саша переводил английские слова. Сколько слов он успел перевести, если на перевод одного слова у него уходило 5 минут?
Вводятся 4 числа N, X, Y, Z, вывод - количество переведенных слов.
I: 2 30 20 30
O: 8
Ограничения: 64 мб памяти, время 1 с

Мое решение:
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
 
using namespace std;
 
int main(void)
{
    int n, x, y, z;
    cin>>n>>x>>y>>z;
    cout<<(n * 60 - x - y - z)/5;
    return 0;
}
Неправильный ответ на 10 тесте

4. Дана последовательность чисел в странном формате: у каждого числа в начале записано количество цифр в том числе, а потом через пробел - сами цифры. Последовательность заканчивается числом 0. Напишите программу, которая в первой строке выведет количество чисел в последовательности, а затем - сами числа, по одному в строке. Количество чисел в последовательности не более 1000. В числах - не более 4-х знаков.
I: 2 2 7 3 3 5 1 0
O: 2 27 351
I: 4 1 2 3 4 2 4 3 0
O: 2 1234 43
Ограничения: 64 мб памяти, время 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
#include <iostream>
 
using namespace std;
 
int main(void)
{
    int n = 0, i, j, k = 0;
    int* nums = new int[1000];
    int* newnums = new int[1000];
 
    do cin>>nums[n++];
    while (nums[n - 1] != 0);
    for (i = 0; i < n; i++)
        newnums[i] = 0;
    n--;
    for (i = 0; i < n - 1; i++)
    {
        for (j = 0; j < nums[i]; j++)
        {
            newnums[k] *= 10;
            newnums[k] += nums[i + j + 1];
        }
        k++;
        i += j;
    }
    cout<<k<<"\n";
    for (i = 0; i < k; i++) cout<<newnums[i]<<"\n";
    return 0;
}
Неправильный ответ на 4 тесте.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.04.2013, 13:29
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задачи с олимпиады (C++):

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

Задание с олимпиады. Массивы - C++
условие в прикрепленнов файле. я не смог ее решить. однако очень интересно и хотелосб ьы узнать как и что.

сложная задача с олимпиады по программированию - C++
Перевозчику необходимо доставить груз из одного города (А) в другое (В). Известно, что при доставке груза перевозчик несет затраты...

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

Отобрать кандадатов на олимпиады (с отличными оценками) по каждому из предметов - C++
Для группы учащихся известны годовые оценки по следующим предметам:математика,физика,химия, информатика. Отобрать кандадатов на олимпиады(с...

Разбор задач второго этапа Республиканской олимпиады по информатике, 9-11 классы,РК I-II туры - C++
Здравствуйте. На днях(8-9 декабря) прошел районный этап Республиканской олимпиады по информатике в Казахстане. Всего в этапе было два тура....

38
zer0mail
2342 / 1972 / 193
Регистрация: 03.07.2012
Сообщений: 7,090
Записей в блоге: 1
12.04.2013, 13:54 #2
В 1 и 2 какие-то бездумные решения "в лоб". Такие решения может предложить любой, кто хоть что-то смыслит в программировании.
Например: в 1-й задаче легко сделать шаги цикла не по 1, а по 1033 (и на 3 порядка сократить время расчета!)

Во 2-й цикл можно сократить до 30 или вообще создать массив и заполнить его нужными значениями заранее.
2
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 14:05  [ТС] #3
Цитата Сообщение от zer0mail Посмотреть сообщение
В 1 и 2 какие-то бездумные решения "в лоб". Такие решения может предложить любой, кто хоть что-то смыслит в программировании.
Так вот хочу усовершенствовать свою логику для решения подобных задач
Цитата Сообщение от zer0mail Посмотреть сообщение
Например: в 1-й задаче легко сделать шаги цикла не по 1, а по 1033 (и на 3 порядка сократить время расчета!)
Переписал так:
C++
1
2
for (i = 1; i < 2147483647; i += 971)
        if ((i % 971 == n1) && (i % 997 == n2) && (i % 1033 == n3)) break;
Неправильный ответ на первом же тесте, хотя пример решает.
Цитата Сообщение от zer0mail Посмотреть сообщение
Во 2-й цикл можно сократить до 30 или вообще создать массив и заполнить его нужными значениями заранее.
Как?
1
zer0mail
2342 / 1972 / 193
Регистрация: 03.07.2012
Сообщений: 7,090
Записей в блоге: 1
12.04.2013, 14:06 #4
Неправильно переписал, думай дальше.
1
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 14:09  [ТС] #5
Цитата Сообщение от zer0mail Посмотреть сообщение
Неправильно переписал, думай дальше.
А подсказку?
1
zer0mail
2342 / 1972 / 193
Регистрация: 03.07.2012
Сообщений: 7,090
Записей в блоге: 1
12.04.2013, 14:13 #6
В олимпиадных задачах по программированию главное - придумать эффективный алгоритм, т.е. осмыслить задачу математически. А кодирование - дело техники.
1
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 14:15  [ТС] #7
Цитата Сообщение от zer0mail Посмотреть сообщение
В олимпиадных задачах по программированию главное - придумать эффективный алгоритм, т.е. осмыслить задачу математически. А кодирование - дело техники.
Ну это очевидно.
1
zer0mail
2342 / 1972 / 193
Регистрация: 03.07.2012
Сообщений: 7,090
Записей в блоге: 1
12.04.2013, 14:15 #8
C++
1
2
3
 
for (i = n3; i < 2147483647; i += 1033)
        if ((i % 971 == n1) && (i % 997 == n2)) break;
Что тут сложного, непосильного? "Ну это очевидно" - почему тогда не искали другое решение.
1
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 14:19  [ТС] #9
Дошло...
А как вторую решить?

Цитата Сообщение от zer0mail Посмотреть сообщение
"Ну это очевидно" - почему тогда не искали другое решение.
Потому что я больше кодер, чем математик
1
zer0mail
2342 / 1972 / 193
Регистрация: 03.07.2012
Сообщений: 7,090
Записей в блоге: 1
12.04.2013, 14:27 #10
"Чистому кодеру" не победить в олимпиаде (разве что в команде с математиком).
2*3*5=30, те в каждой "тридцатке" одинаковое число подходящих чисел (M). Значит, надо умножить количество полных тридцаток в числе на M + добавить "хвостик".
1
w8me
496 / 11 / 1
Регистрация: 10.04.2013
Сообщений: 44
12.04.2013, 14:30 #11
На 2,3,5 делиться только число кратное 30, можно готовые значения заранее в массив добавить
0
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 14:44  [ТС] #12
Цитата Сообщение от zer0mail Посмотреть сообщение
"Чистому кодеру" не победить в олимпиаде (разве что в команде с математиком).
Знаю, но попытаться то стоит.
Цитата Сообщение от zer0mail Посмотреть сообщение
2*3*5=30, те в каждой "тридцатке" одинаковое число подходящих чисел (M). Значит, надо умножить количество полных тридцаток в числе на M + добавить "хвостик".
На примере в числе 10 тридцаток 0, хвост получается 2. Что за число M и как рассчитать хвост?

Добавлено через 2 минуты
Цитата Сообщение от w8me Посмотреть сообщение
На 2,3,5 делиться только число кратное 30, можно готовые значения заранее в массив добавить
Так нужно найти числа от 1 до N, которые не делятся на 2, 3 и 5. Если N = 10, то таких числа 2 - 1 и 7. Причем здесь 30?

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

Добавлено через 3 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
 
using namespace std;
 
int main(void)
{
    long n, i, k = 0;
    int numbers[8] = {1, 7, 11, 13, 17, 19, 23, 29};
    cin>>n;
    k = n / 30 * 8;
    for (i = 0; i < 8; i++) if (numbers[i] < (n % 30)) k++;
    cout<<k;
    return 0;
}
Неправильный ответ на первом тесте. Что я не учел?
0
w8me
496 / 11 / 1
Регистрация: 10.04.2013
Сообщений: 44
12.04.2013, 14:56 #13
for (i = 0; i <= 8; i++) if (numbers[i] < (n % 30)) k++;
Это скорее всего
0
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 14:58  [ТС] #14
Цитата Сообщение от w8me Посмотреть сообщение
for (i = 0; i <= 8; i++) if (numbers[i] < (n % 30)) k++;
Это скорее всего
Нет, с <= будет сравнение с несуществующим 9-м элементом массива.
1
zer0mail
2342 / 1972 / 193
Регистрация: 03.07.2012
Сообщений: 7,090
Записей в блоге: 1
12.04.2013, 14:59 #15
Вы даже понять меня, как математик, не можете Попробую как кодировщику (только алгоритм)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
   int n;
   int m[30];// m[i]=количество чисел, <=i, не делящихся на 2,3,5
   m[0]=0;
   for (int i=1; i<30; ++i) {
     m[i]=m[i-1];
     if ((i % 2 != 0) && (i % 3 != 0) && (i % 5 != 0)) m[i]++;
   };
 
    // массив готов, используем его для расчета
   cin>>n; // исходные данные
   cout<<(m[29]* (n/30)+m[n%30]); // расчет в одну строку, без циклов!
 
   return 0;
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2013, 14:59
Привет! Вот еще темы с ответами:

Найти, из какой школы (школ) было больше всего участников олимпиады - C++
Прошу помощи. Болел - ничего не понял. Скоро экзамен, а я ничего не понимаю в С++. Дали примерные задачи, а я не понимаю как решать. Вот...

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

Задачи олимпиады - Физика
http://www.cyberforum.ru/attachment.php?attachmentid=201929&amp;d=1353155009 Помогите, пожалуйста, решить задачи во Всероссийской...

Задачи с олимпиады по информатике - Pascal ABC
Помогите решить задачи


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

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

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