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

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

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

Показать сообщение отдельно
Керра
Модератор
 Аватар для Керра
1271 / 439 / 45
Регистрация: 24.08.2011
Сообщений: 2,127
01.07.2014, 11:29     Олимпиадная задача с тимуса №1209
Ограничение времени: 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м тесте
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 04:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru