Добро пожаловать на новую статью по решению алгоритмических задач, в которой я собрал для вас список новых задач из разных источников разной сложности, чтобы каждый смог попробовать в себя в этом увлекательном деле!
Цель статьи заключается в тренировке практик по применению различных алгоритмов, в поддержании навыка "Писать код" в тонусе ну и, само собой, немного поразвлечься!
Что было раньше:
В предыдущей части (нажмите на строку) мы решили:
- Count the number of cubes with paint on (Подсчитайте количество кубиков, на которых нанесена краска.) (Нажмите на строку)
- Logical calculator (Логический калькулятор) (Нажмите на строку)
- Capitalize first letter of a string (Заглавная буква первой буквы строки) (Нажмите на строку)
- Count number of zeros from 1 to N (Подсчитайте количество нулей от 1 до N) (Нажмите на строку)
- Hexagon Beam Max Sum (Максимальная сумма шестигранных балок) (Нажмите на строку)
- Department scheduler [simple] (Планировщик отделов [простой]) (Нажмите на строку)
В этой части вас ждут еще более интересные алгоритмические задачи. Давайте приступим!
Решение новых задач:
Пояснение сложности задач у разных платформ:
Codewars
8 kyu - Самая простая задача
7 kyu - ...
6 kyu - ...
5 kyu - ...
4 kyu - ...
3 kyu - ...
2 kyu - ...
1 kyu - Самая сложная задач
Задача 1
Платформа: CodeWars
Название задачи: Coding 3min : Jumping Dutch act (3 минуты программирования: Прыжковый голландский номер)
Ссылка на задачу: https://www.codewars.com/kata/570bcd9715944a2c8e000009 (Нажмите на строку)
Сложность: 8 (8 / 8) kyu
Уже решили (На момент написания статьи): 575 из 5,144
Тэги: Головоломки, Игры
Оригинальное описание задачи:
Coding 3min : Jumping Dutch act
This is the simple version of Shortest Code series. If you need some challenges, please try the challenge version
Task:
Mr. despair wants to jump off Dutch act, So he came to the top of a building.
Scientific research shows that a man jumped from the top of the roof, when the floor more than 6, the person will often die in an instant; When the floor is less than or equal to 6, the person will not immediately die, he would scream. (without proof)
Input: floor
, The height of the building (floor)
Output: a string, The voice of despair(When jumping Dutch act)
Example:
sc(2) should return "Aa~ Pa! Aa!"
It means:
Mr. despair jumped from the 2 floor, the voice is "Aa~"
He fell on the ground, the voice is "Pa!"
He did not die immediately, and the final voice was "Aa!"
sc(6) should return "Aa~ Aa~ Aa~ Aa~ Aa~ Pa! Aa!"
sc(7) should return "Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Pa!"
sc(10) should return "Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Pa!"
if floor
<=1, Mr. despair is safe, return ""
-
The final advice
Just play in this kata, Don't experiment in real life ;-)
##Series:
- Bug in Apple
- Father and Son
- Jumping Dutch act
- Planting Trees
- Give me the equation
- Find the murderer
- Reading a Book
- Eat watermelon
- Special factor
- Guess the Hat
- Symmetric Sort
- Are they symmetrical?
- Max Value
- Trypophobia
- Virus in Apple
- Balance Attraction
- Remove screws I
- Remove screws II
- Regular expression compression
- Collatz Array(Split or merge)
- Tidy up the room
- Waiting for a Bus
Пояснение задачи:
Задача состоит в симуляции прыжка мистера отчаяния с крыши здания.
Научные исследования показывают, что человек, прыгнувший с высоты более 6 этажей, часто умирает мгновенно.
Если высота меньше или равна 6 этажам, человек не умирает сразу, а кричит.
Вход: этаж, высота здания.
Выход: строка, представляющая голос отчаяния при прыжке.
Примеры:
sc(2) вернет "Aa~ Pa! Aa!": Мистер отчаяние прыгнул с 2 этажа, его крик "Aa~"
Он упал на землю, его крик "Pa!"
Он не умер немедленно, и его последний крик был "Aa!"
sc(6) вернет "Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Pa! Aa!"
sc(7) вернет "Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Pa!"
sc(10) вернет "Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Pa!"
Если этаж меньше или равен 1, мистер отчаяние в безопасности, вернуть пустую строку.
Задача 2
Платформа: CodeWars
Название задачи: Total pressure calculation (Расчет общего давления)
Ссылка на задачу: https://www.codewars.com/kata/5b7ea71db90cc0f17c000a5a (Нажмите на строку)
Сложность: 8 (8 / 8) kyu
Уже решили (На момент написания статьи): 2,883 из 5,662
Тэги: Фундаментальные
Оригинальное описание задачи:
Given the molecular mass of two molecules M1M_1M1R03; and M2M_2M2R03;, their masses present m1m_1m1R03; and m2m_2m2R03; in a vessel of volume V at a specific temperature T, find the total pressure PtotalR03; exerted by the molecules. Formula to calculate the pressure is:
Ptotal=(m1M1+m2M2)RTVR03;
Input
Six values :
- M1R03;, M2R03;: molar masses of both gases, in g⋅mol−1
- m1 and m2: present mass of both gases, in grams (g)
- V: volume of the vessel, in dm3
- T: temperature, in °C
Output
One value: Ptotal, in units of atm.
Notes
Remember: Temperature is given in Celsius while SI unit is Kelvin (K). 0°C=273.15K
The gas constant R=0.082dm3⋅atm⋅K−1⋅mol−1
Пояснение задачи:
Задача заключается в расчёте общего давления, оказываемого смесью двух газов в сосуде объёмом V при температуре T. Давление рассчитывается по формуле:
Ptotal=(m1M1+m2M2)RT
где:
M1 и M2 — молярные массы газов, выраженные в граммах на моль (g/mol)
m1 и m2 — массы газов в граммах (g)
R — универсальная газовая постоянная, равная R=0.082dm3⋅atm⋅K−1⋅mol−1
T — температура в градусах Цельсия (°C), которую нужно перевести в Кельвины (K) по формуле
T(K)=T(°C)+273.15,
V — объём сосуда в дециметрах кубических (dm3).
На выходе нужно получить давление Ptotal в атмосферах (atm).
Задача 3
Платформа: CodeWars
Название задачи: Driving School Series #1 (Серия "Автошкола №1")
Ссылка на задачу: https://www.codewars.com/kata/58999425006ee3f97c00011f (Нажмите на строку)
Сложность: 7 (7 / 8) kyu
Уже решили (На момент написания статьи): 787 из 2,442
Тэги: Фундаментальные
Оригинальное описание задачи:
Every month, a random number of students take the driving test at Fast & Furious (F&F) Driving School. To pass the test, a student cannot accumulate more than 18 demerit points.
At the end of the month, F&F wants to calculate the average demerit points accumulated by ONLY the students who have passed, rounded to the nearest integer.
Write a function which would allow them to do so. If no students passed the test that month, return 'No pass scores registered.'.
Example:
[10,10,10,18,20,20] --> 12
Пояснение задачи:
Задача заключается в написании функции, которая вычисляет среднее количество штрафных баллов, накопленных студентами, сдавшими экзамен по вождению.
Студент сдает экзамен, если набрал не более 18 штрафных баллов.
Если никто не сдал экзамен, функция должна вернуть сообщение "No pass scores registered.".
Пример:
Входной массив: [10, 10, 10, 18, 20, 20]
Студенты с баллами 10, 10, 10 и 18 сдали экзамен.
Среднее значение: (10 + 10 + 10 + 18) / 4 = 12
Задача 4
Платформа: CodeWars
Название задачи: Anagram Detection (Обнаружение анаграммы)
Ссылка на задачу: https://www.codewars.com/kata/529eef7a9194e0cbc1000255 (Нажмите на строку)
Сложность: 7 (7 / 8) kyu
Уже решили (На момент написания статьи): 14,403 из 49,685
Тэги: Строки, Фундаментальные
Оригинальное описание задачи:
An anagram is the result of rearranging the letters of a word to produce a new word (see wikipedia).
Note: anagrams are case insensitive
Complete the function to return true
if the two arguments given are anagrams of each other; return false
otherwise.
Examples
-
"foefet"
is an anagram of "toffee"
-
"Buckethead"
is an anagram of "DeathCubeK"
Пояснение задачи:
Анограмма — это слово, получаемое перестановкой букв другого слова.
Задача состоит в написании функции, которая проверяет, являются ли два слова анограммами друг друга, независимо от регистра символов.
Примеры:
"foefet" является анограммой слова "toffee".
"Buckethead" является анограммой слова "DeathCubeK".
Задача 5
Платформа: CodeWars
Название задачи: Make That Move (Сделай Этот Ход)
Ссылка на задачу: https://www.codewars.com/kata/6611b3ccb42a1927e9663bf7 (Нажмите на строку)
Сложность: 6 (6 / 8) kyu
Уже решили (На момент написания статьи): 19 из 82
Тэги: Алгоритмы, Симуляция, Строки
Оригинальное описание задачи:
Task
Given a string s
portraying a surface like '.......'
, you start on the left-most edge and face to the right. You continue to move until you either:
- exit the surface
- end up in an infinite cycle
- reach an oracle
Tiles
The surface consists of several tiles:
'.'
: on a regular surface you continue to walk in your current direction
'o'
: when reaching an oracle, the simulation ends
- jump-points
'p'
: jump to the next 'p'
on the right, face right and walk one tile to the right
'q'
: jump to the next 'q'
on the left, face left and walk one tile to the left
- if no other similar jump-point is available in the direction of the current jump-point, exit the surface in that direction
- you exit the surface if you jump to a jump-point on the edge of the surface
Output
- when reaching an oracle
'o'
, return 'o'
- when you exit the surface to the left, return
'q'
- when you exit the surface to the right, return
'p'
- when encountering an infinite cycle, return
'x'
Constraints
- 550 random tests (50 on biggest surfaces)
1 <= size of surface <= 100000
Examples
surface | expected result
-----------------------------------------
"....." "p" # walk on surface and exit to the right
"..o.." "o" # walk towards oracle
"p...." "p" # jump beyond the edge of the surface to the right
"q...." "q" # jump beyond the edge of the surface to the left
"....p" "p" # walk and then jump beyond the edge of the surface to the right
"....q" "q" # walk and then jump beyond the edge of the surface to the left
"p..o." "p" # jump over the oracle beyond the edge of the surface to the right
"....p............p...." "p" # jump over the next 'p' and exit the surface walking to the right
"....p............p..q." "q" # jump over the next 'p' reaching 'q' and jump beyond the edge of the surface to the left
"....p......q.....p..q." "x" # jump over the next 'p' reaching 'q', then jump over the other 'q', reaching the initial 'p' again, creating an infinite cycle
"....p...o..q.....p..q." "o" # jump over the next 'p' reaching 'q', then jump over the other 'q', and walk towards the oracle
".q..p............p..q." "q" # jump beyond the edge of the surface to the left
Пояснение задачи:
Задача заключается в симуляции перемещения по поверхности, состоящей из различных типов плиток.
Начав с левого края, вы двигаетесь направо, пока не произойдёт одно из событий:
1. Вы покинете поверхность.
2. Попадёте в бесконечный цикл.
3. Достигнете оракула.
Типы плиток:
- `.`: обычная поверхность, продолжаете движение вперёд.
- `o`: достижение оракула останавливает симуляцию.
- `p`: переходите к следующей правой плитке `p`, поворачиваясь направо и продвигаясь на одну плитку.
- `q`: переходите к следующей левой плитке `q`, поворачиваясь налево и продвигаясь на одну плитку.
Выходы:
- `o`: достигли оракула.
- `q`: вышли слева.
- `p`: вышли справа.
- `x`: попали в бесконечный цикл.
Примеры:
- `"....."` → `p` (проходим по поверхности и выходим направо).
- `"..o.."` → `o` (двигаемся к оракулу).
- `"p...."` → `p` (перепрыгиваем край поверхности направо).
- `"q...."` → `q` (перепрыгиваем край поверхности налево).
- `"....p"` → `p` (идем вперед и перепрыгиваем край поверхности направо).
- `"....q"` → `q` (идем вперед и перепрыгиваем край поверхности налево).
- `"p..o."` → `p` (перепрыгиваем оракула и выходим направо).
- `"....p............p...."` → `p` (перепрыгиваем следующую плитку `p` и выходим направо).
- `"....p............p..q."` → `q` (перепрыгиваем следующую плитку `p`, достигаем `q` и выходим налево).
- `"....p......q.....p..q."` → `x` (создаём бесконечный цикл, перепрыгивая между `p` и `q`).
- `"....p...o..q.....p..q."` → `o` (перепрыгиваем плитку `p`, достигаем `q`, идём к оракулу).
- `".q..p............p..q."` → `q` (перепрыгиваем край поверхности налево).
Задача 6
Платформа: CodeWars
Название задачи: Simple Fun #335: Two Programmers And Gold (Простая забава #335: Два программиста и Золото)
Ссылка на задачу: https://www.codewars.com/kata/59549d482a68fe3bc2000146 (Нажмите на строку)
Сложность: 5 (5 / 8) kyu
Уже решили (На момент написания статьи): 116 из 307
Тэги: Производительность, Алгоритмы
Оригинальное описание задачи:
Task
In the field, two programmers A and B found some gold at the same time. They all wanted the gold, and they decided to use the following rules to distribute gold:
They divided gold into n piles and be in line. The amount of each pile and the order of piles all are randomly.
They took turns to take away a pile of gold from the far left or the far right.
In each round, the programmer will use his wisdom to choose the gold that is best for him.
Input
A list* of integers representing gold.
Output
Calculated final amount of gold obtained by A and B in a tuple* ( amount of A, amount of B ).
*list / tuple representation varies with language - see Example tests
Note, we can assume that A always takes first, and each time they used the best strategy.
Example
For gold = [10,1000,2,1]
, the output should be [1001,12]
.
At 1st turn, A can take 10 or 1, 10 is greater than 1.
Should we choose 10? No, clever programmer don't think so ;-)
Because if A choose 10, next turn B can choose 1000.
So, A choose 1 is the best choice.
At 2nd turn, Whether B chooses 10 or 2, in the 3rd turn, A can always choose 1000.
So, B choose 10 is the best choice.
Final result:
A: 1 + 1000 = 1001
B: 10 + 2 = 12
For golds = [10,1000,2]
, the output should be [12,1000]
.
In this example, the choice A faces is the same as the 2nd turn in the previous example.
Пояснение задачи:
Два программиста нашли золото и решили разделить его следующим образом: золото разделили на несколько кучек, порядок которых случаен.
Они по очереди берут одну кучу золота с любого конца ряда.
Задача состоит в том, чтобы рассчитать, какое количество золота получит каждый программист, если они используют оптимальную стратегию выбора.
Пример:
Для золотого ряда `[10, 1000, 2, 1]`.
Первый ход делает программист A.
Он выбирает между 10 и 1.
Если выберет 10, то на следующем ходу программист B возьмет 1000.
Поэтому A выбирает 1.
Программист B выбирает между 10 и 2.
Независимо от выбора, на третьем ходу A возьмет 1000.
Программист B берет 10.
Результат:
A: 1 + 1000 = 1001
B: 10 + 2 = 12
Новое в конфигурации Algo1C:

https://github.com/SalavatovNabiulla/Algo1C
- 0.5 : Добавлена возможность выбирать контекст исполнения кода, например: НаСервере или НаКлиенте
- 0.4 : Исправлена ошибка при выводе содержимого исключения
- 0.3 : Добавлена возможность сохранять и загружать задачи; Внесены небольшие изменения в интерфейс
- 0.2 : Исправлена ошибка при выводе результата (Отдельная благодарность SAShikutkin)
Заключение:
Codewars
8 kyu - Самая простая задача
7 kyu - ...
6 kyu - ...
5 kyu - ...
4 kyu - ...
3 kyu - ...
2 kyu - ...
1 kyu - Самая сложная задач
Платформа: CodeWars
Название задачи: Coding 3min : Jumping Dutch act (3 минуты программирования: Прыжковый голландский номер)
Ссылка на задачу: https://www.codewars.com/kata/570bcd9715944a2c8e000009 (Нажмите на строку)
Сложность: 8 (8 / 8) kyu
Уже решили (На момент написания статьи): 575 из 5,144
Тэги: Головоломки, Игры
Оригинальное описание задачи:
Coding 3min : Jumping Dutch act
This is the simple version of Shortest Code series. If you need some challenges, please try the challenge version
Task:
Mr. despair wants to jump off Dutch act, So he came to the top of a building.
Scientific research shows that a man jumped from the top of the roof, when the floor more than 6, the person will often die in an instant; When the floor is less than or equal to 6, the person will not immediately die, he would scream. (without proof)
Input:
floor
, The height of the building (floor)Output: a string, The voice of despair(When jumping Dutch act)
Example:
sc(2) should return
"Aa~ Pa! Aa!"
It means:
Mr. despair jumped from the 2 floor, the voice is "Aa~" He fell on the ground, the voice is "Pa!" He did not die immediately, and the final voice was "Aa!"
sc(6) should return
"Aa~ Aa~ Aa~ Aa~ Aa~ Pa! Aa!"
sc(7) should return
"Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Pa!"
sc(10) should return
"Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Pa!"
if
floor
<=1, Mr. despair is safe, return""
The final advice
Just play in this kata, Don't experiment in real life ;-)
##Series:
- Bug in Apple
- Father and Son
- Jumping Dutch act
- Planting Trees
- Give me the equation
- Find the murderer
- Reading a Book
- Eat watermelon
- Special factor
- Guess the Hat
- Symmetric Sort
- Are they symmetrical?
- Max Value
- Trypophobia
- Virus in Apple
- Balance Attraction
- Remove screws I
- Remove screws II
- Regular expression compression
- Collatz Array(Split or merge)
- Tidy up the room
- Waiting for a Bus
Пояснение задачи:
Задача состоит в симуляции прыжка мистера отчаяния с крыши здания.
Научные исследования показывают, что человек, прыгнувший с высоты более 6 этажей, часто умирает мгновенно.
Если высота меньше или равна 6 этажам, человек не умирает сразу, а кричит.
Вход: этаж, высота здания.
Выход: строка, представляющая голос отчаяния при прыжке.
Примеры:
sc(2) вернет "Aa~ Pa! Aa!": Мистер отчаяние прыгнул с 2 этажа, его крик "Aa~"
Он упал на землю, его крик "Pa!"
Он не умер немедленно, и его последний крик был "Aa!"
sc(6) вернет "Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Pa! Aa!"
sc(7) вернет "Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Pa!"
sc(10) вернет "Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Aa~ Pa!"
Если этаж меньше или равен 1, мистер отчаяние в безопасности, вернуть пустую строку.
Платформа: CodeWars
Название задачи: Total pressure calculation (Расчет общего давления)
Ссылка на задачу: https://www.codewars.com/kata/5b7ea71db90cc0f17c000a5a (Нажмите на строку)
Сложность: 8 (8 / 8) kyu
Уже решили (На момент написания статьи): 2,883 из 5,662
Тэги: Фундаментальные
Оригинальное описание задачи:
Given the molecular mass of two molecules M1M_1M1R03; and M2M_2M2R03;, their masses present m1m_1m1R03; and m2m_2m2R03; in a vessel of volume V at a specific temperature T, find the total pressure PtotalR03; exerted by the molecules. Formula to calculate the pressure is:
Ptotal=(m1M1+m2M2)RTVR03;Input
Six values :
- M1R03;, M2R03;: molar masses of both gases, in g⋅mol−1
- m1 and m2: present mass of both gases, in grams (g)
- V: volume of the vessel, in dm3
- T: temperature, in °C
Output
One value: Ptotal, in units of atm.
Notes
Remember: Temperature is given in Celsius while SI unit is Kelvin (K). 0°C=273.15K
The gas constant R=0.082dm3⋅atm⋅K−1⋅mol−1
Пояснение задачи:
Задача заключается в расчёте общего давления, оказываемого смесью двух газов в сосуде объёмом V при температуре T. Давление рассчитывается по формуле:
Ptotal=(m1M1+m2M2)RT
где:
M1 и M2 — молярные массы газов, выраженные в граммах на моль (g/mol)
m1 и m2 — массы газов в граммах (g)
R — универсальная газовая постоянная, равная R=0.082dm3⋅atm⋅K−1⋅mol−1
T — температура в градусах Цельсия (°C), которую нужно перевести в Кельвины (K) по формуле
T(K)=T(°C)+273.15,
V — объём сосуда в дециметрах кубических (dm3).
На выходе нужно получить давление Ptotal в атмосферах (atm).
Платформа: CodeWars
Название задачи: Driving School Series #1 (Серия "Автошкола №1")
Ссылка на задачу: https://www.codewars.com/kata/58999425006ee3f97c00011f (Нажмите на строку)
Сложность: 7 (7 / 8) kyu
Уже решили (На момент написания статьи): 787 из 2,442
Тэги: Фундаментальные
Оригинальное описание задачи:
Every month, a random number of students take the driving test at Fast & Furious (F&F) Driving School. To pass the test, a student cannot accumulate more than 18 demerit points.
At the end of the month, F&F wants to calculate the average demerit points accumulated by ONLY the students who have passed, rounded to the nearest integer.
Write a function which would allow them to do so. If no students passed the test that month, return 'No pass scores registered.'.
Example:
[10,10,10,18,20,20] --> 12
Пояснение задачи:
Задача заключается в написании функции, которая вычисляет среднее количество штрафных баллов, накопленных студентами, сдавшими экзамен по вождению.
Студент сдает экзамен, если набрал не более 18 штрафных баллов.
Если никто не сдал экзамен, функция должна вернуть сообщение "No pass scores registered.".
Пример:
Входной массив: [10, 10, 10, 18, 20, 20]
Студенты с баллами 10, 10, 10 и 18 сдали экзамен.
Среднее значение: (10 + 10 + 10 + 18) / 4 = 12
Платформа: CodeWars
Название задачи: Anagram Detection (Обнаружение анаграммы)
Ссылка на задачу: https://www.codewars.com/kata/529eef7a9194e0cbc1000255 (Нажмите на строку)
Сложность: 7 (7 / 8) kyu
Уже решили (На момент написания статьи): 14,403 из 49,685
Тэги: Строки, Фундаментальные
Оригинальное описание задачи:
An anagram is the result of rearranging the letters of a word to produce a new word (see wikipedia).
Note: anagrams are case insensitive
Complete the function to return
true
if the two arguments given are anagrams of each other; returnfalse
otherwise.Examples
"foefet"
is an anagram of"toffee"
"Buckethead"
is an anagram of"DeathCubeK"
Пояснение задачи:
Анограмма — это слово, получаемое перестановкой букв другого слова.
Задача состоит в написании функции, которая проверяет, являются ли два слова анограммами друг друга, независимо от регистра символов.
Примеры:
"foefet" является анограммой слова "toffee".
"Buckethead" является анограммой слова "DeathCubeK".
Платформа: CodeWars
Название задачи: Make That Move (Сделай Этот Ход)
Ссылка на задачу: https://www.codewars.com/kata/6611b3ccb42a1927e9663bf7 (Нажмите на строку)
Сложность: 6 (6 / 8) kyu
Уже решили (На момент написания статьи): 19 из 82
Тэги: Алгоритмы, Симуляция, Строки
Оригинальное описание задачи:
Task
Given a string
s
portraying a surface like'.......'
, you start on the left-most edge and face to the right. You continue to move until you either:
- exit the surface
- end up in an infinite cycle
- reach an oracle
Tiles
The surface consists of several tiles:
'.'
: on a regular surface you continue to walk in your current direction'o'
: when reaching an oracle, the simulation ends- jump-points
'p'
: jump to the next'p'
on the right, face right and walk one tile to the right'q'
: jump to the next'q'
on the left, face left and walk one tile to the left- if no other similar jump-point is available in the direction of the current jump-point, exit the surface in that direction
- you exit the surface if you jump to a jump-point on the edge of the surface
Output
- when reaching an oracle
'o'
, return'o'
- when you exit the surface to the left, return
'q'
- when you exit the surface to the right, return
'p'
- when encountering an infinite cycle, return
'x'
Constraints
- 550 random tests (50 on biggest surfaces)
1 <= size of surface <= 100000
Examples
surface | expected result ----------------------------------------- "....." "p" # walk on surface and exit to the right "..o.." "o" # walk towards oracle "p...." "p" # jump beyond the edge of the surface to the right "q...." "q" # jump beyond the edge of the surface to the left "....p" "p" # walk and then jump beyond the edge of the surface to the right "....q" "q" # walk and then jump beyond the edge of the surface to the left "p..o." "p" # jump over the oracle beyond the edge of the surface to the right "....p............p...." "p" # jump over the next 'p' and exit the surface walking to the right "....p............p..q." "q" # jump over the next 'p' reaching 'q' and jump beyond the edge of the surface to the left "....p......q.....p..q." "x" # jump over the next 'p' reaching 'q', then jump over the other 'q', reaching the initial 'p' again, creating an infinite cycle "....p...o..q.....p..q." "o" # jump over the next 'p' reaching 'q', then jump over the other 'q', and walk towards the oracle ".q..p............p..q." "q" # jump beyond the edge of the surface to the left
Пояснение задачи:
Задача заключается в симуляции перемещения по поверхности, состоящей из различных типов плиток.
Начав с левого края, вы двигаетесь направо, пока не произойдёт одно из событий:
1. Вы покинете поверхность.
2. Попадёте в бесконечный цикл.
3. Достигнете оракула.
Типы плиток:
- `.`: обычная поверхность, продолжаете движение вперёд.
- `o`: достижение оракула останавливает симуляцию.
- `p`: переходите к следующей правой плитке `p`, поворачиваясь направо и продвигаясь на одну плитку.
- `q`: переходите к следующей левой плитке `q`, поворачиваясь налево и продвигаясь на одну плитку.
Выходы:
- `o`: достигли оракула.
- `q`: вышли слева.
- `p`: вышли справа.
- `x`: попали в бесконечный цикл.
Примеры:
- `"....."` → `p` (проходим по поверхности и выходим направо).
- `"..o.."` → `o` (двигаемся к оракулу).
- `"p...."` → `p` (перепрыгиваем край поверхности направо).
- `"q...."` → `q` (перепрыгиваем край поверхности налево).
- `"....p"` → `p` (идем вперед и перепрыгиваем край поверхности направо).
- `"....q"` → `q` (идем вперед и перепрыгиваем край поверхности налево).
- `"p..o."` → `p` (перепрыгиваем оракула и выходим направо).
- `"....p............p...."` → `p` (перепрыгиваем следующую плитку `p` и выходим направо).
- `"....p............p..q."` → `q` (перепрыгиваем следующую плитку `p`, достигаем `q` и выходим налево).
- `"....p......q.....p..q."` → `x` (создаём бесконечный цикл, перепрыгивая между `p` и `q`).
- `"....p...o..q.....p..q."` → `o` (перепрыгиваем плитку `p`, достигаем `q`, идём к оракулу).
- `".q..p............p..q."` → `q` (перепрыгиваем край поверхности налево).
Платформа: CodeWars
Название задачи: Simple Fun #335: Two Programmers And Gold (Простая забава #335: Два программиста и Золото)
Ссылка на задачу: https://www.codewars.com/kata/59549d482a68fe3bc2000146 (Нажмите на строку)
Сложность: 5 (5 / 8) kyu
Уже решили (На момент написания статьи): 116 из 307
Тэги: Производительность, Алгоритмы
Оригинальное описание задачи:
Task
In the field, two programmers A and B found some gold at the same time. They all wanted the gold, and they decided to use the following rules to distribute gold:
They divided gold into n piles and be in line. The amount of each pile and the order of piles all are randomly.
They took turns to take away a pile of gold from the far left or the far right.
In each round, the programmer will use his wisdom to choose the gold that is best for him.
Input
A list* of integers representing gold.
Output
Calculated final amount of gold obtained by A and B in a tuple* ( amount of A, amount of B ).
*list / tuple representation varies with language - see Example tests
Note, we can assume that A always takes first, and each time they used the best strategy.
Example
For
gold = [10,1000,2,1]
, the output should be[1001,12]
.At 1st turn, A can take 10 or 1, 10 is greater than 1. Should we choose 10? No, clever programmer don't think so ;-) Because if A choose 10, next turn B can choose 1000. So, A choose 1 is the best choice. At 2nd turn, Whether B chooses 10 or 2, in the 3rd turn, A can always choose 1000. So, B choose 10 is the best choice. Final result: A: 1 + 1000 = 1001 B: 10 + 2 = 12
For
golds = [10,1000,2]
, the output should be[12,1000]
.In this example, the choice A faces is the same as the 2nd turn in the previous example.
Пояснение задачи:
Два программиста нашли золото и решили разделить его следующим образом: золото разделили на несколько кучек, порядок которых случаен.
Они по очереди берут одну кучу золота с любого конца ряда.
Задача состоит в том, чтобы рассчитать, какое количество золота получит каждый программист, если они используют оптимальную стратегию выбора.
Пример:
Для золотого ряда `[10, 1000, 2, 1]`.
Первый ход делает программист A.
Он выбирает между 10 и 1.
Если выберет 10, то на следующем ходу программист B возьмет 1000.
Поэтому A выбирает 1.
Программист B выбирает между 10 и 2.
Независимо от выбора, на третьем ходу A возьмет 1000.
Программист B берет 10.
Результат:
A: 1 + 1000 = 1001
B: 10 + 2 = 12
https://github.com/SalavatovNabiulla/Algo1C
- 0.5 : Добавлена возможность выбирать контекст исполнения кода, например: НаСервере или НаКлиенте
- 0.4 : Исправлена ошибка при выводе содержимого исключения
- 0.3 : Добавлена возможность сохранять и загружать задачи; Внесены небольшие изменения в интерфейс
- 0.2 : Исправлена ошибка при выводе результата (Отдельная благодарность SAShikutkin)
Ну что ж, пока на этом всё, надеюсь, статья была увлекательной для вас, благодарю за внимание.
Подключайтесь к решению алгоритмических задач вместе со мной, делитесь вашим мнением и решениями в комментариях, сохраняя при этом позитивный настрой!
Увидимся в новой статье!