Sukarna_Paul's blog

By Sukarna_Paul, history, 2 months ago, In English,

My Solution with KMP is getting TLE . How can I approach in a faster way? Problem Link

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 2 months ago, In English,

How can I solve this problem ? Link

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 2 months ago, In English,

Problem Link How can I approach for this problem???

F. Find the Substrings

Score: 1

CPU: 3s Memory: 1500MB

You are given a string S and Q queries. On the ith query, you will be given two integers Ni and Mi. Now for each query, you have to find such strings consisting of lowercase letters whose lengths are at least Ni and at most Mi and also those strings are not substrings of S.

For example: You are given S=“abac”. If a query contains Ni=3 and Mi=4 then according to our problem, “aba”, “bac” and “abac” are not valid as they are substrings of S while “abc” is a valid string as it is not substring of S and also maintaining the constraints for the length. Now you have to find all other strings which are also valid for this string S.

To make the problem a bit simple, you don’t have to print all the strings. You will just need to print the number of such strings which are valid. To make the output more simple, print the answer modulo 1000000007 (109+7 ).

Input The first line of the input file will be a single integer T (1 ≤ T ≤ 5), denoting the number of test cases.

Each test case contains two lines. First line will contain the string S (1 ≤ |S| ≤ 1000000) of lowercase letters and the second line will contain an integer Q (1 ≤ Q ≤ 100000). Each of the next Q lines will contain two integers Ni and Mi (1 ≤ Ni ≤ Mi ≤ |S|).

Output For each test case, the first line of the output should contain the case number in the format: “Case X:”, where X is the test case number. Each of the next Q lines should contain the answer for the specific query modulo 1000000007 (109+7).

Sample Input 1 abcab 5 1 2 2 2 3 5 1 1 1 5 Output Case 1: 696 673 12355922 23 12356618

N.B. Data set is large. Use faster I/O methods.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 2 months ago, In English,

I was solving a problem from spoj, Link. I need to keep two same string in the prefix_trie. For first query the answer 2, but I am getting 1. Because the duplicate is not counted. My code link . One more thing I want to how can I print the size of prefix range in O(1). Please Help.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 3 months ago, In English,

Contest Link

Password : NSTU_insomnia

[Problems were chosen from different online judges]

A. Unknown Numbers

এই প্রব্লেমে দুই জন একটি গেম খেলবে যেখানে একজন 1 থেকে n পর্যন্ত যেকোনো একটি সংখ্যা অনুমান করবে । দ্বিতীয় জনকে সেই সংখ্যাটি বলতে হবে । এই সংখ্যা বের করার জন্য সে প্রথম জনকে বিভিন্ন প্রশ্ন করতে পারবে । প্রশ্নের ধরন এমন হবে যে , দ্বিতীয় জন একটি সংখ্যা বলবে এবং প্রথম জন তাকে বলে দিবে যে তার অনুমেয় সংখ্যাটি ওই সংখ্যা দ্বারা নিঃশেষে ভাগ যায় কিনা । এক্ষেত্রে দ্বিতীয় জন minimum সংখ্যক প্রশ্নের মাধ্যমে সংখ্যাটি বের করতে চায় । এই জন্য optimal approach হচ্ছে প্রথমে প্রথম মৌলিক সংখ্যা দিয়ে প্রশ্ন করতে হবে, এরপর যদি ওই মৌলিক সংখ্যা দিয়ে অনুমেয় সংখ্যাটি ভাগ যায় তবে ওই মৌলিক সংখ্যার power 2 এর জন্য প্রশ্ন করতে হবে । এবারও যদি উত্তর হ্যাঁ হয় , তবে ওই মৌলিক সংখ্যার power 3 এর জন্য প্রশ্ন করতে হবে এবং এভাবে চলতে থাকবে । যদি কখনো উত্তর না হয় অথবা ভাজকের মান n থেকে বড় হয়ে যায় তবে পরবর্তী মৌলিক সংখ্যার জন্য এভাবে প্রশ্ন করতে থাকতে হবে । এভাবে n থেকে ছোট পর্যন্ত সব মৌলিক সংখ্যার জন্য যেতে হবে ।

ধরুন, n এর মান 16 এবং অনুমেয় সংখ্যাটি 9 . তাহলে প্রশ্ন করার sequence হবে 2, 4, 8, 16, 3, 9, 5, 7, 11, 13 . এখন যেহেতু অনুমেয় সংখ্যাটি 1 থেকে n পর্যন্ত যেকোনোটি হতে পারে , তাই 1 থেকে n পর্যন্ত প্রতিটি সংখ্যাই কোন না কোন অনুমেয় সংখ্যার sequence এ থাকবে । তাহলে আমাদের ultimate answer এর squence হবে, n থেকে ছোট প্রথম মৌলিক সংখ্যার power গুলো , এরপর দ্বিতীয় মৌলিক সংখ্যার power গুলো এবং এভাবে চলেতে থাকবে। 

এবার code implementation এ আসা যাক । আমি প্রথমেই n পর্যন্ত মৌলিক সংখ্যা গুলো generate করে নিব sieve() ফাংশনের মাধ্যমে । এরপর বাকি কাজ প্রতিটি মৌলিক সংখ্যার জন্য তাদের power গুলো generate করে একটি vector এর ভিতর রাখলেই হয়ে গেল ।  [My Solution Link](https://codeforces.com/contest/577/submission/56873852)

B. Total Sum

এই প্রব্লেমের optimal solution হল maximum value এর letter কে প্রদত্ত string এর শেষে k সংখ্যক বার যোগ করতে হবে । এরপর string এর প্রতিটি character এর value কে তার position দ্বারা গুণ করে মোট যোগফলটাই answer হবে ।  [My solution link](https://codeforces.com/contest/447/submission/56880773)

এখানে sum বের করার জন্য উপরের মত bruteforce না math এর logic ব্যবহার করতে পারি আমরা। তাহলে আমাদের solution টি k এর আরও বড় মানের জন্যও কাজ করবে । এক্ষেত্রে আমরা 1 থেকে n পর্যন্ত ক্রমিক সংখ্যাগুলোর যোগফলের সূত্র ব্যবহার করব । 

প্রথমে প্রদত্ত string এর প্রতিটি character জন্য value গুলোকে তাদের নিজ নিজ position দিয়ে গুণ করে sum কে update করব । এখানে string এর length n হলে n+1 থেকে (n+k) পর্যন্ত সংখ্যাগুলোর যোগফল বের করে তাকে letter গুলোর মধ্যে maximum value দিয়ে গুণ করতে হবে । এর জন্য আমরা প্রথমে 1 থেকে (n+k) পর্যন্ত সংখ্যাগুলোর যোগফল বের করব , এরপর তা থেকে 1 থেকে n পর্যন্ত সংখ্যাগুলোর যোগফল বিয়োগ করব । এই বিয়োগফলকে letter গুলোর মধ্যে maximum value দিয়ে গুণ করে আগের sum এর সাথে যোগ করলেই হয়ে গেল । 

My solution link

C. Black and White

এই প্রব্লেমে nXm আকারের একটি chessboard দেওয়া আছে । আমাকে ‘B’ আর ‘W’ দ্বারা ঘরগুলো পূরণ করতে হবে যেন adjacent দুইটি ঘর same color এর না হয় । এখানে প্রদত্ত chessboard এর যে ঘরগুলোতে  ‘-’  চিহ্ন আছে সেই ঘরগুলোতে ‘B’ আর ‘W’ বসানো যাবে না । খুবই সহজ সমস্যা । আমরা bruteforce approach এ ‘B’ আর ‘W’ বসিয়ে যাব , শুধু  ‘-’  চিহ্নওয়ালা ঘরগুলোকে ignore করব ।  [My solution link](https://codeforces.com/problemset/submission/445/56884608)

D. Coprime and GCD

এখানে আমাদেরকে a2 থেকে an পর্যন্ত (n-1) টি সংখ্যা print করতে বলেছে যেন i এবং j coprime হলে ai ≠ aj হয় । এই প্রব্লেমের solution হচ্ছে n পর্যন্ত প্রতিটি সংখ্যার জন্য উত্তর হবে তাদের প্রত্যেকের কোনো না কোনো মৌলিক উৎপাদকের জন্য উত্তরের সমান । এর সমাধানের জন্য আমরা sieve ব্যবহার করব । seive function এ প্রতিবার multiple কাটার সময় answer টা রেখে দিবো । My solution link

E. Towhid's New game

এই প্রব্লেমে আমাকে একটা string s দেওয়া থাকবে আর দুইটা empty string t এবং u দেওয়া থাকবে । আমি দুই ধরনের operation চালাতে পারব ।

১। s এর প্রথম character টি তুলে t এর শেষে যোগ করব । ২। t এর শেষ character টি তুলে u এর শেষে যোগ করব ।

আমাকে এভাবে s এর সব character u তে নিয়ে যেতে হবে এমনভাবে যেন possible u গুলোর মধ্যে আমাদের ultimate answer টি lexicographically minimal হয় । 

একটু খেয়াল করলে আমরা দেখব এখানে string t একটি stack এর মত কাজ করছে । আমরা যে character টি সবার শেষে নিচ্ছি , সেটি সবার আগে u তে যাবে। এখন আমরা প্রথমে string s এর প্রতিটি character কে তাদের position এর সাথে pair করে sort করব । এর জন্য আমরা stl এর set ব্যবহার করতে পারি । 

এবার আমরা s এর character গুলো একটি একটি করে check করব যে সেটি আমাদের set এর শুরুতে আছে কিনা । যদি শুরুতে থাকে , তবে সেটিকে u এর সাথে যোগ করব । অন্যথায় সেটিকে stack t তে push করব । প্রতিবারে এই জিনিসটা check করার আগে , আমাদেরকে check করে নিতে হবে এই character টি stack এর top এর সমান বা ছোট কিনা , যদি হয় তাহলে আমাদেরকে অবশ্যই top of stack কে u এর সাথে যোগ করতে হবে । [My solution link](https://codeforces.com/contest/797/submission/56954879)

F. Result of a game

    দুইটা string এর মধ্যে যে string টা বেশিবার আছে সেটিই উত্তর হবে । কোন string কতবার আছে তা গুনার জন্য আমরা map ব্যবহার করতে পারি । [My solution link](https://codeforces.com/contest/43/submission/56955476)

G. Dim

এখানে আমাদেরকে color গুলকে বৃত্তাকারে এমনভাবে সাজাতে হবে যেন পরপর ৪ টি same না হয় । খেয়াল রাখতে হবে প্রথমটি আর শেষটি adjacent . এখন আমি সম্পূর্ণটাকে ( n/7 +1 ) segment এ ভাগ করব । প্রথম n/7 segment কে “ROYGBIV” দিয়ে পূরণ করব । অবশিষ্ট segment কে প্রয়োজনমত “GBIVGB” দিয়ে পূরণ করব । My solution link

H. Equation

    এই প্রব্লেমে আমাকে একটি অ্যারে দেওয়া থাকবে যেখানে 1 থেকে n পর্যন্ত সংখ্যাগুলোর একটি বিন্যাস থাকবে আর কিছু query থাকবে । প্রতিটি query তে একটি করে সংখ্যা দেওয়া থাকবে , আমাদেরকে প্রথমে ওই সংখ্যাটি প্রথম থেকে কততম পজিশনে সেটা বের করতে হবে এবং দ্বিতীয়ত সেটি শেষ থেকে কততম পজিশনে আছে । এরপর সবগুলো query এর প্রথম থেকে পাওয়া পজিশনগুলোর যোগফল প্রিন্ট করতে হবে এবং শেষ থেকে পাওয়া পজিশনগুলোর যোগফল প্রিন্ট করতে হবে । কোন সংখ্যা কোন পজিশনে আছে সেটা আমি একটা map এ store করেছি । [My solution link](https://codeforces.com/problemset/submission/227/57078173)

I. Team Practise

    এই প্রব্লেমে বলা, হয়েছে , কিছু experienced আর কিছু newbie contestant আছে  ।  আমি তিন জন নিয়ে একটি টিম বানাতে পারবো যেখানে হয় ১ জন experienced আর ২ জন newbie থাকবে অথবা ১ জন newbie আর ২ জন experienced থাকবে । এভাবে আমাকে সর্বাধিক সংখ্যক টিম বানাতে হবে । 

খুব সহজেই আমরা O(n) solution লিখতে পারি । আমি একটি লুপ চালাব যেখানে বেশি সংখ্যক contestant ওয়ালা অংশ থেকে ২ জন আর কম সংখ্যক contestant ওয়ালা অংশ থেকে ১ জন নিব । প্রতিবার নেওয়ার পর উভয় ধরনের contestant এর সংখ্যা এবং বানানো team সংখ্যা update করবো । যদি উভয় ধরনের contestant এর সংখ্যা ২ এর থেকে ছোট হয় অথবা কোন এক ধরনের contestant এর সংখ্যা ০ হয় , তবে আর team বানানো যাবে না । এটিই হবে লুপের breaking point . My solution link

K. Minimum people

    এখানে n জন লোক আছে যারা প্রত্যেকে বছরের একটি নির্দিষ্ট  range এর দিনে আসতে পারবে । প্রত্যেকের জন্য এই range টি ভিন্ন ভিন্ন । Male আর felmale মিলে একটি couple হয় এবং সবাই অনুষ্ঠানে couple আকারেই আসতে হবে । এখন আমাকে বলতে হবে অনুষ্ঠান হলে সবচেয়ে বেশি লোক আসতে পারবে ।

    যেহেতু আমদের লোকের সংখ্যা সর্বাধিক 5000 হতে পারে , তাহলে আমরা brute force approch করবো । আমরা বছরের কোন দিন কত জন পুরুষ বা মহিলা আসতে পারবে তার জন্য একটি অ্যারে রাখব । প্রতিটি মানুষের জন্য তাদের ব্যক্তিগত range এ লুপ চালিয়ে এই সংখ্যা count করবো । কোন নির্দিষ্ট দিনে পুরুষ ও মহিলার সংখ্যার minimum টা হবে ওই দিন আসতে পারবে এমন সর্বাধিক couple সংখ্যা ।  এভাবে সবগুলো দিনের মধ্যে যেটা maximum সেটার দ্বিগুণই হবে answer . [My solution link](https://codeforces.com/contest/629/submission/57099152)

L. Summation

    String ব্যবহার করে সংখ্যাটি input নিতে হবে । এখন প্রতিটি character এর ASCII value থেকে 0 এর ASCII value বাদ দিলেই numerical value পাওয়া যাবে । এভাবে সবগুলো digit traverse করে sum বের করতে হবে । [My soluion link](https://codeforces.com/contest/102/submission/42254743)

M. Difficult Problem

    আমাকে এ প্রব্লেমে n দেওয়া থাকবে । n এর মান 105  ডিজিটের হতে পারে । (1n + 2n + 3n + 4n) %5 এর মান প্রিন্ট করতে হবে । খেয়াল করলে দেখব , n এর দুইটি value এর জন্য যদি (n%4) এর মান সমান হয় তবে answer একই হবে । তার মানে (1n + 2n + 3n + 4n) %5 এর জন্য answer যা, (1n %4+ 2n%4 + 3n%4 + 4n%4) %5 জন্যও answer তা । প্রকৃতপক্ষে , (1n + 2n + 3n + 4n) %5 = (1n%ɸ(n) + 2n%ɸ(n) + 3n%ɸ(n) + 4n%ɸ(n)) %5 লিখা যায় । [My solution link](https://codeforces.com/contest/456/submission/57161296)

N. Easy Problem

    এই প্রব্লেমে আমাকে n সংখ্যক সংখ্যা দেওয়া আছে । আমি এই সংখ্যাগুলোর উপর এক ধরনের অপারেশন যেকোনো সংখ্যক বার চালাতে পারবো । প্রতি অপারেশনে আমি যেকোনো একটি সংখ্যা নিব এবং সংখ্যাটি ak হলে , ak  অ্যারে থেকে delete হবে এবং সাথে সাথে ak-1 এবং ak+1 এর সমান সকল সংখ্যা অ্যারে থেকে মুছে যাবে । আর answer এর সাথে ak যোগ হবে । এভাবে আমাকে answer এর মান সর্বোচ্চ করতে হবে । 

    এইটা Basic DP(Dynamic Programming) problem . আমরা যদি ak নেই তাহলে আর ak+1 নেওয়া সম্ভব না । আবার যদি ak+1 নেই , তবে ak নেওয়া কোনভাবেই সম্ভব না । আমরা এই concept দিয়েই এই প্রবলেমটা solve করবো । প্রথমেই কোন সংখ্যাটি কতবার আছে তা count করে একটি map রাখবো । dp নামে একটি 2D অ্যারে নিবো ।   একটি dimension কোন সংখ্যার জন্য state নির্দেশ করবে । এক্ষেত্রে state হবে দুইটি - হয় আমি সংখ্যাটি নিব, না হয় নিবো না ।  প্রথম dimension এর জন্য 0 দ্বারা element টা নেইনি বুঝাব আর 1 দ্বারা element টা নিয়েছি বুঝাব । যেহেতু আমাদের কোন element এর মান সর্বোচ্চ 105 হতে পারে , তাই আমরা অপর dimension টি এমন size এর নিবো । এখন আমরা দ্বিতীয় dimension এর উপর লুপ চালাবো । প্রতিবার dp[i][0] = max(dp[i-1][0], dp[i-1][1]) হবে , কারণ আমরা যদি i-1 মানধারী element টি নেই এবং না নেই , এই উভয় ক্ষেত্রেই আমরা  i মানধারী element টি নিতে পারবো । আবার dp[i][1] = dp[i-1][0] + i*mp[i] , অর্থাৎ আমি যদি  i মানধারী element টি নিই তবে  i-1 মানধারী element টি নিতে পারবো না এবং  i মানধারী সকল element ই আমি নিতে পারবো । এভাবে সর্বোচ্চ element টি যদি x হয়, তবে max(dp[x][0], dp[x][1]) ই হবে answer . [My solution link](https://codeforces.com/contest/456/submission/57162455)

O. Decimal Digit

    এই প্রব্লেমে দুইটি সংখ্যা a ও b দেওয়া আছে । b!a!এর মানের last digit টি প্রিন্ট করতে হবে । এখানে a≤b . আমরা যদি b! কে a! দ্বারা ভাগ করি , তবে b! এর 1 থেকে a পর্যন্ত গুণনীয়কগুলো কাটা যাবে । এখন প্রথমে ans=1 রাখব এবং a+1 থেকে b পর্যন্ত সংখ্যা দিয়ে একে গুণ করব । প্রতি ধাপে গুণফলকে 10 দিয়ে ভাগ করে ভাগশেষ ans এ রাখব । লক্ষ করলে দেখব ,maximum 10টি ক্রমিক সংখ্যা check করলেই আমরা 10 এর কোন কোন multiple পেয়ে যাব । ফলে last digit 0 হয়ে যাবে এবং একবার 0 হয়ে গেলে পরে যা দিয়েই গুণ করা হোক না কেন 0 ই থাকবে ।  [My solution link](https://codeforces.com/contest/869/submission/57199576)

Q. Army

    প্রথমে আমরা কোন সংখ্যাটি কতবার আছে তা count করার জন্য একটি map use করবো । কোন সংখ্যা একাধিক বার থাকলে অতিরিক্ত বার গুলোর জন্য brute force approch এ check করবো যে পরবর্তী কোন minimum সংখ্যাটি array তে নেই । এই দুটি সংখ্যার বিয়োগফলকে ans এর সাথে যোগ করে update করে এগিয়ে যাব । [My solution link](http://codeforces.com/problemset/submission/546/57484232)

Read more »

 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

By Sukarna_Paul, history, 4 months ago, In English,
 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By Sukarna_Paul, history, 7 months ago, In English,

How can I approach for this problem ? https://codeforces.com/gym/102055/problem/L

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 7 months ago, In English,

How to avoid TLE for this problem as the number of test cases can be 10^4 .

Here is the problem link

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 7 months ago, In English,

Here is the problem link UVA Live 6844

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 8 months ago, In English,

I have been trying to solve this problem for last few days . Here is the Problem link SPOJ PTRI .

I have used Linear sieve , but the limit is so high that it is getting TLE in O(N) . I have tried it with sieve of aktin also. But still got TLE . Please help me to solve this one.

I found this problem in -Morass- blog Link . You can visit it , I am confident that you will find it useful.

Read more »

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

By Sukarna_Paul, history, 8 months ago, In English,

I was solving the problem from SPOJ Link . But my solution is getting TLE. Please help me out!

Here is my solution :

#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define pli pair<long long , int>
#define pil pair<int ,long long>
#define pi acos(-1)
#define pb push_back
#define mkp make_pair
#define all(a) a.begin(), a.end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define MAX 300005
#define INF 0x3f3f3f3f
template <class T> inline T bigmod(T p,T e,T M){ll ret = 1LL;for(; e > 0LL; e >>= 1LL){if(e & 1LL) ret = (ret * p) % M;p = (p * p) % M;}return (T)ret;}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}   // M is prime}
using namespace std;

vector <ll> prime;
bitset <100000010> bs;

void sieve ()
{
	bs.set ();
    prime.pb(2LL);
	for (ll i = 3; i < 100000000; i+=2)
	{
		if (bs[i])
		{
			prime.pb(i);
			for (ll j = i * i; j < 10000000; j += i+i)
			{
				bs[j] = 0;
			}
		}
	}
}

int main(){
    IOS
    //freopen("output.txt","w",stdout);
    sieve();
    int i=0;
    unordered_map<int,int>r,c;

    for(auto it=prime.begin();it!=prime.end();){
        i++;
        for(int j=1;j<=i;j++){
            r[(*it)]=i;
            c[(*it)]=j;
            it++;
        }
    }
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        int a;
        cin>>a;
        if(r[a]==0){
            cout<<"-1"<<endl;
            continue;
        }
        cout<<r[a]<<" "<<c[a]<<endl;

    }
}

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 8 months ago, In English,

How Can I Create A Contest On Codeforces?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 8 months ago, In English,

This problem is from ACM ICPC Dhaka Regional 2018 (Contest Link)

How can I approach for this problem?

Problem Satement:

The function d(n) denotes the number of positive divisors of an integer n. For example d(24) = 8, because there are 8 divisors of 24 and they are 1, 2, 3, 4, 6, 8, 12 and 24. The function sndd(n) is a new function defined for this problem. This denotes “The summation of number of divisors of the divisors” of an integer n. For example,

sndd(24) = d(1) + d(2) + d(3) + d(4) + d(6) + d(8) + d(12) + d(24) = 1 + 2 + 2 + 3 + 4 + 4 + 6 + 8 = 30.

Given the value of n, you will have to find sndd(n!), here n! means factorial of n. So n! = 1 × 2 × 3 × … × n.

Input The input contains at most 1000 lines of test cases. Each line contains a single integer that denotes a value of n (1 ≤ n ≤ 10^6). Input is terminated by a line containing a single zero.

Output For each line of input produce one line of output. This line contains an integer that denotes the modulo 10000007 (or 10^7 + 7) value of sndd(n).

Sample Input 4 5 0

Sample Output 30 90

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By Sukarna_Paul, history, 9 months ago, In English,
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 10 months ago, In English,

How can I approach for this Geometry problem . Here is the link URI 1291

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 10 months ago, In English,

How can I approach for this problem Problem Link

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By Sukarna_Paul, history, 11 months ago, In English,

How can I approach for this number theory problem ? [Problem Link](http:// https://codeforces.com/contest/1070/problem/A)

A. Find a Number time limit per test3 seconds memory limit per test256 megabytes inputstandard input outputstandard output

You are given two positive integers d and s. Find minimal positive integer n which is divisible by d and has sum of digits equal to s.

Input The first line contains two positive integers d and s (1≤d≤500,1≤s≤5000) separated by space.

Output Print the required number or -1 if it doesn't exist.

Examples input 13 50 output 699998

input 61 2 output 1000000000000000000000000000001

input 15 50 output -1

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Sukarna_Paul, history, 11 months ago, In English,

How can I approach for this problem ?

8085 Divisors (Link)

The number of divisor function or d(n) is a very interesting function in number theory. It denotes the number of positive divisors of a particular number. For example d(24) = 8 as 24 has eight divisors 1, 2, 3, 4, 6, 8, 12 and 24 . In mathematics factorial of a positive integer number n is written as n! and is defined as below: n! = 1 × 2 × 3 × · · · × n

Another interesting function AF(n) (Again factorial in short) is defined as: AF(n) = 1! × 2! × 3! × . . . × n!

Given n , your job is to find the value of d(AF(n)).

Input The input file contains at most 101 lines of inputs. Each line contains an integer n (0 < n < 5000001) . Input is terminated by a line containing a single zero. This value should not be processed.

Output For each line of input produce one line of output.

This line contains the modulo 100000007 (10^8 + 7) of d(AF(n)).

Sample Input 1 2 3 4 100 0

Sample Output 1 2 6 18 59417661

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By Sukarna_Paul, history, 14 months ago, In English,

Some Big integer problems for beginners Solving BigInteger Problem is fun. There are many problem solvers around the world who come to use Java BigInteger class though they do not code in Java usually. Here are some simple problems with their links and solution. This problem are chosen from different online judges. Try yourself before you see the solution.

Codeforces Gym : 112

Solution

import java.util.Scanner ;
import java.math.BigInteger;
public class Main{
  public static void main(String[] args){
    int a,b;
    Scanner input = new Scanner(System.in);
    a = input.nextInt();
    b = input.nextInt();
    BigInteger A = BigInteger.valueOf(a);
    BigInteger B= BigInteger.valueOf(b);
    System.out.printf("%d",A.pow(b).subtract(B.pow(a)));
    
  }
}

Uva 10183 — How Many Fibs?

Solution

import java.util.*;
import java.math.*;
public class Main{
  public static void main(String[] args){
    Scanner input = new Scanner(System.in);
    BigInteger arr[] = new BigInteger[50000];
    arr[0]= BigInteger.valueOf(1);
    arr[1]= BigInteger.valueOf(2);
    for(int i=2;i<50000;i++){
      arr[i] = arr[i-1].add(arr[i-2]);
    }
    while(true){
      
      BigInteger a,b;
      a = input.nextBigInteger();
      b = input.nextBigInteger();
      if(b.compareTo(BigInteger.valueOf(0))==0){
        break;
      }
      int count=0;
      for(int i=0;i<50000;i++){
        if(arr[i].compareTo(a)>=0 && arr[i].compareTo(b)<=0){
          count++;
        }
        if(arr[i].compareTo(b)>0){
          break;
        }
      }
      System.out.println(count);
    }
  }
}

URI 1279

Solution

import java.util.*;
import java.math.*;
import java.io.*;  
public class Main{
  public static void main(String[] args){
    Scanner input = new Scanner(System.in);
    boolean start = true;
    while(input.hasNext()){
      boolean leap_year = false;
      boolean ordinary = true;
      if(start == false){
        System.out.print("\n");
      }
      start = false;
      BigInteger year;
      year = input.nextBigInteger();
      BigInteger four;
      four = BigInteger.valueOf(4);
      BigInteger fourh;
      fourh = BigInteger.valueOf(400);
      BigInteger oneh;
      oneh = BigInteger.valueOf(100);
      BigInteger temp = year.remainder(four);
      if(temp.compareTo(BigInteger.valueOf(0))==0){
        temp = year.remainder(oneh);
        if(temp.compareTo(BigInteger.valueOf(0))==0){
          temp = year.remainder(fourh);
          if(temp.compareTo(BigInteger.valueOf(0))==0){
            System.out.println("This is leap year.");
            leap_year = true;
            ordinary = false;
          }
        }
        else{
          System.out.println("This is leap year.");
          leap_year = true;
          ordinary = false;
        }
      }
      temp = year.remainder(BigInteger.valueOf(15));
      if(temp.compareTo(BigInteger.valueOf(0))==0){
        System.out.println("This is huluculu festival year.");
        ordinary = false;
      }
      if(leap_year==true){
        temp = year.remainder(BigInteger.valueOf(55));
        if(temp.compareTo(BigInteger.valueOf(0))==0){
          System.out.println("This is bulukulu festival year.");
          ordinary = false;
        }
      }
      if(ordinary == true){
        System.out.println("This is an ordinary year.");
      }
    }
  }
}

Project Euler Problem 13

Solution

import java.util.*;
import java.math.*;

public class problem13{
  public static void main(String[] args){
    Scanner input = new Scanner(System.in);
    BigInteger sum, a;
    sum = BigInteger.valueOf(0);
    for(int i=0;i<100;i++){
      a = input.nextBigInteger();
      sum = sum.add(a);
    }
    System.out.println(sum);    //take the first 10 digits manually
  }
}

Project Euler Problem 15

Solution

import java.math.*;

public class Problem15{
  public static void main(String[] args){
    BigInteger n=BigInteger.valueOf(1);
    BigInteger ans=BigInteger.valueOf(1);
    for(int i=0;i<40;i++){
        ans=ans.multiply(n);
        n= n.add(BigInteger.valueOf(1));
    }
    n=BigInteger.valueOf(1);
    BigInteger ans2=BigInteger.valueOf(1);
    for(int i=0;i<20;i++){
        ans2=ans2.multiply(n);
        n= n.add(BigInteger.valueOf(1));
    }
    System.out.println(ans.divide(ans2.multiply(ans2)));
  }
}

Project Euler Problem 16

Solution

import java.math.*;

public class Problem16{
  public static void main(String[] args){
    //BigInteger n=BigInteger.valueOf(1000);
    BigInteger two = BigInteger.valueOf(2);
    BigInteger ans = two.pow(1000);
    String s = ""+ans;
    System.out.println(s);
    int sum=0;
    for(int i=0;i<s.length();i++){
      sum+=s.charAt(i)-'0';
    }
    System.out.println(sum);
  }
}

Thank you. Happy coding.

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it