我真的是太菜了

A. Perfect Squares
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Given an array a1, a2, ..., an of n integers, find the largest number in the array that is not a perfect square.

A number x is said to be a perfect square if there exists an integer y such that x = y2.

Input

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of elements in the array.

The second line contains n integers a1, a2, ..., an ( - 106 ≤ ai ≤ 106) — the elements of the array.

It is guaranteed that at least one element of the array is not a perfect square.

Output

Print the largest number in the array which is not a perfect square. It is guaranteed that an answer always exists.

Examples
input
2
4 2
output
2
input
8
1 2 4 8 16 32 64 576
output
32
Note

In the first sample case, 4 is a perfect square, so the largest number in the array that is not a perfect square is 2.

让我们找最大的不perfect的number

这个直接负数都不行,排序遍历就行了

#include<bits/stdc++.h>
using namespace std;
int a[];
int main()
{
int n;
cin>>n;
for(int i=; i<n; i++)
cin>>a[i];
sort(a,a+n);
for(int i=n-; i>=; i--)
{
if(a[i]<)
{
cout<<a[i];
return ;
}
int x=sqrt(a[i]+0.5);
if(x*x!=a[i])
{
cout<<a[i];
return ;
}
}
return ;
}
B. Conan and Agasa play a Card Game
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Edogawa Conan got tired of solving cases, and invited his friend, Professor Agasa, over. They decided to play a game of cards. Conan has n cards, and the i-th card has a number ai written on it.

They take turns playing, starting with Conan. In each turn, the player chooses a card and removes it. Also, he removes all cards having a number strictly lesser than the number on the chosen card. Formally, if the player chooses the i-th card, he removes that card and removes the j-th card for all j such that aj < ai.

A player loses if he cannot make a move on his turn, that is, he loses if there are no cards left. Predict the outcome of the game, assuming both players play optimally.

Input

The first line contains an integer n (1 ≤ n ≤ 105) — the number of cards Conan has.

The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105), where ai is the number on the i-th card.

Output

If Conan wins, print "Conan" (without quotes), otherwise print "Agasa" (without quotes).

Examples
input
3
4 5 7
output
Conan
input
2
1 1
output
Agasa
Note

In the first example, Conan can just choose the card having number 7 on it and hence remove all the cards. After that, there are no cards left on Agasa's turn.

In the second example, no matter which card Conan chooses, there will be one one card left, which Agasa can choose. After that, there are no cards left when it becomes Conan's turn again.

这个题就是你拿走一个,在你前面比你小的你都可以拿走,虽然两个人都尽力想赢,但是明显第一个人更占光,他永远可以制裁你

然后就变成了看看其中存在不存在一个数是奇数个的,其他的也都可以转移过来这个,所以这就是先手必胜

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
int a[N];
int main()
{
int n;
cin>>n;
for(int i=,x; i<n; i++)
cin>>x,a[x]++;
for(int i=;i<N;i++)
{
if(a[i]&)
{
cout<<"Conan\n";
return ;
}
}
cout<<"Agasa\n";
return ;
}
C. Travelling Salesman and Special Numbers
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The Travelling Salesman spends a lot of time travelling so he tends to get bored. To pass time, he likes to perform operations on numbers. One such operation is to take a positive integer x and reduce it to the number of bits set to 1 in the binary representation of x. For example for number 13 it's true that 1310 = 11012, so it has 3 bits set and 13 will be reduced to 3 in one operation.

He calls a number special if the minimum number of operations to reduce it to 1 is k.

He wants to find out how many special numbers exist which are not greater than n. Please help the Travelling Salesman, as he is about to reach his destination!

Since the answer can be large, output it modulo 109 + 7.

Input

The first line contains integer n (1 ≤ n < 21000).

The second line contains integer k (0 ≤ k ≤ 1000).

Note that n is given in its binary representation without any leading zeros.

Output

Output a single integer — the number of special numbers not greater than n, modulo 109 + 7.

Examples
input
110
2
output
3
input
111111011
2
output
169
Note

In the first sample, the three special numbers are 3, 5 and 6. They get reduced to 2 in one operation (since there are two set bits in each of 3, 5 and 6) and then to 1 in one more operation (since there is only one set bit in 2).

C就是变变变,但注意到长度最长是1000,k也不是很大,可以直接预处理__builtin_popcount,这个函数可以获取当前这个数字的二进制里有多少个1,可以这样预处理去dfs,也可以组合数学去处理

#include <bits/stdc++.h>
using namespace std;
const int MD=1e9+,N=1e3+;
char s[N];
int K,n,f[N],dp[N],pre,ans;
int main()
{
scanf("%s%d",s+,&K);
n=strlen(s+);
if(K==)
{
printf("%d\n",);
return ;
}
for (int i=; i<=n; i++)
f[i]=f[__builtin_popcount(i)]+;
for(int i=; i<=n; i++)
{
for(int j=n; j; j--)
dp[j]=(dp[j]+dp[j-])%MD;
if(s[i]=='') dp[pre]++;
pre+=s[i]-'';
}
dp[pre]++;
for (int i=; i<=n; i++)
if(f[i]==K-)ans=(ans+dp[i])%MD;
if (K==) ans=(ans-+MD)%MD;
printf("%d\n",ans);
return ;
}

最新文章

  1. 几种display:table-cell的应用
  2. PHPCMS v9 超级安全防范教程!
  3. Java 13 字符串
  4. Config the Android 5.0 Build Environment
  5. Mysql慢日志查询
  6. ubuntu eclipse CDT 问题
  7. HDU_2052——画矩形
  8. Linux 重定向
  9. grub2的/etc/default/grub文件详解
  10. centos在设置时区
  11. Intellij Idea搭建java web项目(问题总结)
  12. JQ 判断 浏览器打开的设备类型
  13. PostgreSql 使用dblink跨库
  14. Linux中设置服务自启动的三种方式,ln -s 建立启动软连接
  15. 心路历程(一)-自学java两个月心得
  16. MAC Gradle 下载的问题
  17. RabbitMQ(四): rabbitmq 的消息确认机制(事务+confirm)
  18. 【转载】C# Graphics类具体解释
  19. laravel 在linux环境下解决.htaccess无效和去除index.php
  20. 读书笔记-iOS核心动画高级技巧

热门文章

  1. SpringBoot服务监控
  2. JavaScript_9_循环
  3. java面试题(杨晓峰)---第一讲谈谈你对java平台的理解
  4. SAP CRM Survey调查问卷的存储模型
  5. 使用ABAP代码提交SAP CRM Survey调查问卷
  6. EditPlus 3.7激活码注册码
  7. Linux学习日记:第一天
  8. iOS--获取文件目录的方法
  9. spring boot yaml 自定义配置 映射到 java POJO
  10. Choose unique values for the &#39;webAppRootKey&#39; context-param in your web.xml files! 错误的解决