Prob.3 of NOIP 2002 (Junior) *Solution*

酱油 posted @ Wed, 02 Sep 2015 16:46:22 +0800 in OI life with tags Solution , 747 readers

More than two years ago, I thought it was an Ad Hoc problem and I had a try, but I failed.

Now I've realized it is just a math problem with floyd!

"Sky Gate":

Given a positive integer number n, and k ways of changing a digit.
You could change a digit in a way called x y. Which means you could change number x into y.
Then how many numbers could be produced after a series of changing operations? (Caution: We could change 0 times)
n k
xi yi(1<=i<=k)
The answer required
Sample Input:
234 2
2 5
3 6
Sample Output:
234, 264, 534, 564 are numbers available.
For all 5 testcases: 1<=n<=10^30, 1<=k<=15, 0<=xi<=9, 1<=yi<=9 

It's a problem of calculating the number of possible answers, but not a problem requiring every answer. So it's not recommended to use BFS, and that's why I failed two years ago...

Consider this situation: If a[i] means the number of ways that the i-th digit could change into, then the answer to the question is Πa[i]. It's obvious since every number couldn't be changed into zero unless it is zero at the beginning.

So use floyd to get can[i][j] indicating whether i could be changed into j.

Then get a[i]=Σcan[i][j].

Now calculate Πa[i] with higher precision.

Then it comes to coding...

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
int k,i,j,jw,x,y,ans[110],st[110],len,f[110];
bool a[10][10];
char c;
int main()
	while((c=getchar())!=' ')st[++len]=c-48;
	for(i=ans[0];i>=1;i--)printf("%d",ans[i]);puts("");return 0;

Not very complex, in fact.


If you have a better solution, please show your solution through comments, and I'll take it seriously.

(Comments are welcomed and it is recommended that you reply in English.)


Connaught Place Esco said:
Sat, 22 Jan 2022 13:31:34 +0800

The Hot and Sexy Girls are here to give all sorts of fun and enjoyment here.

AAA said:
Tue, 01 Feb 2022 21:49:57 +0800

Wow, cool post. I'd like to publish similar to this too - taking time and real hard work to produce a great article... but I put things off too much and never seem to obtain started. Thanks though. 토토사이트

AAA said:
Sun, 27 Mar 2022 20:04:30 +0800

Youre so cool! I dont suppose Ive read anything this way before. So nice to uncover somebody by incorporating original applying for grants this subject. realy thank you for starting this up. this website is one thing that is required on the internet, someone after some originality. helpful job for bringing new stuff to your world wide web! Licensed Clinical Social Workers

AAA said:
Fri, 27 May 2022 18:25:07 +0800

Thanks for the auspicious writeup. It actually used to be a leisure account it. Glance complicated to more delivered agreeable from you! However, how can we be in contact? 먹튀검증

AAA said:
Sat, 04 Jun 2022 21:33:39 +0800

Thanks , I’ve just been searching for info about this topic for a while and yours is the greatest I have found out so far. But, what about the conclusion? Are you sure about the supply? 麥克風

AAA said:
Mon, 13 Jun 2022 21:03:36 +0800

This is actually exciting, You’re an enormously knowledgeable blogger. I have enrolled with your feed and also anticipate witnessing the useful write-ups. At the same time, I’ve shared your site in our social networks. 回收手提電腦

Anamika said:
Tue, 14 Jun 2022 15:28:01 +0800

Tangling page on the web. The creator portrays all focal concentrate completely. Individuals can be reasonable. Overpowering explanation of the thing easy to understand.Keep posting

<a href="">Agartala Escorts</a> ||
<a href="">Escorts in Ajmer</a> ||
<a href="">Akola Escorts Service</a> ||
<a href="">Escorts Service in Ambattur</a> ||
<a href="">Amravati Escorts Agency</a> ||

Anamika said:
Tue, 28 Jun 2022 16:18:02 +0800

Particularly overwhelming article all encounters reveals major as everybody would be reachable and clear. By approaches of the maker for sharing this blog. [url=]Independent Escorts in Bangalore[/url] Keep on circumnavigating

AP 1st Inter Economi said:
Thu, 08 Sep 2022 21:35:46 +0800

The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student, and the economics subject paper-1 AP 1st Inter Economics Model Paper and paper-2 important questions with suggestions are available through AP Jr and Sr inter Economics Model Paper 2023 Pdf with guess paper.

meidir said:
Mon, 03 Oct 2022 19:08:46 +0800

A domain name is an identification label which defines a realm of administrative autonomy, authority, or control in the Internet. Domain names are also critica for domain hosting\website hosting Macbook air

New Delhi Escort said:
Sat, 29 Oct 2022 19:09:39 +0800

Extraordinary news particularly stunning site!! Individual .. Critical .. Floundering .. I will bookmark your blog and take the feeds furthermore,I'm fulfilled to track down a great deal of clear data here inside the set up, appreciation for sharing.

Massge Republic said:
Sat, 29 Oct 2022 19:11:46 +0800

Appreciation for sharing this information. I really like your blog region obviously. You have truly shared an illuminating and overpowering web journal district with people.

Bangalore Escort Ser said:
Sat, 29 Oct 2022 19:13:22 +0800

This is a gigantic article. I think this is conceivably of the best part I've at whatever point disengaged. Your work is stunning and convincing. I really feel a commitment of appreciation.

meidir said:
Fri, 04 Nov 2022 23:48:51 +0800

Im no professional, but I believe you just crafted a very good point point. You definitely understand what youre talking about, and I can seriously get behind that. Thanks for staying so upfront and so truthful. 카지노사이트

meidir said:
Sat, 19 Nov 2022 03:53:24 +0800

Some genuinely interesting information, well written and loosely user friendly. 온라인카지노

shivani09 said:
Sat, 11 Mar 2023 12:53:52 +0800

What would you do if you know that Saket Escorts || is one of the best place where luxury high-class escort service providers are available? It has a list of finest and most beautiful as well as independent girls in this world. 

shivani09 said:
Sat, 11 Mar 2023 19:59:52 +0800

You've probably heard about it just by chance. If not, then your partner might have told you that Escorts in Saket are among the best in the world. In fact, with a little research, you'll find that Delhi Escorts are among the most in-demand service providers for those seeking intimate companionship. 

shivani09 said:
Mon, 13 Mar 2023 17:57:07 +0800

If you are searching for a reliable escort in Delhi, Do not worry anymore. Here is the right place to spend a totally night fun with Karol Bagh Call Girls .

aliya said:
Mon, 20 Mar 2023 19:38:24 +0800

She will bring you to some unforgettable places where you can relax, unwind and get yourself together when things need it. Hbr Layout Escorts || Hennur Escorts || Hangasandra Escorts || Horamavu Escorts || Hosur Escorts || Hsr Layout Escorts || Indraprastha Escorts || Jalahalli Escorts || Jayanagar Escorts || Kadugodi Escorts || Kalyan Nagar Escorts || Kengri Escorts || Mg Road Escorts |

aliya said:
Mon, 20 Mar 2023 19:39:40 +0800

Our ladies are all very experienced, friendly and ready to make you feel special. call girl number || bhabhi whatsapp number || sex videos || porn clip ||

aliya said:
Mon, 20 Mar 2023 19:40:40 +0800

They can give you a night of unforgettable passion Bangalore Escorts Service and delight that you will never forget in your entire life

shivani09 said:
Tue, 21 Mar 2023 15:14:51 +0800

Sex Stories Hindi || Articles is an Indian blog that aims to provide a sex platform for people who want to read and write sex stories in Hindi. 

Login *

loading captcha image...
(type the code from the image)
or Ctrl+Enter