「UVa100～110」の編集履歴（バックアップ）一覧はこちら
「UVa100～110」(2013/03/18 (月) 17:30:24) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*100 - The 3n + 1 problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36
初めてのＵＶaですが解いてみたらコード実行速度3892/74613位。
上位5％近辺に入れて悪くないスタートですが、私は英語がほとんどできないので他の問題も解けるかは不明。
#include<stdio.h>
#include<string.h>
int memo[1000*1000+1];
int saiki(unsigned int n){
if(n<=1000*1000&&memo[n]!=-1){
return memo[n]+1;
}else{
int no=saiki(n%2==1?3*n+1:n/2);
if(n<=1000*1000)memo[n]=no;
return no+1;
}
}
int main(){
memset(memo,-1,sizeof(memo));
memo[1]=1;
for(int i=2;i<=1000*1000;i++){
if(memo[i]==-1)memo[i]=saiki(i%2==1?3*i+1:i/2);
}
int a,b;
while(scanf("%d",&a)!=EOF){
if(scanf("%d",&b)==EOF)break;
int max=0;
if(a<=b)for(int i=a;i<=b;i++)if(max<memo[i])max=memo[i];
if(b<=a)for(int i=b;i<=a;i++)if(max<memo[i])max=memo[i];
printf("%d %d %d\n",a,b,max);
}
}
*問い101 - The Blocks Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=37
アームロボットにブロックの移動命令が与えられる。
移動後のブラックの状態を答えよという問題。
#include<stdio.h>
#include<vector>
#include<string>
#include<iostream>
//私は英語が苦手なため何度もＷＡになってから題意をつかむという状態です。
//必然的に正答率は非常に低くなります
std::vector<int> bs[25];
int main(){
int n,a,b;
scanf("%d",&n);
for(int i=0;i<n;i++)bs[i].push_back(i);
std::string com1,com2;
while(1){
std::cin>>com1;
if(com1=="quit")break;
std::cin>>a>>com2>>b;
int no1,no2;
std::vector<int>::iterator it1,it2,it3;
for(int i=0;i<n;i++){
for(std::vector<int>::iterator it=bs[i].begin();it!=bs[i].end();it++){
if((*it)==b){
no2=i;//b置かれる場所
it2=it;
}
if((*it)==a){
it1=it;//a置くもの
no1=i;
}
}
}
if(no1==no2)continue;
if(com1=="move"&&com2=="onto"){
it2++;
it2=bs[no2].insert(it2,(*it1));
it2++;
it1=bs[no1].erase(it1);
while(it2!=bs[no2].end()){
bs[(*it2)].push_back((*it2));
it2=bs[no2].erase(it2);
}
while(it1!=bs[no1].end()){
bs[(*it1)].push_back((*it1));
it1=bs[no1].erase(it1);
}
}
if(com1=="move"&&com2=="over"){
bs[no2].push_back((*it1));
it1=bs[no1].erase(it1);
while(it1!=bs[no1].end()){
bs[(*it1)].push_back((*it1));
it1=bs[no1].erase(it1);
}
}
if(com1=="pile"&&com2=="onto"){
it2++;
it3=it1;
while(it1!=bs[no1].end()){
it2=bs[no2].insert(it2,(*it1));
it2++;
it1++;
}
while(it2!=bs[no2].end()){
bs[(*it2)].push_back((*it2));
it2=bs[no2].erase(it2);
}
bs[no1].erase(it3,bs[no1].end());
}
if(com1=="pile"&&com2=="over"){
bs[no2].insert(bs[no2].end(),it1,bs[no1].end());
bs[no1].erase(it1,bs[no1].end());
}
}
for(int i=0;i<n;i++){
printf("%d:",i);
for(int j=0;j<bs[i].size();j++){
printf(" %d",bs[i][j]);
}
printf("\n");
}
}
*102 Ecological Bin Packing
http://uva.onlinejudge.org/external/1/102.html
ビンを分けるらしいのだがよくわからなかった問題。
1682/17942位獲得。
題意がよくわからなかったので検索したら中国語の正答コード掲載ブログが出てきた。
ブログを読んでもやはり良くわからなかったので参考にコードを縮めれないか試したくらい。
この問題で速度差が出るとは思えないので同順位多数ということだと思う。
#include<stdio.h>
int main(){
int b1,c1,g1,b2,c2,g2,b3,c3,g3,ws[6];
char ansCom[6][4]={"BCG","BGC","CBG","CGB","GBC","GCB"};
while(1){
int sum;
if(scanf("%d %d %d %d %d %d %d %d %d",&b1,&g1,&c1,&b2,&g2,&c2,&b3,&g3,&c3)==EOF)return 0;
sum=b1+c1+g1+b2+g2+c2+b3+g3+c3;
ws[0]=b1+c2+g3;
ws[1]=b1+g2+c3;
ws[2]=c1+b2+g3;
ws[3]=c1+g2+b3;
ws[4]=g1+b2+c3;
ws[5]=g1+c2+b3;
int max=ws[0],no=0;
for(int i=0;i<6;i++){
if(max<ws[i]){
max=ws[i];
no=i;
}
}
printf("%s %d\n",ansCom[no],sum-max);
}
}
*問い103
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39
ｄ次元空間の箱を別の箱に入れて入れ子にしていく時もっともたくさんたくさん入る入れ子を出力せよという問題。
箱は回転しても良いがどのへんも次元の軸と平行でなくてはいけない。
例えば３次元なら箱のどの辺もＸ軸、Ｙ軸、Ｚ軸のどれかと平行でなくてはいけない。
解法
箱が別の箱に入る関係を半順序集合のグラフとして表現。
箱の回転は回転行列の概念より2この座標を入れ替えるのと同じなので全ての組み合わせを考えることが出来る。
5,4,3,2,1の長さで表される箱なら5,4,3,2,1を並べ替えたすべての組み合わせとして表現することが出来る。
後はダイクストラ法もどきで解決。
入るかどうかの判断関数をもっと高速化できると気付かずランクは。
3242/8598位と平凡な結果に。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
bool isInOk(std::vector<int> q1,std::vector<int> q2){
//ベクターはソート済みであると仮定
std::vector<int>::iterator it;
for(int i=0;i<q1.size();i++){
it=std::upper_bound( q2.begin(), q2.end(), q1[i] );
if(it==q2.end())return false;
q2.erase(it);
}
return true;
}
void upData(std::vector<int>& ansA,std::vector<int>& ansB){
if(ansA.size()<ansB.size()){
ansA.clear();
ansA.insert(ansA.begin(),ansB.begin(),ansB.end());
}
}
int main(){
int n,d,l;
while(scanf("%d %d",&n,&d)!=EOF){
std::vector<int> qs[31],ans[31],lastAns;
std::set<int> G[31];
std::set<int>::iterator it;
for(int i=0;i<n;i++){
for(int j=0;j<d;j++){
scanf("%d",&l);
qs[i].push_back(l);
}
std::sort(qs[i].begin(),qs[i].end());
ans[i].push_back(i);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
if(isInOk(qs[i],qs[j])==true){
//ｊの中にiが入った
G[j].insert(i);
}
}
}
int spents[31]={0};
for(int i=0;i<n;i++){
std::vector<int> dells;
for(int j=0;j<n;j++){
if(G[j].empty()==true&&spents[j]==0){
dells.push_back(j);
spents[j]=1;
}
}
if(dells.empty()==true)break;
for(int j=0;j<dells.size();j++){
int no=dells[j];
for(int k=0;k<n;k++){
if(G[k].find(no)!=G[k].end()){
ans[no].push_back(k);
upData(ans[k],ans[no]);
ans[no].pop_back();
G[k].erase(no);
}
}
}
}
for(int i=0;i<n;i++){
if(lastAns.size()<ans[i].size()){
lastAns.clear();
lastAns.insert(lastAns.begin(),ans[i].begin(),ans[i].end());
}
}
printf("%d\n",lastAns.size());
for(int i=0;i<lastAns.size();i++){
printf("%d",lastAns[i]+1);
if(i<lastAns.size()-1)printf(" ");
}
printf("\n");
}
}
*104 - Arbitrage
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=40
通貨売買をして1％以上の儲けを出せるならその売買手順を表示する問題。
解法
この問題サンプルデータを見てもしかして一度使った通貨は使えないと勘違い。
そんな激ムズ問題と勘違いしてどうすれば高速に動くかばかり考えＷＡを３連続でくらってしまった（←かなりの馬鹿）
実際は、同じ通貨を何度使っても良いという優しい問題でした。
まあそれでも一発で通ると思って書いたちょっぱやでかいたコードに書き間違いがあってて提出してＷＡくらったんですけどね。
速度よりも実装の分かりやすさを優先して書いた結果2586/4947位という妥当な順位になりました。
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
#include<map>
struct S{
int now,size;
double val;
std::vector<int> ans;
};
class permSorter{
public:
bool operator()(const S& l, const S& r) const {
if(l.size!=r.size)return l.size<r.size;
if(l.ans[0]!=r.ans[0])return l.ans[0]<r.ans[0];
return l.now<r.now;
}
};
class valSorter {
public:
bool operator()(const S& l, const S& r) const {
if(l.size!=r.size)return l.size>r.size;//サイズの小さい方優先
if(l.ans[0]!=r.ans[0])return l.ans[0]>r.ans[0];
if(l.now!=r.now)return l.now>r.now;
return l.val<r.val;//値の大きい方が優先
}
};
void ansPrint(std::vector<int> ans){
for(unsigned int i=0;i<ans.size();i++){
printf("%d",ans[i]+1);
if(i<ans.size()-1)printf(" ");
}
printf("\n");
}
void calc(int n){
double Ds[21][21];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)Ds[i][j]=1.0;
else scanf("%lf",&Ds[i][j]);
}
}
std::map<S,double,permSorter> memo;
std::priority_queue<S,std::vector<S>,valSorter> qu;
S s1;
for(int i=0;i<n;i++){
s1.val=1.0;
s1.now=i;
s1.size=0;
s1.ans.push_back(i);
qu.push(s1);
s1.ans.pop_back();
}
while(qu.empty()==false){
s1=qu.top();
qu.pop();
if(s1.size>=n)break;
if(memo.find(s1)!=memo.end()&&memo[s1]>=s1.val)continue;
memo[s1]=s1.val;
s1.size++;
double d1=s1.val;
int now=s1.now;
for(int k=0;k<n;k++){
if(k==s1.now)continue;
if(s1.val*Ds[now][k]>=1.01&&s1.ans[0]==k){
s1.ans.push_back(k);
ansPrint(s1.ans);
return ;
}else if(memo.find(s1)==memo.end()||memo[s1]<s1.val){
s1.val*=Ds[now][k];
s1.now=k;
s1.ans.push_back(k);
qu.push(s1);
s1.ans.pop_back();
s1.val=d1;
s1.now=now;
}
}
}
printf("no arbitrage sequence exists\n");
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
calc(n);
}
}
*105- The Skyline Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=41
y=0を床とする平面の上に長方形が置かれている。
長方形の高さに変化があった場所を表示せよという問題。
コード実行速度325/6697位を獲得。
何一つ工夫しないで素朴に実装しただけなのに何故こんなに高ランクになってんだろ？
#include<stdio.h>
#include<algorithm>
#include<map>
#include<vector>
const int OUT=1,IN=0;
struct S{
int x,h,type;
bool operator<(const S& s)const{
if(x!=s.x)return x<s.x;
return type>s.type;
}
};
int main(){
int nowX;
std::map<int,int> memo;
std::map<int,int>::iterator it;
std::vector<S> datas;
S s1;
int a,b,h;
while(scanf("%d",&a)!=EOF){
scanf("%d %d",&h,&b);
s1.x=a;
s1.h=h;
s1.type=IN;
datas.push_back(s1);
s1.x=b;
s1.type=OUT;
datas.push_back(s1);
}
std::sort(datas.begin(),datas.end());
nowX=datas[0].x;
int no=0,nowH=0;
while(no<datas.size()){
while(no<datas.size()&&nowX==datas[no].x){
s1=datas[no];
if(s1.type==OUT){
memo[s1.h]--;
}else{
memo[s1.h]++;
}
if(memo[s1.h]<=0)memo.erase(s1.h);
nowX=s1.x;
no++;
}
if(datas.size()<=no)break;
it=memo.end();
if(it!=memo.begin())it--;
if(nowH!=(*it).first){
printf("%d %d ",nowX,(*it).first);
nowH=(*it).first;
}
nowX=datas[no].x;
}
printf("%d 0\n",nowX);
}
*106 - Fermat vs. Pythagoras
http://uva.onlinejudge.org/external/1/106.html
x^2+y^2=z^2でｚがｎ以下になる原始ピタゴラス数の数と、ｚ＜＝ｎとなる（原始でないのもふくむ）ピタゴラス数の組に使われてないｎ以下の数の個数を答える問題。
例えば5と問われたら3,4,5の組しかないので1と２は使ってない。
ピタゴラス数にでてこない数は1と２の２個と答える問題です。
1059/5437位、自分で考えたにしては健闘したほう。
整数論の教育は中学どまりなのでこの手の問題で上位入りは不可能だとわかってる。
解法
原始ピタゴラス数を求める公式から斜辺がmax以下(問われた一番大きな数)までの組を求め、これを優先順位付きキューにいれて斜辺の長さでソーティング。
後は斜辺の短い方から出現した数を足し合わせていけば答えとなります。
これより賢い方法を自分では考えつけない状態。
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<queue>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
struct Delta{
int a,b,c;
bool operator<(const Delta& d)const{
return c>d.c;
}
};
int all[1000*1000+1]={0};
int main(){
std::vector<int> Qs;
std::set<int> sortQs;
std::map<int,int> memo,memoBase;
std::map<int,int>::iterator mIt;
std::map<int,int> ans,ansBase;
std::priority_queue<Delta> qu;
Delta d1;
int n,max=0;
while(scanf("%d",&n)!=EOF){
Qs.push_back(n);
sortQs.insert(n);
memo[n]=0;
memoBase[n]=0;
if(max<n)max=n;
}
for(int m=2;m*m+1<=max;m++){
for(int n=1;n<m&&m*m+n*n<=max;n++){
if(((m-n)&1)==0 || gcd(m,n)!=1)continue;
int a=m*m-n*n;
int b=2*m*n;
int c=m*m+n*n;
mIt=memoBase.lower_bound(c);
(*mIt).second++;
for(int i=1;i*c<=max;i++){
d1.a=a*i;
d1.b=b*i;
d1.c=c*i;
qu.push(d1);
}
}
}
while(qu.empty()==false){
d1=qu.top();
qu.pop();
mIt=memo.lower_bound(d1.c);
if(all[d1.a]==0){
all[d1.a]=1;
(*mIt).second++;
}
if(all[d1.b]==0){
all[d1.b]=1;
(*mIt).second++;
}
if(all[d1.c]==0){
all[d1.c]=1;
(*mIt).second++;
}
}
int sum=0,sumBase=0;
for(std::set<int>::iterator sIt=sortQs.begin();sIt!=sortQs.end();sIt++){
int num=(*sIt);
sum+=memo[num];
ans[num]=sum;
sumBase+=memoBase[num];
ansBase[num]=sumBase;
}
for(int i=0;i<Qs.size();i++){
printf("%d %d\n",ansBase[Qs[i]],Qs[i]-ans[Qs[i]]);
}
}
*107 - The Cat in the Hat
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=43
問題
読解に苦労した問題。
１匹の帽子の中にr匹の猫が入っている。
そのr匹の猫の帽子の中にr匹の猫が入っていて連鎖する。
これはr分木になっている。
帽子をかぶってる猫は、その帽子の中に入ってる猫の（r+1）倍の大きさであり一番奥の帽子に入ってる猫のサイズ１である。
一番大きな猫のサイズnと一番小さな猫の数mが一行に与えられるので一番小さな猫以外の数と全部の猫の身長の合計を答えよ。
解法
n=(i+1)^kかつm=i^kとなるiが見つかればそれが答えのカギとなります。
後は計算して足し合わせるだけです。
GCDとかその辺を使えば高速化できるかもしれません。
922/４９９７位と平凡な結果に。
#include<stdio.h>
#include<iostream>
void calc(long long int n,long long int m){
for(long long int i=1;i*i<=m;i++){
long long int n1=n;
long long int m1=m;
long long int ans1=0,ans2=m1,k=1;
while(n1%(i+1)==0&&m1%i==0){
n1/=(i+1);
m1/=(i);
k*=(i+1);
ans1+=m1;
ans2+=m1*k;
if(k>n)break;
}
if(n1==1&&m1==1){
std::cout<<ans1<<" "<<ans2<<"\n";
return ;
}
}
if(n==m+1){
std::cout<<"1 "<<m+1+m<<"\n";
}
}
int main(){
int n,m;
while(1){
std::cin>>n>>m;
if(n==0&&m==0)break;
calc(n,m);
}
}
*108 - Maximum Sum
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44
Ｎ*Ｎのマス目に数字が書かれている。
マス目を長方形で囲んだとき内部の数字の合計が最大になる領域の合計値を求めよという問題。
解法
とりあえず賢い方法を思いつかなかったので尺取り虫法で列の長さをそろえながら一行ずつ計算してみました。
1568/1034位という平凡な結果に。
#include<stdio.h>
#include<string.h>
int main(){
int n;
int board[101][101];
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d" ,&board[i][j]);
}
}
int ans=-1000000;
for(int i=0;i<n;i++){
int colSum[101];
memset(colSum,0,sizeof(colSum));
for(int c=0;c<n;c++){
for(int r=0;r<=i;r++){
colSum[c]+=board[r][c];
}
}
for(int r=i+1;r<=n;r++){
int rowSum=0;
for(int c=0;c<n;c++){
rowSum+=colSum[c];
if(rowSum<colSum[c])rowSum=colSum[c];
if(ans<rowSum)ans=rowSum;
}
if(r==n)break;
for(int c=0;c<n;c++){
colSum[c]=colSum[c]+board[r][c]-board[r-i-1][c];
}
}
}
printf("%d\n",ans);
}
*109 SCUD Busters
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=45
外壁で囲まれた国にミサイルが降り注ぐ。
国内にミサイルが落ちた全ての国の面積の総計を答えよという問題。
解法
最初の２点を選びさえできれば後は角度変化の小ささを基準に外壁の頂点を決定していけばループが一つ減って高速化できたのですが、最初の２点を選ぶ処理と角度の処理でコードが膨らむのはどうかと思って回避しました。
かわりに半開平面の概念を使って解いてます。
外側になる２点をとおる直線を描いたとき、残りのすべての点が半開平面の片側にあればその２点は外壁となります。
この処理を採用した結果ループが一つ多くなり、1085/1590位という酷い結果になってます。
100％間違いないコードを書いたところでふとどうしても辺上や頂点にミサイルが着弾した場合の処理を解釈できない状態でした。
投稿直前のチェック用に、頂点や辺上での処理がどうなるか他の人のコードを見てから投稿した問題です。
#include<stdio.h>
#include<math.h>
#include<vector>
struct P{
int x,y;
};
std::vector<P> getOutLines(const std::vector<P>& ps){
std::vector<P> ans;
int size=ps.size();
int sp,spents[101]={0},Lx=500;
for(int i=0;i<size;i++){
if(Lx>ps[i].x){
Lx=ps[i].x;
sp=i;
}
}
int p=sp,mod,count=0;
P p1,p2,p3;
ans.push_back(ps[p]);
while(1){
p1=ps[p];
for(int i=0;i<size;i++){
if(i==sp&&count<2)continue;
if(i==p)continue;
if(spents[i]==1)continue;
p2=ps[i];
mod=-2;
int y1=p2.y-p1.y;
int x1=p2.x-p1.x;
bool ok=true;
for(int k=0;k<size;k++){
if(i==k||p==k)continue;
p3=ps[k];
int y2=p3.y-p1.y;
int x2=p3.x-p1.x;
int g1=x1*y2-x2*y1;
if(g1==0){
if(x1*x2+y1*y2<=0)continue;
if(x1*x1+y1*y1>x2*x2+y2*y2){
ok=false;
break;
}else{
continue;
}
}
g1=g1>0?1:-1;
if(mod==-2)mod=g1;
if(mod!=g1){
ok=false;
break;
}
}
if(ok==true){
p=i;
break;
}
}
p1=ans[ans.size()-1];
if(p1.x!=ps[p].x||p1.y!=ps[p].y){
ans.push_back(ps[p]);
}
spents[p]=1;
count++;
if(p==sp)break;
}
return ans;
}
double sumS(P p1,P p2,P p3){
double x1,x2,y1,y2;
x1=p3.x-p1.x;
y1=p3.y-p1.y;
x2=p2.x-p1.x;
y2=p2.y-p1.y;
return 0.5*(x2*y1-x1*y2);
}
int main(){
std::vector<std::vector<P> > ps;
std::vector<P> v,re;
std::vector<double> outs;
P p1;
int n;
while(1){
scanf("%d",&n);
if(n==-1)break;
ps.push_back(v);
int no=ps.size()-1;
while(n--){
scanf("%d %d",&p1.x,&p1.y);
ps[no].push_back(p1);
}
ps[no]=getOutLines(ps[no]);
double sum=0;
for(int i=1;i<ps[no].size()-1;i++){
sum+=sumS(ps[no][0],ps[no][i],ps[no][i+1]);
}
if(sum<0.0)sum=-sum;
outs.push_back(sum);
//printf("(%d %lf)",no,sum);
}
double ans=0;
while(scanf("%d %d",&p1.x,&p1.y)!=EOF){
double g1,g2;
for(int i=0;i<ps.size();i++){
if(outs[i]==0)continue;
bool isOut=true;
g1=sumS(ps[i][0],ps[i][1],p1);
for(int j=1;j<ps[i].size()-1;j++){
g2=sumS(ps[i][j],ps[i][j+1],p1);
if(g2==0||g1==0){
break;
}
if(g1>=0&&g2<0){
isOut=false;
break;
}
if(g1<0&&g2>0){
isOut=false;
break;
}
}
if(isOut==true){
ans+=outs[i];
outs[i]=0;
}
}
}
printf("%.2lf\n",ans);
}
*110 - Meta-Loopless Sorts
変数の数1<=ｎ<=8が与えられるので、これをa,b、、とaから始まる８個の変数までに読みこみ
if,else if,else,readln,writeln、<文だけを使って,a,b,c,,,,をソートできるphytonプログラムを生成せよという問題。
解法
順序集合が分岐する場合全部を探索して出力しました。
凄くめんどくさい問題という印象しかありません。
#include<stdio.h>
#include<string.h>
#include<algorithm>
char text[10]="abcdefgh";
void roopSlide(int perm[10],int s,int g){
int t=perm[g];
for(int i=g-1;i>=s;i--){
perm[i+1]=perm[i];
}
perm[s]=t;
}
void saiki(int perm[10],int deep,int m){
if(deep==m-1){
for(int i=0;i<=deep;i++)printf(" ");
printf("writeln(");
for(int i=0;i<m;i++)printf("%c%c",text[perm[i]],i==m-1?')':',');
printf("\n");
}else{
for(int i=0;i<=deep;i++)printf(" ");
printf("if %c < %c then\n",text[perm[deep]],text[perm[deep+1]]);
saiki(perm,deep+1,m);
int temp[10];
memcpy(temp,perm,sizeof(temp));
for(int i=deep-1;i>=0;i--){
for(int j=0;j<=deep;j++)printf(" ");
printf("else if %c < %c then\n",text[perm[i]],text[perm[deep+1]]);
roopSlide(perm,i+1,deep+1);
saiki(perm,deep+1,m);
memcpy(perm,temp,sizeof(temp));
}
for(int i=0;i<=deep;i++)printf(" ");
printf("else\n");
roopSlide(perm,0,deep+1);
saiki(perm,deep+1,m);
memcpy(perm,temp,sizeof(temp));
}
}
int main(){
int n,m;
scanf("%d",&n);
for(int i=0;i<n;i++){
if(i!=0)printf("\n");
scanf("%d",&m);
printf("program sort(input,output);\nvar\n");
for(int i=0;i<m;i++){
printf("%c%c",text[i],i==m-1?' ':',');
}
printf(": integer;\nbegin\n readln(");
for(int i=0;i<m;i++){
printf("%c",text[i]);
if(i<m-1)printf(",");
}
printf(");\n");
int perm[10]={0,1,2,3,4,5,6,7};
saiki(perm,0,m);
printf("end.\n");
}
}
*100 - The 3n + 1 problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36
初めてのＵＶaですが解いてみたらコード実行速度3892/74613位。
上位5％近辺に入れて悪くないスタートですが、私は英語がほとんどできないので他の問題も解けるかは不明。
#include<stdio.h>
#include<string.h>
int memo[1000*1000+1];
int saiki(unsigned int n){
if(n<=1000*1000&&memo[n]!=-1){
return memo[n]+1;
}else{
int no=saiki(n%2==1?3*n+1:n/2);
if(n<=1000*1000)memo[n]=no;
return no+1;
}
}
int main(){
memset(memo,-1,sizeof(memo));
memo[1]=1;
for(int i=2;i<=1000*1000;i++){
if(memo[i]==-1)memo[i]=saiki(i%2==1?3*i+1:i/2);
}
int a,b;
while(scanf("%d",&a)!=EOF){
if(scanf("%d",&b)==EOF)break;
int max=0;
if(a<=b)for(int i=a;i<=b;i++)if(max<memo[i])max=memo[i];
if(b<=a)for(int i=b;i<=a;i++)if(max<memo[i])max=memo[i];
printf("%d %d %d\n",a,b,max);
}
}
*問い101 - The Blocks Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=37
アームロボットにブロックの移動命令が与えられる。
移動後のブラックの状態を答えよという問題。
#include<stdio.h>
#include<vector>
#include<string>
#include<iostream>
//私は英語が苦手なため何度もＷＡになってから題意をつかむという状態です。
//必然的に正答率は非常に低くなります
std::vector<int> bs[25];
int main(){
int n,a,b;
scanf("%d",&n);
for(int i=0;i<n;i++)bs[i].push_back(i);
std::string com1,com2;
while(1){
std::cin>>com1;
if(com1=="quit")break;
std::cin>>a>>com2>>b;
int no1,no2;
std::vector<int>::iterator it1,it2,it3;
for(int i=0;i<n;i++){
for(std::vector<int>::iterator it=bs[i].begin();it!=bs[i].end();it++){
if((*it)==b){
no2=i;//b置かれる場所
it2=it;
}
if((*it)==a){
it1=it;//a置くもの
no1=i;
}
}
}
if(no1==no2)continue;
if(com1=="move"&&com2=="onto"){
it2++;
it2=bs[no2].insert(it2,(*it1));
it2++;
it1=bs[no1].erase(it1);
while(it2!=bs[no2].end()){
bs[(*it2)].push_back((*it2));
it2=bs[no2].erase(it2);
}
while(it1!=bs[no1].end()){
bs[(*it1)].push_back((*it1));
it1=bs[no1].erase(it1);
}
}
if(com1=="move"&&com2=="over"){
bs[no2].push_back((*it1));
it1=bs[no1].erase(it1);
while(it1!=bs[no1].end()){
bs[(*it1)].push_back((*it1));
it1=bs[no1].erase(it1);
}
}
if(com1=="pile"&&com2=="onto"){
it2++;
it3=it1;
while(it1!=bs[no1].end()){
it2=bs[no2].insert(it2,(*it1));
it2++;
it1++;
}
while(it2!=bs[no2].end()){
bs[(*it2)].push_back((*it2));
it2=bs[no2].erase(it2);
}
bs[no1].erase(it3,bs[no1].end());
}
if(com1=="pile"&&com2=="over"){
bs[no2].insert(bs[no2].end(),it1,bs[no1].end());
bs[no1].erase(it1,bs[no1].end());
}
}
for(int i=0;i<n;i++){
printf("%d:",i);
for(int j=0;j<bs[i].size();j++){
printf(" %d",bs[i][j]);
}
printf("\n");
}
}
*102 Ecological Bin Packing
http://uva.onlinejudge.org/external/1/102.html
ビンを分けるらしいのだがよくわからなかった問題。
1682/17942位獲得。
題意がよくわからなかったので検索したら中国語の正答コード掲載ブログが出てきた。
ブログを読んでもやはり良くわからなかったので参考にコードを縮めれないか試したくらい。
この問題で速度差が出るとは思えないので同順位多数ということだと思う。
#include<stdio.h>
int main(){
int b1,c1,g1,b2,c2,g2,b3,c3,g3,ws[6];
char ansCom[6][4]={"BCG","BGC","CBG","CGB","GBC","GCB"};
while(1){
int sum;
if(scanf("%d %d %d %d %d %d %d %d %d",&b1,&g1,&c1,&b2,&g2,&c2,&b3,&g3,&c3)==EOF)return 0;
sum=b1+c1+g1+b2+g2+c2+b3+g3+c3;
ws[0]=b1+c2+g3;
ws[1]=b1+g2+c3;
ws[2]=c1+b2+g3;
ws[3]=c1+g2+b3;
ws[4]=g1+b2+c3;
ws[5]=g1+c2+b3;
int max=ws[0],no=0;
for(int i=0;i<6;i++){
if(max<ws[i]){
max=ws[i];
no=i;
}
}
printf("%s %d\n",ansCom[no],sum-max);
}
}
*問い103
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39
ｄ次元空間の箱を別の箱に入れて入れ子にしていく時もっともたくさんたくさん入る入れ子を出力せよという問題。
箱は回転しても良いがどのへんも次元の軸と平行でなくてはいけない。
例えば３次元なら箱のどの辺もＸ軸、Ｙ軸、Ｚ軸のどれかと平行でなくてはいけない。
解法
箱が別の箱に入る関係を半順序集合のグラフとして表現。
箱の回転は回転行列の概念より2この座標を入れ替えるのと同じなので全ての組み合わせを考えることが出来る。
5,4,3,2,1の長さで表される箱なら5,4,3,2,1を並べ替えたすべての組み合わせとして表現することが出来る。
後はダイクストラ法もどきで解決。
入るかどうかの判断関数をもっと高速化できると気付かずランクは。
3242/8598位と平凡な結果に。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
bool isInOk(std::vector<int> q1,std::vector<int> q2){
//ベクターはソート済みであると仮定
std::vector<int>::iterator it;
for(int i=0;i<q1.size();i++){
it=std::upper_bound( q2.begin(), q2.end(), q1[i] );
if(it==q2.end())return false;
q2.erase(it);
}
return true;
}
void upData(std::vector<int>& ansA,std::vector<int>& ansB){
if(ansA.size()<ansB.size()){
ansA.clear();
ansA.insert(ansA.begin(),ansB.begin(),ansB.end());
}
}
int main(){
int n,d,l;
while(scanf("%d %d",&n,&d)!=EOF){
std::vector<int> qs[31],ans[31],lastAns;
std::set<int> G[31];
std::set<int>::iterator it;
for(int i=0;i<n;i++){
for(int j=0;j<d;j++){
scanf("%d",&l);
qs[i].push_back(l);
}
std::sort(qs[i].begin(),qs[i].end());
ans[i].push_back(i);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
if(isInOk(qs[i],qs[j])==true){
//ｊの中にiが入った
G[j].insert(i);
}
}
}
int spents[31]={0};
for(int i=0;i<n;i++){
std::vector<int> dells;
for(int j=0;j<n;j++){
if(G[j].empty()==true&&spents[j]==0){
dells.push_back(j);
spents[j]=1;
}
}
if(dells.empty()==true)break;
for(int j=0;j<dells.size();j++){
int no=dells[j];
for(int k=0;k<n;k++){
if(G[k].find(no)!=G[k].end()){
ans[no].push_back(k);
upData(ans[k],ans[no]);
ans[no].pop_back();
G[k].erase(no);
}
}
}
}
for(int i=0;i<n;i++){
if(lastAns.size()<ans[i].size()){
lastAns.clear();
lastAns.insert(lastAns.begin(),ans[i].begin(),ans[i].end());
}
}
printf("%d\n",lastAns.size());
for(int i=0;i<lastAns.size();i++){
printf("%d",lastAns[i]+1);
if(i<lastAns.size()-1)printf(" ");
}
printf("\n");
}
}
*104 - Arbitrage
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=40
通貨売買をして1％以上の儲けを出せるならその売買手順を表示する問題。
解法
この問題サンプルデータを見てもしかして一度使った通貨は使えないと勘違い。
そんな激ムズ問題と勘違いしてどうすれば高速に動くかばかり考えＷＡを３連続でくらってしまった（←かなりの馬鹿）
実際は、同じ通貨を何度使っても良いという優しい問題でした。
まあそれでも一発で通ると思って書いたちょっぱやでかいたコードに書き間違いがあってて提出してＷＡくらったんですけどね。
速度よりも実装の分かりやすさを優先して書いた結果2586/4947位という妥当な順位になりました。
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
#include<map>
struct S{
int now,size;
double val;
std::vector<int> ans;
};
class permSorter{
public:
bool operator()(const S& l, const S& r) const {
if(l.size!=r.size)return l.size<r.size;
if(l.ans[0]!=r.ans[0])return l.ans[0]<r.ans[0];
return l.now<r.now;
}
};
class valSorter {
public:
bool operator()(const S& l, const S& r) const {
if(l.size!=r.size)return l.size>r.size;//サイズの小さい方優先
if(l.ans[0]!=r.ans[0])return l.ans[0]>r.ans[0];
if(l.now!=r.now)return l.now>r.now;
return l.val<r.val;//値の大きい方が優先
}
};
void ansPrint(std::vector<int> ans){
for(unsigned int i=0;i<ans.size();i++){
printf("%d",ans[i]+1);
if(i<ans.size()-1)printf(" ");
}
printf("\n");
}
void calc(int n){
double Ds[21][21];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)Ds[i][j]=1.0;
else scanf("%lf",&Ds[i][j]);
}
}
std::map<S,double,permSorter> memo;
std::priority_queue<S,std::vector<S>,valSorter> qu;
S s1;
for(int i=0;i<n;i++){
s1.val=1.0;
s1.now=i;
s1.size=0;
s1.ans.push_back(i);
qu.push(s1);
s1.ans.pop_back();
}
while(qu.empty()==false){
s1=qu.top();
qu.pop();
if(s1.size>=n)break;
if(memo.find(s1)!=memo.end()&&memo[s1]>=s1.val)continue;
memo[s1]=s1.val;
s1.size++;
double d1=s1.val;
int now=s1.now;
for(int k=0;k<n;k++){
if(k==s1.now)continue;
if(s1.val*Ds[now][k]>=1.01&&s1.ans[0]==k){
s1.ans.push_back(k);
ansPrint(s1.ans);
return ;
}else if(memo.find(s1)==memo.end()||memo[s1]<s1.val){
s1.val*=Ds[now][k];
s1.now=k;
s1.ans.push_back(k);
qu.push(s1);
s1.ans.pop_back();
s1.val=d1;
s1.now=now;
}
}
}
printf("no arbitrage sequence exists\n");
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
calc(n);
}
}
*105- The Skyline Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=41
y=0を床とする平面の上に長方形が置かれている。
長方形の高さに変化があった場所を表示せよという問題。
コード実行速度325/6697位を獲得。
何一つ工夫しないで素朴に実装しただけなのに何故こんなに高ランクになってんだろ？
#include<stdio.h>
#include<algorithm>
#include<map>
#include<vector>
const int OUT=1,IN=0;
struct S{
int x,h,type;
bool operator<(const S& s)const{
if(x!=s.x)return x<s.x;
return type>s.type;
}
};
int main(){
int nowX;
std::map<int,int> memo;
std::map<int,int>::iterator it;
std::vector<S> datas;
S s1;
int a,b,h;
while(scanf("%d",&a)!=EOF){
scanf("%d %d",&h,&b);
s1.x=a;
s1.h=h;
s1.type=IN;
datas.push_back(s1);
s1.x=b;
s1.type=OUT;
datas.push_back(s1);
}
std::sort(datas.begin(),datas.end());
nowX=datas[0].x;
int no=0,nowH=0;
while(no<datas.size()){
while(no<datas.size()&&nowX==datas[no].x){
s1=datas[no];
if(s1.type==OUT){
memo[s1.h]--;
}else{
memo[s1.h]++;
}
if(memo[s1.h]<=0)memo.erase(s1.h);
nowX=s1.x;
no++;
}
if(datas.size()<=no)break;
it=memo.end();
if(it!=memo.begin())it--;
if(nowH!=(*it).first){
printf("%d %d ",nowX,(*it).first);
nowH=(*it).first;
}
nowX=datas[no].x;
}
printf("%d 0\n",nowX);
}
*106 - Fermat vs. Pythagoras
http://uva.onlinejudge.org/external/1/106.html
x^2+y^2=z^2でｚがｎ以下になる原始ピタゴラス数の数と、ｚ＜＝ｎとなる（原始でないのもふくむ）ピタゴラス数の組に使われてないｎ以下の数の個数を答える問題。
例えば5と問われたら3,4,5の組しかないので1と２は使ってない。
ピタゴラス数にでてこない数は1と２の２個と答える問題です。
1059/5437位、自分で考えたにしては健闘したほう。
整数論の教育は中学どまりなのでこの手の問題で上位入りは不可能だとわかってる。
解法
原始ピタゴラス数を求める公式から斜辺がmax以下(問われた一番大きな数)までの組を求め、これを優先順位付きキューにいれて斜辺の長さでソーティング。
後は斜辺の短い方から出現した数を足し合わせていけば答えとなります。
これより賢い方法を自分では考えつけない状態。
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<queue>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
struct Delta{
int a,b,c;
bool operator<(const Delta& d)const{
return c>d.c;
}
};
int all[1000*1000+1]={0};
int main(){
std::vector<int> Qs;
std::set<int> sortQs;
std::map<int,int> memo,memoBase;
std::map<int,int>::iterator mIt;
std::map<int,int> ans,ansBase;
std::priority_queue<Delta> qu;
Delta d1;
int n,max=0;
while(scanf("%d",&n)!=EOF){
Qs.push_back(n);
sortQs.insert(n);
memo[n]=0;
memoBase[n]=0;
if(max<n)max=n;
}
for(int m=2;m*m+1<=max;m++){
for(int n=1;n<m&&m*m+n*n<=max;n++){
if(((m-n)&1)==0 || gcd(m,n)!=1)continue;
int a=m*m-n*n;
int b=2*m*n;
int c=m*m+n*n;
mIt=memoBase.lower_bound(c);
(*mIt).second++;
for(int i=1;i*c<=max;i++){
d1.a=a*i;
d1.b=b*i;
d1.c=c*i;
qu.push(d1);
}
}
}
while(qu.empty()==false){
d1=qu.top();
qu.pop();
mIt=memo.lower_bound(d1.c);
if(all[d1.a]==0){
all[d1.a]=1;
(*mIt).second++;
}
if(all[d1.b]==0){
all[d1.b]=1;
(*mIt).second++;
}
if(all[d1.c]==0){
all[d1.c]=1;
(*mIt).second++;
}
}
int sum=0,sumBase=0;
for(std::set<int>::iterator sIt=sortQs.begin();sIt!=sortQs.end();sIt++){
int num=(*sIt);
sum+=memo[num];
ans[num]=sum;
sumBase+=memoBase[num];
ansBase[num]=sumBase;
}
for(int i=0;i<Qs.size();i++){
printf("%d %d\n",ansBase[Qs[i]],Qs[i]-ans[Qs[i]]);
}
}
*107 - The Cat in the Hat
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=43
問題
読解に苦労した問題。
１匹の帽子の中にr匹の猫が入っている。
そのr匹の猫の帽子の中にr匹の猫が入っていて連鎖する。
これはr分木になっている。
帽子をかぶってる猫は、その帽子の中に入ってる猫の（r+1）倍の大きさであり一番奥の帽子に入ってる猫のサイズ１である。
一番大きな猫のサイズnと一番小さな猫の数mが一行に与えられるので一番小さな猫以外の数と全部の猫の身長の合計を答えよ。
解法
n=(i+1)^kかつm=i^kとなるiが見つかればそれが答えのカギとなります。
後は計算して足し合わせるだけです。
GCDとかその辺を使えば高速化できるかもしれません。
922/４９９７位と平凡な結果に。
#include<stdio.h>
#include<iostream>
void calc(long long int n,long long int m){
for(long long int i=1;i*i<=m;i++){
long long int n1=n;
long long int m1=m;
long long int ans1=0,ans2=m1,k=1;
while(n1%(i+1)==0&&m1%i==0){
n1/=(i+1);
m1/=(i);
k*=(i+1);
ans1+=m1;
ans2+=m1*k;
if(k>n)break;
}
if(n1==1&&m1==1){
std::cout<<ans1<<" "<<ans2<<"\n";
return ;
}
}
if(n==m+1){
std::cout<<"1 "<<m+1+m<<"\n";
}
}
int main(){
int n,m;
while(1){
std::cin>>n>>m;
if(n==0&&m==0)break;
calc(n,m);
}
}
*108 - Maximum Sum
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44
Ｎ*Ｎのマス目に数字が書かれている。
マス目を長方形で囲んだとき内部の数字の合計が最大になる領域の合計値を求めよという問題。
解法
とりあえず賢い方法を思いつかなかったので尺取り虫法で列の長さをそろえながら一行ずつ計算してみました。
1568/1034位という平凡な結果に。
#include<stdio.h>
#include<string.h>
int main(){
int n;
int board[101][101];
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d" ,&board[i][j]);
}
}
int ans=-1000000;
for(int i=0;i<n;i++){
int colSum[101];
memset(colSum,0,sizeof(colSum));
for(int c=0;c<n;c++){
for(int r=0;r<=i;r++){
colSum[c]+=board[r][c];
}
}
for(int r=i+1;r<=n;r++){
int rowSum=0;
for(int c=0;c<n;c++){
rowSum+=colSum[c];
if(rowSum<colSum[c])rowSum=colSum[c];
if(ans<rowSum)ans=rowSum;
}
if(r==n)break;
for(int c=0;c<n;c++){
colSum[c]=colSum[c]+board[r][c]-board[r-i-1][c];
}
}
}
printf("%d\n",ans);
}
*109 SCUD Busters
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=45
外壁で囲まれた国にミサイルが降り注ぐ。
国内にミサイルが落ちた全ての国の面積の総計を答えよという問題。
解法
最初の２点を選びさえできれば後は角度変化の小ささを基準に外壁の頂点を決定していけばループが一つ減って高速化できたのですが、最初の２点を選ぶ処理と角度の処理でコードが膨らむのはどうかと思って回避しました。
かわりに半開平面の概念を使って解いてます。
外側になる２点をとおる直線を描いたとき、残りのすべての点が半開平面の片側にあればその２点は外壁となります。
この処理を採用した結果ループが一つ多くなり、1085/1590位という酷い結果になってます。
100％間違いないコードを書いたところでふとどうしても辺上や頂点にミサイルが着弾した場合の処理を解釈できない状態でした。
投稿直前のチェック用に、頂点や辺上での処理がどうなるか他の人のコードを見てから投稿した問題です。
#include<stdio.h>
#include<math.h>
#include<vector>
struct P{
int x,y;
};
std::vector<P> getOutLines(const std::vector<P>& ps){
std::vector<P> ans;
int size=ps.size();
int sp,spents[101]={0},Lx=500;
for(int i=0;i<size;i++){
if(Lx>ps[i].x){
Lx=ps[i].x;
sp=i;
}
}
int p=sp,mod,count=0;
P p1,p2,p3;
ans.push_back(ps[p]);
while(1){
p1=ps[p];
for(int i=0;i<size;i++){
if(i==sp&&count<2)continue;
if(i==p)continue;
if(spents[i]==1)continue;
p2=ps[i];
mod=-2;
int y1=p2.y-p1.y;
int x1=p2.x-p1.x;
bool ok=true;
for(int k=0;k<size;k++){
if(i==k||p==k)continue;
p3=ps[k];
int y2=p3.y-p1.y;
int x2=p3.x-p1.x;
int g1=x1*y2-x2*y1;
if(g1==0){
if(x1*x2+y1*y2<=0)continue;
if(x1*x1+y1*y1>x2*x2+y2*y2){
ok=false;
break;
}else{
continue;
}
}
g1=g1>0?1:-1;
if(mod==-2)mod=g1;
if(mod!=g1){
ok=false;
break;
}
}
if(ok==true){
p=i;
break;
}
}
p1=ans[ans.size()-1];
if(p1.x!=ps[p].x||p1.y!=ps[p].y){
ans.push_back(ps[p]);
}
spents[p]=1;
count++;
if(p==sp)break;
}
return ans;
}
double sumS(P p1,P p2,P p3){
double x1,x2,y1,y2;
x1=p3.x-p1.x;
y1=p3.y-p1.y;
x2=p2.x-p1.x;
y2=p2.y-p1.y;
return 0.5*(x2*y1-x1*y2);
}
int main(){
std::vector<std::vector<P> > ps;
std::vector<P> v,re;
std::vector<double> outs;
P p1;
int n;
while(1){
scanf("%d",&n);
if(n==-1)break;
ps.push_back(v);
int no=ps.size()-1;
while(n--){
scanf("%d %d",&p1.x,&p1.y);
ps[no].push_back(p1);
}
ps[no]=getOutLines(ps[no]);
double sum=0;
for(int i=1;i<ps[no].size()-1;i++){
sum+=sumS(ps[no][0],ps[no][i],ps[no][i+1]);
}
if(sum<0.0)sum=-sum;
outs.push_back(sum);
//printf("(%d %lf)",no,sum);
}
double ans=0;
while(scanf("%d %d",&p1.x,&p1.y)!=EOF){
double g1,g2;
for(int i=0;i<ps.size();i++){
if(outs[i]==0)continue;
bool isOut=true;
g1=sumS(ps[i][0],ps[i][1],p1);
for(int j=1;j<ps[i].size()-1;j++){
g2=sumS(ps[i][j],ps[i][j+1],p1);
if(g2==0||g1==0){
break;
}
if(g1>=0&&g2<0){
isOut=false;
break;
}
if(g1<0&&g2>0){
isOut=false;
break;
}
}
if(isOut==true){
ans+=outs[i];
outs[i]=0;
}
}
}
printf("%.2lf\n",ans);
}
*110 - Meta-Loopless Sorts
変数の数1<=ｎ<=8が与えられるので、これをa,b、、とaから始まる８個の変数までに読みこみ
if,else if,else,readln,writeln、<文だけを使って,a,b,c,,,,をソートできるphytonプログラムを生成せよという問題。
解法
順序集合が分岐する場合全部を探索して出力しました。
凄くめんどくさい問題という印象しかありません。
順位は291/1520位まあまあです。
#include<stdio.h>
#include<string.h>
#include<algorithm>
char text[10]="abcdefgh";
void roopSlide(int perm[10],int s,int g){
int t=perm[g];
for(int i=g-1;i>=s;i--){
perm[i+1]=perm[i];
}
perm[s]=t;
}
void saiki(int perm[10],int deep,int m){
if(deep==m-1){
for(int i=0;i<=deep;i++)printf(" ");
printf("writeln(");
for(int i=0;i<m;i++)printf("%c%c",text[perm[i]],i==m-1?')':',');
printf("\n");
}else{
for(int i=0;i<=deep;i++)printf(" ");
printf("if %c < %c then\n",text[perm[deep]],text[perm[deep+1]]);
saiki(perm,deep+1,m);
int temp[10];
memcpy(temp,perm,sizeof(temp));
for(int i=deep-1;i>=0;i--){
for(int j=0;j<=deep;j++)printf(" ");
printf("else if %c < %c then\n",text[perm[i]],text[perm[deep+1]]);
roopSlide(perm,i+1,deep+1);
saiki(perm,deep+1,m);
memcpy(perm,temp,sizeof(temp));
}
for(int i=0;i<=deep;i++)printf(" ");
printf("else\n");
roopSlide(perm,0,deep+1);
saiki(perm,deep+1,m);
memcpy(perm,temp,sizeof(temp));
}
}
int main(){
int n,m;
scanf("%d",&n);
for(int i=0;i<n;i++){
if(i!=0)printf("\n");
scanf("%d",&m);
printf("program sort(input,output);\nvar\n");
for(int i=0;i<m;i++){
printf("%c%c",text[i],i==m-1?' ':',');
}
printf(": integer;\nbegin\n readln(");
for(int i=0;i<m;i++){
printf("%c",text[i]);
if(i<m-1)printf(",");
}
printf(");\n");
int perm[10]={0,1,2,3,4,5,6,7};
saiki(perm,0,m);
printf("end.\n");
}
}
