図書管理者【2017年普及組第二題】

7883 ワード

図書管理者図書管理者図書管理者


タイトルの説明


図書館には本ごとに図書コードがあり、図書を迅速に検索するために使用することができます。この図書コードは正の整数です。


本を借りた読者一人一人の手には需要コードがあり、この需要コードも正の整数です。もし1冊の本の図書コードがちょうど読者の需要コードで終わるならば、この本はこの読者が必要とするものです。


Dさんは図書館の管理人になったばかりで、彼女は図書館のすべての本の図書のコードを知っていて、彼女はあなたにプログラムを書いてもらって、すべての読者に対して、彼の必要な本の中で図書のコードが一番小さい本を求めて、もし彼の必要な本がなければ、-1を出力してください。


入力


入力ファイルの最初の行は、2つの正の整数nとqを含み、図書館の本の数と読者の数をそれぞれ表すスペースで区切られています。


次のn行は、各行に正の整数が含まれており、図書館のある本の図書コードを表しています。


次のq行は、各行に2つの正の整数を含み、1つのスペースで分けられ、1つ目の正の整数は図書館の読者の需要コードの長さを表し、2つ目の正の整数は読者の需要コードを表す。


しゅつりょく


出力ファイルにはq行があり、各行には整数が含まれており、i番目の読者が必要とする本が存在する場合、i番目の読者が必要とする本の中で図書コードが最も小さい本の図書コードが出力され、そうでなければ-1が出力される。


入力サンプル


5 5


2123


1123


23


24


24


2 23


3 123


3 124


2 12


2 12


出力サンプル


23


1123


-1


-1


-1


説明


20%のデータに対して,1≦n≦2であった。


さらに20%のデータがあり、q=1です。


さらに20%のデータがあり、すべての読者の需要コードの長さは1です。


さらに20%のデータがあり、すべての図書コードは小さいものから大きいものまでの順序で与えられています。


100%のデータに対して、1≦n≦1000、1≦q≦1000であり、すべての図書符号化および需要符号は1000000を超えない。


問題解決の考え方:


この問題は、i番目の読者需要コードの長さを教えてくれたので、1 0 x 10^{x}10 xに対して図書コードで余(xは読者需要コードの長さ)を求めた結果を読者需要コードと比較し、同じであれば現在の最適化である。

#include
#include
#include
#include
#include
#include
using namespace std;
int n,m,x,z,k,st,a[1005];
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	  scanf("%d",&a[i]);// 
	sort(a+1,a+1+n);// 
	for (int i=1;i<=m;i++)
	  {
	  	scanf("%d%d",&x,&k);//x ,k 
	  	st=-1;z=1;// 
	  	while(x) x--,z*=10;// 10^x
	  	for (int j=1;j<=n;j++)
	  	  if (k==a[j]%z) 
	  	    {
	  	    	st=a[j];// , 
				break;// , , 
	  	    }
		printf("%d
"
,st); } }