Възлагане
В класната стая децата седят на столове, подредени в кръг. Те чакат нещо. По техните лъчезарни очи можем да усетим, че те чакат нещо добро. Вероятно няма да е хартия. Те са нетърпеливо смачкани и много вече се слюнка. Чакат ли някаква храна? За бъркотия? Или те чакат най-голямото съкровище от всички лакомства, самият шоколад?
Да, учителят скоро ще дойде в стаята и ще им донесе шоколад. За съжаление шоколадът е само един 1, така че децата ще трябва да споделят шоколад. Някои може дори да не успеят.
Помогнете на учителя да разбере колко деца могат да ядат от шоколад.
Задачата
Шоколадовата маса се състои от \ (r \) редове и \ (s \) колони с шоколадови кубчета. Учителят започва с връчването на шоколада на дете в кръг. Детето отчупва или един ред, или една колона шоколад и дава останалото на детето, седнало отдясно.
Момчетата са ненаситни и винаги, когато получат шоколад, отчупват колкото се може повече парче. Така че, когато шоколадът има повече редове, отколкото колони, те разбиват една колона, в противен случай разбиват един ред.
Момичетата не са толкова алчни и освен това искат да запазят тънка линия. Следователно те отчупват възможно най-малкото парче, също един ред или една колона, но избират това, което има по-малко кубчета шоколад.
Разберете колко деца остават без шоколад, ако учителят избере с кое дете да започне. Детето се брои само веднъж, дори ако пропусне шоколада повече от веднъж.
Формат на въвеждане
Първият ред съдържа броя класове \ (t \), в които този проблем трябва да бъде решен. На всеки от следващите редове \ (t \) има описание на един клас, състоящ се от числата \ (r \), \ (s \) и низа \ (Z \) .
Шоколадът има размерите на \ (r \ times s \) кубчета. \ (Z \) е низ, състоящ се от буквите „C“ и „D“, описващи кои деца са момчета и кои момичета.
Буквите "C" означават момчета и "D" момичета, като детето седи най-близо до дъската в първата позиция на низа \ (Z \), а детето седи отдясно на детето във втората позиция, след това дете, седнало отдясно на другия и т.н. Първото дете от веригата също седи вдясно от последното дете.
Ограниченията за размера на входа са както следва:
Броят на редовете и броят на колоните на всеки шоколад е най-малко \ (1 \) и най-много \ (10 ^ 6 \). Във всеки клас има най-малко \ (1 \) ученици и най-много \ (10 ^ 6 \) ученици.
Броят на класовете е най-много \ (10 ^ 6 \) и освен това има най-много \ (10 ^ 7 \) ученици във всички класове заедно. Всички шоколадови бонбони заедно имат най-много \ (10 ^ 7 \) редове и най-много \ (10 ^ 7 \) колони.
В таблицата можете да видите горните граници на броя на класовете \ (t \) и броя на учениците в един клас \ (z \) и броя на редовете \ (r \) и колоните \ (r \) на един шоколад във всеки набор от входове.
| Максимум \ (t \) | \ (50 \) | \ (1 \, 000 \) | \ (10 ^ 6 \) | \ (10 \) | \ (10 ^ 6 \) |
| Максимум \ (z, r, s \) | \ (50 \) | \ (1 \, 000 \) | \ (20 \) | \ (10 ^ 6 \) | \ (10 ^ 6 \) |
Изходен формат
Напишете \ (t \) редове в изхода, за всеки клас напишете колко деца могат да ядат шоколад, ако го разделят по начина, описан в заданието.
Пример
Вход:
Изход:
В трети клас момичетата трябва първо да ядат, защото момчето изяжда целия шоколад, който му идва. В четвърти клас шоколадът е толкова голям, че всеки може да го изяде. В пети клас децата ще се хранят в следния ред: CCDDCDC. По този начин размерите на шоколада ще бъдат (4.4), (4.3), (4.2), (3.2), (2.2), (2.1), (1.1), (0), 0) и всеки яде.
Защото училищата имат малко пари
Ключовата част на решението е да можем да отговорим бързо на такъв въпрос: „ако започнем да раздаваме шоколад от \ (i \) -то дете на \ (j \) -то дете, би ли бил достатъчен шоколадът за нас?"
А именно, ако знаехме това, бихме могли да разрешим проблема, използвайки така наречената техника с два бегача. Вземаме двама бегачи и сядаме и двамата в началото на кръга. Бегачите ще се наричат Иван и Йожо и ще бъдат на позиции \ (i \) и \ (j \). Винаги, когато можем да нахраним децата от позиция \ (i \) до позиция \ (j \), Jožo се премества на следващия квадрат в кръга. В противен случай Иван се движи. Имайте предвид, че Иван никога не изпреварва Йожа, защото можем да храним нула деца. Алгоритъмът приключва, когато Jožo обиколи целия кръг два пъти и решението на проблема ще бъде възможно най-голямото разстояние на бегачите по време на изпълнението на алгоритъма. Помислете защо е така.
Изключението е, че ако отговорът е по-голям от броя на децата, ще изброим само броя на децата.
И двамата бегачи изпълняват най-много \ (2 \ ell \) стъпки, където \ (\ ell \) е размерът на кръга (дължина на низа \ (Z \)), което прави алгоритъма значително по-бърз, отколкото ако тествахме всички \ (O (\ ell ^ 2) \) двойки \ ((i, j) \) .
И така, как да разберете дали част от децата могат да бъдат хранени?
Първо обръщаме шоколада, така че да е поне толкова висок, колкото и широк. След това можем да запазим това свойство през цялата консумация - момчето винаги яде колоната и стеснява шоколада. Ако едно момиче получи шоколад, който е по-висок от по-широкия, то изяжда линия. Ако обаче едно момиче яде шоколад, който е толкова висок, колкото и широк, то яде барче.
Нека разгледаме раздела за деца от \ (i \) до \ (j \). Представете си, че детето \ (i \) -te детето е първото, което яде шоколад. Нека \ (c \) е броят на момчетата в този раздел, \ (d \) броят на момичетата и \ (e \) броят на момичетата, които са изяли блокче шоколад. След това шоколад с размери \ (r \ times s \), където \ ((r \ leq s) \) е достатъчен за деца от \ (i \) до \ (j \), ако \ (e + c \ leq s \) и в същото време \ (de \ leq r \). В противен случай това е същото като проверката на \ (e + c \ leq s \) и \ (c + d \ leq r + s \) .
Намирането на \ (c \) и \ (d \) за някакъв участък от кръг е лесно. Единствената трудна част от тази задача беше да се разбере ефективно \ (д \) .
Имайте предвид, че когато едно момиче е шоколад след момче, това със сигурност не се брои за \ (e \). По същия начин, ако имаме \ (8 \) момичета след \ (8 \) момчета. Интуитивно, за да бъдем големи \ (д \), имаме нужда от много момичета, които да ядат шоколад, без много момчета да ядат шоколад пред тях. По-точно, нека вземем последователностите на деца от позиция \ (i \), до всички възможни позиции \ (k \), \ (k \ leq j \), във всяка последователност броим момичетата и момчетата, и нека \ (f \) е най-голямата от разликите в броя на момичетата минус броя на момчетата. Тогава \ (e = max (0, (s-r + f + 1) // 2) \). (Помислете защо.)
Така че просто трябва да разберем как да изчислим \ (f \). Това може да се направи чрез консумиране на \ (O (\ ell) \) време заедно за изчисляване на всички \ (f \), но е достатъчно по-просто решение, използващо интервално дърво във времето \ (O (\ ell \ log \ ell) \ \), като се използва мулти-набор със същата сложност.
Първо съхраняваме разликата в броя на момичетата и момчетата от началото на кръга до дадената позиция в отделно поле за всяка позиция. За да намерим \ (f \), трябва да знаем максимума на интервала от \ (i \) до \ (j \) в това поле и да извадим стойността на позиция \ (i-1 \) .
Дискусия
Тук можете свободно да обсъждате решението, да споделяте своите парчета код и така нататък.
Трябва да влезете, за да добавяте коментари.