Codeforces Round #313 (Div. 2)
9599 ワード
試合リンクclick here~~
A題:
【考え方】:入力が1であれば-1、そうでなければ1です.
B題:3つの矩形の大きさをあげて、後の2つに最初の矩形の中に入れることができるかどうかを聞いて、それぞれの状況を列挙して、合法的なのはYESで、さもなくばNOです.
コード:
C題:
各内角が120度の六角形を与えて、この六角形の中でどれだけの辺の長さが1の等辺の三角形を置くことができますかを聞きます
【考え方】:数学の問題は、問題の中のこの六角形を2つの等腰台形と中間の1つの平行四角形に分割することができ、このように各図形に含まれる三角形の数をそれぞれ算出し、最後に加算すればよい.
コード:
D題:条件を満たす文字列を求めて、2つの長さの同じ文字列、それぞれ同じ2つの部分に分割して、もし2つの部分が条件を満たすならば、その文字列は等しくて、等しいかどうかを判断します
【考え方】len&1の場合、直接判断し、そうでなければ、2つの文字列の残りの部分を検索する
コード:
A題:
【考え方】:入力が1であれば-1、そうでなければ1です.
B題:3つの矩形の大きさをあげて、後の2つに最初の矩形の中に入れることができるかどうかを聞いて、それぞれの状況を列挙して、合法的なのはYESで、さもなくばNOです.
コード:
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)
#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)
#define lowbit(a) a&-a
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef unsigned long long LLU;
typedef double db;
const int N=1e5+100;
const int inf=0x3f3f3f3f;
int n,m,t,ans,res,cnt,tmp;
char str[N];
bool vis[N];
int mat[1005][1005];///
int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
int movv[5][2]= {{1,0},{0,1},{0,0},{-1,0},{0,-1}};
inline LL read()
{
int c=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
c=c*10+ch-'0';
ch=getchar();
}
return c*f;
}
int a1,b1;
int a2,b2;
int a3,b3;
bool get(int x,int y)
{
if(x<=a1&&y<=b1||y<=a1&&x<=b1) return 1;
return 0;
}
int main()
{
while(cin>>a1>>b1)
{
cin>>a2>>b2;
cin>>a3>>b3;
bool f1=get(a2+a3,max(b2,b3));
bool f2=get(b2+b3,max(a2,a3));
bool f3=get(a2+b3,max(b2,a3));
bool f4=get(a3+b2,max(a2,b3));
if(f1||f2||f3||f4) puts("YES");
else puts("NO");
}
return 0;
}
/*
Sample test(s)
input
3 2
1 3
2 1
output
YES
input
5 5
3 3
3 3
output
NO
input
4 2
2 3
1 2
output
YES
100 16
41 76
24 15
NO
*/
C題:
各内角が120度の六角形を与えて、この六角形の中でどれだけの辺の長さが1の等辺の三角形を置くことができますかを聞きます
【考え方】:数学の問題は、問題の中のこの六角形を2つの等腰台形と中間の1つの平行四角形に分割することができ、このように各図形に含まれる三角形の数をそれぞれ算出し、最後に加算すればよい.
コード:
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)
#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)
#define lowbit(a) a&-a
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef unsigned long long LLU;
typedef double db;
const int N=1e5+100;
const int inf=0x3f3f3f3f;
int n,m,t,ans,res,cnt,tmp;
char str[N];
bool vis[N];
int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
int movv[5][2]= {{1,0},{0,1},{0,0},{-1,0},{0,-1}};
inline LL read()
{
int c=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
c=c*10+ch-'0';
ch=getchar();
}
return c*f;
}
int uu[100];
int calc1(int a,int h)
{
return (2*a*h+h*h);
}
int calc2(int a,int h)
{
return 2*a*h;
}
int main()
{
for(int i=0; i<6; ++i)
{
cin>>uu[i];
}
int h1=uu[1]+uu[2];
int h2=min(uu[1],uu[5]);
int h3=min(uu[2],uu[4]);
cout<<calc1(uu[0],h2)+calc2(uu[0]+h2,h1-h2-h3)+calc1(uu[3],h3)<<endl;
return 0;
}
D題:条件を満たす文字列を求めて、2つの長さの同じ文字列、それぞれ同じ2つの部分に分割して、もし2つの部分が条件を満たすならば、その文字列は等しくて、等しいかどうかを判断します
【考え方】len&1の場合、直接判断し、そうでなければ、2つの文字列の残りの部分を検索する
コード:
//
// B. Equivalent Strings
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)
#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)
#define lowbit(a) a&-a
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef unsigned long long LLU;
typedef double db;
const int N=2*1e5+100;
const int inf=0x3f3f3f3f;
int n,m,t,ans,res,cnt,tmp;
int hh[28];
char str1[N],str2[N];
bool vis[N];
int mat[1005][1005];
int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
int movv[5][2]= {{1,0},{0,1},{0,0},{-1,0},{0,-1}};
inline LL read()
{
int c=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
c=c*10+ch-'0';
ch=getchar();
}
return c*f;
}
int a1,b1;
int a2,b2;
int a3,b3;
bool dfs(char *s,char *t,int len)
{
if(len&1) return strncmp(s,t,len)==0;
mem(hh,0);
for(int i=0; i<len; ++i)
{
hh[s[i]-'a']++;
hh[t[i]-'a']--;
}
for(int i=0; i<26; ++i)
{
if(hh[i]!=0) return false;
}
len/=2;
if(dfs(s,t,len)&&dfs(s+len,t+len,len)) return true;
if(dfs(s+len,t,len)&&dfs(s,t+len,len)) return true;
return false;
}
int main()
{
scanf("%s%s",str1,str2);
int len=strlen(str1);
printf("%s
",dfs(str1,str2,len)?"YES":"NO");
return 0;
}