Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
MayaNash
1291 / 461 / 151
Регистрация: 24.08.2011
Сообщений: 2,248
1

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

01.07.2014, 11:29. Просмотров 1226. Ответов 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
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.07.2014, 11:29
Ответы с готовыми решениями:

Задача с тимуса
Вот задача с тимуса, возникли с ней проблемы.Я знаю, что на форуме уже есть решение, но всё-таки...

Задача с тимуса
совсем недавно в программировании встретилась задачка с тимуса 1295 проблема в том что в ней...

задача с Тимуса
http://acm.timus.ru/problem.aspx?space=1&amp;num=1123 Задача на зачет нужна :scratch:

задача с Тимуса
http://acm.timus.ru/problem.aspx?space=1&amp;num=1192

Задача с Тимуса 1446
Всем привет. Я несколько дней бился над задачей с Тимуса. Вот ссыль: вырезано Задача не сложная -...

13
GuGo1991
270 / 264 / 146
Регистрация: 02.08.2012
Сообщений: 609
01.07.2014, 13:35 2
Керра, лучше сначала заполнить массив, а потом производить поиск.
Так думаю будет быстрее.
0
MayaNash
1291 / 461 / 151
Регистрация: 24.08.2011
Сообщений: 2,248
01.07.2014, 13:56  [ТС] 3
GuGo1991, для входных данных я вообще массив не использую. А как дополнительные действия могут ускорить программу?
И вообще проблема во вложенном цикле. Известно, что есть какая-то формула, которая сразу что-то вычисляет, без цикла. Но эту формулу я не могу ни найти, ни придумать.
0
HighPredator
5801 / 2061 / 732
Регистрация: 10.12.2010
Сообщений: 5,871
Записей в блоге: 3
01.07.2014, 13:59 4
Я предлагаю решение вообще в другом ключе: вычисляйте позиции 1 и 0. Так как с каждым увеличением разряда прибавляется только один 0.
Код
int GetDigit(const int pos)
{
  int delta = 0;
  int start = 1; // позиция 1
  int end = 1;  // конец числа
  while pos not in [start..end]
  {
     delta++;
     start = end + 1;
     end = start + delta;
  }
  if pos == start return 1;
  else return 0;
}
1
01.07.2014, 13:59
GuGo1991
270 / 264 / 146
Регистрация: 02.08.2012
Сообщений: 609
01.07.2014, 14:32 5
Керра, формула кажется эта k(k + 1) / 2 + k + 2, поиск точного квадрата.
Должно работать:
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
#include <iostream>
#include <cmath>
#include <conio.h>
 
char value(int index)
{
    if(index == 1) return '1';
    double k;
    k = floor(sqrt(9.0 - 4.0 * (4.0 - 2.0 * index)));
    if(k * k == 9.0 - 4.0 * (4.0 - 2.0 * index)) return '1';
    return '0';
}
 
int main()
{
    int n, index;
    std::string result;
    std::cin >> n;
    while(n > 0)
    {
        std::cin >> index;
        result += value(index);
        result += ' ';
        n--;
    }
    
    std::cout << result;
    
    std::cout << "\nOperation succeeded\n";
    getch();
    return 0;
}
0
IrineK
Заблокирован
01.07.2014, 14:53 6
Если
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (\sqrt{8k-7}-1)/2
целое, то на позиции k - единица
если нет - то 0
0
MayaNash
1291 / 461 / 151
Регистрация: 24.08.2011
Сообщений: 2,248
01.07.2014, 15:24  [ТС] 7
IrineK, вот откуда эта формула, и почему там какое-то 8, по какой логике это работает?
0
IrineK
Заблокирован
01.07.2014, 15:48 8
Лучший ответ Сообщение было отмечено HighPredator как решение

Решение

Керра,
Работает?

Добавлено через 14 минут
Рассмотрим строку
11010010001000 и т.д.
пока будем нумеровать с 0
Единицы стоят на позициях
0 = 0
0+1= 1
0+1+2 = 3
0+1+2+3 = 6
0+1+...+n = n(n+1) / 2
Пусть k - позиция единицы, т.е. n(n+1) / 2 = k
Найдем соответствующее n, решив квадратное уравнение

n^2 + n - 2k = 0
D = 1 + 8k (вот и 8)
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (-1\pm \sqrt{1+8k})/2
Поскольку n>=0
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (\sqrt{1+8k}-1)/2

Теперь внесем поправку на нумерацию k не от 0, а с 1
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (\sqrt{1+8(k-1)}-1)/2
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (\sqrt{8k-7}-1)/2
3
dzrkot
zzzZZZ...
523 / 354 / 94
Регистрация: 11.09.2013
Сообщений: 2,040
01.07.2014, 15:58 9

Не по теме:

я вообще в шоке с таких заданий, особенно после 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
#include <iostream>
using namespace std;
int main()
{
  int y;
  cin>>y;
  char s;
  for(int i=0;i<y;)
    {
      s='1';
      i++;
      int t=i;
      if(i==y)
          break;
      for(int j=0;j<t-1;j++,i++)
        {
        s='0';
        if(i==y)
          break;
        }
    }
cout<<s;
}
Добавлено через 2 минуты
Цитата Сообщение от IrineK Посмотреть сообщение
Рассмотрим строку
11010010001000 и т.д.
пока будем нумеровать с 0
Единицы стоят на позициях
0 = 0
0+1= 1
0+1+2 = 3
0+1+2+3 = 6
0+1+...+n = n(n+1) / 2
Пусть k - позиция единицы, т.е. n(n+1) / 2 = k
Найдем соответствующее n, решив квадратное уравнение
n^2 + n - 2k = 0
D = 1 + 8k (вот и 8)
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (-1\pm \sqrt{1+8k})/2
Поскольку n>0
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (\sqrt{1+8k}-1)/2
Теперь внесем поправку на нумерацию k не от 0, а с 1
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (\sqrt{1+8(k-1)}-1)/2
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (\sqrt{8k-7}-1)/2
0
MayaNash
1291 / 461 / 151
Регистрация: 24.08.2011
Сообщений: 2,248
01.07.2014, 19:17  [ТС] 10
IrineK, благодарю
0
Trwsdf
Заблокирован
01.07.2014, 19:21 11
Цитата Сообщение от IrineK Посмотреть сообщение
Теперь внесем поправку на нумерацию k не от 0, а с 1
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (\sqrt{1+8(k-1)}-1)/2
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (\sqrt{8k-7}-1)/2
Математические подход есть, но формула выведена не правильно, относительно поправки. Поправки не делают методом "тыка", вдруг сработает, делая неочевидные вещи.
Изначально надо было решать уравнение -
k=(n*(n-1))/2 +1.
0
IrineK
Заблокирован
01.07.2014, 19:25 12
Цитата Сообщение от Trwsdf Посмотреть сообщение
Изначально надо было решать уравнение -
k=(n*(n-1))/2 +1.
Была решена система
К=(n*(n+1))/2
К = k-1

Неочевидно?
0
Trwsdf
Заблокирован
01.07.2014, 19:37 13
Цитата Сообщение от IrineK Посмотреть сообщение
Была решена система
К=(n*(n+1))/2
К = k-1
Неочевидно?
вы забыли что у вас в уравнении стоит n+1, а это совсем другое уравнение. Но решение вы угадали да.
0
IrineK
Заблокирован
01.07.2014, 19:39 14
Ну дай бог мне и дальше угадывать.
0
01.07.2014, 19:39
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.07.2014, 19:39

Задача с тимуса №1881
http://acm.timus.ru/problem.aspx?space=1&amp;num=1881 #include &lt;iostream&gt; using std::cin; using...

Задача с тимуса про сороконожку
У сороконожки 40 левых ножек и 40 правых ножек. Под кроватью у сороконожки a левых тапочек и b...

Предохранители. Задача с тимуса №1327
Ограничение времени: 1.0 секунды Ограничение памяти: 64 МБ Янус Полуэктович (не помню уже, А...


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

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

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