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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Керра
1276 / 444 / 45
Регистрация: 24.08.2011
Сообщений: 2,133
#1

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

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

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

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
GuGo1991
267 / 261 / 93
Регистрация: 02.08.2012
Сообщений: 609
01.07.2014, 13:35     Олимпиадная задача с тимуса №1209 #2
Керра, лучше сначала заполнить массив, а потом производить поиск.
Так думаю будет быстрее.
Керра
1276 / 444 / 45
Регистрация: 24.08.2011
Сообщений: 2,133
01.07.2014, 13:56  [ТС]     Олимпиадная задача с тимуса №1209 #3
GuGo1991, для входных данных я вообще массив не использую. А как дополнительные действия могут ускорить программу?
И вообще проблема во вложенном цикле. Известно, что есть какая-то формула, которая сразу что-то вычисляет, без цикла. Но эту формулу я не могу ни найти, ни придумать.
HighPredator
5474 / 1840 / 342
Регистрация: 10.12.2010
Сообщений: 5,430
Записей в блоге: 3
01.07.2014, 13:59     Олимпиадная задача с тимуса №1209 #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;
}
GuGo1991
267 / 261 / 93
Регистрация: 02.08.2012
Сообщений: 609
01.07.2014, 14:32     Олимпиадная задача с тимуса №1209 #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;
}
IrineK
Заблокирован
01.07.2014, 14:53     Олимпиадная задача с тимуса №1209 #6
Если
http://www.cyberforum.ru/cgi-bin/latex.cgi?n = (\sqrt{8k-7}-1)/2
целое, то на позиции k - единица
если нет - то 0
Керра
1276 / 444 / 45
Регистрация: 24.08.2011
Сообщений: 2,133
01.07.2014, 15:24  [ТС]     Олимпиадная задача с тимуса №1209 #7
IrineK, вот откуда эта формула, и почему там какое-то 8, по какой логике это работает?
IrineK
Заблокирован
01.07.2014, 15:48     Олимпиадная задача с тимуса №1209 #8
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Керра,
Работает?

Добавлено через 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
dzrkot
zzzZZZ...
519 / 349 / 53
Регистрация: 11.09.2013
Сообщений: 1,996
01.07.2014, 15:58     Олимпиадная задача с тимуса №1209 #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
Керра
1276 / 444 / 45
Регистрация: 24.08.2011
Сообщений: 2,133
01.07.2014, 19:17  [ТС]     Олимпиадная задача с тимуса №1209 #10
IrineK, благодарю
Trwsdf
Заблокирован
01.07.2014, 19:21     Олимпиадная задача с тимуса №1209 #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.
IrineK
Заблокирован
01.07.2014, 19:25     Олимпиадная задача с тимуса №1209 #12
Цитата Сообщение от Trwsdf Посмотреть сообщение
Изначально надо было решать уравнение -
k=(n*(n-1))/2 +1.
Была решена система
К=(n*(n+1))/2
К = k-1

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

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

Задача про Петю и таксиста с тимуса - C++
Петя любит ездить на такси. Для него это не только удовольствие от быстрой и комфортной поездки, но и возможность всласть поторговаться с...

Олимпиадная задача на перевертыши - C++
Жетоны По случаю организации сотого чемпионата по спортивной рыбалке, администратор рыбхоза Валерий Карпович решил устроить лотерею....

Олимпиадная задача. Деревни - C++
Всем привет.. задача такая: Деревни В тридесятом государстве есть N деревень. Некоторые пары деревень соединены дорогами. В целях...

Олимпиадная задача по программированию - C++
Помогите написать программу для решения следующей задачи (из Всесибирской Открытой Олимпиады Школьников по информатике за 2011-2012 года): ...


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

Или воспользуйтесь поиском по форуму:
IrineK
Заблокирован
01.07.2014, 19:39     Олимпиадная задача с тимуса №1209 #14
Ну дай бог мне и дальше угадывать.
Yandex
Объявления
01.07.2014, 19:39     Олимпиадная задача с тимуса №1209
Ответ Создать тему
Опции темы

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