ACM-ICPC 2018 焦作赛区网络预赛J题 Participate in E-sports

Jessie and Justin want to participate in e-sports. E-sports contain many games, but they don't know which one to choose, so they use a way to make decisions.

They have several boxes of candies, and there are $i^{th}ith box, each candy is wrapped in a piece of candy paper. Jessie opens the candy boxes in turn from the first box. Every time a box is opened, Jessie will take out all the candies inside, finish it, and hand all the candy papers to Justin.$

When Jessie takes out the candies in the $N^{th}Nth box and hasn't eaten yet, if the amount of candies in Jessie's hand and the amount of candy papers in Justin's hand are both perfect square numbers, they will choose Arena of Valor. If only the amount of candies in Jessie's hand is a perfect square number, they will choose Hearth Stone. If only the amount of candy papers in Justin's hand is a perfect square number, they will choose Clash Royale. Otherwise they will choose League of Legends.$

Now tell you the value of

Input

The first line contains an integer

Each test case contains one line with a single integer: $10^{200})N(1≤N≤10200) .$

Output

For each test case, output one line containing the answer.

样例输入

样例输出

Arena of Valor
Clash Royale
League of Legends
Hearth Stone

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

题解：判断N和N*(N-1)/2,由于N范围是1~10^200.数据太大，故用大数运算；

下面附上大数运算模板：

参考代码：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 // base and base_digits must be consistent
  4 constexpr int base = 1000000000;
  5 constexpr int base_digits = 9;
  6 struct bigint{
  7     vector<int> z;
  8     int sign;
  9     bigint() : sign(1) {}
 10     bigint(long long v) { *this = v; }
 11     bigint& operator=(long long v)
 12     {
 13         sign = v < 0 ? -1 : 1;
 14         v*=sign;
 15         z.clear();
 16         for(; v > 0; v = v / base) z.push_back((int)(v % base));
 17         return *this;
 18     }
 19 
 20     bigint(const string& s) { read(s); }
 21 
 22     bigint& operator+=(const bigint& other)
 23     {
 24         if (sign == other.sign)
 25         {
 26             for (int i = 0, carry = 0; i < other.z.size() || carry; ++i)
 27             {
 28                 if (i == z.size())
 29                     z.push_back(0);
 30                 z[i] += carry + (i < other.z.size() ? other.z[i] : 0);
 31                 carry = z[i] >= base;
 32                 if (carry)
 33                     z[i] -= base;
 34             }
 35         }
 36         else if (other != 0 /* prevent infinite loop */)
 37         {
 38             *this -= -other;
 39         }
 40         return *this;
 41     }
 42 
 43     friend bigint operator+(bigint a, const bigint& b)
 44     {
 45         return a += b;
 46     }
 47 
 48     bigint& operator-=(const bigint& other)
 49     {
 50         if (sign == other.sign)
 51         {
 52             if (sign == 1 && *this >= other || sign == -1 && *this <= other)
 53             {
 54                 for (int i = 0, carry = 0; i < other.z.size() || carry; ++i)
 55                 {
 56                     z[i] -= carry + (i < other.z.size() ? other.z[i] : 0);
 57                     carry = z[i] < 0;
 58                     if (carry)
 59                         z[i] += base;
 60                 }
 61                 trim();
 62             }
 63             else
 64             {
 65                 *this = other - *this;
 66                 this->sign = -this->sign;
 67             }
 68         }
 69         else
 70         {
 71             *this += -other;
 72         }
 73         return *this;
 74     }
 75 
 76     friend bigint operator-(bigint a, const bigint& b)
 77     {
 78         return a -= b;
 79     }
 80 
 81     bigint& operator*=(int v)
 82     {
 83         if (v < 0)
 84             sign = -sign, v = -v;
 85         for (int i = 0, carry = 0; i < z.size() || carry; ++i)
 86         {
 87             if (i == z.size())
 88                 z.push_back(0);
 89             long long cur = (long long)z[i] * v + carry;
 90             carry = (int)(cur / base);
 91             z[i] = (int)(cur % base);
 92         }
 93         trim();
 94         return *this;
 95     }
 96 
 97     bigint operator*(int v) const
 98     {
 99         return bigint(*this) *= v;
100     }
101 
102     friend pair<bigint, bigint> divmod(const bigint& a1, const bigint& b1)
103     {
104         int norm = base / (b1.z.back() + 1);
105         bigint a = a1.abs() * norm;
106         bigint b = b1.abs() * norm;
107         bigint q, r;
108         q.z.resize(a.z.size());
109 
110         for (int i = (int)a.z.size() - 1; i >= 0; i--)
111         {
112             r *= base;
113             r += a.z[i];
114             int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
115             int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
116             int d = (int)(((long long)s1 * base + s2) / b.z.back());
117             r -= b * d;
118             while (r < 0)
119                 r += b, --d;
120             q.z[i] = d;
121         }
122 
123         q.sign = a1.sign * b1.sign;
124         r.sign = a1.sign;
125         q.trim();
126         r.trim();
127         return {q, r / norm};
128     }
129 
130     friend bigint sqrt(const bigint& a1)
131     {
132         bigint a = a1;
133         while (a.z.empty() || a.z.size() % 2 == 1)
134             a.z.push_back(0);
135 
136         int n = a.z.size();
137 
138         int firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
139         int norm = base / (firstDigit + 1);
140         a *= norm;
141         a *= norm;
142         while (a.z.empty() || a.z.size() % 2 == 1)
143             a.z.push_back(0);
144 
145         bigint r = (long long)a.z[n - 1] * base + a.z[n - 2];
146         firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
147         int q = firstDigit;
148         bigint res;
149 
150         for (int j = n / 2 - 1; j >= 0; j--)
151         {
152             for(;;--q)
153             {
154                 bigint r1=(r-(res*2*base+q)*q)*base*base+(j>0?(long long)a.z[2*j-1]*base+a.z[2*j-2]:0);
155                 if(r1>= 0)
156                 {
157                     r = r1;
158                     break;
159                 }
160             }
161             res *= base; res += q;
162             if(j > 0)
163             {
164                 int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
165                 int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
166                 int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()]:0;
167                 q = (int)(((long long)d1*base*base+(long long)d2*base+d3)/(firstDigit*2));
168             }
169         }
170 
171         res.trim();
172         return res / norm;
173     }
174 
175     bigint operator/(const bigint& v) const
176     {
177         return divmod(*this, v).first;
178     }
179 
180     bigint operator%(const bigint& v) const
181     {
182         return divmod(*this, v).second;
183     }
184 
185     bigint& operator/=(int v)
186     {
187         if(v<0) sign=-sign,v=-v;
188         for (int i = (int)z.size() - 1, rem = 0; i >= 0; --i)
189         {
190             long long cur = z[i] + rem * (long long)base;
191             z[i] = (int)(cur / v);
192             rem = (int)(cur % v);
193         }
194         trim();
195         return *this;
196     }
197 
198     bigint operator/(int v) const
199     {
200         return bigint(*this) /= v;
201     }
202 
203     int operator%(int v) const
204     {
205         if(v<0) v=-v;
206         int m=0;
207         for(int i=(int)z.size()-1;i>=0;--i) m=(int)((z[i]+m*(long long)base)%v);
208         return m * sign;
209     }
210 
211     bigint& operator*=(const bigint& v)
212     {
213         *this = *this * v;
214         return *this;
215     }
216 
217     bigint& operator/=(const bigint& v)
218     {
219         *this = *this / v;
220         return *this;
221     }
222 
223     bool operator<(const bigint& v) const
224     {
225         if(sign!=v.sign) return sign < v.sign;
226         if(z.size()!=v.z.size()) return z.size()*sign<v.z.size()*v.sign;
227         for(int i = (int)z.size() - 1; i >= 0; i--)
228             if(z[i] != v.z[i])  return z[i] * sign < v.z[i] * sign;
229         return false;
230     }
231 
232     bool operator>(const bigint& v) const { return v < *this; }
233     bool operator<=(const bigint& v) const { return !(v < *this); }
234     bool operator>=(const bigint& v) const { return !(*this < v); }
235     bool operator==(const bigint& v) const { return !(*this < v) && !(v < *this); }
236     bool operator!=(const bigint& v) const { return *this < v || v < *this; }
237 
238     void trim()
239     {
240         while(!z.empty() && z.back() == 0) z.pop_back();
241         if(z.empty()) sign = 1;
242     }
243 
244     bool isZero() const { return z.empty(); }
245 
246     friend bigint operator-(bigint v)
247     {
248         if(!v.z.empty()) v.sign = -v.sign;
249         return v;
250     }
251 
252     bigint abs() const
253     {
254         return sign == 1 ? *this : -*this;
255     }
256 
257     long long longValue() const
258     {
259         long long res = 0;
260         for(int i = (int)z.size() - 1; i >= 0; i--) res = res * base + z[i];
261         return res * sign;
262     }
263 
264     friend bigint gcd(const bigint& a, const bigint& b)
265     {
266         return b.isZero() ? a : gcd(b, a % b);
267     }
268 
269     friend bigint lcm(const bigint& a, const bigint& b)
270     {
271         return a / gcd(a, b) * b;
272     }
273 
274     void read(const string& s)
275     {
276         sign = 1;
277         z.clear();
278         int pos = 0;
279         while (pos < s.size() && (s[pos] == '-' || s[pos] == '+'))
280         {
281             if(s[pos] == '-') sign = -sign;
282             ++pos;
283         }
284         for (int i = (int)s.size() - 1; i >= pos; i -= base_digits)
285         {
286             int x = 0;
287             for(int j = max(pos, i - base_digits + 1); j <= i; j++) x = x * 10 + s[j] - '0';
288             z.push_back(x);
289         }
290         trim();
291     }
292 
293     friend istream& operator>>(istream& stream, bigint& v)
294     {
295         string s;
296         stream >> s;
297         v.read(s);
298         return stream;
299     }
300 
301     friend ostream& operator<<(ostream& stream, const bigint& v)
302     {
303         if(v.sign == -1) stream << '-';
304         stream << (v.z.empty() ? 0 : v.z.back());
305         for(int i = (int)v.z.size() - 2; i >= 0; --i)
306             stream << setw(base_digits) << setfill('0') << v.z[i];
307         return stream;
308     }
309 
310     static vector<int> convert_base(const vector<int>& a, int old_digits, int new_digits)
311     {
312         vector<long long> p(max(old_digits, new_digits) + 1);
313         p[0] = 1;
314         for (int i = 1; i < p.size(); i++)
315             p[i] = p[i - 1] * 10;
316         vector<int> res;
317         long long cur = 0;
318         int cur_digits = 0;
319         for (int v : a)
320         {
321             cur += v * p[cur_digits];
322             cur_digits += old_digits;
323             while (cur_digits >= new_digits)
324             {
325                 res.push_back(int(cur % p[new_digits]));
326                 cur /= p[new_digits];
327                 cur_digits -= new_digits;
328             }
329         }
330         res.push_back((int)cur);
331         while (!res.empty() && res.back() == 0)
332             res.pop_back();
333         return res;
334     }
335 
336     typedef vector<long long> vll;
337     static vll karatsubaMultiply(const vll& a, const vll& b)
338     {
339         int n=a.size();
340         vll res(n + n);
341         if(n <= 32)
342         {
343             for (int i = 0; i < n; i++)
344                 for (int j = 0; j < n; j++)
345                     res[i + j] += a[i] * b[j];
346             return res;
347         }
348 
349         int k = n >> 1;
350         vll a1(a.begin(), a.begin() + k);
351         vll a2(a.begin() + k, a.end());
352         vll b1(b.begin(), b.begin() + k);
353         vll b2(b.begin() + k, b.end());
354         vll a1b1 = karatsubaMultiply(a1, b1);
355         vll a2b2 = karatsubaMultiply(a2, b2);
356         for(int i=0;i<k;i++) a2[i]+=a1[i];
357         for(int i=0;i<k;i++) b2[i]+=b1[i];
358 
359         vll r = karatsubaMultiply(a2, b2);
360         for(int i=0;i<a1b1.size();i++) r[i]-=a1b1[i];
361         for(int i=0;i<a2b2.size();i++) r[i]-=a2b2[i];
362         for(int i=0;i<r.size();i++) res[i+k]+=r[i];
363         for(int i=0;i<a1b1.size();i++) res[i]+=a1b1[i];
364         for(int i = 0;i<a2b2.size();i++) res[i+n]+=a2b2[i];
365         return res;
366     }
367 
368     bigint operator*(const bigint& v) const
369     {
370         vector<int> a6=convert_base(this->z,base_digits,6);
371         vector<int> b6=convert_base(v.z,base_digits,6);
372         vll a(a6.begin(),a6.end());
373         vll b(b6.begin(),b6.end());
374         while(a.size()<b.size()) a.push_back(0);
375         while(b.size()<a.size()) b.push_back(0);
376         while(a.size()&(a.size()-1)) a.push_back(0),b.push_back(0);
377         vll c=karatsubaMultiply(a, b);
378         bigint res;
379         res.sign = sign * v.sign;
380         for (int i = 0, carry = 0; i < c.size(); i++)
381         {
382             long long cur = c[i] + carry;
383             res.z.push_back((int)(cur % 1000000));
384             carry = (int)(cur / 1000000);
385         }
386         res.z = convert_base(res.z, 6, base_digits);
387         res.trim();
388         return res;
389     }
390 };
391 
392 int main()
393 {
394     ios::sync_with_stdio(0);
395     cin.tie(0);
396     bigint a, b, sa, sb;
397     int T; cin >> T;
398     while(T--)
399     {
400         cin >> b;
401         a = b * (b - 1) / 2;
402         sa = sqrt(a); sb = sqrt(b);
403         bool f1 = (sa * sa) == a;
404         bool f2 = (sb * sb) == b;
405         if(f1&&f2) cout<<"Arena of Valor"<<endl;
406         else if(f1 && !f2) cout<<"Clash Royale"<<endl;
407         else if(!f1 && !f2) cout<<"League of Legends"<<endl;
408         else if (!f1 && f2) cout<<"Hearth Stone"<<endl;
409     }
410     return 0;
411 }
412 　　
413 
414 　　java代码：
415 
416 import java.util.Scanner;
417 import java.math.BigInteger;
418 public class Main {
419     public static void main(String[] args) 
420     {
421         Scanner cin = new Scanner(System.in);
422         int T = cin.nextInt();
423         for(int cas = 1; cas <= T; ++cas) 
424         {
425             String str = cin.next();
426             BigInteger n = new BigInteger(str);
427             BigInteger m = n.multiply(n.subtract(BigInteger.ONE)).shiftRight(1);
428             boolean nIsSquare = isSquare(n);
429             boolean mIsSquare = isSquare(m);
430             if(nIsSquare && mIsSquare) System.out.println("Arena of Valor");
431             else if(nIsSquare && !mIsSquare) System.out.println("Hearth Stone");
432             else if(!nIsSquare && mIsSquare) System.out.println("Clash Royale");
433             else System.out.println("League of Legends");
434         }
435     }
436     public static boolean isSquare(BigInteger n) 
437     {
438         BigInteger low = BigInteger.ZERO;
439         BigInteger high = n;
440         while (low.compareTo(high) <= 0) 
441         {
442             BigInteger mid = low.add(high).shiftRight(1);
443             BigInteger square = mid.multiply(mid);
444             int result = square.compareTo(n);
445             if (result == 0) return true;
446             else if(result>0) high=mid.subtract(BigInteger.ONE);
447             else low = mid.add(BigInteger.ONE);
448         }
449         return false;
450     }
451 }
452

View Code