2017.09.09【NOIP普及組】アナログC組

T1
タイトルの説明
2つの数aを与える.b,操作毎にa+1またはa*2を少なくとも何回操作できるかを聞くことでa=b
入力
1行2個の数a;b
しゅつりょく
1行に1つの数ansは、少なくとも何回の操作がa=bになることができるかを示す.
考え方:
逆さに押す.b mod 2=1の場合は+1操作を行い、逆にa=bまで*2操作を行う.
コード:

var x,y,ans:longint;
begin
  assign(input,'dis.in');
  assign(output,'dis.out');
  reset(input);
  rewrite(output);
  read(x,y);
  while y div 2>=x do
  begin
    if y mod 2=1 then inc(ans);
    y:=y div 2; inc(ans);
  end;
  ans:=ans+y-x;
  write(ans);
  close(input);
  close(output);
end.

T2
タイトルの説明
Bessieはコミュニティ大学でコンピューターの授業を受けています.彼女は最近進数に興味を持っています.思い出してみると、1つの数がB進数と書かれているので、この数は右から左へおいしいものが1を表しています.B;B2;B 3、このままでは.例えば、私たちがよく知っている十進法システムでは、1桁当たり1,101001000をそれぞれ表しています.数値1234が10進数と理解される場合、それは実際には1(1000)+2(100)+3(10)+4(1)を表すべきである.同じ数字を5進数と理解すると、1(125)+2(25)+3(5)+4(1)を意味し、10進数に変換するのは19である.Bessieは、進数が増加すると、同じ数字列で表される値も増加することに気づいた.たとえば、1234の7進数の値は1234の6進数の値よりも大きい.B進法で数字を書くとき、各数字の範囲は0です.B-1は、例えば10進数で1桁あたりの範囲が0である.9、5進数で0です.4.進数が10より大きいことを考慮することは完全に可能である.コンピューター科学者たちはよく16進法を使っていますFはそれぞれ値10を示す.15.例えば、BEEFは、16進数で11(4096)+14(256)+14(16)+15、10進数で48879に対応する.Bessieは「進数が10より大きい」という概念に深く魅了された.彼女は1つの数字Nを持っていて、X進数とY進数の2つの進数の下でそれぞれ書いて、XとYの範囲は10です.15,000. 興味深いことに、すべての状況で、彼女は3つの数字の数字の列を手に入れて、すべての数字は0しかありません.9.残念なことに、Bessieは記憶力が悪いので、彼女は今N、X、Yを忘れています.3桁の数字を2つあげて、使ったXとYを見つけてください.XとYの潜在的なサイズのため、すべての可能性を検索するプログラムがタイムアウトします(15;0002に近い可能性があります!)、このプログラムでは満点は取れません
入力
入力ファイルは整数Kで始まる.次にK行があり、各行がテストケースです.各テストケースには、3桁の数字が2つ含まれています.1番目の数字NはX進法、2番目の数はY進法(N,X,Yはテストケースごとに異なる場合があります)
しゅつりょく
あなたの出力にはK行が含まれているはずです.各テストケースは1行です.各行このテストケースに対応するXとYは、スペースで区切られています.各テストケースについて、唯一の答えがあることを保証します.
コード:

var a,b:array [1..3] of longint;
    num:array [10..15000,0..3] of longint;
    i,j,k,a1,b1,t,r:longint;
procedure init;
begin
  assign(input,'whatbase.in');
  assign(output,'whatbase.out');
  reset(input);
  rewrite(output);
  read(k);
  for i:=10 to 15000 do
  begin
    num[i,1]:=1;
    for j:=2 to 3 do num[i,j]:=num[i,j-1]*i;
  end;
end;
procedure get;
begin
  a[1]:=a1 div 100; a[2]:=a1 mod 100 div 10; a[3]:=a1 mod 10;
  b[1]:=b1 div 100; b[2]:=b1 mod 100 div 10; b[3]:=b1 mod 10;
end;
function find(l,r,dep:longint):longint;
var mid,o:longint;
begin
  while ldo
  begin
    mid:=(l+r) div 2;
    o:=b[1]*num[mid,3]+b[2]*num[mid,2]+b[3]*num[mid,1];
    if o=dep then exit(mid) else if o>dep then r:=mid  else l:=mid+1;
  end;
  exit(0);
end;

begin
  init;
  for i:=1 to k do
  begin
    read(a1,b1);
    for j:=10 to 15000 do
    begin
      get;
      r:=a[1]*num[j,3]+a[2]*num[j,2]+a[3]*num[j,1];
      t:=find(10,15000,r);
      if t<>0 then writeln(j,' ',t);
      if t<>0 then break;
    end;
  end;
  close(input);
  close(output);
end.

T4
タイトルの説明
誰もが直面する問題のように、ベッシーはcowtubeのパスワードを忘れた.しかし、彼女はパスワードに関する情報を覚えています.まず、彼女はパスワードが小文字で構成され、長さがLであることを確定した.次に、このパスワードはいくつかの単語を組み合わせたものです.ベッシーは全部でN個の単語を認識し、各単語の長さは1から20の間で、小文字から構成されている.最後に、ベッシーはパスワードの上のいくつかの位置のアルファベットを覚えていて、彼女はできるだけ覚えている部分を提供して、もしいくつかの位置のアルファベットが覚えていないならば、使いますか?代わりに.ベッシーが覚えているパスワードの断片と彼女が知っている単語のリストを与えて、彼女のパスワードを復元してください.もし完全に条件に合っているパスワードが1つ以上あれば、辞書の順序で一番前に並んでいるものを出力します.
入力
1行目:2つのスペースで区切られた整数:LとN、1≦L≦1000、1≦N≦1000 2行目:1つのLの長い文字列、パスワードPの3行目からN+2行目を表す:i+2に1つの文字列W_i,ベッシーの認識を表すi番目の単語W_i
しゅつりょく
≪第1行｜First Row｜oem_src≫:条件に一致する、ディクショナリ・シーケンスの下で最も前のパスワードを表す文字列
考え方:
リュックサック.文字列をリュックサックに抽象化する.
コード:

#include  
#include  
#include  
#include  
using namespace std;  
const int MAXN=1005;  
string a[MAXN],f[MAXN];  
int l,n;  
string Min(string a,string b)  
{

    return aint main()  
{

    int i,j,k;  
    scanf("%d%d",&l,&n);  
    for(i=0; i<=n; i++)
    {

        cin>>a[i];  

    }  
    for(i=1; i<=l; i++)
    {

        for(j=1; j<=n; j++)
        {

            int l=a[j].length();  
            if(l>i||(f[i-l]==""&&i-l!=0)) continue;      
            for (k=i-l+1; k<=i; k++)
            {

                if(a[0][k-1]!='?'&&a[0][k-1]!=a[j][k-i+l-1])    break;  

            }  
            if(k==i+1)
            {

                if(f[i]=="") f[i]=f[i-l]+a[j];  
                else         f[i]=Min(f[i],f[i-l]+a[j]);  

            }  

        }

    }  
    cout<return 0;  
}