В класната стая децата седят на столове, подредени в кръг. Те чакат нещо. По техните лъчезарни очи можем да усетим, че те чакат нещо добро. Вероятно няма да е хартия. Те са нетърпеливо смачкани и много вече се слюнка. Чакат ли някаква храна? За бъркотия? Или те чакат най-голямото съкровище от всички лакомства, самият шоколад?
Да, учителят скоро ще дойде в стаята и ще им донесе шоколад. За съжаление шоколадът е само един 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) и всеки яде.
Защото училищата имат малко пари
Качване
Трябва да сте влезли, за да качите
Въпроси и дискусия
В края на кръга ще имате възможност да обсъдите решения в дискусия под моделно решение.