Problem Name: Problem F: Cosmic Market
Problem Description: Cosmic Market, also known as Kosumike, is the largest doujinshi convention in the entire universe. Fans of all genres gather at Kosumike. In recent years, the number of visitors to Kosumike has been increasing. Since it is dangerous if everyone can enter at the same time, admission restrictions are enforced immediately after the opening of the event. Only a certain number of people are allowed to enter at the same time, and the rest have to wait for a while before they can enter.
However, if admission is on a first-come-first-served basis, people will start lining up overnight from the day before. Since there are many minors among the participants of Kosumike, there is also a problem with security, so choosing by first-come-first-served is not a good idea. For this reason, Kosumike has a certain kind of game among the participants, and the people who survived the game will be given the right to enter first. To ensure fairness, a random game with a high degree of randomness is adopted every year.
I plan to participate in Kosumike this time, too. There is a doujinshi that I absolutely must get at this year's Kosumike. It is a doujinshi dealing with the anime of a popular magical girl that was talked about in the spring of this year, which is distributed by a certain popular circle. However, this circle is very popular and the distribution is always over soon. It will be almost impossible to get it if I can't enter at the same time as the opening. Of course, it will definitely be available at a later date in a doujin shop, etc. However, I cannot endure until then. I must get it on the day of Kosumike, no matter what. Unfortunately, I have never been the first to enter Kosumike in all the previous years.
According to the catalog of Kosumike, the following game will be used to select the person who enters first. First, a certain number of people,
r
×
c
, among the participants will sit wherever they like in a grid of
r
×
c
seats. Since the positions can be chosen in the order of arrival, those who come early will have more choices. When
r
×
c
people have sat down, the game will begin. In this game, a certain number of times, all the people in a certain column (or row) will be instructed to sit down or stand up. Those who are already seated should remain seated if they are instructed to sit down, and those who are standing should do the same. The column (or row) targeted by the instruction and the content of the instruction are determined randomly by a roulette. Only those who are standing at the end of a certain number of instructions will be the first to enter. Since the participants do not know how many times the instructions will be given, they do not know when the game will end. Therefore, it is emphasized in the catalog that they can enjoy the thrill of it.
At 1:00 p.m. on the day before Kosumike, I obtained all the data about this year's game. According to the information I obtained, the number of instructions,
q
, has already been decided. Moreover, all
q
instructions are already determined. Although it is said that it is highly random, it was a lie. I don't know why it was decided in advance. However, this information is like a gift from heaven