首页 > 代码库 > Acdream Chinese Girls' Amusement
Acdream Chinese Girls' Amusement
A - Chinese Girls‘ Amusement
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
SubmitStatus
Problem Description
You must have heard that the Chinese culture is quite different from that of Europe or Russia. So some Chinese habits seem quite unusual or even weird to us.
So it is known that there is one popular game of Chinese girls. N girls stand forming a circle and throw a ball to each other. First girl holding a ball throws it to the K-th girl on her left (1 ≤ K ≤ N/2). That girl catches the ball and in turn throws it to the K-th girl on her left, and so on. So the ball is passed from one girl to another until it comes back to the first girl. If for example N = 7 and K = 3, the girls receive the ball in the following order: 1, 4, 7, 3, 6, 2, 5, 1.
To make the game even more interesting the girls want to choose K as large as possible, but they want one condition to hold: each girl must own the ball during the game.
So it is known that there is one popular game of Chinese girls. N girls stand forming a circle and throw a ball to each other. First girl holding a ball throws it to the K-th girl on her left (1 ≤ K ≤ N/2). That girl catches the ball and in turn throws it to the K-th girl on her left, and so on. So the ball is passed from one girl to another until it comes back to the first girl. If for example N = 7 and K = 3, the girls receive the ball in the following order: 1, 4, 7, 3, 6, 2, 5, 1.
To make the game even more interesting the girls want to choose K as large as possible, but they want one condition to hold: each girl must own the ball during the game.
Input
Input contains one integer number N (3 ≤ N ≤ 102000) — the number of Chinese girls taking part in the game.
Output
Output the only number — K that they should choose.
Sample Input
76
Sample Output
31
Hint
Java is not prepared !
1 /* 2 * this code is made by 987690183 3 * Problem: 1210 4 * Verdict: Accepted 5 * Submission Date: 2014-10-14 13:59:15 6 * Time: 0MS 7 * Memory: 1680KB 8 */ 9 #include<iostream> 10 #include<cstring> 11 #include<iomanip> 12 #include<algorithm> 13 #include<cstdlib> 14 #include<cstdio> 15 using namespace std; 16 17 #define MAXN 9999 18 #define MAXSIZE 1000 19 #define DLEN 4 20 21 class BigNum 22 { 23 private: 24 int a[MAXSIZE]; //可以控制大数的位数 25 int len; //大数长度 26 public: 27 BigNum(){ len = 1;memset(a,0,sizeof(a)); } //构造函数 28 BigNum(const int); //将一个int类型的变量转化为大数 29 BigNum(const char*); //将一个字符串类型的变量转化为大数 30 BigNum(const BigNum &); //拷贝构造函数 31 BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算 32 33 friend istream& operator>>(istream&, BigNum&); //重载输入运算符 34 friend ostream& operator<<(ostream&, BigNum&); //重载输出运算符 35 36 BigNum operator+(const BigNum &) const; //重载加法运算符，两个大数之间的相加运算 37 BigNum operator-(const BigNum &) const; //重载减法运算符，两个大数之间的相减运算 38 BigNum operator*(const BigNum &) const; //重载乘法运算符，两个大数之间的相乘运算 39 BigNum operator/(const int &) const; //重载除法运算符，大数对一个整数进行相除运算 40 41 BigNum operator^(const int &) const; //大数的n次方运算 42 int operator%(const int &) const; //大数对一个int类型的变量进行取模运算 43 bool operator>(const BigNum & T)const; //大数和另一个大数的大小比较 44 bool operator>(const int & t)const; //大数和一个int类型的变量的大小比较 45 46 void print(); //输出大数 47 }; 48 BigNum::BigNum(const int b) //将一个int类型的变量转化为大数 49 { 50 int c,d = b; 51 len = 0; 52 memset(a,0,sizeof(a)); 53 while(d > MAXN) 54 { 55 c = d - (d / (MAXN + 1)) * (MAXN + 1); 56 d = d / (MAXN + 1); 57 a[len++] = c; 58 } 59 a[len++] = d; 60 } 61 BigNum::BigNum(const char*s) //将一个字符串类型的变量转化为大数 62 { 63 int t,k,index,l,i; 64 memset(a,0,sizeof(a)); 65 l=strlen(s); 66 len=l/DLEN; 67 if(l%DLEN) 68 len++; 69 index=0; 70 for(i=l-1;i>=0;i-=DLEN) 71 { 72 t=0; 73 k=i-DLEN+1; 74 if(k<0) 75 k=0; 76 for(int j=k;j<=i;j++) 77 t=t*10+s[j]-‘0‘; 78 a[index++]=t; 79 } 80 } 81 BigNum::BigNum(const BigNum & T) : len(T.len) //拷贝构造函数 82 { 83 int i; 84 memset(a,0,sizeof(a)); 85 for(i = 0 ; i < len ; i++) 86 a[i] = T.a[i]; 87 } 88 BigNum & BigNum::operator=(const BigNum & n) //重载赋值运算符，大数之间进行赋值运算 89 { 90 int i; 91 len = n.len; 92 memset(a,0,sizeof(a)); 93 for(i = 0 ; i < len ; i++) 94 a[i] = n.a[i]; 95 return *this; 96 } 97 istream& operator>>(istream & in, BigNum & b) //重载输入运算符 98 { 99 char ch[MAXSIZE*4];100 int i = -1;101 in>>ch;102 int l=strlen(ch);103 int count=0,sum=0;104 for(i=l-1;i>=0;)105 {106 sum = 0;107 int t=1;108 for(int j=0;j<4&&i>=0;j++,i--,t*=10)109 {110 sum+=(ch[i]-‘0‘)*t;111 }112 b.a[count]=sum;113 count++;114 }115 b.len =count++;116 return in;117 118 }119 /*ostream& operator<<(ostream& out, BigNum& b) //重载输出运算符120 {121 int i;122 cout << b.a[b.len - 1];123 for(i = b.len - 2 ; i >= 0 ; i--)124 {125 cout.width(DLEN);126 cout.fill(‘0‘);127 cout << b.a[i];128 }129 return out;130 }*/131 132 BigNum BigNum::operator+(const BigNum & T) const //两个大数之间的相加运算133 {134 BigNum t(*this);135 int i,big; //位数136 big = T.len > len ? T.len : len;137 for(i = 0 ; i < big ; i++)138 {139 t.a[i] +=T.a[i];140 if(t.a[i] > MAXN)141 {142 t.a[i + 1]++;143 t.a[i] -=MAXN+1;144 }145 }146 if(t.a[big] != 0)147 t.len = big + 1;148 else149 t.len = big;150 return t;151 }152 BigNum BigNum::operator-(const BigNum & T) const //两个大数之间的相减运算153 {154 int i,j,big;155 bool flag;156 BigNum t1,t2;157 if(*this>T)158 {159 t1=*this;160 t2=T;161 flag=0;162 }163 else164 {165 t1=T;166 t2=*this;167 flag=1;168 }169 big=t1.len;170 for(i = 0 ; i < big ; i++)171 {172 if(t1.a[i] < t2.a[i])173 {174 j = i + 1;175 while(t1.a[j] == 0)176 j++;177 t1.a[j--]--;178 while(j > i)179 t1.a[j--] += MAXN;180 t1.a[i] += MAXN + 1 - t2.a[i];181 }182 else183 t1.a[i] -= t2.a[i];184 }185 t1.len = big;186 while(t1.a[len - 1] == 0 && t1.len > 1)187 {188 t1.len--;189 big--;190 }191 if(flag)192 t1.a[big-1]=0-t1.a[big-1];193 return t1;194 }195 196 BigNum BigNum::operator*(const BigNum & T) const //两个大数之间的相乘运算197 {198 BigNum ret;199 int i,j,up;200 int temp,temp1;201 for(i = 0 ; i < len ; i++)202 {203 up = 0;204 for(j = 0 ; j < T.len ; j++)205 {206 temp = a[i] * T.a[j] + ret.a[i + j] + up;207 if(temp > MAXN)208 {209 temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);210 up = temp / (MAXN + 1);211 ret.a[i + j] = temp1;212 }213 else214 {215 up = 0;216 ret.a[i + j] = temp;217 }218 }219 if(up != 0)220 ret.a[i + j] = up;221 }222 ret.len = i + j;223 while(ret.a[ret.len - 1] == 0 && ret.len > 1)224 ret.len--;225 return ret;226 }227 BigNum BigNum::operator/(const int & b) const //大数对一个整数进行相除运算228 {229 BigNum ret;230 int i,down = 0;231 for(i = len - 1 ; i >= 0 ; i--)232 {233 ret.a[i] = (a[i] + down * (MAXN + 1)) / b;234 down = a[i] + down * (MAXN + 1) - ret.a[i] * b;235 }236 ret.len = len;237 while(ret.a[ret.len - 1] == 0 && ret.len > 1)238 ret.len--;239 return ret;240 }241 int BigNum::operator %(const int & b) const //大数对一个int类型的变量进行取模运算242 {243 int i,d=0;244 for (i = len-1; i>=0; i--)245 {246 d = ((d * (MAXN+1))% b + a[i])% b;247 }248 return d;249 }250 BigNum BigNum::operator^(const int & n) const //大数的n次方运算251 {252 BigNum t,ret(1);253 int i;254 if(n<0)255 exit(-1);256 if(n==0)257 return 1;258 if(n==1)259 return *this;260 int m=n;261 while(m>1)262 {263 t=*this;264 for( i=1;i<<1<=m;i<<=1)265 {266 t=t*t;267 }268 m-=i;269 ret=ret*t;270 if(m==1)271 ret=ret*(*this);272 }273 return ret;274 }275 bool BigNum::operator>(const BigNum & T) const //大数和另一个大数的大小比较276 {277 int ln;278 if(len > T.len)279 return true;280 else if(len == T.len)281 {282 ln = len - 1;283 while(a[ln] == T.a[ln] && ln >= 0)284 ln--;285 if(ln >= 0 && a[ln] > T.a[ln])286 return true;287 else288 return false;289 }290 else291 return false;292 }293 bool BigNum::operator >(const int & t) const //大数和一个int类型的变量的大小比较294 {295 BigNum b(t);296 return *this>b;297 }298 299 void BigNum::print() //输出大数300 {301 int i;302 //cout << a[len - 1];303 printf("%d",a[len-1]);304 for(i = len - 2 ; i >= 0 ; i--)305 {306 /*cout.width(DLEN);307 cout.fill(‘0‘);308 cout << a[i];*/309 printf("%04d",a[i]);310 }311 //cout << endl;312 printf("\n");313 }314 int main()315 {316 char zero[100]={"0"};317 char one[100]={"1"};318 char two[100]={"2"};319 char hxl[2022];320 BigNum z,ZERO(zero),ONE(one),TWO(two);321 while(gets(hxl)>0)322 {323 BigNum x(hxl);324 z=x%2;325 if(z>0)/**奇数**/326 {327 z=(x-ONE)/2;328 }329 else /**偶数**/330 {331 x=x/2;332 z=x%2;333 if(z>0)/**奇数**/334 {335 z=x-TWO;336 }337 else /**偶数**/338 {339 z=x-ONE;340 }341 }342 z.print();343 }344 return 0;345 }
Acdream Chinese Girls' Amusement
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。