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

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

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

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

C++ Задание с олимпиады. Массивы
C++ Он-лайн олимпиады по программированию
№ задачи на С++ C++
C++ 3 задачи по С++
C++ Задачи
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zer0mail
2183 / 1866 / 187
Регистрация: 03.07.2012
Сообщений: 6,633
Записей в блоге: 1
12.04.2013, 16:13     Задачи с олимпиады #21
Насчет Саши вроде верно... Может, там числа могут быть нецелыми или нужно проверять их на корректность.
А со "странным форматом" лень разбираться в таком некомментированном коде. Одно дело иметь "в голове алгоритм" и претворять его в код, а другое - смотреть на код и "восстанавливать алгоритм".

Если некто хочет, чтобы ему помогали, пусть этот "некто" сделает так, чтобы ему захотели помочь. А код без комментариев или условие в виде "кривых фоток" этому не способствуют
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 16:27  [ТС]     Задачи с олимпиады #22
Понял Пожалуйста:
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); // пока не 0
    for (i = 0; i < n; i++)
        newnums[i] = 0; // заполняем массив для новых чисел нулями
    n--; // уменьшаем количество полученых цифр, чтоб откинуть 0
    for (i = 0; i < n; i++)
    { // смотрим массив цифр
        for (j = 0; j < nums[i]; j++)
        { // складываем число из nums[i] цифр
            newnums[k] *= 10; // умножаем на число на 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;
}
Пока писал комментарии, нашел одну ошибку:
C++
1
2
    n--;
    for (i = 0; i < n - 1; i++)
Забыл убрать "- 1" в условии, я же перед ним уже уменьшил n. Исправил, код прошел 11 тестов.
zer0mail
2183 / 1866 / 187
Регистрация: 03.07.2012
Сообщений: 6,633
Записей в блоге: 1
12.04.2013, 19:57     Задачи с олимпиады #23
1. Что, если в середине числа встретится 0
2. Если чисел 1000, каждое по 4 цифры, то массива nums не хватит
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 20:19  [ТС]     Задачи с олимпиады #24
Цитата Сообщение от zer0mail Посмотреть сообщение
1. Что, если в середине числа встретится 0
2. Если чисел 1000, каждое по 4 цифры, то массива nums не хватит
1. Число умножиться на 10 и к нему прибавиться 0. Что неправильно?
2. Исправил на 10000000
zer0mail
2183 / 1866 / 187
Регистрация: 03.07.2012
Сообщений: 6,633
Записей в блоге: 1
12.04.2013, 20:25     Задачи с олимпиады #25
1.Введи данные 3 1 0 1 4 1 2 0 3 0, что в ответе?
2.На скольно исправил?

Программа работает, как написана, а не как хочет программист
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 20:52  [ТС]     Задачи с олимпиады #26
Понял, пофиксил ввод:
C#
1
2
3
4
5
6
    do {
        cin>>nums[n++]; // получаем цифру
        if (k > 0) k--; // если k > 0, значит текущая цифра не количество цифр в числе
        else k = nums[n - 1]; // иначе присваиваем k количество цифр в числе
        if (k == 0 && nums[n - 1] == 0) break; // если введенная цифра 0 и она не для числа - останавливаем цикл
    } while (1);
Но все равно ошибка на 11 тесте
zer0mail
2183 / 1866 / 187
Регистрация: 03.07.2012
Сообщений: 6,633
Записей в блоге: 1
12.04.2013, 20:52     Задачи с олимпиады #27
см замечание раньше насчет комментариев
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 21:03  [ТС]     Задачи с олимпиады #28
Цитата Сообщение от zer0mail Посмотреть сообщение
см замечание раньше насчет комментариев
F5

Добавлено через 6 минут
Массив nums теперь на 5000 элементов:
C++
1
int* nums = new int[5000];
zer0mail
2183 / 1866 / 187
Регистрация: 03.07.2012
Сообщений: 6,633
Записей в блоге: 1
12.04.2013, 21:31     Задачи с олимпиады #29
А без ошибок можешь закодировать (на олимпиаде "за спиной" нет тестера-консультанта) ?
1. Введи 4 1 1 0 0 0
2. 5000 не хватит для такого алгоритма.
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 21:38  [ТС]     Задачи с олимпиады #30
Цитата Сообщение от zer0mail Посмотреть сообщение
А без ошибок можешь закодировать (на олимпиаде "за спиной" нет тестера-консультанта) ?
1. Введи 4 1 1 0 0 0
Вывод:
1
1100

Цитата Сообщение от zer0mail Посмотреть сообщение
2. 5000 не хватит для такого алгоритма.
Почему?
Не более 1000 чисел из 4 знаков - 4000 цифр + 1000 на четверки.

Добавлено через 3 минуты
Увидел.
zer0mail
2183 / 1866 / 187
Регистрация: 03.07.2012
Сообщений: 6,633
Записей в блоге: 1
12.04.2013, 21:55     Задачи с олимпиады #31
1 А так: 2 1 0 2 1 0 0
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
12.04.2013, 22:28  [ТС]     Задачи с олимпиады #32
Чего-то я не понимаю уже.
Если так:
C++
1
2
    int nums[9] = {2, 1, 0, 2, 1, 0, 2, 1, 0};
    n = 9;
В nums 9 элементов: 210210210
Вывод:
3
10
10
10

Если так:
C++
1
2
3
4
5
6
7
8
    int* nums = new int[5000];
    do {
        cin>>nums[n];
        if (k == 0) k--;
        else k = nums[n];
        if ((k < 0) && (nums[n] == 0)) break;
        n++;
    } while (1);
И ввести 2 1 0 2 1 0 2 1 0 0, в nums тоже 9 (n = 9) элементов: 210210210
А вывод уже:
2
10
10

Весь код:
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
31
32
33
34
35
36
37
38
39
40
#include <iostream>
 
using namespace std;
 
int main(void)
{
    int n = 0, i, j, k = 0;
    int* newnums = new int[1000];
    //int nums[9] = {2, 1, 0, 2, 1, 0, 2, 1, 0};
    //n = 9;
    int* nums = new int[5000];
    do {
        cin>>nums[n];
        if (k == 0) k--;
        else k = nums[n];
        if ((k < 0) && (nums[n] == 0)) break;
        n++;
    } while (1);
    // вывод n и массива:
    cout<<"\n"<<n<<": ";
    for (i = 0; i < n; i++) cout<<nums[i];
    cout<<"\n";
 
    for (i = 0; i < 1000; i++)
        newnums[i] = 0;
 
    for (i = 0; i < n; 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;
}
Добавлено через 3 минуты
В общем с вводом все-таки что-то неладно.
zer0mail
2183 / 1866 / 187
Регистрация: 03.07.2012
Сообщений: 6,633
Записей в блоге: 1
12.04.2013, 22:33     Задачи с олимпиады #33
Цитата Сообщение от A1exSun Посмотреть сообщение
В общем с вводом все-таки что-то неладно.
Кажется, пчелы что-то подозревают (с) Винни-пух.
AnyOne697
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
13.04.2013, 02:07     Задачи с олимпиады #34
Учась на кафедре комплексной безопасности, наш декан очень любил говорить, что программирование наш хлеб и без него мы будем просто голодными. Здесь почти все задачи "на реализацию". Даже первые две задачи в принципе должны пройти и с лобовым решением, хотя математика там вроде есть (гуглим кольца вычетов), но что из неё можно получить... я не пробовал.
Последние две именно на реализацию, никакой сложной математики там вообще нет.
Правда, не понимаю, что с третей задачей, ибо это магия. Может приведёте ссылку на условия?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.04.2013, 10:42     Задачи с олимпиады #35
1. Вроде бы это на китайскую теорему о остатках.
2. Это на формулу включений-исключений
C++
1
2
std::cin >> n;
std::cout << n - n / 2 - n / 3 - n / 5 + n / 6 + n / 10 + n / 15 - n / 30;
3-4. Лень вникать в условие.
zer0mail
2183 / 1866 / 187
Регистрация: 03.07.2012
Сообщений: 6,633
Записей в блоге: 1
13.04.2013, 11:46     Задачи с олимпиады #36
Цитата Сообщение от diagon Посмотреть сообщение
1. Вроде бы это на китайскую теорему о остатках.
Это что - такой код программы?
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
13.04.2013, 11:59  [ТС]     Задачи с олимпиады #37
Цитата Сообщение от AnyOne697 Посмотреть сообщение
Здесь почти все задачи "на реализацию". Даже первые две задачи в принципе должны пройти и с лобовым решением
Ограничение 64 мб памяти и времени на выполнение 1 с, написал же. Поэтому "в лоб" не проходит.
Цитата Сообщение от AnyOne697 Посмотреть сообщение
Правда, не понимаю, что с третей задачей, ибо это магия. Может приведёте ссылку на условия?
В первом посте же все описано.
zer0mail
2183 / 1866 / 187
Регистрация: 03.07.2012
Сообщений: 6,633
Записей в блоге: 1
13.04.2013, 12:55     Задачи с олимпиады #38
4-я задача (и массив один и считает быстрее):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main(void)
{
    int n, i, k;
    int* newnums = new int[1000]; // здесь будут числа
    n = -1; // индекс последнего прочитанного числа
    k=0;    // осталось ввести цифр в числе
    do {
        cin>>i; // получаем цифру
        if (k-- ==0) { // очередное число полностью прочитано?
            k = i; // да, мы прочитали количество цифр в следующем числе, запомним его в k
            if (k == 0) break; // если введенное количество=0, конец ввода
            newnums[++n]=0;    // готовы ввести новое число
        }
        else {
            newnums[n] *= 10; // учтем очередную цифру числа
            newnums[n] += i;
        }
    } while (1);
    cout<<n+1<<"\n"; // выводим количество чисел
    for (i = 0; i <= n; i++) cout<<newnums[i]<<"\n"; // выводим числа
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.04.2013, 19:10     Задачи с олимпиады
Еще ссылки по теме:

C++ Задачи на C++
C++ Определить среднее количество участников олимпиады из одной школы
Найти, из какой школы (школ) было больше всего участников олимпиады C++

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

Или воспользуйтесь поиском по форуму:
A1exSun
C#
51 / 51 / 1
Регистрация: 09.03.2013
Сообщений: 214
13.04.2013, 19:10  [ТС]     Задачи с олимпиады #39
Засчитана. Позже буду еще оставшиеся 5 делать, так что думаю еще отпишу здесь
Не ясно что с 3й задачей, у нескольких людей засчитана.

Добавлено через 6 минут
Пробовал проверять Z:
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
 
using namespace std;
 
int main(void)
{
    int n, x, y, z;
    cin>>n>>x>>y>>z;
    if (z == 0) cout<<(n * 60 - x)/5;
    else cout<<(n * 60 - x - y - z)/5;
    return 0;
}
Мол если он ничего не рисовал, то ничего не нужно стирать.
Еще пробовал принимать числа double и потом выдавать int.
Не принялись.

Добавлено через 55 минут
А вот и следующая не получившаяся задача:
Дано 3 числа. Между ними можно ставить знаки математических операций: сложение, вычитание, умножение, деление. Сколько различных значений может образоваться в результате вычисления полученных таким образом выражений?
Пример:
2 + 2 + 8 = 12
2 + 2 - 8 = -4
2 + 2 * 8 = 18
2 + 2 / 8 = 2.25
2 - 2 + 8 = 8
2 - 2 - 8 = -8
2 - 2 * 8 = -14
2 - 2 / 8 = 1.75
2 * 2 + 8 = 12
2 * 2 - 8 = -4
2 * 2 * 8 = 32
2 * 2 / 8 = 0.5
2 / 2 + 8 = 9
2 / 2 - 8 = -7
2 / 2 * 8 = 8
2 / 2 / 8 = 0.125
Различные значения: -14, -8, -7, -4, 0.125, 0.5, 1.75, 2.25, 8, 9, 12, 18, 32. Всего 13 значений.
Входные данные - 3 числа, выходные - количество различных значений.

Мое решение:
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
31
32
33
34
35
36
37
38
39
#include <iostream>
 
using namespace std;
 
int main(void)
{
    double a, b, c;
    double res[16];
    bool flags[16];
    long i, j, k = 0;
    cin>>a>>b>>c;
    res[0] = a + b + c;
    res[1] = a + b - c;
    res[2] = a + b * c;
    res[3] = a + b / c;
    res[4] = a - b + c;
    res[5] = a - b - c;
    res[6] = a - b * c;
    res[7] = a - b / c;
    res[8] = a * b + c;
    res[9] = a * b - c;
    res[10] = a * b * c;
    res[11] = a * b / c;
    res[12] = a / b + c;
    res[13] = a / b - c;
    res[14] = a / b * c;
    res[15] = a / b / c;
 
    for (i = 0; i < 16; i++) flags[i] = false;
 
    for (i = 0; i < 16; i++) 
        if (!flags[i]) // если не установлен, значит этого числа еще не было
            for (j = i + 1; j < 16; j++) // ищем равные ему
                if (res[i] == res[j]) flags[j] = true; // нашли - установили ему true, дальше оно обрабатываться не будет
 
    for (i = 0; i < 16; i++) if (!flags[i]) k++; // считаем сколько уникальных чисел
    cout<<k;
    return 0;
}
Ошибка на 51 тесте
Подозреваю, какое-то входящее число 0 и возникает ошибка деления. Но как это обрабатывать? Просто не считать?

Добавлено через 4 часа 57 минут
Мой код неправильно считает количество разных ответов, если среди них есть NaN или Inf.
Yandex
Объявления
13.04.2013, 19:10     Задачи с олимпиады
Ответ Создать тему
Опции темы

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