tc 147 2 PeopleCircle(再见约瑟夫环) SRM 147 2 600PeopleCircle

Problem Statement

There are numMales males and numFemales females arranged in a circle. Starting from a given point, you count clockwise and remove the K'th person from the circle (where K=1 is the person at the current point, K=2 is the next person in the clockwise direction, etc...). After removing that person, the next person in the clockwise direction becomes the new starting point. After repeating this procedure numFemales times, there are no females left in the circle.

Given numMales, numFemales and K, your task is to return what the initial arrangement of people in the circle must have been, starting from the starting point and in clockwise order.

For example, if there are 5 males and 3 females and you remove every second person, your return String will be "MFMFMFMM".

Definition

PeopleCircle
order
int , int , int
string
string order(int numMales, int numFemales, int K)

(be sure your method is public)

Limits

Time limit (s)2.000
Memory limit (MB)64

Constraints

numMales is between 0 and 25 inclusive
numFemales is between 0 and 25 inclusive
K is between 1 and 1000 inclusive

Test cases

- numMales5
- numFemales3
- K2
Returns"MFMFMFMM"

Return "MFMFMFMM". On the first round you remove the second person - "M_MFMFMM". Your new circle looks like "MFMFMMM" from your new starting point. Then you remove the second person again etc.
- numMales7
- numFemales3
- K1
Returns"FFFMMMMMMM"

Starting from the starting point you remove the first person, then you continue and remove the next first person etc. Clearly, all the females are located at the beginning. Hence return "FFFMMMMMMM"
- numMales25
- numFemales25
- K1000
Returns"MMMMMFFFFFFMFMFMMMFFMFFFFFFFFFMMMMMMMFFMFMMMFMFMMF"

numMales5
numFemales5
K3

Returns"MFFMMFFMFM"

Here we mark the removed people with '_', and the starting position with lower-case:

Number of      | People Remaining
Rounds         | (in initial order)
---------------+-----------------
 0             | mFFMMFFMFM
 1             | MF_mMFFMFM
 2             | MF_MM_fMFM
 3             | MF_MM_FM_m
 4             | M__mM_FM_M
 5             | M__MM__m_M

- numMales1
- numFemales0
- K245
Returns"M"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstring>
  4 #include <ctime>
  5 #include <iostream>
  6 #include <algorithm>
  7 #include <set>
  8 #include <vector>
  9 #include <sstream>
 10 #include <typeinfo>
 11 #include <fstream>
 12 
 13 using namespace std;
 14 char s[2000] ;
 15 vector<int> g ;
 16 int n ;
 17 int k ;
 18 
 19 void dead (int id , int ans , int m)
 20 {
 21     for (int i = ans ; i <= n ; i ++) {
 22         k = m % i ;
 23         id = (id + k) % i ;
 24     }
 25    // printf ("id = %d
" , id ) ;
 26     g.push_back (id) ;
 27 }
 28 
 29 void solve (int fmale , int m)
 30 {
 31     dead (0 , 2 , m ) ;
 32     for (int i = 2 ; i <= n ; i ++) {
 33         k = m % i ;
 34         int id = (0 + k) % i ;
 35         if (id - 1 < 0) id = id - 1 + i ;
 36         else id -- ;
 37         dead (id , i + 1 , m ) ;
 38     }
 39     reverse (g.begin () , g.end ()) ;
 40    // for (int i :g ) printf ("%d " , i) ; puts ("") ;
 41     for (int i = 0 ; i < n ; i ++) {
 42         if (i < fmale) s[g[i]] = 'F' ;
 43         else s[g[i]] = 'M' ;
 44     }
 45     s[n] = '