Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.54/26: Рейтинг темы: голосов - 26, средняя оценка - 4.54
C#
57 / 57 / 5
Регистрация: 09.03.2013
Сообщений: 216
1

Задачи с олимпиады

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

Author24 — интернет-сервис помощи студентам
Помогите разобраться с данными задачами с олимпиады:

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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.04.2013, 13:29
Ответы с готовыми решениями:

Задача из олимпиады
Здравствуйте уважаемые форумники. На днях столкнулся с задачкой из одной олимпиады и хотел бы вас...

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

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

C++ vs C# для олимпиады. Примеры задач
Здравствуйте. На информатике в школе, говорят что я 1 из самых знающий в области программирования...

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

Во 2-й цикл можно сократить до 30 или вообще создать массив и заполнить его нужными значениями заранее.
2
C#
57 / 57 / 5
Регистрация: 09.03.2013
Сообщений: 216
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
2664 / 2239 / 240
Регистрация: 03.07.2012
Сообщений: 8,141
Записей в блоге: 1
12.04.2013, 14:06 4
Неправильно переписал, думай дальше.
1
C#
57 / 57 / 5
Регистрация: 09.03.2013
Сообщений: 216
12.04.2013, 14:09  [ТС] 5
Цитата Сообщение от zer0mail Посмотреть сообщение
Неправильно переписал, думай дальше.
А подсказку?
1
2664 / 2239 / 240
Регистрация: 03.07.2012
Сообщений: 8,141
Записей в блоге: 1
12.04.2013, 14:13 6
В олимпиадных задачах по программированию главное - придумать эффективный алгоритм, т.е. осмыслить задачу математически. А кодирование - дело техники.
1
C#
57 / 57 / 5
Регистрация: 09.03.2013
Сообщений: 216
12.04.2013, 14:15  [ТС] 7
Цитата Сообщение от zer0mail Посмотреть сообщение
В олимпиадных задачах по программированию главное - придумать эффективный алгоритм, т.е. осмыслить задачу математически. А кодирование - дело техники.
Ну это очевидно.
1
2664 / 2239 / 240
Регистрация: 03.07.2012
Сообщений: 8,141
Записей в блоге: 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;
Что тут сложного, непосильного? "Ну это очевидно" - почему тогда не искали другое решение.
2
C#
57 / 57 / 5
Регистрация: 09.03.2013
Сообщений: 216
12.04.2013, 14:19  [ТС] 9
Дошло...
А как вторую решить?

Цитата Сообщение от zer0mail Посмотреть сообщение
"Ну это очевидно" - почему тогда не искали другое решение.
Потому что я больше кодер, чем математик
1
2664 / 2239 / 240
Регистрация: 03.07.2012
Сообщений: 8,141
Записей в блоге: 1
12.04.2013, 14:27 10
"Чистому кодеру" не победить в олимпиаде (разве что в команде с математиком).
2*3*5=30, те в каждой "тридцатке" одинаковое число подходящих чисел (M). Значит, надо умножить количество полных тридцаток в числе на M + добавить "хвостик".
1
496 / 11 / 6
Регистрация: 10.04.2013
Сообщений: 44
12.04.2013, 14:30 11
На 2,3,5 делиться только число кратное 30, можно готовые значения заранее в массив добавить
0
C#
57 / 57 / 5
Регистрация: 09.03.2013
Сообщений: 216
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
496 / 11 / 6
Регистрация: 10.04.2013
Сообщений: 44
12.04.2013, 14:56 13
for (i = 0; i <= 8; i++) if (numbers[i] < (n % 30)) k++;
Это скорее всего
0
C#
57 / 57 / 5
Регистрация: 09.03.2013
Сообщений: 216
12.04.2013, 14:58  [ТС] 14
Цитата Сообщение от w8me Посмотреть сообщение
for (i = 0; i <= 8; i++) if (numbers[i] < (n % 30)) k++;
Это скорее всего
Нет, с <= будет сравнение с несуществующим 9-м элементом массива.
1
2664 / 2239 / 240
Регистрация: 03.07.2012
Сообщений: 8,141
Записей в блоге: 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
C#
57 / 57 / 5
Регистрация: 09.03.2013
Сообщений: 216
12.04.2013, 15:09  [ТС] 16
OMG. Что еще сказать... Ваш алгоритм засчитан.
Зато у меня код красивее

По 3 и 4 не знаете? Там тоже по сути "в лоб". Жаль, пока что недоступны логи тестировщика, неизвестны входящие данные на которых решение ломается...
1
2664 / 2239 / 240
Регистрация: 03.07.2012
Сообщений: 8,141
Записей в блоге: 1
12.04.2013, 15:13 17
Так олимпада что - сейчас идет?
0
C#
57 / 57 / 5
Регистрация: 09.03.2013
Сообщений: 216
12.04.2013, 15:15  [ТС] 18
Цитата Сообщение от zer0mail Посмотреть сообщение
Так олимпада что - сейчас идет?
Да, и я с Вашей помощью выигрываю
Это открытая тренировка, может зарегистрироваться кто хочет. Цель - проверить систему. На самой олимпиаде задачи будут значительно сложнее...
1
2664 / 2239 / 240
Регистрация: 03.07.2012
Сообщений: 8,141
Записей в блоге: 1
12.04.2013, 15:26 19
Я считаю, на олимпиаде каждый должен выступать за себя. Знал одного, который задачи школьной олимпиады (школа с матуклоном) размещал на форуме (не этом). Их решали и он как победитель ехал на городскую олимпиаду (где с треском проваливался).
1
C#
57 / 57 / 5
Регистрация: 09.03.2013
Сообщений: 216
12.04.2013, 15:45  [ТС] 20
Цитата Сообщение от zer0mail Посмотреть сообщение
Я считаю, на олимпиаде каждый должен выступать за себя. Знал одного, который задачи школьной олимпиады (школа с матуклоном) размещал на форуме (не этом). Их решали и он как победитель ехал на городскую олимпиаду (где с треском проваливался).
Не вижу смысла так делать
То что Вы мне подсказали, моей команде никак не поможет через неделю. Разве что, я стал немножечко умнее, наверное.

Так не знаете по поводу остальных задач? Вроде простейшие же, а какие-то входные данные не решают.
1
12.04.2013, 15:45
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.04.2013, 15:45
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru