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

Олимпиадная задача с тимуса №1209 - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Умножение матриц через перегруженный оператор http://www.cyberforum.ru/cpp-beginners/thread1220407.html
функции сложения и вычитания матриц работают правильно, в умножении - выдаёт ошибку сборки
C++ Объединить ветки оператора выбора Ребят, нужна помощь. Последние две ветки необходимо объединить в одну, начиная с c<0. Тоесть если после запятой нет цифр, то... Заранее большое спасибо #include "stdafx.h" #include <stdlib.h>... http://www.cyberforum.ru/cpp-beginners/thread1220397.html
Интегрирование методом левых прямоугольников C++
Доброго времени суток, дорогие программисты. В универе дали задание, а я С++ не особо шарю, помогите пожалуйста выполнить) Задание: "В прикладной программе проводится функция f(x)=cos(x), пределы...
Получить таблицу значений функции C++
Получить таблицу значений функции y=th(x) при x, изменяющемся от -1 до 1 с шагом 0.1. Вычисление значений функции оформить в виде функции. Результаты представить в виде таблицы. Функция...
C++ Прием, передача и сравнение последовательности Баркера http://www.cyberforum.ru/cpp-beginners/thread1220379.html
Подскажите пожалуйста.Пишу программу клиент-сервер. Клиент передает м-последовательность или последовательность Баркера, сервер ее принимает и проверяет правильная ли последовательность пришла, для...
C++ Найти слово, начинающееся буквой "а" и оканчивающееся буквой "я" дана строка. найти какое-нибудь слово, начинающееся буквой а и оканчивающееся буквой я. если таких слов нет, то сообщить об этом подробнее

Показать сообщение отдельно
MayaNash
1285 / 453 / 47
Регистрация: 24.08.2011
Сообщений: 2,214

Олимпиадная задача с тимуса №1209 - C++

01.07.2014, 11:29. Просмотров 818. Ответов 13
Метки (Все метки)

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.

Исходные данные
В первой строке находится целое число N (1 ≤ N ≤ 65535). В i-й из N последующих строк записано целое число Ki — номер позиции в последовательности (1 ≤ Ki ≤ 2^31 − 1).

Результат
Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.

Пример
исходные данные
4
3
14
7
6
результат
0 0 1 0

Мое решение:
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
#include <iostream>
using std::cin;
using std::cout;
 
#define U unsigned int
#define U64 unsigned __int64
 
int main()
{
    U n;
    U64 tek;
    char res[65535];
 
    cin >> n; // количество тестов
    for (U i = 0; i < n; i++)
    {
        cin >> tek; // вводим номер позиции
        for (U64 j = 1; n - j > 0; j++) // пока возможно, отнимаем количество цифр в числах, которые были до текущего
            tek -= j;                   // например, при tek = 10 отнимаем 1 (первое число 1), 2 (второе число 10), 3 (третье число 100) и т.д.
        res[i] = (tek == 1? '1' : '0'); // если после этого нам нужна первая позиция, то нужная цифра - 1, иначе 0
    }
    
    for (int i = 0; i < n; i++)
        cout << res[i] << " ";
    return 0;
}
Ошибка на втором же тесте. В чем дело?

Добавлено через 1 минуту
Цитата Сообщение от Керра Посмотреть сообщение
for (U64 j = 1; n - j > 0; j++)
Затупила тут - очевидно, что должно быть tek - j > 0

Добавлено через 1 минуту
Но теперь почему-то Time limit exceeded

Добавлено через 7 минут
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
#include <iostream>
using std::cin;
using std::cout;
 
#define U unsigned int
#define U64 unsigned __int64
 
int main()
{
    U n;
    U64 tek;
    char res[65535];
 
    cin >> n; // количество тестов
    for (U i = 0; i < n; i++)
    {
        cin >> tek; // вводим номер позиции
        for (U64 j = 1; tek > j; j++) // пока возможно, отнимаем количество цифр в числах, которые были до текущего
            tek -= j;                   // например, при tek = 10 отнимаем 1 (первое число 1), 2 (второе число 10), 3 (третье число 100) и т.д.
        res[i] = (tek == 1? '1' : '0'); // если после этого нам нужна первая позиция, то нужная цифра - 1, иначе 0
    }
    
    for (int i = 0; i < n; i++)
        cout << res[i] << " ";
    return 0;
}
Это уже лучше, но все равно превышение лимита по времени на 3м тесте
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru