In a serious attempt to downsize (reduce) the dole queue, The New National Green Labour Rhinoceros Party has decided on the following strategy. Every day all dole applicants will be placed in a large circle, facing inwards. Someone is arbitrarily chosen as number 1, and the rest are numbered counter-clockwise up to N (who will be standing on 1's left). Starting from 1 and moving counter-clockwise, one labour official counts off k applicants, while another official starts from N and moves clockwise, counting m applicants. The two who are chosen are then sent off for retraining; if both officials pick the same person she (he) is sent off to become a politician. Each official then starts counting again at the next available person and the process continues until no-one is left. Note that the two victims (sorry, trainees) leave the ring simultaneously, so it is possible for one official to count a person already selected by the other official.
Input
Write a program that will successively read in (in that order) the three numbers (N, k and m; k, m > 0, 0 < N < 20) and determine the order in which the applicants are sent off for retraining. Each set of three numbers will be on a separate line and the end of data will be signalled by three zeroes (0 0 0).
Output
For each triplet, output a single line of numbers specifying the order in which people are chosen. Each number should be in a field of 3 characters. For pairs of numbers list the person chosen by the counter-clockwise official first. Separate successive pairs (or singletons) by commas (but there should not be a trailing comma).
Sample input
10 4 3
0 0 0
Sample output
4 8, 9 5, 3 1, 2 6, 10, 7
where represents a space.
题目类型：简单模拟
算法分析：本题类似于约瑟夫问题，按照题目的要求直接进行模拟即可。本题对于顺时针和逆时针运动可以统一用一个函数go来解决，本函数具有较强的技巧性，下面第二个代码是更好的实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
/************************************************** filename :d.cpp author :maksyuki created time :2017/12/5 8:42:29 last modified :2017/12/5 9:21:22 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 66; int N, k, m, v[maxn]; int findv(int p, int cnt) { while(1) { if(cnt == 1) { if(p == N) p = 1; else p++; } else { if(p == 1) p = N; else p--; } if(v[p] != -1) return p; } return -6; } int go(int p, int vv, int cnt) { int ans = p; for(int i = 1; i < vv; i++) ans = findv(ans, cnt); return ans; } int main() { #ifdef LOCAL CFF; //CFO; #endif while(scanf(" %d %d %d", &N, &k, &m) != EOF) { if(!N && !k && !m) break; int tmp = N; int pa = 1, pb = N, va, vb; for(int i = 0; i < maxn; i++) v[i] = i; bool is_first = true; while(tmp) { va = go(pa, k, 1); vb = go(pb, m, -1); if(is_first) is_first = false; else printf(","); if(va == vb) { v[va] = -1; printf("%3d", va); tmp--; } else { v[va] = -1, v[vb] = -1; printf("%3d%3d", va, vb); tmp -= 2; } if(!tmp) break; pa = go(findv(va, 1), 1, 1); pb = go(findv(vb, -1), 1, -1); } puts(""); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <cstdio> #include <iostream> #include <fstream> using namespace std; const int maxn = 66; int a[maxn], n; //bool is_first = true; int go (int start, int step, int flag) { /* if (is_first) step--, is_first = false; */ while (step--) { do { start = (start + flag + n - 1) % n + 1; } while (!a[start]); } return start; } int main() { int k, m; //ifstream cin ("aaa.txt"); while (cin >> n >> k >> m && n && k && m) { int i; for (i = 1; i <= n; i++) a[i] = i; int Aweizhi = 1, Bweizhi = n, leave = n; while (leave) { Aweizhi = go (Aweizhi, m, -1); Bweizhi = go (Bweizhi, k, 1); printf ("%3d", Bweizhi); leave--; if (Aweizhi != Bweizhi) { printf ("%3d", Aweizhi); leave--; } a[Aweizhi] = a[Bweizhi] = 0; if (leave) printf (","); } printf ("\n"); } return 0; } |
- « 上一篇：uva489
- uva512：下一篇 »