3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82
1

Считалка. Олимпиадная задача по программированию

09.01.2020, 18:36. Показов 2615. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Ирочка попросила маму придумать новую считалочку. Мама тут же ей "выдала".

Пусть в кругу N человек. Это число N будем изменять следующим образом: если число четное, то разделим его на 2, если нечетное, прибавим 1. После нескольких таких изменений мы получаем число 1. На кого попадет один, тот - выходит.

Теперь в кругу N-1 человек. Это число N-1 будем изменять следующим образом: если число четное, то разделим его на 2, если нечетное, прибавим 1. После нескольких таких изменений мы опять получаем число 1 На кого попадет один, тот - выходит.

И т.д.

Кто останется последним, тот и водит. Например, в кругу 3 игрока - N-3. Из числа 3 получается число 4 - первого пропускаем. Из числа 4 получается число 2 - второго пропускаем. Из числа 2 1 юлу чается число 1 - третий выходит. Теперь в кругу 2 игрока - N==2. Из числа 2 получается число 1 - первый выходит. Второй остался один - он водит.

Входные данные: Количество игроков (1<=N<=32000)
Выходные данные: Номер по порядку игрока, кому водить

Пример 1.
Входные данные:
3
Результат:
2

Пример 2.
Входные данные:
4
Результат:
4
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.01.2020, 18:36
Ответы с готовыми решениями:

Олимпиадная задача по программированию. PascalABC.NET. Задача L. Переключение между окнами
Когда пользователь работает в операционной системе Winux, у него часто запущено несколько...

Олимпиадная задача по программированию. PascalABC.NET
Вася с Петей и Колей заработали много денег. Чтобы не мучиться с дележкой, они решили, что сначала...

Олимпиадная задача по программированию. PascalABC.NET
Здравствуйте, я готовлюсь к школьной олимпиаде по информатике, не могу решить задачу (85 баллов из...

Олимпиадная задача по программированию. PascalABC.NET
Найти количество целых решений, удовлетворяющих неравенству: A ≤ B*x + C ≤ D. Формат ввода В...

Олимпиадная задача по программированию
Помогите, пожалуйста c задачей, я смог решить на 80/100 баллов. Условие В этом году третий раз...

11
80 / 33 / 10
Регистрация: 14.06.2019
Сообщений: 516
09.01.2020, 18:47 2
Цитата Сообщение от sadfasfsad Посмотреть сообщение
На кого попадет один
Как это понять? Если я получу единицу, она ни в кого не попадает. Можно, пожалуйста, выдать условие не пересказом?
0
3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82
09.01.2020, 18:50  [ТС] 3
Вроде я ничего не пропустил
Миниатюры
Считалка. Олимпиадная задача по программированию  
0
3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82
09.01.2020, 19:12  [ТС] 4
Подскажите, пожалуйста, правильно ли будет работать эта программа?

Pascal
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
41
42
43
44
45
program task_C;
 
var
  n: integer;
  player: integer;
  players: array of boolean;
 
procedure change(num: integer);
begin
  if num <> 1 Then
  begin
    player := 0;
    while num <> 1 do
    begin
      inc(player);
      if num mod 2 = 0 Then
      begin
        num := num div 2;  
      end
      else
    begin
        inc(num);
      end;
    end;
    n -= 1;
    players[player-1] := False;
    
    change(n);
  end;
end;
 
begin
  readln(n); 
  SetLength(players, n);
  for var i := 0 to players.Length - 1 do
    players[i] := True;
  change(n);
  
  for var i := 0 to players.Length - 1 do
    if players[i] Then
    begin
      writeln(i+1);
      break;
    end;
end.
0
2962 / 1600 / 637
Регистрация: 19.03.2019
Сообщений: 5,232
10.01.2020, 10:00 5
Цитата Сообщение от ProMix0 Посмотреть сообщение
Как это понять? Если я получу единицу, она ни в кого не попадает.
тут фишка в том, что как в обычной считалочке произносятся поочерёдно слова для каждого игрока по кругу, так здесь выполняются вычисления. берём N вычисляем первое число if odd(N) then Inc(N) else N := N div 2;
если получилось 1 - то игрок, на котором это произошло - выбывает.
потом "считалочка" повторяется заново, уже для нового числа игроков (теперь N стало на единицу меньше, т.к. один игрок выбыл)
повторяем, пока не останется один единственный игрок. В задаче нужно определить номер этого игрока (номер - это порядковый номер в самом начале, перед первой считалкой)
1
80 / 33 / 10
Регистрация: 14.06.2019
Сообщений: 516
10.01.2020, 10:35 6
Какое-то странное условие в плане формулировки...
Да, я уже понял, но решить сильно не пытался
1
2962 / 1600 / 637
Регистрация: 19.03.2019
Сообщений: 5,232
10.01.2020, 11:11 7
Цитата Сообщение от sadfasfsad Посмотреть сообщение
Пример 2.
Входные данные:
4
Результат:
4
а кто-нибудь мне может объяснить, как из 4-х игроков по считалке остался водить игрок с номером четыре?
на мой взгляд - это глупость, т.к. игрок выбывает, а его место остаётся и на это место участвует в считалке!

Цитата Сообщение от sadfasfsad Посмотреть сообщение
правильно ли будет работать эта программа?
если считать, что из 4-х игроков по считалке будет водить четвёртый игрок, то да, программа работает верно.
1
Status 418
Эксперт Python
4540 / 2308 / 600
Регистрация: 26.11.2017
Сообщений: 5,240
Записей в блоге: 3
10.01.2020, 13:30 8
Лучший ответ Сообщение было отмечено sadfasfsad как решение

Решение

Цитата Сообщение от mr-Crocodile Посмотреть сообщение
а кто-нибудь мне может объяснить, как из 4-х игроков по считалке остался водить игрок с номером четыре?
дано:
1 2 3 4
2 1 - удаляем 2й

остались:
3 4 1
4 2 1 - удаляем 3й

остались:
3 4
1 - удаляем 1й

остался:
4

счет не прерывается когда кто-то выходит.

Добавлено через 13 минут
mr-Crocodile, вот, но это не решение:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
begin
  var n := ReadInteger;
  var a := ArrGen(n, i -> i + 1).ToList;
  a.Println;
  while a.Count > 1 do
  begin
    n := a.Count;
    Print('Счет:');
    var t := 0;
    while n > 1 do
    begin
      if n mod 2 = 0 then n := n div 2 else n += 1;
      t += 1;
      Print(n)
    end;
    Println;
    Println('Удалить:', t + 'й');
    var k := (t - 1) mod a.Count;
    a := a?[k + 1:] + a?[:k];
    a.Println
  end
end.
2
2962 / 1600 / 637
Регистрация: 19.03.2019
Сообщений: 5,232
10.01.2020, 14:08 9
Цитата Сообщение от eaa Посмотреть сообщение
счет не прерывается когда кто-то выходит.
Спасибо. Именно этот момент и влияет. В условии задачи (тем более олимпиадной), имхо, это должно быть чётко сформулировано.

Добавлено через 14 минут
Цитата Сообщение от eaa Посмотреть сообщение
вот, но это не решение:
а почему, собственно, это не решение? Если убрать промежуточный вывод - то вполне себе решение.

или имеется в виду, что это "грубо" и "неэффективно"? Типа олимпиадные задачи "в лоб" не решают?
1
Status 418
Эксперт Python
4540 / 2308 / 600
Регистрация: 26.11.2017
Сообщений: 5,240
Записей в блоге: 3
10.01.2020, 14:14 10
По времени не пройдет это решение.
1
2962 / 1600 / 637
Регистрация: 19.03.2019
Сообщений: 5,232
10.01.2020, 14:35 11
Цитата Сообщение от eaa Посмотреть сообщение
По времени не пройдет это решение.
ну, так ограничения по времени в условии нет
проверил. на n=32000 ответ примерно через 4 секунды. Если ограничение по времени есть, то не пройдёт.
1
Status 418
Эксперт Python
4540 / 2308 / 600
Регистрация: 26.11.2017
Сообщений: 5,240
Записей в блоге: 3
10.01.2020, 22:46 12
Цитата Сообщение от mr-Crocodile Посмотреть сообщение
на n=32000 ответ примерно через 4 секунды
У меня примерно 3 секунды выполняется.

Переписал решение на удаление элемента по индексу (RemoveAt) из списка (List)
и сделал рекуррентный прекалк за O(n) для счёта, чтобы в цикле не считать постоянно
на n = 32000 выполняется 0.033 секунды, а на n = 320000 выполняется 2.3 секунды.
2
10.01.2020, 22:46
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.01.2020, 22:46
Помогаю со студенческими работами здесь

Олимпиадная задача по программированию
Разъясните кто-нибудь пожалуйста по поводу ограничения по времени и ограничения по памяти в...

Олимпиадная задача по программированию
Помогите написать программу для решения следующей задачи (из Всесибирской Открытой Олимпиады...

Олимпиадная задача по программированию: Таджикские имена
Отсортировать N слов по алфавиту. Разделить по группам те которые заканчиваются на &quot;хон&quot;,...

Олимпиадная задача по программированию.Ошибка в моем коде
Здравствуйте, буду краток, поэтому...задача: Узник пытается бежать из замка, который состоит из MN...

Олимпиадная задача
Не могу решить эту задачу уже 3 дня, не понимаю в чем логика, может быть кто-то догадается и сможет...

Олимпиадная задача №4
Захар любит игры со словами. Но играть одному не интересно, поэтому Захар подсадил на эти игры...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru