Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.90/10: Рейтинг темы: голосов - 10, средняя оценка - 4.90
A1exSun
C#
55 / 55 / 5
Регистрация: 09.03.2013
Сообщений: 216
#1

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

12.04.2013, 13:29. Просмотров 1762. Ответов 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++ vs C# для олимпиады. Примеры задач
Здравствуйте. На информатике в школе, говорят что я 1 из самых знающий в...

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

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

Цитата Сообщение от zer0mail Посмотреть сообщение
"Ну это очевидно" - почему тогда не искали другое решение.
Потому что я больше кодер, чем математик
1
zer0mail
2452 / 2089 / 216
Регистрация: 03.07.2012
Сообщений: 7,569
Записей в блоге: 1
12.04.2013, 14:27 #10
"Чистому кодеру" не победить в олимпиаде (разве что в команде с математиком).
2*3*5=30, те в каждой "тридцатке" одинаковое число подходящих чисел (M). Значит, надо умножить количество полных тридцаток в числе на M + добавить "хвостик".
1
w8me
496 / 11 / 6
Регистрация: 10.04.2013
Сообщений: 44
12.04.2013, 14:30 #11
На 2,3,5 делиться только число кратное 30, можно готовые значения заранее в массив добавить
0
A1exSun
C#
55 / 55 / 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
w8me
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
A1exSun
C#
55 / 55 / 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
zer0mail
2452 / 2089 / 216
Регистрация: 03.07.2012
Сообщений: 7,569
Записей в блоге: 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
A1exSun
C#
55 / 55 / 5
Регистрация: 09.03.2013
Сообщений: 216
12.04.2013, 15:09  [ТС] #16
OMG. Что еще сказать... Ваш алгоритм засчитан.
Зато у меня код красивее

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

Так не знаете по поводу остальных задач? Вроде простейшие же, а какие-то входные данные не решают.
1
12.04.2013, 15:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2013, 15:45

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

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